This thesis is concerned with the use of block codes to transmit information over two-way communication systems which have a discrete memoryless, noisy channel in the forward direction and a reverse channel which is noiseless and undelayed and has unlimited capacity. It has been known that the capacity in the forward direction is not increased by the reverse channel. It has also been known that the probability of error approaches zero exponentially with increasing block length at any fixed rate less than capacity. For a region of rates between a critical rate and capacity it has been known that the exponent with which the probability of error approaches zero cannot be improved by the use of feedback, and there was some question whether the feedback channel could be made to serve any useful purpose at all, either to improve the probability of error or to decrease the complexity of the coding and decoding operations.
In view of these results, we focus on primary attention on low rate codes, including zero-rate codes whose block length approaches infinity while the number of codewords remains fixed. We succeed in obtaining several new and improved bounds on the probability of error for such codes, both within and without feedback.
We evaluate the zero-rate exponents for arbitrary one-way channels. This new general result leads to improved lower bounds on the probability of error at low rates, via techniques recently introduced by C. E. Shannon and R. G. Gallager. We evaluate the zero-rate exponent for large classes of feedback channels, including all binary-input channels which satisfy certain symmetry requirements. These results lead to strengthened bounds on the probability of error for channels with feedback. We find that at low rates it is possible to obtain substantially improved error probabilities with the use of feedback. Although our results may be invalidated if the feedback channel is noisy, we show that the results are not effected by a delay in the feedback channel unless the delay is comparable to the block length.
Several constructive feedback coding strategies are presented. Using elaborate inductive arguments, we derive a class of coding strategies which are asymptotically optimum for the binary symmetric channel with feedback over a large region of rates. It is felt that these strategies could be profitably applied to problems in the statistical design of experiments whenever the situation is such that successive experiments may be modified according to the results of previous ones. Most previous studies in the statistical design of experiments have not permitted such modificiations. By utilizing this “feedback”, we not only find that it is possible to achieve much smaller error probability, but we show how.
