5
$\begingroup$

Given a code $c:S\rightarrow T^*$ let $n_i$ denote the number of symbols in S that are encoded by strings of length $i$ in $T^*$

If we want to construct a uniquely decodable code for 12 symbols using binary words of length less than or equal to 4. Make a list of all the sets of parameters $n_1,n_2,n_3,n_4$ for which a suitable code exists.

I'm sure I need to use the Kraft-Mcmillian number here and I think this is pretty simple but I'm a bit lost as where to go.

Thanks for any help.

1 Answers 1

5

According to the Kraft-McMillan theorem, a necessary and sufficient condition for $c$ to be uniquely decodable is that $\sum_{k=1}^4 n_k\left(\frac12\right)^k\le1\;.\tag{1}$ Thus, you need to find all of the $4$-tuples $\langle n_1,n_2,n_3,n_4\rangle$ of non-negative integers such that $(1)$ holds and $n_1+n_2+n_3+n_4=12$.

One way to do it systematically is to observe that $\langle 0,0,0,12\rangle$ is a solution and then try to transfer $4$-bit strings to shorter strings. For instance, $\langle 0,0,1,11\rangle$ is still okay, because $\frac18+\frac{11}{16}\le1$. What about $\langle 0,0,2,10\rangle$? The lefthand side of $(1)$ is then $\frac28+\frac{10}{16}=\frac78\le1$, so that’s okay, too. So are $\langle 0,0,3,9\rangle$ and $\langle 0,0,4,8$: the sums are $\frac38+\frac9{16}=\frac{15}{16}\le1$ and $\frac48+\frac8{16}=1$. But $\langle 0,0,5,7\rangle$ isn’t acceptable: $\frac58+\frac7{16}=\frac{17}{16}>1$.

There are ways to speed things up, but a good way to discover some of them is to continue the brute-force procedure until you start seeing some patterns. For instance, you might notice just in what I did above that every time I transferred one symbol from a $4$-bit to a $3$-bit code, the sum on the lefthand side of $(1)$ increased by $1/16$. Can you see why? Better yet, can you see how to make use of this in transferring symbols between codes of other lengths?

  • 0
    +1 For extra credit (in proving that the OP has understood how Kraft-McMillan works) the OP could also exhibit examples of uniquely decodable codes in each case :-)2012-08-18