A binary prefix code assigns each source symbol a distinct finite binary word, with no assigned word a prefix of another. It is instantaneous because a decoder can identify the symbol as soon as its last digit arrives, without reading digits from the next word. Such a code is optimal when it minimizesamong all binary prefix codes for that source distribution. Symbols of zero probability may be removed from the optimization.
Make a rooted binary tree with an edge labelled zero for the first branch and one for the second branch at each interior node. Put each source symbol at the leaf reached by following the successive digits of its codeword. The prefix property ensures no assigned word ends at an ancestor of another assigned word.
The route of a codeword is its root-to-leaf path; its length is the number of edges on that path, equal to the number of binary digits in the word. For an optimal tree with positive leaf probabilities, every interior node has two children: a node with just one child could be contracted, shortening all words below it and strictly reducing the expected length. The diagram in the earlier Huffman calculation is one such full binary tree.
Articles by others on the same topic
There are currently no matching articles.