Finding a binary prefix code provided lengths

Question

Firstly, I am relatively new to this particular forum, and I usually use Stack exchange (maths). I do not know if this is the right place to post so please be aware in case, I should ask this question on a different stack exchange.

For the following numbers: 1,2,3,3,3. Find a binary prefix code for these lengths.

In my working out I realise by the sum of 3^x, where x is each of the respective numbers is {/frac 5/9}

Then with 3 symbols I have the following prefix code:

With length 1, I have the code 0. With length 2, I have the code 10. With 3 words that have length 3 I have the codes: 110, 111, 112.

I am asking this question because my tutor said that 112 was a possible code. I have only thought of this now, but since I am required to find a binary code how can there be a code 112? Should it not be something like 011? From my understanding, the code which is binary should only contain 0's and 1's.

I have attempted to contact my tutor but to no avail.

Any help would be welcome.

Thnx

Answer 1

With 3 words that have length 3 I have the codes: 110, 111, 112

Your try:

L C
1 0
2 10
3 110
3 111
3 112

If you are looking for a binary prefix-free code , then 112 does not make sense.

Before looking for such a code, with prescribed lengths, you might test if it's possible. A necessary and sufficient criterion is Kraft's inequality: $\sum 2^{-l_i} \le 1$. In this case we have $\frac12 + \frac 14 + 3 \frac18=\frac98>1$ Hence, it's not possible to find a binary prefix-free code with those lengths.

BTW: I have no idea why you've you've computed $\sum 3^{-l_i} $ (I guess that's you meant). That would make sense if you wanted a ternary code. In that case, yes, the Kraft's inequality is verified, and you can build a ternary prefix-free code (your try is fine).

Answer 2

I would think but cannot be certain that 112 is not a binary code because 2 is not a binary number, and that it should be 0's and 1's only. However I am not completely sure.