Databases Reference
In-Depth Information
T A B L E 3 . 6
Reduced four-letter alphabet.
Letter
Probability
Codeword
a
2
0.4
c
(
a
2
)
a
4
0.2
α
1
a
1
0.2
c
(
a
1
)
a
3
0.2
c
(
a
3
)
(0.4)
(0.4)
(0.6) 0
a
2
(0.4)
(1.0)
(0.2)
(0.4) 0
(0.4) 1
a
1
(0.2)
(0.2) 0
(0.2) 1
a
3
(0.2)
(0.2) 1
a
4
(0.1)
0
a
5
(0.1)
1
F I GU R E 3 . 2
Building the binary Huffman tree.
0
′
′
a
2
(0.4)
a
2
(0.4)
a
1
(0.4)
a
2
(0.6)
′
1
′
a
1
(0.2)
a
4
(0.2)
a
2
(0.4)
0
a
1
(0.4)
′
1
a
3
(0.2)
a
1
(0.2)
0
a
4
(0.2)
a
4
(0.1)
0
a
3
(0.2)
1
a
5
(0.1)
1
F I GU R E 3 . 3
The minimum variance Huffman encoding procedure.
Now combine
a
1
and
a
3
into
a
1
, which has a probability of 0
4. Sorting the alphabet
a
2
,
a
4
, and
a
1
and putting
a
1
as far up the list as possible, we get Table
3.7
. Finally, by combining
a
2
and
a
4
and re-sorting, we get Table
3.8
. If we go through the unbundling procedure, we get
the codewords in Table
3.9
. The procedure is summarized in Figure
3.3
. The average length
of the code is
.
l
=
.
4
×
2
+
.
2
×
2
+
.
2
×
2
+
.
1
×
3
+
.
1
×
3
=
2
.
2 bits/symbol
.
The two codes are identical in terms of their redundancy. However, the variance of the
length of the codewords is significantly different. This can be clearly seen from Figure
3.4
.
Remember that in many applications, although you might be using a variable-length code,
the available transmission rate is generally fixed. For example, if we were going to transmit
symbols from the alphabet we have been using at 10,000 symbols per second, we might ask
for a transmission capacity of 22,000 bits per second. This means that during each second, the
