Cryptography Reference
In-Depth Information
When the redundant parts of the inner and outer codewords both undergo
supplementary encoding, the concatenation is said to be double serial concate-
nation. The most well-known example of this type of encoding structure is
the product code, which implements BCH codes (see Chapters 4 and 8). Mixed
structures, combining parallel and serial concatenations have also been proposed
[6.6]. Moreover, elementary concatenated codes can be of a different nature, for
example a convolutional code and a BCH code [6.2]. We then speak of hybrid
concatenated codes. From the moment elementary decoders accept and produce
weighted values, all sorts of mixed and/or hybrid schemes can be imagined.
Whilst SC can use systematic or non-systematic codes indifferently, parallel
concatenation uses systematic codes. If they are convolutional codes, at least
one of these codes must be recursive, for a fundamental reason to do with the
minimum input weight
w
min
, which is only 1 for non-recursive codes but is 2 for
recursive codes (see Chapter 5). To show this, see Figure 6.3 which presents two
non-recursive systematic codes, concatenated in parallel. The input sequence is
"all zero" (reference sequence) except in one position. This single "1" perturbs
the output of the encoder
C
1
for a short length of time, equal to the constraint
length 4 of the encoder. The redundant information
Y
1
is poor, in relation to
this particular sequence, as it contains only 3 values different from 0. After
permutation, of whatever type, the sequence is still "all zero", except in one
single position. Again, this "1" perturbs the output of the encoder
C
2
for a
length of time equal to the constraint length, and redundancy
Y
2
provided by the
second code is as poor in information as redundancy
Y
1
. In fact, the minimum
distance of this two-dimensional code is not higher than that of a single code,
with the same rate as that of the concatenated code. If we replace at least one
of the two non-recursive encoders by a recursive encoder, the "all zero" sequence
except in one position is no longer a "Return to Zero" (RTZ, see Section 5.3.2)
sequence for this recursive encoder, and the redundancy that it produces is thus
of much higher weight.
What we have explained above about the PC of non-recursive convolutional
codes suggests that the choice of elementary codes for the PC in general is
limited. As another example, let us build a parallel concatenated code from the
extended Hamming code defined by Figure 1.1 and the encoding Table 1.1. The
information message contains 16 bits, arranged in a 4x4 square (Figure 6.4(a)).
Each line and each column is encoded by the elementary Hamming code. The
horizontal and vertical parity bits are denoted
r
i,j
and
r
i,j
, respectively. The
global coding rate is 1/3. Decoding this type of code can be performed using the
principles of turbo decoding (optimal local decoding according to the maximum
likelihood and continuous exchanges of extrinsic information).
The MHD of the code is given by the pattern of errors of input weight 1
(Figure 6.4(b)). Whatever the position of the 1 in the information message,
the weight is 7. The figure of merit
Rd
min
(see Section 1.5) is therefore equal
to 7x(1/3), compared with the figure of merit of the elementary code 4x(1/2).
