Coding for Non-IID Sources and Channels: Entropic Approximations and a Question of Ahlswede

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

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

3 Scopus citations

Abstract

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.

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

Cite this

Boche, H., Schaefer, R. F., & Poor, H. V. (2019). Coding for Non-IID Sources and Channels: Entropic Approximations and a Question of Ahlswede. In 2019 IEEE Information Theory Workshop, ITW 2019 [8989316] (2019 IEEE Information Theory Workshop, ITW 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITW44776.2019.8989316