Cryptography Reference
In-Depth Information
latter, very many constraint nodes, each node being made up of the simplest
linear code possible (parity code). Note that from this representation of the
bipartite graph, an infinite number of more or less exotic codes can be built.
It is interesting to note that encoding LDPC codes is tending to be performed
more and more like the encoding of turbo codes (in a serial concatenation).
The precursors were, without doubt, the
Repeat Accumulate
codes proposed in
[9.16] whose encoding is composed of a repetition code, an interleaver and an
accumulator. These codes are then decoded by an algorithm of the LDPC type
with an adapted schedule. In the literature, we can now find many variants
of this type of encoding, which involves combining elementary encoders and
interleavers.
Figure 9.7 - Representation of a turbo code in the form of a bipartite graph.
The similarity between turbo codes and LDPC codes is even greater than can
be assumed from the representations in the form of bipartite graphs. Indeed,
it is shown in [9.36], [9.44] and in Section 6.2 that it is possible to represent
a turbo code in the form of an LDPC matrix. The resemblance stops there.
Parity check matrix
H
of a turbo code contains many rectangular patterns (four
1s making a rectangle in matrix
H
), that is, many cycles of length 4, which make
the algorithms for decoding LDPC codes, to be described below, inecient.
9.1.4 Decoding LDPC codes
Decoding an LDPC code is done using the same principle as decoding a turbo
code by an iterative algorithm called a belief propagation algorithm. Each vari-
able node sends to the parity nodes with which it is associated a message about
the estimated value of the variable (
a priori
information). The set of
a priori
messages received enables the parity constraint to compute then return the ex-
trinsic information. The successive processing of the variable then parity nodes
make up one iteration. At each iteration, there is therefore a bilateral exchange
of messages between the parity nodes and variable nodes, on the arcs of the
bipartite graph representing the LDPC code. At the level of the receiver, the
