On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate
On the ϵ-Capacity of Finite Compound Channels with Applications to the Strong Converse and Second Order Coding Rate
复制标题
有限复合通道的ε容量及其在强逆和二阶编码率中的应用
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
H. Poor
中科院分区：
文献类型：
--
作者：
H. Boche;Rafael F. Schaefer;H. Poor
本文研究了实际信道实现未知的复合信道。我们只知道它来自一个给定的不确定性集合，并且在整个传输期间保持不变。容量已经建立提供了一个完整的表征和一个简单的公式计算的最大传输速率。这不再是复合信道的带宽容量的情况，其特征在于当容忍非零平均误差时的最大传输速率。在这种情况下，已知复合信道在平均误差准则下不具有强匡威，并且因此，对于消失误差的容量可能大于容量。由于复合通道的容量是未知的，Ahlswede提出的问题，是否存在一个（简单的）递归公式，本文探讨了这个问题，从一个基本的，算法的角度来看，通过研究是否可以找到这样的公式，在原则上算法（不把任何限制的算法的计算复杂性）。为此，它表明，不存在算法或图灵机，采取的复合通道和错误作为输入，并计算相应的可扩展性。因此，也没有递归公式的能力提供一个否定的答案Ahlswede的最初的问题。开发的框架随后被应用到一个强匡威的存在，存在一个最佳的二阶编码率的问题，以及是否悲观和乐观的定义的可伸缩性容量相吻合。投决策问题，它表明，这些问题是不可判定的，从而不可能得到回答的算法。
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.
影响因子：
20.6
作者：
Rafael F. Schaefer;H. Boche;Vincent Poor
通讯作者：
Rafael F. Schaefer;H. Boche;Vincent Poor