A training based scheme for communicating over unknown channels with feedback

We consider a communication system with noiseless feedback where the channel is not known to the encoder or the decoder. The channel belongs to a known family of channels and remains constant over time. Using the noiseless feedback, the encoder can learn the channel over time and communicate at a rate equal to the capacity of the actual realization of the channel. Thus, not knowing the channel does not affect capacity. However, analyzing the error exponent (for variable length coding) is more challenging. Tchamkerten and Telatar (2006) showed that for certain families of channels, not knowing the channel does not change the error exponent; for other families, not knowing the channel results in a strict decrease in the error exponent. In general, the error exponent is not known. It is also known that simple training based schemes have poor error exponent behavior. In this paper, we show that a smart training based scheme can achieve an error exponent which is a multiplicative factor less than the error exponent for known channel. This shows that contrary to popular belief, smart training based schemes preserve the main advantage of feedback - an error exponent with non-zero slope at rates close to capacity.