The posterior matching scheme, for feedback encoding of a message point lying on the unit interval over memoryless channels, maximizes mutual information for an arbitrary number of channel uses. However, it in general does not always achieve any positive rate; so far, elaborate analyses have been required to show that it achieves any positive rate below capacity. More recent efforts have introduced a random "dither" shared by the encoder and decoder to the problem formulation, to simplify analyses and guarantee that the randomized scheme achieves any rate below capacity. Motivated by applications (e.g. human-computer interfaces) where (a) common randomness shared by the encoder and decoder may not be feasible and (b) the message point lies in a higher dimensional space, we focus here on the original formulation without common randomness, and use optimal transport theory to generalize the scheme for a message point in a higher dimensional space. By defining a stricter, almost sure, notion of message decoding, we use classical probabilistic techniques (e.g. change of measure and martingale convergence) to establish succinct necessary and sufficient conditions on when the message point can be recovered from infinite observations: Birkhoff ergodicity of a random process sequentially generated by the encoder. We also show a surprising "all or nothing" result: the same ergodicity condition is necessary and sufficient to achieve any rate below capacity. We provide applications of this message point framework in human-computer interfaces and multi-antenna communications.
Although the PM scheme maximizes mutual information, in some situations the posterior @math never converges to a point mass at @math , implying that no positive rate is achievable. [Example 11] Shayevitz2011pm shows that the breakdown of reliability or achieving capacity is not solely a property of the channel: for the same channel, variants of the original scheme involving measure-preserving transformations of the input can ameliorate these issues. Sufficient conditions for reliability [Lemma 13] Shayevitz2011pm and achieving capacity [Theorem 4] Shayevitz2011pm were originally established in @cite_57 , involving regularity' and uniformly bounded max-to-min ratios assumptions along with elaborate fix-point analysis. This has led researchers to slightly alter the problem formulation and encoding schemes to more simply confirm guarantees on subsequent performance. Li and El Gamal @cite_27 considered a non-sequential, fixed-rate, fixed-block-length feedback coding scheme for discrete memoryless channels (DMCs) when @math and introduced a random dither known to the encoder and decoder to provide a simple proof of achieving capacity.
@cite_57 @cite_27
2011914761 1975231568
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. Existing fixed-length feedback communication schemes are either specialized to particular channels (Schalkwijk–Kailath, Horstein), or apply to general channels but either have high coding complexity (block feedback schemes) or are difficult to analyze (posterior matching). This paper introduces a new fixed-length feedback coding scheme which achieves the capacity for all discrete memoryless channels, has an error exponent that approaches the sphere packing bound as the rate approaches the capacity, and has @math coding complexity. These benefits are achieved by judiciously combining features from previous schemes with new randomization technique and encoding decoding rule. These new features make the analysis of the error probability for the new scheme easier than for posterior matching.