论文标题
具有反馈的有限状态通道的能力：算法和优化理论特性
Capacity of Finite State Channels with Feedback: Algorithmic and Optimization Theoretic Properties
论文作者
论文摘要
具有反馈的有限状态通道（FSC）的容量已显示为一系列多字母表达式的限制。尽管做了很多努力，但迄今为止，封闭形式的单个字母容量表征尚不清楚。在本文中，从基本算法的角度研究了反馈能力，通过解决了是否可以通过算法计算能力的问题来研究反馈能力。为此，使用了图灵机的概念，该概念提供了数字计算机的基本性能限制。结果表明，FSC的反馈能力不可计算Banach-Mazur，因此不能计算Borel-Turing。结果，结果表明，可实现性或匡威不是可以计算的Banach-Mazur，这意味着有可计算的FSC，无法找到可计算的紧密上限和下限。此外，结果表明，反馈能力不能表征为熵量有限字母公式的最大化。
The capacity of finite state channels (FSCs) with feedback has been shown to be a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization is unknown to date. In this paper, the feedback capacity is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that the feedback capacity of FSCs is not Banach-Mazur computable and therefore not Borel-Turing computable. As a consequence, it is shown that either achievability or converse is not Banach-Mazur computable, which means that there are computable FSCs for which it is impossible to find computable tight upper and lower bounds. Furthermore, it is shown that the feedback capacity cannot be characterized as the maximization of a finite-letter formula of entropic quantities.
