Page 43 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

20 Chapter 2. Video Coding: Fundamentals

where S K denotes all possible realizations of S j−1 ;:::;S j−K , and

H(S|S j−1 ;:::;S j−K )

= − p(S j = a i |S j−1 ;:::;S j−K ) log p(S j = a i |S j−1 ;:::;S j−K ):
a i ∈A
(2.6)

The performance bound of a lossless coding system is given by the lossless
coding theorem [16]:

Lossless coding theorem: The minimum bit rate R min that can be
achieved by lossless coding of a source S can be arbitrarily close,
but not less than, the source entropy H(S). Thus R min = H(S)+ ,
where is a positive quantity that can be made arbitrarily close to zero.
For a DMS, this lower bound can be approached by coding symbols inde-
pendently, whereas for a Markov-K source, blocks of K symbols should be
encoded at a time.
The performance bounds of lossy coding systems are addressed by a branch
of information theory known as rate-distortion theory [16, 17, 18]. This the-
ory provides lower bounds on the obtainable average distortion for a given
average bit rate, or vice versa. It also promises that codes exist that approach
the theoretical bounds when the code dimension and delay become large. An
important theorem in this branch is the source coding theorem [17]:

Source coding theorem: There exists a mapping from source symbols
to codewords such that for a given distortion D, R(D) bits=symbol are
suGcient to achieve an average distortion that is arbitrarily close to D.

The function R(D) is known as the rate-distortion function. It is a convex,
continuous, and strictly decreasing function of D, as illustrated in Figure 2.4.
This function is normally computed using numerical methods [18], although
for simple source and distortion models it can be computed analytically. Al-
though rate-distortion theory does not give an explicit method for constructing
practical optimum coding systems, it gives very important hints about the
properties of such systems.

2.5.4 Quantization

As already discussed, quantization is a key element of a video coding system.
Quantization can be viewed as a many-to-one mapping. It represents a set
of continuous-valued samples with a nite number of symbols. If each input
sample is quantized independently, then the process is referred to as scalar