loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (DCC'05)
Generalizing the Kraft-McMillan Inequality to Restricted Languages
Snowbird, Utah
March 29-March 31
ISBN: 0-7695-2309-9
Mordecai J. Golin, HKUST, Kowloon, Hong Kong
Hyeon-Suk Na, Soongsil University, Seoul, South Korea
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.