Recent results in non-asymptotic Shannon theory

The results of Shannon theory are asymptotic and do not reflect the finite codeword lengths used in practice. Recent progress in design of channel codes and distributed source codes has made it crucial to understand how quickly communication systems can approach their ultimate limits.

Shannon theory is largely based on joint typicality. However, for finite block length n, joint typicality may not hold. Therefore, we accept a probability epsilon of codeword error. Our goal is to optimize the performance among communication systems that satisfy an (n,epsilon) constraint. Such non-asymptotic performance measures provide a more informative benchmark for verifying the efficiency of practical systems.

We discuss several channel coding and distributed source coding setups. In these systems, the finite n induces a gap O(1/sqrt(n))to the classical performance limits. Our non-asymptotic measures refine the classical results, because for any epsilon they converge to them as n increases. Finally, we consider a distributed source coding setup with unknown source statistics. We provide an achievable feedback-based scheme whose redundancy rate is as large as O(n^-1/3). This penalty is greater than theO(1/sqrt(n)) penalty with known statistics. Unfortunately, unknown statistics may also be costly in other Shannon theory applications, in particular universal channel coding.

Dror Baron received the B.Sc. (summa cum laude) and M.Sc. degrees from the Technion – Israel Institute of Technology, in 1997 and 1999, and the Ph.D. degree from the University of Illinois at Urbana-Champaign in 2003, all in electrical engineering. From 1997 to 1999 he worked at Witcom Ltd. in modem design. From 1999 to 2003 he was a research assistant at the University of Illinois at Urbana-Champaign, where he was also a visiting assistant professor in 2003. Since 2003 he has been a postdoctoral research associate in the Department of Electrical and Computer Engineering at Rice University. His research interests include information theory and signal processing.

Dr. Baron was a recipient of the 2002 M. E. Van Valkenburg Graduate Research Award, and received honorable mention in the Robert Bohrer Memorial Student Workshop in April 2002, both at the University of Illinois. He also participated from 1994 to 1997 in the Program for Outstanding Students, comprising the top 0.5% of undergraduates at the Technion.