Cryptography Reference
In-Depth Information
0
1
0
1
1
0
S
A
W
01
T
01
*
E
Figure 19.2: Figure 19.1 after the tree is rearranged to make the syn-
chronization code be 0111. These techniques are also used in Section
7.3.3 to scramble the tree to add more confusion to the code.
The code for 'at' is '011110'. Is this the place where we should
start decoding?
It's not clear where the code itself begins. The word '*tea' would
be encoded: '1111110111001'. Where do the four 1s end and the
real message begin?
•
The last two problems can be solved by choosing the synchro-
nization code carefully and tweaking the tree by adding extra values
or nodes. This will decrease the efficiency but not as much as con-
verting to unary.
The key to avoiding the third problem is choosing a synchroniza-
tion code that is not susceptible to
prefix inversion
. That is, it's not
possible to break the code block into two separate parts,
A
and
B
,
such that
where
+
stands for concatenation. The
block
1111
is one of the worst candidates for this because there are
three different ways to break it into
A
+
B
=
B
+
A
A
and
B
that satisfy the equa-
=1
is just one of them. A better choice
is something like
0111
. Figure 19.2 shows a tree redrawn to avoid this
problem.
Avoiding the second problem is a bit trickier. If two adjacent char-
acters can produce the synchronization code, then it would intro-
tion. Setting
A
= 111
and
B
