Cryptography Reference
In-Depth Information
0
1
0
1
1
0
S
W
01
01
T
01
A
*
E
Figure 19.3: Figure 19.2 after the code for 'A' is changed from
11
to
110
. Notice that there's a blank node for the code
111
. This shouldn't
be used.
duce bad synchronization characters. The solution is to add extra
bits to the codes to eliminate this possibility— a process that will
hurt the code's efficiency. The price, however, may be fairly low if
the codes are long. Adding an extra bit to a 12-bit code isn't as bad as
adding an extra one to a 3-bit code.
The trick is to ensure that the code for one character can't be bro-
ken into parts
A
B
B
is a prefix for the synchronization
code. So if the synchronization code is
0111
, then a code that ends
with
01
would be bad because it is a prefix of the synchronization
code.
The codes produced by the Huffman algorithm can be made
longer by adding extra characters to the end. It's not easy to add them
to the beginning or themiddle, but it is to add themto the end. These
are wasted bits that serve no purpose except to prevent the synchro-
nization code from appearing.
Figure 19.3 shows Figure 19.2 after the code for
and
such that
has been rewrit-
ten to use an extra bit,
110
.Thiscreatesacode,
111
, that is never used
when compressing the data. This inefficency, though, ensures that
none of the other letters will combine to form the synchronization
code. There is no code that will produce three 1s in a row except the
synchronization code.
The construction in Figure 19.3 is more of an accident produced
by the fact that the tree is small and there is only one letter that ends
A
