27-07-2012, 09:46 AM
EFFICIENT HUFFMAN DECODING WITH TABLE LOOKUP
EFFICIENT HUFFMAN DECODING.pdf (Size: 151.6 KB / Downloads: 115)
ABSTRACT
We describe an efficient algorithm for Huffman decoding
using table lookup. The algorithm is optimized for ROMbased
Huffman decoding. It is a two-step process of prefix
template matching followed by a direct table access. We
propose an efficient algorithm for choosing the prefix
templates according to different optimization criteria. Also,
we propose different implementations for the prefix template
procedure.
INTRODUCTION
Huffman codes [1] have been widely used for source coding
and have shown high efficiency in exploiting the source
redundancy. Huffman codes along with run-length codes
have been widely used in most international multimedia
standards (e.g., MPEG and ISO standards [5], [7]).
Huffman decoding can be implemented with a lookup-table
(LUT) [2] or multiple lookup-tables [3]. If a single LUT is
used, the decoder throughput can be one codeword per cycle
whereas the throughput for multiple lookup tables is not
deterministic and in the worst case it equals the number of
lookup tables (assuming each LUT is processed in a single
cycle). The single LUT approach is usually adopted in high
efficiency Huffman decoder while the multiple LUTs
approach is usually used in low-power systems.
DECODING PROCEDURE
Background
Any Huffman code can be represented by a non-balanced
binary tree. The tree leaves represent the codewords of the
code. Any codeword has three attributes: the length, the
value, and the corresponding source symbol. An example of
a Huffman table of size 8 is shown in table 1 and the
corresponding tree representation is shown in Fig. 1. The
value of each internal node in Fig. 1 is the sum of its
children values and it is a measure of the internal node
probability.
Decoder structure
Each prefix template is associated with a sub-table that
contains all children codewords. The size of the sub-table is
2M−L, where M and L are the attributes of the prefix template
as defined earlier. The indexing within the sub-table is done
using the last M-L bits of the input word that follow the L
bits of the prefix template. The sub-table is filled with the
children codewords of the templates with possible repetition
of certain codewords. For example, if the node with
frequency 12 in the Huffman Tree of Fig. 1 is selected as a
prefix template, then the size of its sub-table will be 8 and it
is organized as.
PREFIX LUT IMPLEMENTATION
The prefix LUT module can be implemented in different
ways that depend on the structure of the Huffman table and
the target application.
The first choice is to use a programmable logic array (PLA)
as suggested in [4]. The cost of the PLA is proportional to
the number of templates which is significantly less than the
size of the Huffman table (which is used in [4]). In this case,
the prefix template matching can be performed in a single
cycle regardless of the matched template.
The second choice is to use a single comparator for
matching the prefix templates one at a time. This would
require a number of registers equals the number of
templates. To minimize the matching time, the templates are
arranged in descending order according to their
probabilities. The template probability equals the sum of the
probabilities of all its children (assuming source symbols are
independent). In Huffman codes the probability of each
source symbol is inversely proportional to the length of the
corresponding codeword.
DISCUSSION
We propose a generic algorithm for universal variable length
decoding. The algorithm is suited for Huffman tables in
current international multimedia coding standards. However,
it is general to decode any existing prefix code. The
algorithm generates a set of prefix templates and associates
each codeword to one of the templates. The decoding
process includes template matching and codeword retrieval
using direct table access. We proposed an efficient algorithm
for generating the prefix templates to optimize a generic
objective function and we gave several examples of the
objective function.