Source Coding and Simulation

2008 Shannon Lecture
Source Coding and Simulation
Professor Robert M. Gray
Stanford University


The observation that good source codes with respect to a fidelity criterion are related to systems that simulate or synthesize a random process by coding an iid process is over three decades old. This talk traces some of the history, ideas, tools, and results relating source coding and the simulation problem. Particular topics include block vs. sliding-block codes, distance measures on random processes, the generality of processes modeled as time-invariant codings of iid processes, and an information theoretic “folk theorem” on the bits generated by nearly optimal source codes.


Robert M. Gray was born at the North Island Naval Air Station, 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. While a graduate student he spent two summers working at the Jet Propulsion Lab (JPL). Since 1969 he has been with Stanford University, where he is currently the Alcatel Lucent Technologies Professor of Communications and Networking in the School of Engineering, Professor of Electrical Engineering, and a Faculty Affiliate of the Michelle Clayman Institute of Gender Studies. He has worked on a variety of topics in the overlapping areas of source coding, data compression, quantization, and statistical classification. His favorite topics include Shannon rate-distortion theory, Toeplitz matrices, speech coding and recognition, the Lloyd algorithm, the overlap of ergodic theory and information theory, sliding-block codes, sigma-delta modulation, content-addressible browsing, and high rate vector quantization. 

He is a Fellow of the IEEE and the Institute of Mathematical Statistics and a member of the National Academy of Engineering. He was a Fellow of the John Simon Guggenheim Foundation at the University of Paris (1982), of the Japan Society for the Promotion of Science at the University of Osaka (1981), and of the NATO/Consiglio Nazionale delle Ricerche at the University of Naples (1990). 

He was Associate Editor for Source Coding (1977-1980) and Editor (1980-1983) of the IEEE Transactions on Information Theory. He is currently Editor-in-Chief of Foundations and Trends in Signal Processing. With Jerry Gibson he co-chaired the 1993 IEEE International Symposium on Information Theory. He served two terms on the IT Board of Governors (1974-1980, 1984-1987). He was organizer, Proceedings editor, and BBQ chef of a precursor to the IT workshops -- a workshop on Source Coding/Ergodic Theory held at Stanford University in September 1974, which was attended by six future Shannon award winners. 

He was corecipient of the 1976 IEEE IT Group Paper Award and the 1983 IEEE ASSP Society Senior Award. He received the IEEE Signal Processing Society 1993 Society Award, 1997 Technical Achievement Award, and 2005 Meritorious Service Award. He received IEEE Centennial and Third Millennium Medals. In 1998 he received a Golden Jubilee Award for Technological Innovation from the IT Society. He received a 2002 Presidential Award for Excellence in Science, Mathematics and Engineering Mentoring (PAESMEM). He is the recipient of the 2008 IEEE Jack S. Kilby Signal Processing Medal.