Source Coding and Simulation

Stanford University, Stanford CA

Investigators

Abstract

The intimate connection between source coding (data compression, quantization) and simulation (the generation of a signal with prescribed distributions from a purely random mechanism such as coin flips) has been known for over three decades. Recent results suggest even deeper connections with potentially significant implications for the related problems of compression code design, modeling random processes for the analysis and design of signal processing and coding systems, and understanding the nature and structure of mathematical models of random processes capturing the important properties of signals arising in the real world. This research is concerned with developing precise results characterizing and applying these connections to obtain new insight, theory, and algorithms. In 1977 the performance of an optimized source coding system was shown to be bounded by the quality of a constrained simulation of the source, with equality under certain conditions. In 2008 this connection was strengthened by a precise formulation and proof of an information theoretic ``folk theorem'' stating that source coding systems performing near the Shannon optimum yield bit streams that are ``nearly coin flips'' in the rigorous sense of closeness in Ornstein's d-bar process distance. Together these results imply that source coding systems --- including digital speech, audio, image, and video communication and storage systems --- and simulation systems --- comprising stationary codings or filterings of iid bits --- are mathematically approximately equivalent systems, and hence the theory and design algorithms appropriate for one yield corresponding results for the other. This project exploits these connections to develop new theory and design algorithms for codes for compression, simulation, and modeling based on known distributions and on distributions learned from data.