Optimal Feedback Communication Via Posterior Matching

DOI10.1109/TIT.2011.2104992zbMATH Open1366.94260arXiv0909.4828MaRDI QIDQ5281015FDOQ5281015

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper we introduce a fundamental principle for optimal communication over general memoryless channels in the presence of noiseless feedback, termed posterior matching. Using this principle, we devise a (simple, sequential) generic feedback transmission scheme suitable for a large class of memoryless channels and input distributions, achieving any rate below the corresponding mutual information. This provides a unified framework for optimal feedback communication in which the Horstein scheme (BSC) and the Schalkwijk-Kailath scheme (AWGN channel) are special cases. Thus, as a corollary, we prove that the Horstein scheme indeed attains the BSC capacity, settling a longstanding conjecture. We further provide closed form expressions for the error probability of the scheme over a range of rates, and derive the achievable rates in a mismatch setting where the scheme is designed according to the wrong channel model. Several illustrative examples of the posterior matching scheme for specific channels are given, and the corresponding error probability expressions are evaluated. The proof techniques employed utilize novel relations between information rates and contraction properties of iterated function systems.

Full work available at URL: https://arxiv.org/abs/0909.4828

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Coding theorems (Shannon theory) (94A24) Channel models (including quantum) in information and communication theory (94A40)

Cited In (1)

Gaussian lower bound for the information bottleneck limit

This page was built for publication: Optimal Feedback Communication Via Posterior Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281015)