TY - GEN
T1 - On the Structure of the Capacity Formula for General Finite State Channels with Applications
AU - Boche, Holger
AU - Schaefer, Rafael F.
AU - Poor, H. Vincent
PY - 2019/8
Y1 - 2019/8
N2 - Finite state channels (FSCs) model discrete channels with memory where the channel output depends on the channel input and the actual channel state. The capacity of general FSCs has been established as the limit of a sequence of multi-letter expressions; a corresponding finite-letter characterization is not known to date. In this paper, it is shown that it is indeed not possible to find such a finite-letter entropic characterization for FSCs whose input, output, and state alphabets satisfy |X| ≥ 2, |Y| ≥2, and |S| ≥2. Further, the algorithmic computability of the capacity of FSCs is studied. To account for this, the concept of a Turing machine is adopted as it provides fundamental performance limits for today's digital computers. It is shown that the capacity of a FSC is not Banach-Mazur computable and therewith not Turing computable for |X| ≥ 2, |Y| ≥ 2, |S| ≥ 2.
AB - Finite state channels (FSCs) model discrete channels with memory where the channel output depends on the channel input and the actual channel state. The capacity of general FSCs has been established as the limit of a sequence of multi-letter expressions; a corresponding finite-letter characterization is not known to date. In this paper, it is shown that it is indeed not possible to find such a finite-letter entropic characterization for FSCs whose input, output, and state alphabets satisfy |X| ≥ 2, |Y| ≥2, and |S| ≥2. Further, the algorithmic computability of the capacity of FSCs is studied. To account for this, the concept of a Turing machine is adopted as it provides fundamental performance limits for today's digital computers. It is shown that the capacity of a FSC is not Banach-Mazur computable and therewith not Turing computable for |X| ≥ 2, |Y| ≥ 2, |S| ≥ 2.
UR - http://www.scopus.com/inward/record.url?scp=85081107316&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081107316&partnerID=8YFLogxK
U2 - 10.1109/ITW44776.2019.8989035
DO - 10.1109/ITW44776.2019.8989035
M3 - Conference contribution
T3 - 2019 IEEE Information Theory Workshop, ITW 2019
BT - 2019 IEEE Information Theory Workshop, ITW 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE Information Theory Workshop, ITW 2019
Y2 - 25 August 2019 through 28 August 2019
ER -