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

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

10 Zitate (Scopus)

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.

OriginalspracheEnglisch
Titel2019 IEEE Information Theory Workshop, ITW 2019
Herausgeber (Verlag)Institute of Electrical and Electronics Engineers Inc.
ISBN (elektronisch)9781538669006
DOIs
PublikationsstatusVeröffentlicht - Aug. 2019
Veranstaltung2019 IEEE Information Theory Workshop, ITW 2019 - Visby, Schweden
Dauer: 25 Aug. 201928 Aug. 2019

Publikationsreihe

Name2019 IEEE Information Theory Workshop, ITW 2019

Konferenz

Konferenz2019 IEEE Information Theory Workshop, ITW 2019
Land/GebietSchweden
OrtVisby
Zeitraum25/08/1928/08/19

Fingerprint

Untersuchen Sie die Forschungsthemen von „Coding for Non-IID Sources and Channels: Entropic Approximations and a Question of Ahlswede“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren