Databases Reference
In-Depth Information
T A B L E 3 . 2
The reduced four-letter
alphabet.
Letter
Probability
Codeword
a
2
0.4
c
(
a
2
)
a
1
0.2
c
(
a
1
)
a
3
0.2
c
(
a
3
)
a
4
0.2
α
1
T A B L E 3 . 3
The reduced three-letter
alphabet.
Letter
Probability
Codeword
a
2
0.4
c
(
a
2
)
a
3
0.4
α
2
a
1
0.2
c
(
a
1
)
c
(
a
4
)
=
α
1
∗
0
c
(
a
5
)
=
α
1
∗
1
where
denotes concatenation.
We now define a new alphabet
A
with a four-letter alphabet
a
1
,
α
1
is a binary string, and
∗
a
4
, where
a
4
a
2
,
a
3
,
is
a
4
)
=
composed of
a
4
and
a
5
and has a probability
P
(
P
(
a
4
)
+
P
(
a
5
)
=
0
.
2. We sort this
new alphabet in descending order to obtain Table
3.2
.
In this alphabet,
a
3
and
a
4
are the two letters at the bottom of the sorted list. We assign
their codewords as
c
(
a
3
)
=
α
2
∗
0
a
4
)
=
α
2
∗
c
(
1
a
4
)
=
α
1
. Therefore,
but
c
(
α
1
=
α
2
∗
1
which means that
(
a
4
)
=
α
2
∗
c
10
c
(
a
5
)
=
α
2
∗
11
At this stage, we again define a new alphabet
A
a
3
,
that consists of three letters
a
1
,
a
2
,
where
a
3
is composed of
a
3
and
a
4
and has a probability
P
a
3
)
=
a
4
)
=
(
P
(
a
3
)
+
P
(
0
.
4. We
sort this new alphabet in descending order to obtain Table
3.3
.
In this case, the two least probable symbols are
a
1
and
a
3
. Therefore,
a
3
)
=
α
3
∗
c
(
0
c
(
a
1
)
=
α
3
∗
1