2009 Viterbi Lecturer

Codes and Coin Flips: Compression and Modeling
Robert M. Gray
Alcatel/Lucent Technologies Professor of Communications and Networking
Department of Electrical Engineering, Stanford University


In the middle of the last century, Claude Shannon developed mathematical models of communication systems and quantified the best possible performance achievable when information sources — models of real-world signals such as speech, audio, images, and video — are communicated or stored. Shannon’s work lies at the core of modern digital communications, both theory and practice. Many of the fundamental ideas in Shannon information theory — including random processes, entropy, and coding — have parallel roles in ergodic theory, a branch of mathematics which arose in physics and which was also profoundly influenced by Shannon’s work. A few of these parallel ideas are sketched in hindsight via the deceptively simple example of coding coin flips to generate suprisingly general statistical models of information sources. The example highlights deep connections between the Shannon theory of source coding or data compression and the problem of simple modeling or simulating complicated processes. Unsuprisingly, the Viterbi algorithm makes a cameo appearance at a critical point.


Robert M. Gray is the Lucent Technologies Professor of Engineering and Professor of Electrical Engineering at Stanford University, where he has been teaching for almost 40 years. His research interests are in information theory and signal processing, especially in the theory and practice of quantization, compression, and classification.

Gray was a member of the Board of Governors of the IEEE Information Theory Group (1974-1980, 1985-1988) and of the IEEE Signal Processing Society (1998-2001). He was Associate Editor for Source Coding (1977-1980) and Editor-in-Chief (1980-1983) of the IEEE Transactions on Information Theory. He is currently the Editor-in-Chief of Foundations and Trends in Signal Processing. He was Co-Chair of the 1993 IEEE International Symposium on Information Theory and Program Co-Chair of the 1997 and 2004 IEEE International Conference on Image Processing.

He is a Fellow of the Institute of Mathematical Statistics and the IEEE and has held fellowships from the Japan Society for the Promotion of Science at the University of Osaka (1981), the John Simon Guggenheim Foundation at the University of Paris XI (1982), and NATO/Consiglio Nazionale delle Ricerche at the University of Naples (1990). During spring 1995 he was a Vinton Hayes Visiting Scholar at the Division of Applied Sciences of Harvard University. He is a Faculty Affiliate of the Clayman Institute for Gender Studies at Stanford University, where he will be a Faculty Research Fellow during the 2008-2009 academic year.

He was corecipient of the 1976 IEEE Information Theory Group Paper Award and the 1983 IEEE ASSP Senior Award. He was awarded an IEEE Centennial medal (1984) and an IEEE Third Millennium Medal (2000). He received the 1993 Society Award, the 1998 Technical Achievement Award, and the 2005 Meritorious Service Award from the IEEE Signal Processing Society. He received a Golden Jubilee Award for Technological Innovation (1998) and the 2008 Shannon Award from the IEEE Information Theory Society. He received the 2008 IEEE Jack S. Kilby Signal Processing Medal. He received a 2002 Presidential Award for Excellence in Science, Mathematics and Engineering Mentoring (PAESMEM) and the 2003 Distinguished Alumni in Academia Award from the University of Southern California. He is a member of the National Academy of Engineering (2007).

Robert M. Gray was born in San Diego, Calif., on November 1, 1943. He received the B.S. and M.S. degrees from M.I.T. in 1966 and the Ph.D. degree from U.S.C. in 1969, all in Electrical Engineering.

Published on June 26th, 2017

Last updated on February 5th, 2020