Cryptography Reference
In-Depth Information
Figure 7.17(b), during the odd cycles, the accesses to the reading-writing pages
are exchanged.
To further increase the degree of parallelism in the iterative decoder, the
forward and backward recursion operations can also be tackled inside each of the
two decoders (DEC1 and DEC2). This can be easily implemented by considering
the diagram of Figure 7.15.
Finally, depending on the permutation model used, the number of elemen-
tary decoders can be increased beyond two. Consider for example the circular
permutation defined by (7.14) and (7.16), with cycle
C
=4
and
k
a multiple
of 4.
The congruences of
j
and
Π(
j
)
modulo 4, are periodic. Parallelism with
degree 4 is then possible following the principle described in Figure 7.18 [7.17].
For each forward or backward recursion (these also can be done in parallel),
four processors are used. At the same instant, these processors process data
whose addresses have different congruences modulo 4. In the example in the
figure, the forward recursion is considered and we assume that
k/
4
is also a
multiple of 4. Then, we have first processor begin at address 0, the second at
address
k/
4+1
, the third at address
k/
2
+ 2 and finally the fourth at address
3
k/
4+3
. At each instant, as the processors advance by one place each time, the
congruences modulo 4 of the addresses are always different. Addressing conflicts
are avoided via a router that directs the four processors towards four memory
pages corresponding to the four possible congruences. If
k/
4
is not a multiple
of 4, the departure addresses are no longer exactly
0
,
k/
4+1
,
k/
2+2
,
3
k/
4+3
but the process is still applicable.
Figure 7.18 - The forward recursion circle is divided into 4 quadrants.
