Databases Reference
In-Depth Information
has to be truncated. But if we truncate the representation, is the resulting code still unique?
Finally, is the resulting code efficient? How far or how close is the average number of bits per
symbol from the entropy? We will examine all these questions in the next section.
Even if we show the code to be unique and efficient, the method described to this point is
highly impractical. In Section
4.4.2
, we will describe a more practical algorithm for generating
the arithmetic code for a sequence. We will give an integer implementation of this algorithm
in Section
4.4.3
.
4.4.1 Uniqueness and Efficiency of the Arithmetic Code
T
X
(
x
)
is a number in the interval [0, 1). A binary code for
T
X
(
x
)
can be obtained by taking
1
the binary representation of this number and truncating it to
l
1 bits.
Recall that the binary representations of decimal numbers in the interval [0, 1) are obtained
as the negative powers of two. The decimal equivalent of the binary number
(
x
)
=
log
)
+
P
(
x
.
b
1
b
2
b
3
...
b
k
is
b
1
2
−
1
b
2
2
−
2
b
3
2
−
3
b
k
2
−
k
. Thus
2
−
1
2
−
3
.
+
+
+···+
.
101
=
+
Example4.4.1:
Consider a source
A
that generates letters from an alphabet of size four,
A
={
a
1
,
a
2
,
a
3
,
a
4
}
with probabilities
1
2
,
1
4
,
1
8
,
1
8
P
(
a
1
)
=
P
(
a
2
)
=
P
(
a
3
)
=
P
(
a
4
)
=
A binary code for this source can be generated as shown
in
Table
4.4
. The quantity
T
x
is
obtained using Equation (
3
). The binary representation of
T
x
is truncated to
1
log
P
(
x
)
+
1
bits to obtain the binary code.
T A B L E 4 . 4
A binary code for a four-letter alphabet.
1
Symbol
F
X
T
X
In Binary
log
)
+
1
Code
P
(
x
1
.500
.2500
.0100
2
01
2
.750
.6250
.1010
3
101
3
.875
.8125
.1101
4
1101
4
1.000
.9375
.1111
4
1111
We will show that a code obtained in this fashion is a uniquely decodable code. We first
show
th
at this code is unique, and then we
w
ill show that it is uniquely decodable. We will
use
T
X
(
x
)
l
(
x
)
to denote the truncation of
T
X
(
x
)
to l(
x
) bits.
