Hardware 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 fail to meet the speed and performance requirements of current and future systems. This Ph.D. dissertation presents a set of hardware algorithms for compression and decompression techniques and the results of detailed simulations performed to quantify the effects of incorporating such hardware in various architectural environments.

A new pipelined algorithm for data compression applicable to static binary encoding schemes is presented. A fast hardware algorithm for decompression that uses a balanced binary tree structure to eliminate code storage tables is introduced. Hardware algorithms are presented for the multi-group compression technique, run-length encoding method and an enhanced version of arithmetic coding scheme. These algorithms are suitable for VLSI implementation and can provide speeds that are an order of magnitude higher than currently obtainable encoding speeds. The design and implementation of a prototype compression chip for the Huffman's encoding scheme is presented. The chip yields an estimated compression rate of 10 million characters per second.

The effect of employing compression hardware on the performance of a general purpose computer system and a special purpose back-end multiprocessor machine is analyzed by constructing detailed simulation models. Simulation results establish that our VLSI chips for compression and decompression cause significant improvements in system performance.