Moderate Deviation Asymptotics for Variable-Length Codes with Feedback

Abstract

We consider data transmission across discrete memoryless channels (DMCs) using variable-length codes with feedback. We consider the family of such codes whose rates are ${\rho }_N$ below the channel capacity $C$, where ${\rho }_N$ is a positive sequence that tends to zero slower than the reciprocal of the square root of the expectation of the (random) blocklength $N$. This is known as the moderate deviations regime and we establish the optimal moderate deviations constant. We show that in this scenario, the error probability decays sub-exponentially with speed $\exp (-(B/C)N{\rho }_N)$, where $B$ is the maximum relative entropy between output distributions of the DMC.

arXiv comment30 pages; No figures. Revision submitted to the IEEE Transactions on Information Theory