Cryptography Reference
In-Depth Information
6-
∀
p
∈{
1
,
···
,m
}
faire : {Computation of the parity towards
variable message}
7-
J
(
p
)
:
Z
(
n
it
)
j,p
L
(
n
it
)
j,p
∀
j
∈
=
j
∈J
(
p
)
/j
The bits decoded are then estimated by sgn
L
(
n
it
j
.
It is interesting to note that it is possible to modify the algorithm by "order-
ing" the flooding schedule depending on the parity nodes. The latter are then
processed serially, and the algorithm becomes:
−
:
Z
(
n
it
+1)
j
∀
j
∈{
1
,
···
,n
}
3'-
=0
∀
p
∈{
1
,
···
,m
}
4'-
do:
5'- Computation of the input messages
L
(
n
it
)
j,p
=
I
j
+
Z
(
n
it
)
Z
(
n
it
−
1)
j,p
∀
j
∈
J
(
p
)
−
j
6'- Computation of the extrinsic information
Z
(
n
it
)
j,p
L
(
n
it
)
j,p
∀
j
∈
J
(
p
)
=
j
∈
J
(
p
)
/j
7'- Update for the following iteration
Z
(
n
it
+1)
j
=
Z
(
n
it
+1)
j
+
Z
(
n
it
)
j,p
∀
j
∈
J
(
p
)
A similar organization of computations for the variable nodes will be called
"distributed computation" since the computations linked with a variable node
will be distributed during one iteration. In Section 9.2, the different types of
schedule will be detailed then generalized.
It must also be noted that the notion of iteration (the computation of all
the messages of the graph once and only once) is not strict. Thus, Mao
et al.
[9.42] proposed a variant of the flooding schedule in order to limit the impact
of the effect of the cycles on the convergence. This variant, called "probabilis-
tic scheduling", involves not processing some variables at each iteration. The
choice of these variables is random and depends on the size of the smallest cycle
associated with this variable: the smaller the cycle, the lower the probability of
processing the variables involved in this cycle. This method limits phenomena
of self-confirmation introduced by short cycles. It enables convergence to be ob-
tained more rapidly than with the flooding schedule. The architectures linked
with this schedule will not be discussed in this chapter.
