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.
In some communication problems, it is a good assumption that the channel consists of an additive white Gaussian noise forward link and an essentially noiseless feedback link. In this paper, we study channels where no bandwidth constraint is placed on the transmitted signals. Such channels arise in space communications. It is known that the availability of the feedback link cannot increase the channel capacity of the noisy forward link, but it can considerably reduce the coding effort required to achieve a given level of performance. We present a coding scheme that exploits the feedback to achieve considerable reductions in coding and decoding complexity and delay over what would be needed for comparable performance with the best known (simplex) codes for the one-way channel. Our scheme, which was motivated by the Robbins-Monro stochastic approximation technique, can also be used over channels where the additive noise is not Gaussian but is still independent from instant to instant. An extension of the scheme for channels with limited signal bandwidth is presented in a companion paper (Part II). The presence of a feedback channel makes possible a variety of sequential transmission procedures, each of which can be classified as either a block-transmission or a continuous-transmission scheme according to the way in which information is encoded for transmission over a noisy forward channel. A sequential continuous-transmission system employing a binary symmetric forward channel (but which is suitable for use with any discrete memoryless forward channel) and a noiseless feedback channel is described. Its error exponent is shown to be substantially greater than the optimum block-code error exponent at all transmission rates less than channel capacity. The average value and the first-order probability distribution of the effective constraint length, found by simulating the system on an IBM 709 computer, are also given. In Part I of this paper, we presented a scheme for effectively exploiting a noiseless feedback link associated with an additive white Gaussian noise channel with no signal bandwidth constraints. We now extend the scheme for this channel, which we shall call the wideband (WB) scheme, to a band-limited (BL) channel with signal bandwidth restricted to (- W, W) . Our feedback scheme achieves the well-known channel capacity, C = W (1 +P_ u,v N_ 0 W) , for this system and, in fact, is apparently the first deterministic procedure for doing this. We evaluate the fairly simple exact error probability for our scheme and find that it provides considerable improvements over the best-known results (which are lower bounds on the performance of sphere-packed codes) for the one-way channel. We also study the degradation in performance of our scheme when there is noise in the feedback link.