A Note on the Fix-Free Code Property

Kazuyoshi HARADA  Kingo KOBAYASHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.10   pp.2121-2128
Publication Date: 1999/10/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Source Coding/Image Processing
Keyword: 
prefix code,  fix-free code,  Kraft Inequality,  greedy algorithm,  

Full Text: PDF(607.2KB)>>
Buy this Article




Summary: 
We study some sufficient conditions of codeword lengths for the existence of a fix-free code. Ahlswede et al. proposed the 3/4 conjecture that Σi=1n a-li 3/4 implies the existence of a fix-free code with lengths li when a=2 i. e. the alphabet is binary. We propose a more general conjecture, and prove that the upper bound of our conjecture is not greater than 3/4 for any finite alphabet. Moreover, we show that for any a2 our conjecture is true if codeword lengths l1,l2,. . . consist of only two kinds of lengths.