Cryptography Reference
In-Depth Information
•
the clock frequency
f
clk
.
In one second, the number of codewords to process in order to obtain an infor-
mation data rate
D
is equal to
D/k
(words/second). In the worst case, decoding
a codeword requires computing
B
N
it
branches.Toguaranteeadatarate
D
,
an architecture must provide the power to compute
D
×
N
it
/k
branches
per second. The minimum computing power
P
c
to provide per clock cycle is
therefore:
×
B
×
BN
it
D
kf
clk
P
c
=
(
branches/cycle
)
(9.30)
Note that, for a fully parallel architecture in which each node of the graph is
associated with a processor, all the branches of the graph are processed in one
clock cycle. The computing power is then
(
P
c
)
max
=
B
. There is no practical
interest in trying to go beyond this power since the critical path then becomes
longer.
9.2.2 Architecture of a generic node processor (GNP)
The computations performed in a variable node processor (VNP) and in a parity
node processor (PNP) have an identical dependency between the inputs and the
outputs. Indeed, for both the PNP and VNP, the
d
outputs are calculated from
the
d
inputs, with the
i
-th output depending on all the inputs less the
i
-th input.
It is thus possible to represent the different processor architectures abstractly
by a generic node processor. The latter will then be specialized according to the
decoding algorithm used. The GNP therefore receives at its input
d
messages
(
e
i
)
i
=1
..d
and produces at its output
d
messages
(
s
j
)
j
=1
..d
defined by:
s
j
=
i
=
j
e
i
(9.31)
Operator
is a generic associative-commutative operator for computations,
whose implementation will be specified below. The condensed expression 9.31
means that the operator is applied to all the variables
e
i
for
i
⊗
=
j
.
Figure 9.10 illustrates the three main versions of GNP parallel architectures:
•
Direct architecture
: the computations of the
d
output messages are per-
formed independently (Figure 9.10(a)). The computations of the different
outputs can also be factorized. The number of
⊗
components traversed is
of the order of log
2
(
d
)
.
•
Trellis architecture (Forward-Backward type)
: This architecture corre-
sponds to a particular factorized form of parallel architecture which has
great regularity, but whose number of
⊗
operators is linear with
d
.
•
Total sum architecture
: this architecture is possible only if the generic op-
erator
⊗
allows an inverse denoted
inv
⊗
. In this case, the generic operator
