Variable-length Codes for Channels with Memory and Feedback: fundamental limits and practical transmission schemes

The reliability function of memoryless channels with noiseless feedback and variable-length coding was found to be a linear function of the average transmission rate in the classic work of Burnashev. This is a striking and fascinating result: it provides a simple closed form solution, unlike the case of apparently simpler discrete memoryless channels and the discrete channels with memory and fixed-length coding, where the solution is not even known in its entirety. This surprising result demonstrates the analytical power of martingales. In this talk we consider channels with memory and noiseless feedback and generalize Burnashev's analysis in two directions: 1) By making connections to the problem of sequential binary hypothesis testing and Markov Decision Processes, we provide an upper bound for the reliability function. 2) Taking hints from the above bound, we discuss a specific sequential transmission scheme, where both transmitter and receiver summarize their common information in two M-dimensional vectors (with M being the number of messages) and without the need for explicit codebooks. The analysis assumes the presence of some common randomness shared by the transmitter and receiver, and is based on the study of the multi-step drift of the log-likelihood ratio of the transmitted message posterior belief. We discuss a specific point in the analysis that is incomplete and present simulation results for the trapdoor, chemical, and other binary input/state/output unifilar channels confirming tight agreement with the upper bound.
Achilleas Anastasopoulos received the Diploma in Electrical Engineering from the National Technical University of Athens, Greece in 1993, and the M.S. and Ph.D. degrees in Electrical Engineering from University of Southern California in 1994 and 1999, respectively. He is currently an Associate Professor at the University of Michigan, Ann Arbor, Department of Electrical Engineering and Computer Science. His research interests lie in the general area of communication theory, with emphasis in channel coding, multi-user channels, as well as connections between multi-user communications and decentralized stochastic control.