Cryptography Reference
In-Depth Information
6.3
Permutations
The functions of permutation or interleaving, used between elementary encoders
in a concatenated scheme, have a twofold role. On the one hand, they ensure, at
the output of each component decoder, a time spreading of the errors that can
be produced by it in bursts. These packets of errors then become isolated errors
for the following decoder, with far lower correlation effects. This technique for
the spreading of errors is used in a wider context than that of channel coding.
We can use it profitably, for example, to reduce the effects of more or less long
attenuation in transmissions affected by fading, and more generally in situations
where perturbations can alter consecutive symbols. On the other hand, in close
liaison with the characteristics of constituent codes, the permutation is designed
so that the MHD of the concatenated code is as large as possible. This is a
problem of pure mathematics associating geometry, algebra and combinatory
logic which, in most cases, has not yet found a definitive answer. Sections 7.3.2
and 9.1.6 develop the topic of permutation for turbo codes and graphs for LDPC
codes, respectively.
6.4
Turbo crossword
To end this chapter, here is an example of parallel concatenation that is familiar
to everyone: crosswords. The content of a grid has been altered during its
retranscription, as can be seen in Figure 6.7. Fortunately, we have a correct clue
for each line and for each column and we have at our disposal a dictionary of
synonyms.
Figure 6.7 - Crossword grid with wrong answers but correct clues.
To correct (or decode) this grid, we must operate iteratively by line and by
column. The basic decoding rule is the following: "If there is a word in the
dictionary, a synonym or an equivalent to the definition given that differs from
the word in the grid by at most one letter, then this synonym is adopted".
