Coded data generation or conversion – Digital code to digital code converters – Unnecessary data suppression
Reexamination Certificate
1999-08-24
2001-08-28
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Unnecessary data suppression
C341S051000
Reexamination Certificate
active
06281816
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data compression schemes, and more particularly to a method and apparatus for reducing the expansion of data during data compression.
BACKGROUND OF THE INVENTION
The use of data compression or “coding” schemes to increase the storage capacity of storage media (e.g., tape drives, hard drives, etc.) is well known in the art, and can result in significant increases in data storage capacity. However, the efficiency with which data may be compressed depends on the specifics of the compression scheme employed and the type of data compressed. Depending on data entropy, certain data types may be incompressible or inefficiently compressible by the compression scheme, and may cause the data to occupy more memory space than when the data is in an uncompressed format (i.e., data expansion). For example, in many implementations of Lempel-Ziv 1 coding including IBM's adaptive lossless data compression (ALDC), LZS (QIC 122), etc., highly random data can expand in size up to 12.5% (e.g., from 60,000 bytes uncompressed to 67,500 bytes compressed).
When data expansion occurs during data compression, the very purpose of performing data compression (e.g., to increase the storage capacity of a storage media) is subverted. Accordingly, a need exists for a method and apparatus for reducing the expansion of data during data compression.
SUMMARY OF THE INVENTION
To overcome the needs of the prior art, a method and apparatus are provided for reducing data expansion during data compression that determine when the coding scheme used to compress data should be swapped between two or more coding schemes. Specifically, a coding window is provided that holds data to be compressed, and the compression potential of data entering or exiting the coding window is calculated. When a compression potential sum of data entering the window reaches a first predetermined value (e.g., when a first threshold compression potential sum of data entering the window is reached), the coding scheme used to compress the data within the coding window is swapped from one coding scheme to another (e.g., the coding scheme used to compress the data within the coding window is swapped to a new coding scheme and the data within the coding window is then compressed using the new coding scheme). A new compression potential sum is set based upon the compression potential of data exiting the window.
The compression potential sum comprises a running total of the compression potential of data entering the coding window; and the coding scheme used to compress data within the coding window is swapped from one coding scheme to another when the compression potential sum reaches a first predetermined value (e.g., the first threshold compression potential sum). As used herein, “reaches a predetermined value” means has an absolute magnitude greater than or equal to an absolute magnitude of the predetermined value. Preferably the first predetermined value is programmable and is related to the bit cost required to swap back and forth between coding schemes. The two preferred coding schemes are ALDC Lempel-Ziv 1 (hereinafter “LZ1”) coding and a pass-through (hereinafter “RAW”) coding scheme wherein raw data is passed unencoded.
If the end of the coding window is reached before the first predetermined value is reached, swapping of the coding scheme used to compress the data within the coding window preferably is performed if the compression potential sum reaches a second predetermined value.
A coding window circuit also is provided that allows analysis of the compression potential of data in accordance with above described method. The coding window circuit includes a coding window buffer adapted to store data bytes supplied to the coding window circuit, and a first calculation circuit coupled to the coding window buffer and adapted to compute the compression potential of a data byte entering or exiting the coding window buffer. As used herein, coupled means coupled directly or indirectly so as to operate. A second calculation circuit coupled to the first calculation circuit is adapted to compute a compression potential sum based on the computed compression potentials of a plurality of data bytes stored within the buffer. A comparison circuit is coupled to the second calculation circuit and is adapted to compare the computed compression potential sum to a first predetermined value and to generate a signal that swaps the coding scheme used to compress data bytes within the buffer from one scheme to another if the computed compression potential sum is greater than or equal to the first predetermined value. A third calculation circuit is coupled to the second calculation circuit and is adapted to adjust the compression potential sum based on the compression potential of at least one data byte exiting the coding window buffer.
By thus analyzing the compression potential of data prior to coding, and by selecting an appropriate coding scheme based thereon, data compression may be performed with the potential for minimal data expansion. Because the compression potential sum is set to a new compression potential sum (e.g., is adjusted) based upon the compression potential of data exiting the coding window, the inventive coding selection algorithm may be easily implemented in hardware.
Other objects, features and advantages of the present invention will become more fully apparent from the following detailed description of the preferred embodiments, the appended claims and the accompanying drawings.
REFERENCES:
patent: 3394352 (1968-07-01), Wernikoff et al.
patent: 4870415 (1989-09-01), Van Maren et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5177480 (1993-01-01), Clark
patent: 5353024 (1994-10-01), Graybill
patent: 5686912 (1997-11-01), Clark, II et al.
patent: 6008743 (1999-12-01), Jacquette
International Business Machines - Corporation
Schmeiser Olsen & Watts
Walsh Robert A.
Williams Howard L.
LandOfFree
Method and apparatus for reducing data expansion during data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for reducing data expansion during data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing data expansion during data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2493685