Zero-error source coding when side information may be present

Nicolas Charpenay (1) , Maël Le Treust , Aline Roumy

1 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires

Zero-error source coding when side-information (SI) may be present is a fundamental building block of interactive real-world compression systems. In this paper, we show how to use the SI at the encoder in order to lower the compression rate. Indeed, in general, without SI at the encoder, the minimum zero-error compression rate is the entropy of the source to be compressed. In this paper, we show, that the availability of the SI at the encoder allows to achieve lower rate. The code construction relies on the typicality bipartite graph in which the vertices corresponds to the sequences of source and side information, where an edge links the pair of exactly typical sequences. By considering binary source alphabets, we show that the Hamming distance characterize the graph coloring. For short block length, we show that our type grouping code outperforms any timesharing strategy between the Huffman code and the conditional Huffman code. Then we extend these results to arbitrary source alphabets.

Domaines: Théorie de l'information et codage [math.IT]

Nicolas Charpenay, Maël Le Treust, Aline Roumy. Zero-error source coding when side information may be present. 2021. ⟨hal-03290860v1⟩