Browse Prior Art Database

Unified Encoding and Decoding of Huffman Codes

IP.com Disclosure Number: IPCOM000081192D
Original Publication Date: 1974-Apr-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 4 page(s) / 114K

Publishing Venue

IBM

Related People

Cain, RG: AUTHOR

Abstract

The following describes a technique for serially encoding and decoding prefix codes exemplified by the Huffman codes. Huffman codes may be represented by regular binary trees (Fig. 1) wherein sink vertices represent the code symbols, and paths between the top vertex and the bottom sink vertices determine the code symbol digit values. The number of nonsink vertices on a path equal the number of bits in the associated code symbol value, and the value of each hit (1 or 0) is equal to the downward direction (left or right) taken from the respective vertex.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 61% of the total text.

Page 1 of 4

Unified Encoding and Decoding of Huffman Codes

The following describes a technique for serially encoding and decoding prefix codes exemplified by the Huffman codes. Huffman codes may be represented by regular binary trees (Fig. 1) wherein sink vertices represent the code symbols, and paths between the top vertex and the bottom sink vertices determine the code symbol digit values. The number of nonsink vertices on a path equal the number of bits in the associated code symbol value, and the value of each hit (1 or 0) is equal to the downward direction (left or right) taken from the respective vertex.

The rules of such binary tree manipulation are similar for decoding and encoding and may be embodied in a single encoder/decoder device. The cost of such a device would be independent of the symbol distribution function and the associated "worst-case" code word length.

Table 1 shows a hypothetical symbol distribution for a set of 16 (in general N) symbols and an optimum Huffman code for that set. Fig. 1 is the binary tree yielding this encoding. TABLE 1

SYMBOL PROBABILITY CODE

0 0.01763907734 111110

1 0.1017639077 000

2 0.06105834464 1000

3 0.07191316147 1001

4 0.02849389417 11110

5 0.005427408412 11111110

6 0.09090909091 1010

7 0.09090909091 1011

8 0.1261872456 001

9 0.05156037992 1100

10 0.06919945726 1101

11 0.1126187246 010

12 0.004070556309 11111111

13 0.006784260516 1111110

14 0.07055630936 1110

15 0.09090909091 011.

In order to describe the decoder, a pair of upper and lower integer labels is assigned to each vertex below the top vertex (Fig. 2). The upper labels are generated by assigning the labels 0 and 16 (in general N), respectively, to the left and right vertices of the pair just below the top vertex and thereafter assigning unique upper labels to succeeding vertex pairs, such that the label of the left vertex of the pair is less than 16 (in general N) and the label of the right vertex is 16 (or N) plus the left label. The bottom labels of the lowest (sink) vertices are the integers assigned to the respective symbols (Table 1). The bottom labels of inner vertices equal the top labels of successor vertices just below and to the left.

The decoder comprises a memory device with 32 (in general 2N) words, wherein the word width is 1+B (where N = 2 ). The contents of this memory are determined by the rules of labeling applied to the binary tree representation of

1

Page 2 of 4

the code, treating the top labels of the vertices as memory addresses. For inner vertices contents of respective memory addresses are binary 0, followed by binary representations of respective bottom labels. For bottom (sink) vertices memory contents are binary 1, followed by binary representations of respective bottom labels.

Fig. 3 illustrates decoding for this example. The initial word is...