Shannon's two-way channel problem has attracted the attention of information theorists for many years. In a classic paper Shannon gave both an outer and an inner bound to the capacity region of the two-way channel. Schalkwijk recently obtained an improvement to the inner bound for the Blackwell multiplying channel (BMC). We present the first improvements on Shannon's outer bound. Calculation shows that our results are close to optimum when applied to the BMC.

Shannon showed that for the binary multiplying channel (BMC) his inner and outer hounds to the capacity region differ. Schalkwijk gave a simple coding strategy that yields rate pairs(R_{1}, R_{2})outside the Shannon inner bound region. For the case of equal rates in both directions this strategy achievesR_{1} = R_{2} = 0.6 1914beyond Shannon's inner bound rateR_{1} = R_{2} = 0.61695. In this correspondence it is shown that using a result by Slepian and Wolf one can bootstrap the Schalkwijk strategy to find an even larger achievable rate region. In fact, symmetricR_{1} = R_{2}operation of the BMC now yields a common rateR_{1} = R_{2} = 0.63056.

Blackwell's binary multiplying channel is well known as an example of a two-way channel for which Shannon's inner and outer bounds to the capacity region differ. A deterministic coding scheme is given which outperforms the inner region for this channel. Dueck had earlier obtained an analogous result for another type of two-way channel.

Maximum likelihood (ML) decoding of short constraint length convolutional codes became feasible with the invention of the Viterbi decoder. Several authors have since upper bounded the performance of ML decoders. A method to calculate the event error probability of an ML decoder for convolutional codes is described.

The classical Viterbi decoder recursively finds the trellis path (code word) closest to the received data. Given the received data, the syndrome decoder first forms a syndrome instead. Having found the syndrome, that only depends on the channel noise, a recursive algorithm like Viterbi's determines the noise sequence of minimum Hamming weight that can he a possible cause of this syndrome. Given the estimate of the noise sequence, one derives an estimate of the original data sequence. The bit error probability of the syndrome decoder is no different from that of the classical Viterbi decoder. However, for short constraint length codes the syndrome decoder can be implemented using a read-only memory (ROM), thus obtaining a considerable saving in hardware. The syndrome decoder has at most\frac{3}{4}as many path registers as does the Viterbi decoder. There exist convolutional codes for which the number of path registers can be even further reduced.

In this paper we describe a coding strategy for binary duplex channels (BDC's) that essentially matches the performance of a system with two identical binary forward channels using a systematic rate-\frac{1}{2}convolutional code on each of these channels. In other words, our coding strategy achieves the same effect as would the turning around of the feedback channel.

No abstract.

Upper bounds to the capacity of band-limited Gaussianmth-order autoregressive channels with feedback and average energy constraintEare derived. These are the only known hounds on one- and two-way autoregressive channels of order greater than one. They are the tightest known for the first-order case. In this case let\alpha_1be the regression coefficient,\sigma^2the innovation variance,Nthe number of channel iterations per source symbol, ande = E/N; then the first-order capacityC^1is bounded by \begin{equation} C^1 \leq \begin{cases} \frac{1}{2} \ln [\frac{e}{\sigma^2}(1+ \mid \alpha_1 \mid ) ^ 2 +1], & \frac{e}{\sigma^2} \leq \frac{1}{1- \alpha_1^2} \\ \frac{1}{2} \ln [\frac{e}{\sigma^2} + \frac{2\mid \alpha_1 \mid}{\sqrt{1-\alpha_1^2}} \sqrt{\frac{e}{\simga^2}} + \frac{1}{1-\alpha_1^2}], & \text{elsewhere}.\\ \end{cases} \end{equation} This is equal to capacity without feedback for very low and very highe/\sigma^2and is less than twice this one-way capacity everywhere.

The error probability for a class of binary recursive feedback strategies is evaluated. An exact analysis is given for both a nonsequential and a sequential decision strategy. We obtain the interesting result that even for the nonsequential receiver the error probability vanishes exponentially fast at channel capacity. A similar result had been previously obtained by Horstein for the sequential receiver, but was believed to be a consequence of the sequential nature of his decision strategy. For rates below capacity our feedback strategies have two error exponents, i.e., a lower error exponentE^- (R)and an upper error exponentE^+ (R). The lower error exponentE^- (R)exhibits an anomalous behavior in thatE^- (R)increases monotonically fromE^- (0) = 0toE^- (C) = E(C)as the rateRincreases from 0 to capacity.

We derive a simple algorithm for the ranking of binary sequences of lengthnand weightw. This algorithm is then used for source encoding a memoryless binary source that generates O's with probabilityqand l's with probabilityp = 1 - q.

A class of simple feedback strategies is developed. The fixed-length codewords can be described by an interesting sequence of trees. The decoder scans the received block in the reverse direction, starting at the most recent bit. As this scan progresses, a certain pair of characteristic bit patterns are replaced by the digits 0 or 1, respectively. For certain values of the information rateR, this class of strategies corrects the largest error fraction possible.

The error exponent for sequential signaling over the additive-Gaussian-white-noise channel subject to a peak power constraint is derived. This exponent is maximum under the assumption that information is transmitted in blocks.

We considerMsignals in aD-dimensional signal space. TheseMsignals are used to communicate over an additive Gaussian white noise channel. It is shown that if a noiseless feedback channel is available one could use this feedback channel to inform the transmitter of the location of the center of gravity of the signal structure and thus obtain a very efficient signaling scheme. Each signal point is assigned a mass proportional to its posterior probability at the particular instant. The center of gravity is used by the transmitter as a new origin for the signal space. It is shown that some previously considered coding schemes for channels with feedback are particular cases of center-of-gravity feedback. The probability of error decreases as a double exponential function of the coding delay as opposed to an exponential decrease for one-way systems. The effect of noise in the feedback path is briefly considered.

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 {\em 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 \ln (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.

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).