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

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

doi:10.1109/ITW44776.2019.8989035

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 proceeding › Conference contribution

5 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 language	English (US)
Title of host publication	2019 IEEE Information Theory Workshop, ITW 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781538669006
DOIs	https://doi.org/10.1109/ITW44776.2019.8989035
State	Published - Aug 2019
Event	2019 IEEE Information Theory Workshop, ITW 2019 - Visby, Sweden Duration: Aug 25 2019 → Aug 28 2019

Publication series

Name	2019 IEEE Information Theory Workshop, ITW 2019

Conference

Conference	2019 IEEE Information Theory Workshop, ITW 2019
Country/Territory	Sweden
City	Visby
Period	8/25/19 → 8/28/19

All Science Journal Classification (ASJC) codes

Software
Computational Theory and Mathematics
Computer Networks and Communications
Information Systems

Access to Document

10.1109/ITW44776.2019.8989035

Cite this

@inproceedings{10e935609d724fceb90ecfaabbe755c8,

title = "On the Structure of the Capacity Formula for General Finite State Channels with Applications",

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.",

author = "Holger Boche and Schaefer, {Rafael F.} and Poor, {H. Vincent}",

year = "2019",

month = aug,

doi = "10.1109/ITW44776.2019.8989035",

language = "English (US)",

series = "2019 IEEE Information Theory Workshop, ITW 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2019 IEEE Information Theory Workshop, ITW 2019",

address = "United States",

note = "2019 IEEE Information Theory Workshop, ITW 2019 ; Conference date: 25-08-2019 Through 28-08-2019",

}

Boche, H, Schaefer, RF & Poor, HV 2019, On the Structure of the Capacity Formula for General Finite State Channels with Applications. in 2019 IEEE Information Theory Workshop, ITW 2019., 8989035, 2019 IEEE Information Theory Workshop, ITW 2019, Institute of Electrical and Electronics Engineers Inc., 2019 IEEE Information Theory Workshop, ITW 2019, Visby, Sweden, 8/25/19. https://doi.org/10.1109/ITW44776.2019.8989035

On the Structure of the Capacity Formula for General Finite State Channels with Applications. / Boche, Holger; Schaefer, Rafael F.; Poor, H. Vincent.
2019 IEEE Information Theory Workshop, ITW 2019. Institute of Electrical and Electronics Engineers Inc., 2019. 8989035 (2019 IEEE Information Theory Workshop, ITW 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

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

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this