Variable-rate coding with feedback for universal communication systems

Shriram Sarvotham, Dror Baron, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Classical coding schemes that rely on joint typicality (such as Slepian-Wolf coding and channel coding) assume known statistics and rely on asymptotically long sequences. However, in practice the statistics are unknown, and the input sequences are of finite length. In this finite regime, we must allow a non-zero probability of codeword error ε and also pay a penalty in the rate. The penalty manifests itself as redundancy in source coding and a gap to capacity in channel coding. Our contributions in this paper are two-fold. First, we develop a universal scheme for the specific example of the binary symmetric channel. With n channel uses and a fixed ε, the gap to capacity of our scheme is O(√n). The prior art for channel coding with known statistics shows that the penalty is ω(√n). Therefore, we infer for communication systems that rely on joint typicality that the penalty needed to accommodate universality is φ(√n). Second, we derive the penalty incurred in variable-rate universal channel coding when we restrict the number of rounds of feedback. Surprisingly, it turns out that using only two or three rounds of feedback provides near-optimal performance for systems of practical interest. This rule of thumb is valuable for practical communication systems.

Original languageEnglish (US)
Title of host publication43rd Annual Allerton Conference on Communication, Control and Computing 2005
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages1217-1226
Number of pages10
Volume3
ISBN (Print)9781604234916
StatePublished - 2005
Event43rd Annual Allerton Conference on Communication, Control and Computing 2005 - Monticello, United States
Duration: Sep 28 2005Sep 30 2005

Other

Other43rd Annual Allerton Conference on Communication, Control and Computing 2005
CountryUnited States
CityMonticello
Period9/28/059/30/05

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Variable-rate coding with feedback for universal communication systems'. Together they form a unique fingerprint.

Cite this