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.

  • $\begingroup$ Do you mean $D_i^{-L_i}$? As written your inequality is almost always false. $\endgroup$ – Samuel Bodansky Sep 11 at 9:56
  • $\begingroup$ Yes, you are right. Thank you for mentioning $\endgroup$ – Pieter Sep 11 at 10:01

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.

  • $\begingroup$ And those are all prefix codes, right? $\endgroup$ – Pieter Sep 11 at 13:51
  • $\begingroup$ This looks correct, but it when $l_i=l_{i+1}$ it counts as different codes that differ merely in permutation of codes $c_i$ $c_{i+1}$. You might want that or not, it's not clear. $\endgroup$ – leonbloy Sep 11 at 18:37
  • $\begingroup$ yes, all the prefix free codes. @leonbloy yes, this is what I understood from the question, otherwise it would be about the set of codewords right ? $\endgroup$ – P. Quinton Sep 12 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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