Du är här

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

Publiceringsår: 1993
Språk: Engelska
Publikation/Tidskrift/Serie: Div. of Signal Processing, Research Report
Dokumenttyp: Rapport
Förlag: Luleå University of Technology

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering

Övrigt

Published
TULEA 1993:03

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen

LERU logo U21 logo