On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

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

2 Scopus citations

Abstract

This paper considers the compound channel where the actual channel realization is unknown. It is only known that it comes from a given uncertainty set and that it remains constant throughout the entire duration of transmission. The capacity has been established providing a complete characterization and a simple formula for the computation of the maximal transmission rate. This is no longer the case for the ϵ-capacity of a compound channel, which characterizes the maximum transmission rate when a non-vanishing average error ϵ is tolerated. In this case, the compound channel is known to have no strong converse under the average error criterion and, therewith, the ϵ-capacity may be larger than the capacity for a vanishing error. As the capacity of compound channels is unknown, Ahlswede raised the question of whether or not there exists a (simple) recursive formula for it. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such formulas can be found algorithmically in principle (without putting any constraints on the computational complexity of the algorithms). To this end, it is shown that there exists no algorithm or Turing machine that takes the compound channel and error as inputs and computes the corresponding ϵ-capacity. Accordingly, there is also no recursive formula for the ϵ-capacity providing a negative answer to Ahlswede's initial question. The developed framework is subsequently applied to the question of the existence of a strong converse, the existence of an optimal second order coding rate, and whether or not the pessimistic and optimistic definitions of the ϵ-capacity coincide. Cast as decision problems, it is shown that these questions are undecidable and therewith impossible to be answered algorithmically.

Original languageEnglish (US)
Title of host publication2020 54th Annual Conference on Information Sciences and Systems, CISS 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728140841
DOIs
StatePublished - Mar 2020
Event54th Annual Conference on Information Sciences and Systems, CISS 2020 - Princeton, United States
Duration: Mar 18 2020Mar 20 2020

Publication series

Name2020 54th Annual Conference on Information Sciences and Systems, CISS 2020

Conference

Conference54th Annual Conference on Information Sciences and Systems, CISS 2020
Country/TerritoryUnited States
CityPrinceton
Period3/18/203/20/20

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing
  • Information Systems and Management
  • Safety, Risk, Reliability and Quality
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate'. Together they form a unique fingerprint.

Cite this