Cryptography Reference
In-Depth Information
9.1.5 Random construction of LDPC codes
The construction of an LDPC code (or of a family of LDPC codes) must nat-
urally be done so as to optimize the performance of the code while minimizing
the hardware complexity of the associated decoder.
Building a code remains a delicate problem so we refer the reader wishing to
explore the subject further to the references given in this chapter. The problem
of building an LDPC code adapted to decoding hardware will be dealt with in
Section 9.2.
Optimizing an LDPC code is carried out in three steps:
•
a priori
optimization of the irregularity profiles of the parity and variable
nodes;
•
construction of matrices
H
of an adequate size respecting the irregularity
profile and maximizing the length of the cycles;
•
if necessary, selection or rejection of the codes using the minimum distance
criterion or the performance computed by simulation.
Optimization of irregularity profiles
We make the hypothesis of codes with infinite size and an infinite number of
iterations. Indeed, this enables optimization of their asymptotic characteristics
(irregularity profile, rate) as a function of the channel targeted. Two techniques
exist: the density evolution algorithm and its Gaussian approximation, and the
extrinsic information transfer chart.
The
density evolution
algorithm was proposed by Richardson [9.48]. This
algorithm calculates the probability density of messages
L
j,p
and
Z
j,p
after each
new iteration. The algorithm is initialized with the probability density of the
input samples, which depends on the level of noise
σ
2
of the channel. Using
this algorithm enables us to know the maximum value of
σ
2
below which the
algorithm converges, that is, such that the error probability is lower than a given
threshold. It is also possible to determine by linear programming an irregularity
profile that gives the lowest possible threshold.
A simplification of the density evolution algorithm proposed by Chung
et
al.
[9.14, 9.13], is obtained by approximating the real probability densities by
Gaussian densities. The interest of Gaussian density approximation is that it
suces to calculate the evolution of a single parameter by making the hypothesis
that these Gaussian densities are consistent, that is, the variance is equal to
two times the mean. Indeed, assuming that the "all zero"word was sent, at
initialization we have (
n
it
=0
):
N
1
,σ
2
2
r
j
σ
2
L
(0)
j,p
=
−
with
r
j
∼
−
(9.26)
