TY - GEN
T1 - On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate
AU - Boche, Holger
AU - Schaefer, Rafael F.
AU - Vincent Poor, H.
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/3
Y1 - 2020/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85085257285&partnerID=8YFLogxK
U2 - 10.1109/CISS48834.2020.1570617403
DO - 10.1109/CISS48834.2020.1570617403
M3 - Conference contribution
AN - SCOPUS:85085257285
T3 - 2020 54th Annual Conference on Information Sciences and Systems, CISS 2020
BT - 2020 54th Annual Conference on Information Sciences and Systems, CISS 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 54th Annual Conference on Information Sciences and Systems, CISS 2020
Y2 - 18 March 2020 through 20 March 2020
ER -