On the Algorithmic Computability of Achievability and Converse: ϵ-Capacity of Compound Channels and Asymptotic Bounds of Error-Correcting Codes

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

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

Abstract

A coding theorem consists of two parts: achievability and converse which establish lower and upper bounds on the capacity. This paper analyzes these bounds from a fundamental, algorithmic point of view by studying whether or not such bounds can be computed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. To this end, computable continuous functions are studied and properties of computable sequences of such functions are identified. Subsequently, these findings are exemplarily applied to two different open problems. The first one is the ϵ-capacity of compound channels which is unknown to date. It is studied whether or not the ϵ-capacity can be algorithmically computed and it is shown that there is no computable characterization of the difference between computable upper and lower bounds possible. Thus, computable sharp lower and upper bounds on the ϵ-capacity of computable compound channels cannot exist. The crucial consequence is that the ϵ-capacity cannot be characterized by a finite-letter entropic expression. The second application involves asymptotic bounds for error-correcting codes which is a long-standing open problem in coding theory. Only lower and upper bounds are known which are not sharp. It is conjectured that the asymptotic bound is indeed a non-computable function which would then imply with the previous findings that it is impossible to find computable lower and upper bounds that are asymptotically tight.

Original languageEnglish (US)
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2008-2013
Number of pages6
ISBN (Electronic)9781728164328
DOIs
StatePublished - Jun 2020
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States
Duration: Jul 21 2020Jul 26 2020

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2020-June
ISSN (Print)2157-8095

Conference

Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
Country/TerritoryUnited States
CityLos Angeles
Period7/21/207/26/20

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the Algorithmic Computability of Achievability and Converse: ϵ-Capacity of Compound Channels and Asymptotic Bounds of Error-Correcting Codes'. Together they form a unique fingerprint.

Cite this