Cryptography Reference
In-Depth Information
A BIBD is said to be symmetric if
b
=
v
(or, equivalently,
r
=
k
).
These constructions have been widely studied in the literature. For example,
MacKay and Davey [9.37] first proposed the use of Steiner triple systems to
design short LDPC codes. Johnson and Weller [9.30, 9.31], and also B. Vasic
[9.60], presented a family of LDPC codes based on Kirkman triple systems.
A design based on anti-Pasch Steiner systems is also presented in [9.59], and
mutually orthogonal Latin rectangles (MOLR) are used in [9.61].
9.2
Architecture for decoding LDPC codes for
the Gaussian channel
When the belief propagation algorithm is implemented, the general architecture
of decoders for LDPC codes can be performed with the help of generic node pro-
cessors (GNP) modelling either the parity processing, or the variable processing.
This section describes the different possible implementations of these processors
after analysing the decoding complexity of LDPC codes. The different possibili-
ties for controlling this GNP-based architecture enables us to define three classes
of schedule for the belief propagation algorithm: a two-pass schedule, a "verti-
cal" schedule and a "horizontal" schedule. This original, unified presentation of
the architectures of decoders for LDPC codes enables us to cover many existing
architectures published so far, and to synthesize innovatory architectures.
9.2.1 Analysis of the complexity
The decoding complexity of LDPC codes is directly linked with the number of
branches in the bipartite graph of the code, or with the number of 1s in the
parity check matrix. The iterative decoding belief propagation algorithm has
twosteps. Ateachstep,wehavetocalculateinformation
L
j,p
or
Z
j,p
which is
associated with the branch linking variable
j
to parity
p
. Let us denote
B
the
number of branch in the bipartite graph of the LDPC code. For example, in the
case of a regular code
(
d
v
,d
c
)
of size
n
, the number of branches
B
is given by:
B
=
d
v
n
=
d
c
m
(9.29)
The computing power
P
c
necessary to decode LDPC codes is then defined
as the number of branches to process per clock cycle. This parameter depends
on:
•
the number
k
of information bits to transmit per codeword,
•
the number of branches
B
,
•
the data rate
D
of information desired,
•
the maximum number of iterations
N
it
,
