Hardware-friendly general purpose data compression/decompression algorithm
AssigneeXilinx, Inc.
InventorArthur H. Khu
Life of this patent
Estimating the term…
Abstract
Methods and systems are provided for dynamically compressing and decompressing a data stream in a manner that facilitates hardware implementation. In one aspect, a compression system identifies literal data sequences of variable length in the data stream and characterizes each literal sequence with an indicator that is inserted into the data stream. Sequences that repeat previous sequences in the data stream are identified and replaced with codes characterizing the repeating sequence. Another aspect provides a decompression method and system for removing indicators inserted by the compression system and replacing codes in the data stream with the repeating sequences characterized by the codes.
Claims13
A system for representing data, comprising:
- a first memory area comprising a first data sequence having a first set of logical data units;
- a second memory area comprising a second data sequence having a second set of logical data units and a third data sequence having a third set of logical data units;
- and
- circuitry configured to replace the third data sequence with a first indicator, when the third data sequence and the first data sequence are identical, and configured to modify the second data sequence with a second indicator, when the second data sequence and the first data sequence are different, wherein the second indicator characterizes a non-repeating sequence of variable length and comprises an indicator flag and a length of the second sequence.
A system for decompressing a data block, comprising:
- means for recognizing a code characterizing a repeating sequence by a code flag in the code;
- means for extracting a length of the repeating sequence from the code;
- means for extracting a location of the repeating sequence from the code;
- means for replacing the code characterizing a repeating sequence with the repeating sequence;
- means for recognizing a code characterizing a non-repeating sequence by a code flag in the code;
- means for extracting a length of the non-repeating sequence from the code;
- means for removing the code characterizing a non-repeating sequences from the data block.
A system for compressing an input data stream, comprising:
- a first-in-first-out (FIFO) memory arrangement arranged to receive the input data stream;
- a compression circuit coupled to the FIFO arrangement, the compression circuit configured to detect each repeated sequence in the input data stream, output to a compressed data stream a code representing a repeated sequence of data in the input data stream, output to the compressed data stream non-repeating sequences of data and respective indicator values for the non-repeating sequences, wherein each indicator value signals a non-repeating sequence and specifies a number of units of data in the non-repeating sequence.
Dependencies are inferred from the claim text.