1
$\begingroup$

A Random Variable '$X$' take values from a discrete alphabet $K = \{k_1, k_2, k_3,k_4 \}$, with probability mass function {$p(k_i)$} = {$0.6, 0.2, 0.15, 0.05$}.

The constructed Binary Huffman codes on $K$ are {$0, 10, 110, 111$}. The length of codewords are {$l_1, l_2,l_3,l_4$} = {$1, 2, 3, 3 $}. The maximum of {$1, 2, 3, 3 $} is $L = 3$. The number of codewords with length $L = 3$ is $2$, which is even.

Suppose if $K = \{k_1, k_2, k_3,....k_m \}$($m$ is very large), having some valid probability mass function. I constructed Binary Huffman Codes on the alphabet $K$. The length of the Huffman codewords be {$l_1, l_2,....l_m$} . Suppose the maximum of {$l_1, l_2,....l_m$} is $L$. Then can I say 'The number of Huffman codewords of length $L$ is even'$?$

$\endgroup$
3
  • $\begingroup$ Your nomenclature is odd. "for each realization $k_i$ : I guess you mean "for each symbol $k_i$ " (or value). Further, what is $l(max)$ ? Second, your "argument" does not look as an argument but as an affirmation. And I frankly don't understand it. Care to elaborate? $\endgroup$
    – leonbloy
    Sep 4, 2018 at 23:19
  • $\begingroup$ @leonbloy, for each realization $k_i$, yes I mean for each symbol $k_i$. I elaborated the question. Go through it! $\endgroup$ Sep 5, 2018 at 17:28
  • $\begingroup$ It's clear now. One thing that confused me is that you use the word "code" for "codeword". $\endgroup$
    – leonbloy
    Sep 6, 2018 at 13:03

1 Answer 1

2
$\begingroup$

Yes, you can. The easiest way to see it is to take a maximum length code of length $L$. Invert the lat bit of the code and you must get another code. If the version with the last bit flipped were not another code, it must be a prefix of some code, but that would be longer than $L$. You can group the maximum length codes in pairs that agree on the first $L-1$ bits and have opposite last bits, so there is an even number of them.

$\endgroup$
1
  • $\begingroup$ +1 This reasoning also shows that the crucial thing for this property to hold is not that the code is a Huffman code but just instantaneous and complete. $\endgroup$
    – leonbloy
    Sep 6, 2018 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .