Lossless data compression in VLSI

This thesis describes the design of a VLSI circuit for lossless data compression and decompression using the LZH algorithm (Lempel-Ziv and Huffman). The compressed data is compatible with standard software. The required speed is 100Mbit per second, which is much faster than can be achieved with software.

First the requirements were analyzed and a specification was made. The VLSI circuit works as a peripheral device within a computer system. It reads the input data from RAM and writes the output data at another RAM location using two independent DMA channels.

Next we created a detailed architecture of the circuit, which consists of five communicating modules: a bus interface, a sliding window coder, a buffering and statistics module, a Huffman coder and an internal processor. The internal processor runs a software program that supervises the other modules and that implements some parts of the compression algorithm. The chip uses an external RAM for buffering and contains several internal memories. We documented all the design decisions that led to this architecture. Many design decisions were based on simuLation results. We implemented and simulated several parts of the circuit at different levels of abstraction.

To achieve the required speed we had to implement the sliding window coder as an associative array. An associative array consists of identical cells that can match their stored contents with an external value (like associative memories) and perform certain operations. The sliding window coder is the largest part of the chip and it dominates the cost. We can trade compression ratio for cost by changing the size of the sliding window, without affecting compatibility of the compressed data.

The conclusion is that the chip can be fabricated and meets the stated requirements.