[IEEE Trans. on Information Theory, October 2005, pp. 3433- 3444]
Sufficient Conditions for Existence of Binary Fix-Free Codes
Zsolt Kukorelly and Kenneth Zeger
Abstract
Two sufficient conditions are given for the existence of binary fix-free codes
(i.e., both prefix-free and suffix-free).
Let L be a finite multiset of positive integers whose Kraft sum is at most 3/4.
It is shown that there exists a fix-free code whose codeword lengths are the elements of L if
either of the following two conditions holds:
(i) The smallest integer in L is at least 2,
and no integer in L, except possibly the largest one, occurs more than 2min(L)-2 times.
(ii) No integer in L, except possibly the largest one, occurs more than twice.
The results move closer
to the Ahlswede-Balkenhol-Khachatrian conjecture that
Kraft sums of at most 3/4 suffice for the existence of fix-free codes.