Question

Let C be a Huffman binary code for source with alphabet S = {s1, · · · , sq}. The code words are w1, w2, · · · , wq. Prove that the equality holds in Kraft’s inequality, i.e., X q k=1 1 2 lk = 1, where lk is the length of wk.

Let be a Huffman binary code for source with alphabet S = {sı, . . . , sq). The code words are wi, w2,'.. ,wq. Prove that the equality holds in Kraft's inequality, i.e., -1 where lk is the length of wk. k-1

Answer 1

Huffman code creates an prefix code optimally which is used for lossless data compression. It exhibits a property that no code should contain the other code as the prefix or no two codes should have the same prefix.

Huffman code creates an prefix code optimally which is used for lossless data compression. It exhibits a property that no code should contain the other code as the prefix or no two codes should have the same prefix. Proof S = { s_1, s_2........ s_q} code words = {w_1, w_2 ...... w_q } = length of wk. therefore l_1 lessthanorequalto l_2 lessthanorequalto l_3 lessthanequalto..... lessthanequalto lq Thus exist a if at each q, there is atleast one codeword that doesn't match with any of the previous code (property of code) For w_q (codeword w of length),there are 2 combinations possible to choose the code word from but because of the predix property of code, j < q, 2^q - j codes can't be chosen Therefore at step q, a code is possible we choose a code word such that Now 2^lq > sigma^q - 1_k = 1 2 ^lq - lk 2^lq greaterthanorequalto sigma^q - 1_k = 1