1956/12/01 by B. McMillan · 210 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Alphabet #Coding theory and cryptography #Combinatorics #Computer science #DNA and Biological Computing #Discrete mathematics #Information retrieval #Linguistics #Mathematics #Natural language processing #Philosophy #Redundancy (engineering) #String (physics) #Word (group theory) #semigroups and automata theory
paper · doi:10.1109/tit.1956.1056818
published in IEEE Transactions on Information Theory 2(4), 115-116 (Institute of Electrical and Electronics Engineers)
openalex publication_date 1956/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 a-l1 + a-l2 + ⋯ + a-lb ≤ 1, (1) whereli, 1 ≤ i ≤ 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.