A Kraft-Type Sufficient Condition for the Existence of $D$-Ary Fix-Free Codes
Mohammadali Khosravifard, Hassan Halabian, Thomas Aaron Gulliver · IEEE Transactions on Information Theory · 2010
A greedy scheme called Greedy Codeword Assignment Scheme (GCAS) is proposed to assign D-ary codewords to the given code-lengths ¿1,¿2,...,¿n, so that they satisfy the fix-free property. This scheme guarantees that a D-ary fix-free code can be obtained whenever ¿i=1nD-¿¿ ¿(D), where ¿(D) is equal to 5/8 for D even and very close to 5/8 for D 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 mini ¿i= 2, the inequality ¿i=1n2-¿i¿ 21/32 implies the existence of a binary fix-free code with code-lengths ¿1,¿2,...,¿n.