A Kraft-Type Sufficient Condition for the Existence of D-Ary Fix-Free Codes

作者：Khosravifard Mohammadali^*; Halabian Hassan; Gulliver T Aaron

来源：IEEE Transactions on Information Theory, 2010, 56(6): 2920-2927.

DOI：10.1109/TIT.2010.2046244

• D-ary fix-free code
• 3/4-conjecture
• Kraft-sum

A greedy scheme called Greedy Codeword Assignment Scheme (GCAS) is proposed to assign D-ary codewords to the given code-lengths l(1),l(2),...,l(n), so that they satisfy the fix-free property. This scheme guarantees that a D-ary fix-free code can be obtained whenever Sigma(n)(i=1)D-li <= gamma(D), where gamma(D) is equal to 5/8 for even and very close to 5/8 for odd. This result can be regarded as an extension of Yekhanin's theorem on the existence of binary fix-free codes. In the special case D = 2, the greediness of GCAS enables us to prove that if min(i) l(i) = 2, the inequality Sigma(n)(i=1) 2(-li) <= 21/32 implies the existence of a binary fix-free code with code-lengths l(1),l(2),...,l(n) .

• 出版日期2010-6