Distortion and Approximation

Various notions of the distortion between random variables, vectors, and processes as well as between different codings of a common source are quantified in this chapter. A distortion measure is not a “measure” in the sense used so far — it is an assignment of a nonnegative real number which indicates how bad an approximation one symbol or random object or coding is of another. The smaller the distortion, the better the approximation. If the two objects correspond to the input and output of a communication system, then the average distortion provides a measure of the

performance

or

fidelity

of the system. Small average distortion means high fidelity and good performance, while large average distortion means low fidelity and poor performance. Distortion measures generalize the idea of a distance or metric and they need not have metric properties such as the triangle inequality and symmetry, but such properties can be exploited when available and unsurprisingly the most important notions of distortion are either metrics or simple functions of metrics. We shall encounter several notions of distortion and a diversity of applications, with the most important application being the average distortion between input and output as a measure of the performance of a communications system. Other applications include extensions of finite memory channels to channels which approximate finite memory channels, geometric characterizations of the optimal performance of communications systems, approximations of complicated codes by simpler ones, and modeling random processes.