A Bound on the Reliability of Block Coding with Feedback

Coding with feedback has been considered by a number of authors. 1,2, 3 , 4 , 5 , 6 principally because of the advantage it is expected to enjoy in rate, reliability, and equipment costs over coding without feedback. Some early feedback results were obtained by Shannon, who showed that channel capacity of a discrete memoryless channel (DMC) cannot be increased using feedback1 and established that the sphere-packing (lower bound7,8) to the probability of error without feedback applies to block coding with feedback on the DMC uniform at the input (the sets of transition probabilities from each channel input letter are identical except for permutations7). He also conjectured that a spherepacking bound applies to block coding with feedback on all discrete, memoryless channels.2 (A conjecture supported recently by Berlekamp.9) It has been shown that the exponent on the sphere-packing bound agrees with the no-feedback, random-code exponent at rates above the critical rate RCIit ,7,10 so that feedback cannot increase the reliability of block coding at rates gieater than RCT;t. Below Rcrit, Berlekamp first showed that feedback will improve the reliability of block coding.3 He showed that the zero rate exponent of the probability of error with block codes on the binary symmetric channel (BSC) and certain other binary channels having particular symmetries is larger with feedback than the 967