A parallel architecture for high-speed data compression

Data compression is becoming an essential component of high-speed data datmunications and storage. Lossless data compression is when the decompressed data must be identical to the original. Textual substitution methods are among the most powerful approaches to lossless data compression, where repeated substrings are replaced by pointers into a dynamically changing dictionary of strings. We present a massively parallel architecture for textual substitution that is based on a systolic pipe of 3839 identical processing elements that forms what is essentially an associative memory for strings that can "learn" new strings on the basis of the text processed thus far. Key to the design of this architecture is the formulation of an inherently "top-down" serial learning strategy as a "bottom-up" parallel strategy. A custom VLSI chip for this architecture that operates at 320 million bits per second has been fabricated. © 1991.

Duke Scholars

Author John H. Reif Computer Science