Cryptography Reference
In-Depth Information
1. The first mode - delayed update (Figure 9.11) - involves using an
accumulation register initialized to zero at each new iteration. This
register enables
E
(
n
it
+1)
=
e
(
n
it
i
to be calculated directly. This
architecture therefore has
d
+2
memory words,
d
for the inputs
(
e
(
n
it
−
1)
i
⊗
i
=1
..d
)
i
=1
..d
,awordfor
E
(
n
it
)
and a word for the accumulation
of
E
(
n
it
+1)
.
2. The second mode - immediate update - involves replacing the con-
tribution of
e
(
n
it
−
1)
i
in
E
(
n
it
)
by that of
e
(
n
it
)
i
as soon as a new input
e
(
n
it
)
i
arrives, that is:
e
(
n
it
−
1)
i
e
(
n
it
)
i
E
(
n
it
)
=
E
(
n
it
)
⊗
⊗
inv
⊗
(9.32)
At the end of the iteration, we thus have
E
(
n
it
+1)
=
E
(
n
it
)
.This
solution offers two advantages in relation to delayed updating:
•
one less memory word;
•
an acceleration in the convergence of the algorithm as the new
values of the inputs are taken into account sooner.
Choice of a generic operator
Figure 9.12 gives a "cross-section" view of the belief propagation algorithm on
the bipartite graph of the LDPC code. We assume that each branch is split into
two to differentiate the variable towards parity messages from the parity towards
variable messages. This view shows the great resemblance between processing
variables and processing the parities and enables us to imagine other positions
of the interconnection networks in the computation cycle. Each position of the
interconnection graph is thus translated by a different processing of the parity
nodes and the variable nodes. Table 9.2 gives the different computations to be
carried out according to the position of the interconnection network.
When the interconnection network is in position 1 (Table 9.2), we again have
the classical separation between a variable processor and a parity processor. The
latter can then either be performed in the frequency domain (as indicated in
Figure 9.11), or directly in the domain of the LLRs via the
⊕
operator defined
in equation (9.3).
9.2.3 Generic architecture for message propagation
Presentation of the model
PNPs and GNPs are characterized by their architecture and their generic opera-
tor, depending on the position of the interconnection network. The architecture
presented in Figure 9.13 enables the exchange of messages between these differ-
ent processors.
