Analytical Properties of Shannon’s Capacity of Arbitrarily Varying Channels under List Decoding: Super-Additivity and Discontinuity Behavior

H. Boche, R. F. Schaefer, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The common wisdom is that the capacity of parallel channels is usually additive. This was also conjectured by Shannon for the zero-error capacity function, which was later disproved by constructing explicit counterexamples demonstrating the zero-error capacity to be super-additive. Despite these explicit examples for the zero-error capacity, there is surprisingly little known for nontrivial channels. This paper addresses this question for the arbitrarily varying channel (AVC) under list decoding by developing a complete theory. The list capacity function is studied and shown to be discontinuous, and the corresponding discontinuity points are characterized for all possible list sizes. For parallel AVCs it is then shown that the list capacity is super-additive, implying that joint encoding and decoding for two parallel AVCs can yield a larger list capacity than independent processing of both channels. This discrepancy is shown to be arbitrarily large. Furthermore, the developed theory is applied to the arbitrarily varying wiretap channel to address the scenario of secure communication over AVCs.

Original languageEnglish (US)
Pages (from-to)199-228
Number of pages30
JournalProblems of Information Transmission
Volume54
Issue number3
DOIs
StatePublished - Jul 1 2018

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Analytical Properties of Shannon’s Capacity of Arbitrarily Varying Channels under List Decoding: Super-Additivity and Discontinuity Behavior'. Together they form a unique fingerprint.

Cite this