Channel coding with feedback: Two new perspectives

Speaker: Yucel Altug
Electrical Engineering, Princeton University

Venue: Packard 101
Time: 4:15 pm to 5:15 pm
Date: Thursday, November 19, 2015


The success of information theory in dealing with systems that incorporate feedback is limited. Even for the basic setting of fixed-length coding over a discrete memoryless channel (DMC), the effect of feedback on the fundamental limits regarding refined performance measures is not known in general and the common conjecture is that feedback does not improve any of them. However, feedback has been shown to dramatically improve these fundamental limits if one allows the decoding time to be random and impose an average delay constraint. As a result, conventional wisdom is that to gain significant improvements in the aforementioned fundamental limits, one should use variable-length codes.

This talk will question these common beliefs on the effect of feedback in the fixed and variable-length paradigms. In the first part, I will show that feedback can improve the speed of convergence to the capacity for a particular class of DMCs, which disproves the above common conjecture. More importantly, this result suggests that characterization of channels for which feedback improves a fundamental limit is a promising research direction. As a demonstration, I will consider coding over a DMC subject to a cost constraint when there is no restriction on the number of channel uses, and prove a necessary and sufficient condition for feedback to improve the speed of convergence to the capacity per unit cost. In the second part, I will show that the remarkable improvements due to feedback in variable-length paradigm crucially depend on the average delay constraint, which, unfortunately, is lax for various applications. Specifically, I will show that these improvements cease to exist under more stringent delay guarantees, such as probabilistic or risk-averse.

Speaker Bio

Yucel Altug is a postdoctoral research associate in the Electrical Engineering Department at Princeton University. He received the B.S. and M.S. degrees in Electrical and Electronics Engineering from Bogazici University, Turkey, in 2006 and 2008, respectively and the Ph.D. degree in Electrical and Computer Engineering from Cornell University, in 2013. He has received the ECE Director's Ph.D. Thesis Research Award from Cornell University School of Electrical and Computer Engineering.