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

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

4 Zitate (Scopus)

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.

OriginalspracheEnglisch
Titel2020 54th Annual Conference on Information Sciences and Systems, CISS 2020
Herausgeber (Verlag)Institute of Electrical and Electronics Engineers Inc.
ISBN (elektronisch)9781728140841
DOIs
PublikationsstatusVeröffentlicht - März 2020
Veranstaltung54th Annual Conference on Information Sciences and Systems, CISS 2020 - Princeton, USA/Vereinigte Staaten
Dauer: 18 März 202020 März 2020

Publikationsreihe

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

Konferenz

Konferenz54th Annual Conference on Information Sciences and Systems, CISS 2020
Land/GebietUSA/Vereinigte Staaten
OrtPrinceton
Zeitraum18/03/2020/03/20

Fingerprint

Untersuchen Sie die Forschungsthemen von „On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren