Kraft inequality and zero-error source coding with decoder side information
For certain source coding problems, it is well known that the Kraft inequality provides a simple sufficient condition for the existence of codes with given codeword lengths. Motivated by this fact, a sufficient condition based on the Kraft inequality can also be sought for the problem of zero-error instantaneous coding with decoder side information. More specifically, it can be envisioned that a sufficient condition for the existence of such codes with codeword lengths {l(x)} is that for some 0 < alpha <= 1 [GRAPHICS] for each clique F in the characteristic graph G of the source-side information pair. In this correspondence, it is shown that 1) if the above is indeed a sufficient condition for a class G of graphs, then it is possible to come as close as 1 - log(2) alpha bits to the asymptotic limits for each graph in G, 2) there exist graph classes of interest for which such alpha can indeed be found, and finally 3) no such alpha can be found for the class of all graphs.
kraft inequality zero-error side information clique entropy confusability graph rectangle packing redundancy