1
$\begingroup$

I am having trouble understanding a question related to Huffman Coding. We haven't studied it a lot, so I am not even sure how to start.

Given $n ≥ 2$ characters, with probabilities $p_{1} \geq p_{2} \geq ... \geq p_{n}$ Let $p_{i} = 2^{k_{i}}$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n} p_{i} = 1$

Show that $p_{n-1} = p_{n}$ and that the minimum expected codelength amount to $$- \sum_{i=1}^{n} p_{i} \log p_{i}$$

Help?

$\endgroup$
0
$\begingroup$

It's better to use the parametrization $p_i = 2^{-k_i}$. Multiply the equation $\sum_{i=1}^n p_i = 1$ by $2^{k_n}$ to get $$ \sum_{i=1}^n 2^{k_n-k_i} = 2^{k_n}. $$ The right-hand side is even, so the number of $i$ such that $k_i = k_n$ must be even as well (why?). This implies that $p_{n-1} = p_n$.

For your second question, it is known that the minimum expected codeword length is at least $H(p) = \sum_i p_i \log (1/p_i) = \sum_i p_i k_i$. The converse to Kraft's inequality shows that there is a prefix code with codeword lengths $k_1,\ldots,k_n$, and so with expected codeword length $H(p)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.