A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback

Abstract

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.