IEEE Signal Processing - May 2018 - 24

Source Coding and the DRF
The source coding problem addresses the encoding of a
random source sequence so as to attain the minimal distortion over all possible encoding and reconstruction
schemes, under a constraint on the average bits per source
symbol in this encoding. In "Scalar Quantization," we considered the encoding of such sequences subject to the
additional restriction that each source symbol is encoded
independently of the other. By removing this restriction and
considering the joint encoding of n independent source
symbols, we can attain smaller distortion using the same
average number of bits. For this reason, the source coding
problem with respect to a real independent and identically
distributed (i.i.d.) sequence X 1, f, X n is defined as determining the minimum mean squared error attainable under
all possible encoder mappings of a realization of this
r
sequence to an index out of 26nR@ possible indices, as well
as all reconstruction decoder mappings from this set of
indices back to R n. This minimal value is called the operational distortion-rate function (DRF) of the i.i.d. distribution
of the sequence at code rate Rr and is denoted by d n (Rr ).
In his source coding theorem, Shannon showed that, as
the number of jointly described source symbols n extends
to infinity, the operational DRF d n (Rr ) converges to the informational DRF. The latter is defined as

losing generality we can assume that each reconstruction waveform produced by the decoder is only a function of one of
these states, so there are at most 26TR@ possible reconstruction
waveforms. Moreover, any encoder that strives to attain the
minimum MSE (MMSE) in this system would map the input
signal to the state i associated with the reconstruction wave-

SX (f )

f
Lossy Compression Distortion
Preserved Spectrum

FIGURE 9. The reverse water-filling interpretation of (6). Water is poured
into the area bounded by the graph of S X (f ) up to level i . The bit rate
R is tied to the water level i through the preserved part of the spectrum
(6b). The lossy compression distortion D is given by (6a).
24

2
D (Rr ) _ inf E ^X - Xt h ,

(S2)

where the infimum is over all joint probability distributions
p (x, xt ) such that their marginal over the x coordinate coincides with the distributions of X1 and their mutual information does not exceed Rr . For example, when the source
sequence is drawn from a standard normal distribution,
the result of the prior optimization leads to
r

D (Rr ) = 2 -2R.

(S3)

Comparing with the distortion under scalar quantization
in "Scalar Quantization," this value is strictly smaller than
the minimal distortion in encoding the same sequence
using either fixed or variable bit-length scalar quantization. This difference is explained by the fact that as n
extends to infinity, the law of large numbers implies that
the probability mass of n i.i.d. copies of a random variable of bounded variance concentrates around the edges
of an n-dimensional sphere of radius equal to the square
root of this variance. Thus, these n copies can be represented in a more compact manner than with independent
representations of each coordinate, as in scalar quantization [39].

form xt i (t) that is closest to the input in the distance defined by
the L 2 norm over the interval [-T/2, T/2], as derived from our
distortion criterion. Therefore, the only freedom in designing
the optimal encoding scheme is in deciding on the set of reconstruction waveforms " xt i (t), t ! [-T/2, T/2], i = 1, f, 26TR@,,
which we denote as codewords.
The procedure for selecting these codewords and the resulting MMSE distortion are given by Shannon's classical source
coding theorem [4], [5] and its extensions to continuous alphabets [33], [34]. According to this theorem, a near-optimal set
of codewords is obtained by 26TR@ independent random draws
from a distribution on the set of functions over [-T/2, T/2]
with a finite L 2 norm, such that the mutual information of the
joint distribution of the input and the reconstruction waveforms
is limited to 6TR@ bits. Moreover, Shannon's theorem also provides the asymptotic MMSE obtained by using this set of codewords, denoted as Shannon's function or the information DRF
of the source signal X (t) at bit rate R.
Shannon's source coding theorem with respect to a discrete-time independent and identically distributed process is
explained in "Source Coding and the DRF." In the case of a
continuous-time Gaussian stationary input signal with a PSD
of S X ( f ), a closed-form expression for Shannon's DRF was
derived by Pinsker and Kolmogorov [35] and is given by the
following parametric form:

IEEE Signal Processing Magazine

May 2018

Table of Contents for the Digital Edition of IEEE Signal Processing - May 2018