Find number of codes using Kraft inequality

combinatoricsinformation theory

Let $A$ be the alphabet of the codes, with $|A| = D$, and codelengths $1 \leq l_1 \leq … \leq l_n$. Those codelengths satisfy the inequality of Kraft:

$$\sum_{i=1}^n D^{-l_i} \leq 1$$

On how many ways can we choose codewords $c(w_i) \in A^*$ so that $c(w_i)$ had length $l_i$, and that the code is a prefix code? ($A^*$ is the concatenation of ''characters'' in the alphabet, and $w_i$ is just a word)

I don't exactly know where to start. It is not very difficult to show that a code is a prefix code. But how can I find the number of ways we can choose that codewords $c(w_i)$? I hope somebody can help me with that.

Best Answer

There are $D^{l_1}$ ways of picking $c(w_1)$, now fixing it, there are $D^{l_2}-D^{l_2-l_1}$ ways of picking $c(w_2)$. Going further, if we fix $c(w_1)$ to $c(w_{k-1})$, then we have $D^{l_{k}}-\sum_{i=1}^{k-1} D^{l_k-l_i}$ ways of choosing $c(w_k)$. The numbers of way to choose the whole code is the product of that and I cannot find a way of simplifying it.

Related Question