01-12-2012, 06:12 PM
Variable–Length and Huffman Codes
Variable–Length.pptx (Size: 145.8 KB / Downloads: 85)
Shortened Block Codes
With exactly 2m symbols, we can form a set of code words each of length m : b1 …… bm bi {0,1}. This is a complete binary decoding tree of depth m. With < 2m symbols, we can chop off branches to get modified (shortened) block codes.
Huffman Codes in radix
At each stage down, we merge the last (least probable) r states into 1, reducing the # of states by r 1. Since we end with one state, we must begin with no. of states 1 mod (r 1) . We pad out states with probability 0 to get this. Example: r = 4; k = 3