A performance analysis of look-up table based variable-length decoders

In this report we are presenting two decoding algorithms for binary variable-length codes, based on a look-up table approach. This type of algorithms are familiar to software designers, but the authors have not been able to find any scientific material, where the decoding speed is analysed. The algorithms will decode one or several source symbols for each cycle of the algorithm. The look-up table approach is based on a completion of the tree representation of the variable-length code. Decoding is done by indexing a table with a fixed-length block from the concatenated variable-length code sequence. One restriction is that the fixed-length block must be at least as long as the maximal code word length in the used variable-length code.

Both the speed and memory requirement properties of the algorithms are studied. It is shown that the look-up table algorithms are considerably faster than the tree-search algorithm, seen in most tutorial books, at a cost of memory requirements exponentially growing with the fixed-length block size.

On the one hand, the memory requirements of the look-up table decoders are large, but on the other hand the cost per bit of memory has shown a rapidly decreasing trend during the last few decades.

Dedicated hardware proposals are presented for the look-up table algorithms, as well as a software evaluation of the decompression speeds on an i486 PC, using a 32-bit C compiler.