Databases Reference
In-Depth Information
T A B L E 2 . 4
Code 6. A code that is not
uniquely decodable.
Letter
Codeword
a
1
0
a
2
01
a
3
10
A Test for Unique Decodability
In the previous examples, in the case of the uniquely decodable code, the binary string left over
after we had gone through an incorrect decoding was not a codeword. In the case of the code
that was not uniquely decodable, in the incorrect decoding what was left was a valid codeword.
Based on whether the dangling suffix is a codeword or not, we get the following test [
7
,
8
].
We start with some definitions. Suppose we have two binary codewords
a
and
b
, where
a
is
k
bits long,
b
is
n
bits long, and
k
<
n
. If the first
k
bits of
b
are identical to
a
, then
a
is
called a
prefix
of
b
.Thelast
n
−
k
bits of
b
are called the
dangling suffix
[
7
]. For example, if
a
01011, then
a
is a prefix of
b
and the dangling suffix is 11.
Construct a list of all the codewords. Examine all pairs of codewords to see if any codeword
is a prefix of another codeword. Whenever you find such a pair, add the dangling suffix to the
list unless you have added the same dangling suffix to the list in a previous iteration. Now
repeat the procedure using this larger list. Continue in this fashion until one of the following
two things happens:
=
010 and
b
=
1.
You get a dangling suffix that is a codeword.
2.
There are no more unique dangling suffixes.
If you get the first outcome, the code is not uniquely decodable. However, if you get the second
outcome, the code is uniquely decodable.
Let's see how this procedure works with a couple of examples.
Example2.4.1:
Consider Code 5. First list the codewords:
{
0
,
01
,
11
}
The codeword 0 is a prefix for the codeword 01. The dangling suffix is 1. There are no other
pairs for which one element of the pair is the prefix of the other. Let us augment the codeword
list with the dangling suffix:
{
,
,
,
}
0
01
11
1
Comparing the elements of this list, we find 0 is a prefix of 01 with a dangling suffix of 1.
But we have already included 1 in our list. Also, 1 is a prefix of 11. This gives us a dangling
