Cryptography Reference
In-Depth Information
The iterations are repeated until the maximum number of iterations
N
it
is
reached. It is possible to stop the iterations before
N
it
when all the parity
equations are satisfied. This enables either a gain in mean throughput, or a
limit in consumption.
We call
L
j
the total information or the LLR of bit
j
. This is the sum of
the intrinsic information
I
i
and the total extrinsic information
Z
j
which is by
definition the sum of the extrinsic information of branches
Z
j,p
:
Z
j
=
p
Z
j,p
(9.24)
∈
P
(
j
)
We therefore have
L
j
=
I
j
+
Z
j
and Equation (9.23) can then be written:
L
j,p
=
L
j
−
Z
j,p
=
I
j
+
Z
j
−
Z
j,p
(9.25)
The BP algorithm is optimal in the case where the graph of the code does not
contain any cycle: all the schedules
1
give the same result. As LDPC codes
involve cycles, their decoding by the BP algorithm can lead to phenomena of
self-confirmation of the messages which degrade the convergence and make the
BP algorithm distinctly sub-optimal. However, these phenomena can be limited
if the cycles are large enough.
The first schedule proposed is called the "flooding schedule" [9.35].
It
involves successively processing all the parities then all the variables.
Flooding schedule algorithm
Initialization :
1-
n
it
=0
,
Z
(0)
j,p
J
(
p
)
,
I
j
=2
y
j
/σ
2
=0
∀
p
∀
j
∈
∀
j
Repeat until
n
it
=
N
it
or until the system has converged towards a code-
word :
2-
n
it
=
n
it
+1
3-
∀
j
∈{
1
,
···
,n
}
do: {Computation of the variable towards parity
messages}
4-
Z
(
n
it
)
j
=
p∈P
(
j
)
Z
(
n
it
−
1)
j,p
and
L
(
n
it
)
j
=
I
j
+
Z
(
n
it
)
j
5-
∀
p
∈
P
(
j
)
:
L
(
n
it
)
j,p
Z
(
n
it
−
1)
j,p
=
I
j
+
Z
(
n
it
)
j
Z
(
n
it
−
1)
j,p
=
I
j
+
−
p
∈
P
(
j
)
/p
1
By schedules, we mean the order in which each parity and each variable is processed.
