On instantaneous codes for zero-error coding of two correlated sources

We study the problem of finding zero-error instantaneous codes for the Slepian-Wolf configuration. By a zero-error instantaneous code we mean two encoder maps f₁:χ→{0,1}*, f₂:Y→{0,1}* and a decoding algorithm which, for any pair of encoder outputs f₁(x₁)f₁(x₂ )f₁(x₃)... and f₂(y₁)f ₂(y₂)f₂(y₃)..., can correctly determine x₁ and y₁ by reading only the first length (f₁(x₁)) bits of the X encoder output and the first length (f₂(y₁)) bits of the Y encoder output. For |χ|=2, we find a necessary and sufficient condition for the existence of a zero-error instantaneous code with a given set of codeword lengths for Y. Using this condition, we derive an upper bound to the minimum expected codeword length for Y and construct a simple example showing that the coding scheme proposed by Kh, Jabri and Al-Issa (1997) is not optimal in general, and more surprisingly, the optimal code may violate the “Morse condition” that the more probable of two symbols never has the longer codeword. For |χ|=3, we find a necessary but not sufficient condition for the existence of a zero-error instantaneous code with a given set of codeword lengths for Y. Moreover, for |χ|⩾3, the existence of such a code is shown to be related to a rectangle packing problem