Control, delay, and the nature of information

In traditional information theory, there are essentially two kinds of communication problems: those asymptotically equivalent to classical Shannon communication and those equivalent to the much harder problem of zero-error communication. The celebrated classical source-channel separation theorems tell us that for a large class of problems, hardness can be measured by a single number: the Shannon capacity required.

I will show how to include stabilization problems (control over noisy channels) into this picture and illustrate how these problems do not reduce to classical Shannon communication problems. Instead, stabilization problems are asymptotically equivalent to problems of anytime (delay-universal) communication with feedback. Surprisingly, this continues to hold even in many cases with non-nested information patterns. Problems of anytime communication have their hardness measured by a vector of numbers. In the simplest case (equivalent to scalar control), these numbers represent a (rate,reliability) pair. Anytime problems lie between the classical Shannon and zero-error problems in difficulty and we can use information theoretic tools to understand aspects of their structure.

The feedback anytime reliability function is related to the classical Gallager sense of reliability (error exponents), but I will show that it is in general different by providing an upper bound to it for general DMC's as well as evaluating it for certain specific channels. This difference prompts us to look more deeply into how feedback can increase reliability. While feedback does not generally improve high-rate fixed- length block-coding reliability functions, it can dramatically improve the reliability with respect to fixed-delays!

Anant Sahai received the B.S. degree in electrical engineering and computer sciences in 1994 from the University of California at Berkeley, and the M.S. and Ph.D. degrees in electrical engineering and computer science, both from the Massachusetts Institute of Technology, in 1996 and 2001, respectively. In 2001, he developed adaptive signal processing algorithms for software radio at Enuvis in South San Francisco. He joined the EECS department at Berkeley as an Assistant Professor in 2002. His current research interests are in control over noisy channels, information theory, and wireless communication.