TY - GEN
T1 - Capacity of Finite State Channels with Feedback
T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022
AU - Grigorescu, Andrea
AU - Boche, Holger
AU - Schaefer, Rafael F.
AU - Vincent Poor, H.
N1 - Funding Information:
This work of H. Boche was supported in part by the German Federal Ministry of Education and Research (BMBF) within the national initiative on 6G Communication Systems through the research hub 6G-life under Grant 16KISK002, within the national initiative on Post Shannon Communication (NewCom) under Grant 16KIS1003K, and the project Hardware Platforms and Computing Models for Neuromorphic Computing (NeuroCM) under Grant 16ME0442. It has further received funding by the German Research Foundation (DFG) within Germanys Excellence Strategy EXC-2092 390781972. This work of R. F. Schaefer was supported in part by the BMBF within NewCom under Grant 16KIS1004 and in part by the DFG under Grant SCHA 1944/6-1. This work of H. V. Poor was supported by the U.S. National Science Foundation under Grant CCF-1908398.
Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - The capacity of finite state channels (FSCs) with feedback has been expressed by a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization remains 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 also not Borel-Turing computable. As a consequence, it is shown that either achievability or converse (or both) is not Banach-Mazur computable, which means that there are 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.
AB - The capacity of finite state channels (FSCs) with feedback has been expressed by a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization remains 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 also not Borel-Turing computable. As a consequence, it is shown that either achievability or converse (or both) is not Banach-Mazur computable, which means that there are 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.
UR - http://www.scopus.com/inward/record.url?scp=85136292176&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85136292176&partnerID=8YFLogxK
U2 - 10.1109/ISIT50566.2022.9834817
DO - 10.1109/ISIT50566.2022.9834817
M3 - Conference contribution
AN - SCOPUS:85136292176
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 498
EP - 503
BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 26 June 2022 through 1 July 2022
ER -