Patent ID: 7403136
Filing Date: 2008-07-22
Classification: H03M

Abstract:
1. A data compression system comprising a compression apparatus and a decompression apparatus with Multi-Byte search for fast compression of blocks of digital data comprising means for buffering input symbols in a first-in first-out manner (Input FIFO), said symbols connected to arbitration means represented by a Modeling Unit, said Modeling Unit connected to a Trie-Dictionary, to a Zero Look-Up Table, to search means represented by a Comparison Unit, to storage means in the form of a Literal Dictionary and to an Encoder Unit, said Encoder Unit connected through an Aligning Unit to an Output-FIFO, said Trie-Dictionary consisting in a memory massive with a multiplicity of storage locations comprising the Trie-Dictionary, accessed in parallel by said Modeling Unit, said Trie-Dictionary representing the high-order dictionary addressed via a hash function based on the first symbols in the Input FIFO, said Modeling Unit including means for advanced determination of the existence of a certain unused space in the high-order dictionary, said Modeling Unit determining if the string existing in the FIFO can be expressed by internal and terminal nodes of said Trie-Dictionary, said Search Engine executing parallel comparisons of several symbols at once to provide information about the maximal length of matching between a partially-matching internal node in said Trie-Dictionary and the string of symbols contained in said Input FIFO; said Literal Dictionary including means for determining the encoded form granted for unmatched symbols strings (of length equal to one); said Modeling Unit including means for deciding whether it will use the result of the parallel search in the Comparison Unit or the result of the Literal Dictionary as the modeling output; said Modeling Unit including means that permit iterating the parallel search in the Comparison Unit when more internal nodes of the dictionary extend the match within the Input FIFO string of symbols; said Modeling Unit including means to pipeline its results to the Encoder Unit including means to create a compact output codeword of variable length based on the relative representation of said modeling-output and the current state of the Modeling Unit; said Encoder Unit including means to pipeline said resulting output codeword to said Aligning Unit, said Aligning Unit including means for converting the variable length output codeword into a byte-bounded output codeword that is written into said Output FIFO, said Output FIFO including means for storing temporarily the byte-bounded codeword until the output bus-size specified and is reached the output timing arbitration to deliver the results of the compression process to the output memory is reached; and transforming a block of uncompressed digital data into a compressed data-stream that is transferred out by means of the Output-Bus of the Output FIFO.