Zero-error source coding when side information may be present - INRIA - Institut National de Recherche en Informatique et en Automatique Access content directly
Preprints, Working Papers, ... Year : 2021

Zero-error source coding when side information may be present

Maël Le Treust
Aline Roumy
  • Function : Author
  • PersonId : 874177

Abstract

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.
Fichier principal
Vignette du fichier
2021_itw_zero_error_SI_may_be_absent (2).pdf (290.58 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03290860 , version 1 (19-07-2021)
hal-03290860 , version 2 (16-12-2021)

Identifiers

  • HAL Id : hal-03290860 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More