Databases Reference
In-Depth Information
case if all codewords were 1 bit long. If
l
=
max
{
l
1
,
l
2
,...,
l
N
}
then the largest value that the exponent can take is less than or equal to
nl
. Therefore, we can
write this summation as
nl
n
A
k
2
−
k
K
(C)
=
k
=
n
where
A
k
is the number of combinations of
n
codewords that have a combined length of
k
.Let's
take a look at the size of this coefficient. The number of possible distinct binary sequences
of length
k
is 2
k
. If this code is uniquely decodable, then each sequence can represent one
and only one sequence of codewords. Therefore, the number of possible combinations of
codewords whose combined length is
k
cannot be greater than 2
k
. In other words,
2
k
A
k
This means that
nl
nl
n
A
k
2
−
k
2
k
2
−
k
K
(C)
=
=
nl
−
n
+
1
(19)
k
=
n
k
=
n
But if
K
(C)
is greater than one, it will grow exponentially with
n
, while
n
(
l
−
1
)
+
1 can only
grow linearly. So if
K
is greater than one, we can always find an
n
large enough that the
inequality (
19
) is violated. Therefore, for a uniquely decodable code
(C)
C,
K
(C)
is less than
or
equal to one.
This part of the Kraft-McMillan inequality provides a necessary condition for uniquely
decodable codes. That is, if a code is uniquely decodable, the codeword lengths have to satisfy
the inequality. The second part of this result is that if we have a set of codeword lengths that
satisfy the inequality, we can always find a prefix code with those codeword lengths. The proof
of the assertion presented here is adapted from [
9
].
Theorem
Given a set of integers l
1
,
l
2
,...,
l
N
that satisfy the inequality
N
2
−
l
i
1
i
=
1
we can always find a prefix code with codeword lengths l
1
,
l
2
,...,
l
N
.
Proof
We will prove this assertion by developing a procedure for constructing a prefix
code with codeword lengths
l
1
,
l
2
,...,
l
N
that satisfy the given inequality. We will assume,
without loss of generality, that
l
1
l
2
...
l
N
.
