Databases Reference
In-Depth Information
T A B L E 2 . 3
Code 5. A code that is uniquely
decodable but not
instantaneous.
Letter
Codeword
a
1
0
a
2
01
a
3
11
Therefore, the decoding rule is to accumulate bits until you see a 0. The bit before the 0 is the
last bit of the previous codeword.
There is a slight difference between Code 3 and Code 4. In the case of Code 3, the decoder
knows the moment a code is complete. In Code 4, we have to wait till the beginning of the next
codeword before we know that the current codeword is complete. Because of this property,
Code 3 is called an
instantaneous
code. Although Code 4 is not an instantaneous code, it is
almost that.
While this property of instantaneous or near-instantaneous decoding is a nice property to
have, it is not a requirement for unique decodability. Consider the code shown in Table
2.3
.
Let's decode the string 011111111111111111. In this string, the first codeword is either 0
corresponding to
a
1
or 01 corresponding to
a
2
. We cannot tell which one until we have
decoded the whole string. Starting with the assumption that the first codeword corresponds to
a
1
, the next eight pairs of bits are decoded as
a
3
. However, after decoding eight
a
3
s, we are
left with a single (dangling) 1 that does not correspond to any codeword. On the other hand, if
we assume the first codeword corresponds to
a
2
, we can decode the next 16 bits as a sequence
of eight
a
3
s, and we do not have any bits left over. The string can be uniquely decoded. In
fact, Code 5, while it is certainly not instantaneous, is uniquely decodable.
We have been looking at small codes with four letters or less. Even with these, it is not
immediately evident whether the code is uniquely decodable or not. In deciding whether
larger codes are uniquely decodable, a systematic procedure would be useful. Actually, we
should include a caveat with that last statement. Later in this chapter we will include a class
of variable-length codes that are always uniquely decodable, so a test for unique decodability
may not be that necessary. You might wish to skip the following discussion for now, and come
back to it when you find it necessary.
Before we describe the procedure for deciding whether a code is uniquely decodable, let's
take another look at our last example. We found that we had an incorrect decoding because
we were left with a binary string (1) that was not a codeword. If this had not happened, we
would have had two valid decodings. For example, consider the code shown in Table
2.4
.
Let's encode the sequence
a
1
followed by eight
a
3
s using this code. The coded sequence is
01010101010101010. The first bit is the codeword for
a
1
. However, we can also decode it as
the first bit of the codeword for
a
2
. If we use this (incorrect) decoding, we decode the next
seven pairs of bits as the codewords for
a
2
. After decoding seven
a
2
s, we are left with a single
0 that we decode as
a
1
. Thus, the incorrect decoding is also a valid decoding, and this code is
not uniquely decodable.
