US 7,403,136 B2Granted

Block data compression system, comprising a compression device and a decompression device and method for rapid block data compression with multi-byte search

AssigneeGemac-Gesellschaft fuer Mikroelektronikan Wendung Chemnitz mbH

InventorsAlfredo De La Cruz, Claus Dittrich, Thomas Reichert

Life of this patent

Estimating the term…

Loading patent…

Abstract

A block data compression system comprising a Compression unit and a Decompression unit, and an Algorithm for fast block data compression using multi-byte search. Objective of the invention is to develop a block data compression system and algorithm for fast block data compression with multi-byte search for optimal encoding during the learning phase of substitutional methods, allowing length-limited and relative small blocks of input data symbols to be compressed independently, as required by random-access storage or telecommunication devices; and reaching high-performance characteristics by employed accelerating architectures and highly pipelines data-flow principles. According to the present invention these objectives are accomplished by a Compression Unit comprising an Input-FIFO (8), connected to a Modeling Unit (6), where said Modeling Unit (6) is connected to a multitude of memory locations represented by Trie-Dictionary (4) memory, to a Zero-Finder Look-Up Table (3), to search means in the form of a Comparison Unit (5), to memory means in the form of a Literal-Dictionary (2) and also to an Encoder Unit (7); said Encoder Unit (7) also connected through an Aligning Unit (7) to an Output-FIFO (12). The invention comprises a block data compression system, composed of a Compression Unit and a Decompression Unit, and an algorithm for fast block data compression using multi-byte search; and is related to the field of data compression, specifically to the implementation of a lossless, adaptive, reversible and fast block data compression for storage and telecommunication devices.

Claims18

Dependent claims

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.

4 more elements

A procedure for converting a block of input symbols into an output of codified variable-lengths codewords in a data-block compression system, comprising a Trie-Dictionary and a Literal Dictionary, including also input and output first-in first-out (FIFO) buffers, and a multiple-byte search mechanism, comprising

transferring the input symbols into the Input FIFO;
calculating a multitude of hash addresses based on the contents of the first two symbols on top of the Input FIFO and using these addresses to search in parallel in a Zero Look-Up Table and in the Trie-Dictionary, to determine the existence of internal NODE/terminal LEAF node in the high-order dictionary;
operative when a search in the Trie-Dictionary is able to find an internal node which produces a non-single match with the string of symbols represented in the Input FIFO;
iterating a multiple-byte search until the longest match of the Input FIFO string of input symbols is found with respect to existing internal nodes of the Trie-Dictionary;
encoding in relative form the information about the node number founded with respect to the last node created, and identifying the codeword as either internal (NODE) or terminal (LEAF) in the Trie-Dictionary transferring the length of the match to the encoder in differential form and referential to the earlier most recently visited node during the search;
operative when a search in the Trie-Dictionary is not able to find an internal node which produces a non-single match with the string of symbols represented in the Input FIFO;
the code word determining via the Literal Dictionary if the codeword to use is a Known Literal KLIT and identified by the variable-length code granted in an earlier occurrence of said symbol, or if the codeword is identified as a New Literal (NLIT) and reflected in its original byte-form, if the case is the codeword never registered in the Literal Dictionary before;
assigning to each type of codeword a variable-length prefix according to the type of codeword employed, whereas said prefix is determined via a balanced tree weighted on the basis of the specific cumulative counts of each codeword type;
converting the resulting variable length codeword into a byte-bounded output result by an aligning operation;
storing the output-bounded codewords into the Output FIFO, where the codewords are grouped to produce an efficient write operation to the final storage means, both in the sense of timing arbitration and bus-width;
generating from an uncompressed block of input symbols a compressed representation in a the form of a block of output codewords.

8 more elements

Dependencies are inferred from the claim text.