**ISO/IEC 10918-1 : 1993(E)**

**K.2**

**A procedure for generating the lists which specify a Huffman code table**

A Huffman table is generated from a collection of statistics in two steps. The first step is the generation of the list of

lengths and values which are in accord with the rules for generating the Huffman code tables. The second step is the

generation of the Huffman code table from the list of lengths and values.

The first step, the topic of this section, is needed only for custom Huffman table generation and is done only in the

encoder. In this step the statistics are used to create a table associating each value to be coded with the size (in bits) of the

corresponding Huffman code. This table is sorted by code size.

A procedure for creating a Huffman table for a set of up to 256 symbols is shown in Figure K.1. Three vectors are defined

for this procedure:

FREQ(V)

Frequency of occurrence of symbol V

CODESIZE(V)

Code size of symbol V

OTHERS(V)

Index to next symbol in chain of all symbols in current branch of code tree

where V goes from 0 to 256.

Before starting the procedure, the values of FREQ are collected for V

=

0 to 255 and the FREQ value for V

=

256 is set to

1 to reserve one code point. FREQ values for unused symbols are defined to be zero. In addition, the entries in

CODESIZE are all set to 0, and the indices in OTHERS are set to 1, the value which terminates a chain of indices.

Reserving one code point guarantees that no code word can ever be all "1" bits.

The search for the entry with the least value of FREQ(V) selects the largest value of V with the least value of FREQ(V)

greater than zero.

The procedure "Find V1 for least value of FREQ(V1) > 0" always selects the value with the largest value of V1 when

more than one V1 with the same frequency occurs. The reserved code point is then guaranteed to be in the longest code

word category.

**144**

**CCITT Rec. T.81 (1992 E)**