
i
i
i
i
i
i
i
i
8 1 Information Theory
1.2.1 Huffman Coding
An optimal prefix code for a given distribution can be constructed by a simple al-
gorithm proposed by Huffman [6], widely known as Huffman coding. In Huffman
coding, a binary tree of nodes is first created. The size is equal to the number of sym-
bols to code, q. Initially, all nodes are leaf nodes containing the probabilities of the
symbols they represent. The coding process essentially begins with the leaf nodes. A
new node whose children are the two nodes with the smallest probability is created.
The new node’s probability is equal to the sum of the children’s probabilities. With
the previous two ...