A High-Throughput VLSI Architecture for LZFG Data Compression

Jin-Ming CHEN  Che-Ho WEI  

IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.3   pp.497-509
Publication Date: 2002/03/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: VLSI Systems
LZFG,  LZ78,  Ziv-Lempel,  data compression,  CAM,  

Full Text: PDF>>
Buy this Article

This paper presents a high-throughput VLSI architecture for LZFG data compression and decompression. To reduce the hardware cost and maintain both of the interior node and the leaf node numbering systems, we modify the original LZFG data structure. Compared to the original LZFG tree, the number of characters in our modified LZFG data structure must be greater than one to establish one new interior node down the root node into the new node. Meanwhile, this architecture employs a series of encoding cells with content addressable memory (CAM) to search the longest match and maintain the LZFG data tree during the encoding and decoding processes. By using the parallel design, the compressor and decompressor can keep a constant high bit rate to encode and decode one character per clock cycle, that is, it is directly proportional to the operating clock rate, but independent of the sizes of the word dictionary and the input file. By using 0.25 µm CMOS silicon technology, the operating clock rate can be as high as 85 MHz. Some untargeted encoding cells will be disabled to reduce the power consumption during the comparison operation. Therefore, this architecture can be easily applied in the high-speed real-time communication and data storage systems.