Delay, feedback, and the price of ignorance

SPEAKER: Dr. Anant Sahai, UC BerkeleyABSTRACT: 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.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 these cases gives Shannon's otherwise cryptic comment a precise interpretation.These results suggest that the traditional information theoretic recommendation of using messages as big as possible is flawed as far as architectural guidance is concerned. When encoders are not ignorant, messages should be as *small* as possible while avoid integer effects, and queueing ideas should be employed to do appropriate flow control, even when facing hard end-to-end latency constraints.BIO: Anant Sahai received the B.S. degree in EECS in 1994 from U.C. Berkeley, and both his M.S. and Ph.D. degrees in EECS from the Massachusetts Institute of Technology, in 1996 and 2001, respectively. In 2001, he developed adaptive signal processing algorithms for software radio GPS at the startup Enuvis in South San Francisco. He joined the EECS department at Berkeley as an Assistant Professor in 2002. His current research interests are in information theory and wireless communication, particularly the area of opportunistic spectrum reuse by cognitive radios.Host: Professor Urbashi Mitra, ubli@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - -248

Audiences: Everyone Is Invited

Contact: Mayumi Thrasher