Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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?

share|improve this answer
    
+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 :-) –  Jyrki Lahtonen Aug 18 '12 at 11:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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