Advanced

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

Edfors, Ove LU ; Erendi, Alex and Börjesson, Per Ola LU (1993) In Div. of Signal Processing, Research Report TULEA 1993:03.
Abstract
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.... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
publishing date
type
Book/Report
publication status
published
subject
in
Div. of Signal Processing, Research Report
volume
TULEA 1993:03
publisher
Luleå University of Technology
language
English
LU publication?
no
id
6dc7e6a8-03d1-4c28-9424-566cda9e70f6 (old id 1043843)
date added to LUP
2008-03-10 14:03:44
date last changed
2016-06-29 09:19:28
@misc{6dc7e6a8-03d1-4c28-9424-566cda9e70f6,
  abstract     = {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. <br/><br>
 <br/><br>
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. <br/><br>
 <br/><br>
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. <br/><br>
 <br/><br>
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.},
  author       = {Edfors, Ove and Erendi, Alex and Börjesson, Per Ola},
  language     = {eng},
  publisher    = {ARRAY(0x7d136d8)},
  series       = {Div. of Signal Processing, Research Report},
  title        = {A performance analysis of look-up table based variable-length decoders},
  volume       = {TULEA 1993:03},
  year         = {1993},
}