Prove that the codewords of the Shannon-Fano code satisfy $l_i \leq \left \lceil \log _2 \frac1{p_i}\right \rceil$.

Elementary wording: given positive numbers in descending order $p_1,...,p_n$, $\sum_i p_i=1$, we split them such that the difference between the right sum and the left sum is minimal. We do the same to each of the two parts, resulting in four sections. then every $\frac14 \leq p_i < \frac12$ is alone in its section. And after three steps every $\frac18 \leq p_i < \frac14$ is alone etc.

The book just states this without proof, and I couldn't work it out. It is easy when the sum of the section after the first step is $\leq \frac12$, since then there can be at most one $\frac14 \leq p_i < \frac12$ (except the trivial case of two quarters), and it appears first and is at least half of the total sum, so we must split immediately after it. But I struggled with the other case.

(It doesn't really require coding theory, but I'm not sure how to tag it.)

  • $\begingroup$ Suggest mentioning, $l_i$ is the number of edges from root to leaf $p_i$ in the tree. $\endgroup$ – DanielV Jun 12 '14 at 20:02

Your Answer

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

Browse other questions tagged or ask your own question.