Question regarding prefix codes

Question

Question: Show that for any alphabet $E$ of size $[E]=m$ $(m>0)$, there exists a prefix code $f: E \to \{0,1\}*$ with codeword lengths $l = 1,2,\dots,m$.

Just started this topic on Coding and have just learnt about Kraft's Inequality not sure how I would go about showing there exists a prefix code for this alphabet is this something I need to find as a follow up from Kraft's Inequality. Any help or guidance would be greatly appreciated!

Answer 1

Kraft’s inequality can be used here. It says that if your input alphabet $E$ has size $n$, your codeword alphabet has size $r$, there is a prefix code with codeword lengths $\ell_1,\ldots,\ell_n$ if and only if

$$\sum_{k=1}^n\left(\frac1r\right)^{\ell_k}\le 1\;.\tag{1}$$

• What are $m,r$, and $\ell_1,\ldots,\ell_n$ in your problem?

Once you’ve answered that, substitute the appropriate values into the summation in $(1)$ and evaluate it to see whether it is indeed less than or equal to $1$.

Answer 2

You can apply Kraft's inequality (see Brian M Scott answer) to prove that such a code must exist; or, in this particular case, you can also explicitly contruct it:

$$E_1 \to 0$$ $$E_2 \to 10$$ $$E_3 \to 110$$ $$E_4 \to 1110$$ $$ \cdots$$