Contents

1 Introduction

• Designed by David A. Huffman in 1952 [1].
• Optimal performance (better than Shannon-Fano) when a integer number of bits is assigned to each symbol.
• The VLC codec builds a binary tree where the symbols are stored in the leafs and the distance of each symbol to the root of the tree is $\lceil {log}_2\left(p\left(s\right)\right)\rceil$.
• After label each binary branch in the tree, the Huffman code-word for the symbol $s$ is the sequence of bits (labels) that we must use to travel from the root to the $s$-leaf.

2 Algorithm to build the Huffman tree

1. Create a list of nodes. Each node stores a symbol and its probability.
2. While the number of nodes in the list > 1:
   1. Extract from the list the 2 nodes with the lowest probability.
   2. Insert in the list a new node (that is the root of a binary tree) whose probability is the sum of the probability of its leafs.

Example

References