# How many prefix code we can find for a given distribution of probability?

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

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

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.
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.