1
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ – Yuval Filmus Nov 17 '18 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 Nov 17 '18 at 19:07
  • $\begingroup$ Huffman's algorithm doesn't necessarily find all minimum redundancy codes. $\endgroup$ – Yuval Filmus Nov 17 '18 at 19:27
0
$\begingroup$

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.

$\endgroup$
  • $\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 Nov 17 '18 at 19:58
  • $\begingroup$ Probably not, but you'll have to state the problem more formally, as a new question. $\endgroup$ – Yuval Filmus Nov 17 '18 at 20:21

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.