A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the same performance (efficiency)?

  • $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ Commented Nov 17, 2018 at 18:48
  • $\begingroup$ I tried and I got the codes {b, c, aa, ab, ac}, {a, c, ba, bb, bc}, {a, b, ca, cb, cc} using Huffman algorithm but I don't know if it's all of them $\endgroup$
    – Sydney.Ka
    Commented Nov 17, 2018 at 19:07
  • $\begingroup$ Huffman's algorithm doesn't necessarily find all minimum redundancy codes. $\endgroup$ Commented Nov 17, 2018 at 19:27

1 Answer 1


There are infinitely many prefix codes over $\{a,b,c\}$ containing 5 elements, for example $a,ba,b^2,b^3a,b^{4+n}a$ for all $n \geq 0$. I'm assuming the question is concerned with "saturated" or "minimal" prefix codes, which are prefix codes which satisfy one of the following equivalent conditions:

  • Each string in $\{a,b,c\}^\omega$ contains some codeword as a prefix.
  • Kraft's inequality is tight.
  • The ternary tree corresponding to the code is full, that is, each internal vertex has exactly three children.

It's not hard to check that all such codes containing 5 codewords must look as follows: $$ \alpha, \beta, \gamma\alpha, \gamma\beta, \gamma\gamma. $$ For such a code to be optimal for your particular distribution, a necessary and sufficient condition is that $\alpha,\beta$ are assigned to the heavy elements and $\gamma\alpha,\gamma\beta,\gamma\gamma$ to the light elements. You can check it by direct calculation (there are only 3 options, up to symmetry), or by noticing that if a code uses a length-1 codeword for a light element and a length-2 codeword for a heavy element, then switching them reduces the average codeword length.

Indeed, if we fix the codewords, then it is easy to assign them to symbols. The more difficult task is to find the optimal set of codewords. In this case, there is only one set of codewords, so there is no need to run any fancy algorithm such as Huffman's.

  • $\begingroup$ Thank you for your help. I have one more question: Is there any rule to find the exact number of optimal codes for such distributions of probability, where 2 signals or more have the same probability? $\endgroup$
    – Sydney.Ka
    Commented Nov 17, 2018 at 19:58
  • $\begingroup$ Probably not, but you'll have to state the problem more formally, as a new question. $\endgroup$ Commented Nov 17, 2018 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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