Databases Reference
In-Depth Information
If we use the minimum variance code (Table
3.9
), the lengths of the codewords are
{
2
,
2
,
2
,
3
,
3
}
. Substituting these values into the left-hand side of Equation (
2
), we get
2
−
2
2
−
2
2
−
2
2
−
3
2
−
3
+
+
+
+
=
1
which again satisfies the inequality.
The second part of this result, due to Kraft, states that if we have a sequence of positive
integers
K
i
1
that satisfies (
2
), then there exists a uniquely decodable code whose codeword
lengths are given by the sequence
{
l
i
}
=
i
1
.
Using this result, we will now show the following:
{
l
i
}
=
1.
The average codeword length
l
of an optimal code for a source
S
is greater than or equal
(S)
to
H
.
S
2.
The average codeword length
l
of an optimal code for a source
is strictly less than
H
(S)
+
1.
For a source
S
with alphabet
A
={
a
1
,
a
2
,...
a
K
}
, and probability model
{
P
(
a
1
),
P
(
a
2
),...,
P
(
a
K
)
}
, the average codeword length is given by
K
l
=
P
(
a
i
)
l
i
i
=
1
Therefore, we can write the difference between the entropy of the source
H
(S)
and the average
length as
K
K
(S)
−
=−
(
a
i
)
(
a
i
)
−
(
a
i
)
H
l
P
log
2
P
P
l
i
i
=
1
i
=
1
log
2
l
i
K
1
=
P
(
a
i
)
−
P
(
a
i
)
i
=
1
log
2
K
1
2
l
i
=
P
(
a
i
)
−
log
2
[
]
P
(
a
i
)
i
=
1
log
2
2
−
l
i
K
=
P
(
a
i
)
P
(
a
i
)
i
=
1
K
2
−
l
i
≤
log
2
i
=
1
The last inequality is obtained using Jensen's inequality, which states that if
f
(
x
)
is a concave
(convex cap, convex
∩
) function, then
E
[
f
(
X
)
]
f
(
E
[
X
]
)
. The log function is a concave
function.
