On the ratio of prefix codes to all uniquely decodable codes with a given length distribution

Abstract

We investigate the ratio ${\rho }_{n,L}$ of prefix codes to all uniquely decodable codes over an $n$-letter alphabet and with length distribution $L$. For any integers $n\ge 2$ and $m\ge 1$, we construct a lower bound and an upper bound for ${\inf }_L{\rho }_{n,L}$, the infimum taken over all sequences $L$ of length $m$ for which the set of uniquely decodable codes with length distribution $L$ is non-empty. As a result, we obtain that this infimum is always greater than zero. Moreover, for every $m\ge 1$ it tends to 1 when $n\to \infty$, and for every $n\ge 2$ it tends to 0 when $m\to \infty$. In the case $m=2$, we also obtain the exact value for this infimum.