Empirical and Strong Coordination via Soft Covering with Polar Codes

Remi A. Chou, Matthieu R. Bloch, Jorg Kliewer

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low-complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions taking value in an alphabet of prime cardinality. Our results improve previously known polar coding schemes, which (i) were restricted to uniform distributions and to actions obtained via binary symmetric channels for strong coordination, (ii) required a non-negligible amount of common randomness for empirical coordination, and (iii) assumed that the simulation of discrete memoryless channels could be perfectly implemented. As a by-product of our results, we obtain a polar coding scheme that achieves channel resolvability for an arbitrary discrete memoryless channel whose input alphabet has prime cardinality.

Original languageEnglish (US)
Pages (from-to)5087-5100
Number of pages14
JournalIEEE Transactions on Information Theory
Volume64
Issue number7
DOIs
StatePublished - Jul 2018

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Strong Coordination
  • channel resolvability
  • empirical coordination
  • polar codes
  • resolvability
  • soft covering

Fingerprint Dive into the research topics of 'Empirical and Strong Coordination via Soft Covering with Polar Codes'. Together they form a unique fingerprint.

Cite this