Data Compression Conference (DCC'05) Generalizing the Kraft-McMillan Inequality to Restricted Languages Snowbird, Utah March 29-March 31 ISBN: 0-7695-2309-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2005.42
Let l₁, l₂, ..., l_n be a (possibly infinite) sequence of nonnegative integers and Σ some D-ary alphabet. The Kraft-Inequality states that l₁, l₂, ..., l_n are the lengths of the words in some prefix (free) code over Σ if and only if\sum\limits_{i = 1}^n {D^{ - l_i } } \leqslant 1.Furthermore, the code is exhaustive if and only if equality holds. The McMillan Inequality states that if l₁, l₂, ..., l_n are the lengths of the words in some uniquely decipherable code, then the same condition holds.In this note we examine how the Kraft-McMillan Inequality conditions for the existence of a prefix or uniquely decipherable code change when the code is not only required to be prefix but all of the codewords are restricted to belong to a given specific language L. For example, L might be al words that end in a particular pattern or, if Σ is binary, might be all words in which the number of zeros equals the number of ones.
Citation:
Mordecai J. Golin, Hyeon-Suk Na, "Generalizing the Kraft-McMillan Inequality to Restricted Languages," dcc, pp.163-172, Data Compression Conference (DCC'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||