VLSI ALGORITHMS FOR DATA-COMPRESSION

Data compression is the reduction of redundancy in data representation in order to decrease storage and communication costs. Data compression techniques have been used in practice primarily through software implementations which do not meet the speed and performance requirements of current and future systems. In this paper we present a new class of efficient hardware algorithms for data compression and decompression that can provide speeds that are an order of magnitude higher than currently obtainable encoding speeds. Our algorithms for the Huffman compression scheme works on the principle of propagation of a token on the reverse binary tree constructed from the original codes. We show how the same principles can be used to develop hardware algorithms to implement the multi-group compression and decompression methods. Finally, a simple circuit that can be used to implement the run-length and header compression methods is described. The algorithms are suitable for VLSI implementation, and data transformation can be done 'on-the-fly'. Based on a prototype VLSI implementation of a compression chip, the algorithms yield an estimated compression rate of 10 M characters per second.