6.441-6 Huffman codes

LECTURE 6Last time: Kraft inequality • optimal codes. • Lecture outline Huffman codes • Reading: Scts. 5.5-5.7. Kraft inequalityAny instantaneous code C with code lengths l1,l2, . . . , lm must satisfy m� D−li ≤ 1 i=1 Conversely, given lengths l1,l2, . . . , lm that satisfy the above inequality, there exists and instantaneous code with these codeword lengths How do we achieve such a code in a practiica fashion? Make frequent elements short and infrequuen one longer. Huffman codesDefinition: let X be a set of m source symbools let D be a D-ary alphabet. A Huffman code CHuff is an optimum instanta­ X �→ D∗ neous code in which the 2+((m−2)mod(D−1)) least likely source symbols have thesame length and differ only in the last digitProposition: for any set of source symbols X with m symbols, it is possible define a Huffman code for those source symbols Consider a binary code: reorder the xi in terms of decreasing probabiilit the two least likely symbols are xm−1, xm � Huffman codes for binary DFor the code C to be optimal, l(xi) ≥ l(xj) for i ≥ j for every maximal length codeword C(xi) there must a codeword C(xj) that differs only in the last bit -otherwise erase one bit while still satisfying prefix condition to satisfy that C(xm) and C(xm−1) differ only in the last bit: find xi such that C(xm) and C(xi) differ only in the last bit and if xi = xm, swap them repeat with code for symbols x1, . . . , xm−2 How do we construct them?Find the q = 2+((m − 2)mod(D − 1)) leastlikely source symbols xm, . . . , xm−q+1Delete these symbols from the set of sourcesymbols and replace them with a single symbbo ym−qAssign p(ym−q)= �mi=m−qp(xi)Now we have new set of symbols X�Construct a code CHuff,m−q : X� �→D∗Note: could be using arbitrary weight functiio instead of probability Why does this work? Illustrate for binary Why does this work?Amalgamation is not always least likely event in X� Why does this work? Two questions arise: Why is it enough to now find a Huffman code CHuff,m−q? Where does the the q = 2+((m−2)mod(D−1)) come from? Add one more letter for the q symbols xm, . . . , xm−q with respect to CHuff,m−q Average length of code is average length of CHuff,m−q, plus p(ym−q)= �mi=m−qp(xi) Could we have done better by taking some unused node in CHuff,m−q to represent some of the xm, . . . , xm−q? We’ll see that this is not possible and it is related to the first question Complete treesDefinition: a complete code tree is a finiit code tree in which each intermediate node has D nodes of the next higher order stemming from it In a complete tree the Kraft inequality is satisfied with equality Complete treesThe number of terminal nodes in a compllet code tree with alphabet size D must be of the form D + n(D − 1) Smallest complete tree has D terminal nodesWhen we replace a terminal node by an intermeediat node, we lose one terminal node and gain D more, for a net gain of D − 1 Optimal codes and complete treesOptimal code can be seen as a complete tree with some number B of unused terminna nodes By contradiction, if there are incomplete intermediate nodes, nodes of higher order could complete intermediate nodes without adverse effect on length B ≤ D −2, otherwise we could swap unused terminal nodes to group D − 1 of them, in which case we can altogether eliminate those terminal nodes Optimal codes and complete treesHow large is B? B + m = n(D − 1) + D so D − 2 − B is the remainder of dividing m − 2 by D − 1, or (m − 2)mod(D − 1) B = D − 2 − ((m − 2)mod(D − 1)) That is why we first group the q = 2+((m−2)mod(D − 1)) least likely source symbolsAfter we have grouped those symbols, a complete tree is needed for the remaining m − q symbols plus the symbol created by the amalgamation of the least likely q symbool Use the fact that B + q = D m − q +1 = n(D − 1) + D − B − q +1 = n(D − 1) + 1 =(n − 1)(D − 1) + D What happens if the unlikely eventschange probability?Major change may be necessary in the codeCannot do a good job of coding until all events have been catalogued MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.