On the Combinatorial Version of the Slepian-Wolf Problem

Daniyar Chumbalov 1 Andrei Romashchenko 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study the following combinatorial version of the Slepian–Wolf coding scheme. Two isolated Senders are given binary strings X and Y , respectively; the length of each string is equal to n , and the Hamming distance between the strings is at most $\alpha n$ . The Senders compress their strings and communicate the results to the Receiver. Then, the Receiver must reconstruct both the strings X and Y . The aim is to minimize the lengths of the transmitted messages. For an asymmetric variant of this problem (where one of the Senders transmits the input string to the Receiver without compression) with deterministic encoding, a nontrivial bound was found by Orlitsky and Viswanathany. In this paper, we prove a new lower bound for the schemes with syndrome coding, where at least one of the Senders uses linear encoding of the input string. For the combinatorial Slepian--Wolf problem with randomized encoding, the theoretical optimum of communication complexity was known earlier, even though effective protocols with optimal lengths of messages remained unknown. We close this gap and present a polynomial-time randomized protocol that achieves the optimal communication complexity.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054 - 6069. 〈10.1109/TIT.2018.2854589〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233020
Contributeur : Andrei Romashchenko <>
Soumis le : mardi 24 novembre 2015 - 12:22:27
Dernière modification le : mardi 11 septembre 2018 - 14:54:01

Lien texte intégral

Identifiants

Citation

Daniyar Chumbalov, Andrei Romashchenko. On the Combinatorial Version of the Slepian-Wolf Problem. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2018, 64 (9), pp. 6054 - 6069. 〈10.1109/TIT.2018.2854589〉. 〈lirmm-01233020〉

Partager

Métriques

Consultations de la notice

112