On the Structure of the Capacity Formula for General Finite State Channels with Applications

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2019 IEEE Information Theory Workshop, ITW 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538669006
DOIs
StatePublished - Aug 2019
Event2019 IEEE Information Theory Workshop, ITW 2019 - Visby, Sweden
Duration: Aug 25 2019Aug 28 2019

Publication series

Name2019 IEEE Information Theory Workshop, ITW 2019

Conference

Conference2019 IEEE Information Theory Workshop, ITW 2019
CountrySweden
CityVisby
Period8/25/198/28/19

All Science Journal Classification (ASJC) codes

  • Software
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Information Systems

Fingerprint Dive into the research topics of 'On the Structure of the Capacity Formula for General Finite State Channels with Applications'. Together they form a unique fingerprint.

Cite this