Databases Reference
In-Depth Information
the cumulative distribution function when describing what is now known as the Shannon-Fano
code. Peter Elias, another member of Fano's first information theory class at MIT (this class
also included Huffman), came up with a recursive implementation for this idea. However, he
never published it, and we only know about it through a mention in a 1963 topic on information
theory by Abramson [
39
]. Abramson described this coding approach in a note to a chapter. In
another topic on information theory by Jelinek [
40
] in 1968, the idea of arithmetic coding is
further developed, this time in an appendix, as an example of variable-length coding. Modern
arithmetic coding owes its birth to the independent discoveries in 1976 of Pasco [
41
] and
Rissanen [
42
] who solved the problem of finite precision. Finally, several papers appeared that
provided practical arithmetic coding algorithms, the most well known of which is the paper
by Rissanen and Langdon [
43
].
Before we begin our development of the arithmetic code, we need to establish some nota-
tion. Recall that a random variable maps the outcomes, or sets of outcomes, of an experiment
to values on the real number line. For example, in a coin-tossing experiment, the random
variable could map a head to zero and a tail to one (or it could map a head to 2367.5 and a tail
to
192). To use this technique, we need to map the source symbols or letters to numbers.
For convenience, in the discussion in this chapter we will use the mapping
−
X
(
a
i
)
=
i
i
∈
A
(1)
where
is the alphabet for a discrete source and
X
is a random variable.
This mapping means that given a probability model
A
={
a
1
,
a
2
,...,
a
m
}
P
for the source, we also have a probability
density function for the random variable
P
(
X
=
i
)
=
P
(
a
i
)
and the cumulative density function can be defined as
i
F
X
(
)
=
(
=
)
i
P
X
k
k
=
1
Notice that for each symbol
a
i
with a nonzero probability, we have a distinct value of
F
X
(
.
We will use this fact in what follows to develop the arithmetic code. Our development may be
more detailed than what you are looking for, at least on the first reading. If so, skip or skim
Sections 4.3.1-4.4.1 and go directly to Section
4.4.2
.
i
)
4.3.1 Generating a Tag
The procedure for generating the tag works by reducing the size of the interval in which the
tag resides as more and more elements of the sequence are received.
We start out by first dividing the unit interval into subintervals of the form
[
F
X
(
i
−
1
),
,
m
. Because the minimum value of the
cdf
is zero and the maximum value
is one, this exactly partitions the unit interval. We associate the subinterval
F
X
(
i
)),
i
=
1
,...
[
F
X
(
i
−
1
),
F
X
(
i
))
