Cryptography Reference
In-Depth Information
Here it is not a concatenation in the sense that we defined above, since the
parity relations contain several redundancy variables and these variables appear
in several relations. We cannot therefore assimilate LDPC codes to standard
serial or parallel concatenation schemes. However, we can, like MacKay [6.5],
observe that a turbo code is an LDPC code. An RSC code with generator
polynomials
G
X
(
D
)
(recursivity) and
G
Y
(
D
)
(redundancy), whose input is
X
and redundant output
Y
, is characterized by the sliding parity relation:
G
Y
(
D
)
X
(
D
)=
G
X
(
D
)
Y
(
D
)
(6.2)
Using the tail-biting technique (see CRSC, Section 5.5.1, the parity check
matrix takes a very regular form, such as the one presented in Figure 6.6 for a
coding rate 1/2, and choosing
G
X
(
D
)=1+
D
+
D
3
and
G
Y
(
D
)=1+
D
2
+
D
3
.
A CRSC code is therefore an LDPC code since the check matrix is sparse. This
is certainly not a good LDPC code, as the check matrix does not respect certain
properties about the positions of the 1s. In particular, the 1s on a same line
are very close to each other, which is not favourable to the belief propagation
decoding method.
Figure 6.6 - Check matrix of a tail-biting convolutional code. A convolutional code,
particularly of the CRSC type, can be seen as an LDPC code since the check matrix
is sparse.
A parallel concatenation of CRSC codes, that is a turbo code, is also an
LDPC code since it associates elementary codes that are of the LDPC type. Of
course, there are more degrees of freedom in the construction of an LDPC code,
as each 1 of the check matrix can be positioned independently of the others. On
the other hand, decoding a convolutional code, via an algorithm based on the
trellis, does not encounter the problem of correlation between successive symbols
that a belief propagation type of decoding would encounter, if it was applied to
a simple convolutional code. A turbo code cannot therefore be decoded like an
LDPC code.
