Abstract

Consider a list of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</tex> words, each word being a string of letters from a given fixed alphabet of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</tex> letters. 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} where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l_i, 1 \leq i \leq b</tex> , is the length of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> th 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.