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

Section 2.5. Video Coding Basics 25

1 a
0
0.40
2 a 9 a
0 1.00
0.25
3 a 8 a 1
0.20 1 0.60
7 a
4 a 1
1 0.35
0.10
6 a
0.15 0
5 a
0
0.05
Original
alphabet
Figure 2.6: Hu6man coding example

Table 2.4: Comparison between VLC (of Figure 2.6) and a 3-bit FLC
r i p(r i ) I (r i ) VLC c i FLC c i

a 1 0.40 1.32 bits 0 (1 bit) 000
a 2 0.252.00 bits 10 (2 bits) 001
a 3 0.20 2.32 bits 111 (3 bits) 010
a 4 0.10 3.32 bits 1101 (4 bits) 011
a 5 0.054.32 bits 1100 (4 bits) 100
H (R) ≈ 2:04 bits=symbol
R L FLC = 3 bits=word R L VLC ≈ 2:1 bits=word
FLC ≈ 0:68 VLC ≈ 0:97

to the sum of their probabilities. This new symbol creates a new node in
the tree, with two branches connecting it to the original two nodes. A “0” is
assigned to one branch and a “1” is assigned to the other. The original two
nodes are then removed from the next stage. This process is continued until
the new symbol has a probability of 1. Now, to nd the codeword for a given
symbol, start at the right-hand end of the tree and follow the branches that
lead to the symbol of interest combining the “0”s and “1”s assigned to the
branches. Table 2.4 shows the obtained VLC and compares it to an FLC of
3 bits. Clearly, the Hu6man VLC is much more eGcient than the FLC.
There are more eGcient implementations of Hu6man coding. For example,
in many cases, most of the symbols of a large symbol set have very small
probabilities. This leads to very long codewords and consequently to large