Cryptography Reference
In-Depth Information
If a sequence is of the RTZ type before permutation, then it is no
longer so after permutation and vice-versa.
The rule above is impossible to satisfy in practice and a more realistic ob-
jective is:
If a sequence is of the RTZ type before permutation, then it is
no longer so after permutation or it has become a simple long RTZ
sequence and vice-versa.
The dilemma in designing good permutations for turbo codes lies in the
need to satisfy this objective for two distinct classes of input sequences that
require opposing types of processing: simple RTZ sequences and multiple RTZ
sequences, as defined above. To illustrate this problem, consider a rate 1/3
turbo code, with regular rectangular permutation (writing in
M
rows, lecture
in
N
columns) over blocks of
k
=
MN
bits (Figure 7.6). Elementary encoders
are encoders with 8 states whose period is 7 (recursivity generator 15).
The first pattern (a) of Figure 7.6 concerns a sequence of possible errors
with input weight
w
= 2 : 10000001
for code
C
1
, that we can also call the
horizontal code. This is the RTZ minimum sequence with weight 2 for the
encoder considered. The redundancy produced by this encoder is of weight 6
(exactly:
11001111
). The redundancy produced by the vertical encoder
C
2
,for
which the sequence considered is also RTZ (its length is a multiple of 7), is much
more informative because it is simple RTZ and produced over seven columns.
Assuming that
Y
2
is equal to 1 every other time on average, the weight of this
redundancy is around
w
(
Y
2
)
7
M
2
≈
.Whenwemake
k
tend towards infinity via
≈
√
k
), the redundancy produced by one of
the two codes, for this type of pattern, also tends towards infinity. We then say
that the code is
good
.
The second pattern (b) is that of the minimum RTZ sequence of input weight
3. Here again, the redundancy is poor on the first dimension and much more
informative on the second. The conclusions are the same as above.
The other two diagrams in (c) present examples of multiple RTZ sequences,
made up of short RTZ sequences on each of the two dimensions. The input
weights are 6 and 9. The distances associated with these patterns (respectively
30 and 27 for this rate 1/3 code) are not generally sucient to ensure good
performance at low error rates. Moreover, these distances are independent of
block size and therefore, in relation to the patterns considered, the code is not
good
.
Regular permutation is therefore a good permutation for the class of simple
RTZ error patterns. For multiple RTZ patterns, however, regular permutation is
not appropriate. A good permutation must "break" the regularity of rectangular
composite patterns like those of Figure 7.6(c), by introducing some disorder.
But this must not be done to the detriment of the patterns for which regular
permutation is good. The disorder must therefore be managed well! Therein
lies the whole problem when looking for a permutation that must lead to a high
the values of
M
and
N
(
M
≈
N
