Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2002-10-04
2004-07-20
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S087000
Reexamination Certificate
active
06765509
ABSTRACT:
This invention relates to a method and apparatus for the lossless compression of data.
BACKGROUND OF THE INVENTION
While lossy data compression hardware has been available for image and signal processing for some years, lossless data compression has only recently become of interest, as a result of increased commercial pressure on bandwidth and cost per bit in data storage and data transmission; also, reduction in power consumption by reducing data volume is now of importance.
The principles of searching a dictionary and encoding data by reference to a dictionary address is well known, and the apparatus to apply the principle consists of a dictionary and a coder/decoder.
In Proceedings of EUROMICRO-22, 1996, IEEE, “Design and Performance of a Main Memory Hardware Data Compressor”, Kjelso, Gooch and Jones describe a novel compression method, termed the X-Match algorithm, which is efficient at compressing small blocks of data and suitable for high speed hardware implementation.
The X-Match algorithm maintains a dictionary of data previously seen, and attempts to match a current data element, referred to as a tuple, with an entry in the dictionary, replacing a matched tuple with a shorter code referencing the match location. The algorithm operates on partial matching, such as 2 bytes in a 4 byte data element. In Proceedings of EUROMICRO-25, 1999, IEEE, “The X-MatchLITE FPGA-Based Data Compressor”, Nunez, Feregrino, Bateman and Jones describe the X-Match algorithm implemented in a Field Programmable Gate Array (FPGA) prototype.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a lossless data compression algorithm which can compress data at a faster rate than is possible with the published arrangement.
According to the invention a lossless data compression system comprising a dictionary based on content addressable memory and a coder having between them a feedback loop forming a dictionary adaptation path, characterised by register means connected in the feedback loop whereby the dictionary can be updated using data from a previous comparison cycle at the same time as the coder codes a current comparison cycle.
Also according to the invention, a lossless method of compressing data comprising the steps of:
comparing a search tuple of fixed length with a plurality of tuples of said fixed length stored in a dictionary;
indicating the location in the dictionary of a full or partial match or matches;
selecting a best match of any plurality of matches; and
encoding the match location and the match type;
characterised by the further steps of:
providing the dictionary with a current adaptation vector and a next adaptation vector;
and after comparison of each search tuple
(a) updating the contents of the dictionary in accordance with the current adaptation vector and
(b) updating the next adaptation vector in accordance with the current adaptation vector.
REFERENCES:
patent: 4876541 (1989-10-01), Storer
patent: 5861827 (1999-01-01), Welch et al.
patent: 090232967 (1997-09-01), None
patent: WO 98/04045 (1998-01-01), None
Nunez et al., The X-MatchLITE FPGA-based data compressor, Proceedings of the 25THEuromicro Conference, Sep. 1999, pp. 126-132.*
Nunez et al.; “The X-MatchLITE FPGA-Based Data Compressor”;Proceedings of Euromicro-25, (1999), pp. 126-132, XP000920739.
Jones Simon Richard
Yanez Jose Luis Nunez
BTG International Limited
Nixon & Vanderhye
Williams Howard L.
LandOfFree
Data compression having improved compression speed does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression having improved compression speed, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression having improved compression speed will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241968