Data compression having more effective compression

Details Data compression having more effective compression Data compression having more effective compression

2002-10-07

2003-12-23

Williams, Howard L. (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

C341S087000

Reexamination Certificate

active

06667699

ABSTRACT:

This invention relates to a method and apparatus for the lossless compression of data.
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 principle 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.
It is an object of the invention to provide a lossless data compression algorithm which can compress data more effectively than is possible with the published arrangement.
According to the invention, a lossless data compression system comprising a content addressable memory dictionary and a coder, characterised by run length encoding means connected to receive the output of the coder, said encoding means being arranged to count the number of times a match consecutively occurs at a predetermined dictionary location.
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:
loading each search tuple in turn into the same address in the dictionary;
and counting the number of times identical tuples are matched consecutively into said address.
Preferably said same address as the first location in the dictionary.
In the drawings,
FIG. 1
illustrates the architecture of a compressor arrangement published by Nunez et al.


REFERENCES:
patent: 5473326 (1995-12-01), Harrington et al.
patent: 5521597 (1996-05-01), Dimitri
Kjelso et al., Design and perfomance of a Main Mmory Hardware Data Compressor, IEEE 1996, Proceedings of the 22ndEUROMICRO Conference, Beyond 2000 Hardware and Software Design Strategies, pp. 423-430.*
Kjelso et al., Empirical Study of Memory-data: Characteristics and Compressibiility, IEE Proceedings-Computers and Digital Technniques, IEE Jan. 1998, vol. 145, No. 1, pp. 63-67.

Affiliated with

Also associated with

Rating

Data compression having more effective compression 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 more effective compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression having more effective compression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3137726