Cryptography Reference
In-Depth Information
5.3
Code distances and performance
5.3.1 Choosing a good code
As a code is exploited for its correcting capacities, we have to be able to esti-
mate these in order to make a judicious choice of one code rather than another,
according to the application targeted. Among the bad possible choices,
catas-
trophic codes
are such that a finite number of errors at the input of the decoder
can produce an infinite number of errors at the output of the decoder, which
explains their name. One main property of these codes is that there exists at
least one input sequence of infinite weight that generates a coded sequence of
finite weight: systematic codes therefore cannot be catastrophic. These codes
can be identified very simply if they have a rate of the form
R
=1
/N
.Wecan
then show that the code is catastrophic if the largest common divisor (L.C.D.) of
its generator polynomials is different from unity. Thus, the code with generator
polynomials
G
(1)
(
D
)=1+
D
+
D
2
+
D
3
and
G
(2)
(
D
)=1+
D
3
is catastrophic
since the L.C.D. is
1+
D
.
However, choosing a convolutional code cannot be limited to the question "Is
it catastrophic?". By exploiting the graphic representations introduced above,
the properties and performance of codes can be compared.
5.3.2
RTZ
sequences
Since convolutional codes are linear, to determine the distances between the
different coded sequences amounts to determining the distances between the
non-null coded sequences and the "all zero" sequence. Therefore, it suces to
calculate the Hamming weight of all the coded sequences that leave from state
0 and that return to it. These sequences are called
Return To Zero
(RTZ) se-
quences. The smallest Hamming weight thus obtained is called the
free distance
of the code. The minimum Hamming distance of a convolutional code is equal
to its free distance from a certain length of coded sequence. In addition, the
number of RTZ sequences that have the same weight is called the multiplicity
of this weight.
Let us consider the codes that have been used as examples so far. Each RTZ
sequence of minimum weight is shown in bold in Figures 5.12, 5.13 and 5.14.
The non-recursive systematic code has an RTZ sequence with minimum Ham-
ming weight equal to 4. The free distance of this code is therefore equal to 4.
On the other hand, as the classical code and the recursive systematic code each
possess two RTZ sequences with minimum weight 6, their free distance is there-
fore 6. The correction capacity of non-recursive non-systematic and recursive
systematic codes is therefore better than that of the non-recursive systematic
code.
It is interesting, in addition, to compare the weights of the sequences at the
input associated with the RTZ sequences with minimum weight. In the case of
