Databases Reference
In-Depth Information
suffix of 1, which is already in the list. There are no other pairs that would generate a dangling
suffix, so we cannot augment the list any further. Therefore, Code 5 is uniquely decodable.
Example2.4.2:
Consider Code 6. First list the codewords:
{
0
,
01
,
10
}
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. Augmenting the codeword
list with 1, we obtain the list
{
0
,
01
,
10
,
1
}
In this list, 1 is a prefix for 10. The dangling suffix for this pair is 0, which is the codeword
for
a
1
. Therefore, Code 6 is not uniquely decodable.
2.4.2 Prefix Codes
The test for unique decodability requires examining the dangling suffixes initially generated
by codeword pairs in which one codeword is the prefix of the other. If the dangling suffix is
itself a codeword, then the code is not uniquely decodable. One type of code in which we will
never face the possibility of a dangling suffix being a codeword is a code in which no codeword
is a prefix of the other. In this case, the set of dangling suffixes is the null set, and we do not
have to worry about finding a dangling suffix that is identical to a codeword. A code in which
no codeword is a prefix to another codeword is called a
prefix code
. A simple way to check if
a code is a prefix code is to draw the rooted binary tree corresponding to the code. Draw a tree
that starts from a single node (the
root node
) and has a maximum of two possible branches
at each node. One of these branches corresponds to a 1 and the other branch corresponds to
a 0. In this topic, we will adopt the convention that when we draw a tree with the root node
at the top, the left branch corresponds to a 0 and the right branch corresponds to a 1. Using
this convention, we can draw the binary tree for Code 2, Code 3, and Code 4 as shown in
Figure
2.5
.
Note that apart from the root node, the trees have two kinds of nodes—nodes that give
rise to other nodes and nodes that do not. The first kind of nodes are called
internal nodes
,
a
1
a
1
a
2
a
1
a
2
a
2
a
3
a
3
a
4
a
3
a
4
a
4
Code 2
Code 3
Code 4
F I GU R E 2 . 5
Binary trees for three different codes.
