TY - GEN

T1 - Coding for Non-IID Sources and Channels

T2 - 2019 IEEE Information Theory Workshop, ITW 2019

AU - Boche, Holger

AU - Schaefer, Rafael F.

AU - Poor, H. Vincent

PY - 2019/8

Y1 - 2019/8

N2 - The theory of Verdú and Han provides a powerful framework to analyze and study general non-independent and identically distributed (non-i.i. d.) sources and channels. Already for simple non-i.i. d. sources and channels, this framework can result in complicated general capacity formulas. Ahlswede asked in his Shannon lecture if these general capacity formulas can be effectively, i.e., algorithmically, computed. In this paper, it is shown that there exist computable non-i.i. d. sources and channels, for which the capacity is a non-computable number. Even worse, it is shown that there are non-i.i. d. sources and channels for which the capacity is a computable number, i.e., the limit of the corresponding sequence of multi-letter capacity expressions is computable, but the convergence of this sequence is not effective. This answers Ahlswede's question in a strong form, since in this case, the multi-letter capacity expressions for these sources and channels cannot be used to approximate the optimal performance algorithmically.

AB - The theory of Verdú and Han provides a powerful framework to analyze and study general non-independent and identically distributed (non-i.i. d.) sources and channels. Already for simple non-i.i. d. sources and channels, this framework can result in complicated general capacity formulas. Ahlswede asked in his Shannon lecture if these general capacity formulas can be effectively, i.e., algorithmically, computed. In this paper, it is shown that there exist computable non-i.i. d. sources and channels, for which the capacity is a non-computable number. Even worse, it is shown that there are non-i.i. d. sources and channels for which the capacity is a computable number, i.e., the limit of the corresponding sequence of multi-letter capacity expressions is computable, but the convergence of this sequence is not effective. This answers Ahlswede's question in a strong form, since in this case, the multi-letter capacity expressions for these sources and channels cannot be used to approximate the optimal performance algorithmically.

UR - http://www.scopus.com/inward/record.url?scp=85081106389&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081106389&partnerID=8YFLogxK

U2 - 10.1109/ITW44776.2019.8989316

DO - 10.1109/ITW44776.2019.8989316

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.

Y2 - 25 August 2019 through 28 August 2019

ER -