Two inequalities implied by unique decipherability
B. McMillan · IEEE Transactions on Information Theory · 1956
Consider a list ofbwords, each word being a string of letters from a given fixed alphabet ofaletters. If every string of words drawn from this list, when written out in letters without additional space marks to separate the words, is uniquely decipherable, then \begin{equation} a^{-l_1} + a^{-l_2} + \cdots + a^{-l_b} \leq 1, \qquad \qquad (1) \end{equation} wherel_i, 1 \leq i \leq b, is the length of theith word in the list. This result extends a remark of J. L. Doob, who derived the same inequality for lists of a more restricted kind. A consequence of (1) and work of Shannon is that this more restricted kind of list suffices in the search for codes with specified amounts of redundancy.