A performance analysis of look-up table based variable-length decoders
(1993) In Div. of Signal Processing, Research Report- 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:
https://lup.lub.lu.se/record/1043843
- author
- Edfors, Ove LU ; Erendi, Alex and Börjesson, Per Ola LU
- publishing date
- 1993
- type
- Book/Report
- publication status
- published
- subject
- in
- Div. of Signal Processing, Research Report
- publisher
- Luleå University of Technology
- report number
- TULEA 1993:03
- language
- English
- LU publication?
- no
- id
- 6dc7e6a8-03d1-4c28-9424-566cda9e70f6 (old id 1043843)
- date added to LUP
- 2016-04-04 12:19:43
- date last changed
- 2018-11-21 21:10:19
@techreport{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}}, institution = {{Luleå University of Technology}}, language = {{eng}}, number = {{TULEA 1993:03}}, series = {{Div. of Signal Processing, Research Report}}, title = {{A performance analysis of look-up table based variable-length decoders}}, year = {{1993}}, }