CDS/CS: Delay, Feedback, and the Price of Ignorance

Anant Sahai, Electrical Engineering and Computer Science, Berkeley University

In 1959, Shannon made a profound comment:

"[The duality between source and channel coding] can be pursued further and is related to a duality between past and future and the notions of control and knowledge. Thus we may have knowledge of the past and cannot control it; we may control the future but have no knowledge of it."

This comment cannot be understood in the traditional block-code setting and as a result, has remained entirely mysterious. To understand it, we must step back and consider end-to-end delay, since delay is what fundamentally allows the exploitation of the laws of large numbers to give reliability. Delay is also important when considering automatic control over noisy channels and the relevant results will be reviewed briefly.

In channel coding, we show that while feedback often does not improve fixed block-length reliability functions, it can significantly improve  the reliability with respect to fixed delay! (Contrary to a "theorem" by Pinsker claiming otherwise.) A new bound, that we call the "focusing bound," allows us to calculate the limit of what is possible when the encoder is not ignorant of the channel's past behavior.

In source coding, the price of ignorance is demonstrated by considering what happens when receiver side-information is withheld from the transmitter. Block-codes perform equally poorly, but nonblock codes can use side-information to dramatically improve the fixed-delay error exponent. Furthermore, a closer look at the dominant error events for all these cases gives Shannon's otherwise cryptic comment a precise interpretation.

These results suggest that the traditional information theoretic recommendation of aggregating messages into very big blocks is flawed as architectural guidance. When encoders are not ignorant, queuing and variable-length ideas should be employed to do appropriate flow control, even when facing hard end-to-end latency constraints. In a fundamental sense, queues have a large-deviation performance that is superior to blocks.

Hosted by: Henrik Sandberg (CDS) and Jean-Charles Delvenne (CS)