Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2002-06-19
2004-06-01
Jeanglaude, Jean (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S050000
Reexamination Certificate
active
06744388
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to compressing and decompressing a data stream, and more particularly to a method for compressing and decompressing a data stream that is more easily implemented in hardware.
BACKGROUND
Data compression and decompression techniques remove redundancy in a data stream to provide more efficient utilization of memory and communication channel resources. Lossless compression methods are used for data streams that require the original data to be exactly reconstructed from the compressed data stream without any loss of information. One category of lossless compression algorithms, generally termed LZ compression, relies on substitution of a code for a frequently repeating data pattern.
One group of LZ compression algorithms dynamically creates a table of frequently encountered data patterns as the data stream is compressed. Code sequences indicating the location in the table of the frequently encountered data patterns are generated and embedded in the data stream. The table is added by the compression system as part of the compressed data stream for use by the decompression system to decompress the compressed data stream.
Another group of LZ compression algorithms does not add a table of frequently repeated sequences to the data stream. Instead, the decompression system dynamically recreates the repeating data patterns by copying a specified number of data units starting from a buffer location specified by codes embedded in the compressed data stream.
Both groups of LZ compression algorithms send uncompressed literal data that is not part of a repeating pattern from the compression system to the decompression system. A data type flag is typically incorporated into the data stream to indicate whether a particular data unit is code or literal data, resulting in a non-integral data unit size. In compression systems using a byte as the data unit, a data type flag must be added to each data byte by the compression system, resulting in each data byte represented by 9 bits, including 8 bits of data and the data type flag. The decompression system for this compressed data stream must strip out the data type flag and repack the data stream into bytes to reconstruct the original data.
SUMMARY OF THE INVENTION
In various embodiments, a method and apparatus are provided for compressing and decompressing a data stream in a manner that is more easily implemented in hardware.
One aspect of the present invention provides a method and system for replacing repeating sequences in the data stream with codes. The codes characterize a repeating sequence by indicating the location and length of an identical sequence in the data stream. Indicators are inserted into the data stream characterizing the length of non-repeating sequences of data.
In another aspect of the invention, a decompression method and system are provided The decompression method and system removes the indicators inserted by the compression system from the data stream, each indicator characterizes a non-repeating sequence of variable length. Codes inserted into the data stream by the compression system are replaced with the repeating sequences characterized by the codes.
It will be appreciated that various other embodiments are set forth in the Detailed Description and Claims which follow.
REFERENCES:
patent: 5237460 (1993-08-01), Miller et al.
patent: 5371499 (1994-12-01), Graybill et al.
patent: 5729223 (1998-03-01), Trissel
patent: 6446145 (2002-09-01), Har et al.
Jeanglaude Jean
Kanzaki Kim
Maunu LeRoy D.
Xilinx , Inc.
LandOfFree
Hardware-friendly general purpose 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 Hardware-friendly general purpose data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-friendly general purpose data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3363714