Databases Reference
In-Depth Information
T A B L E 3 . 24
A 2-bit Tunstall code.
Sequence
Codeword
AAA
00
AAB
01
AB
10
B
11
3.7 Tunstall Codes
Most of the variable-length codes that we look at in this topic encode letters from the source
alphabet using codewords with varying numbers of bits: codewords with fewer bits for letters
that occur more frequently and codewords with more bits for letters that occur less frequently.
The Tunstall code is an important exception. In the Tunstall code, all codewords are of equal
length. However, each codeword represents a different number of letters. An example of a
2-bit Tunstall code for an alphabet
is shown in Table
3.24
. The main advantage
of a Tunstall code is that errors in codewords do not propagate, unlike other variable-length
codes, such as Huffman codes, in which an error in one codeword will cause a series of errors
to occur.
A
={
A
,
B
}
Example3.7.1:
Let's encode the sequence
AAABAABAABAABAAA
using the code in Table
3.24
. Starting
at the left, we can see that the string
AAA
occurs in our codebook and has a code of 00. We
then code
B
as 11,
AAB
as 01, and so on. We finally end up with the code 001101010100 for
the sequence.
The design of a code that has a fixed codeword length but a variable number of symbols
per codeword should satisfy the following conditions:
1.
We should be able to parse a source output sequence into sequences of symbols that
appear in the codebook.
2.
We should maximize the average number of source symbols represented by each code-
word.
In order to understand what we mean by the first condition, consider the code shown in
Table
3.25
. Let's encode the same sequence
AAABAABAABAABAAA
as in the previous
example using the code in Table
3.25
. We first encode
AAA
with the code 00. We then encode
B
with 11. The next three symbols are
AAB
. However, there are no codewords corresponding
to this sequence of symbols. Thus, this sequence is unencodable using this particular code—not
a desirable situation.
Tunstall [
31
] gives a simple algorithm that fulfills these conditions. The algorithm is as
follows:
Suppose we want an
n
-bit Tunstall code for a source that generates
iid
letters from an
alphabet of size
N
. The number of codewords is 2
n
. We start with the
N
letters of the source
