Cryptography Reference
In-Depth Information
9.1.2 Definition of an LDPC code
Linear block codes
Linear block codes (see Chapter 4) can be defined by a parity check matrix
H
of size
m
k
. This matrix can be seen as a linear system of
m
parity check equations. The words
c
ofthecodedefinedby
H
are the binary
words whose
n
bits simultaneously satisfy the
m
parity check equations. This
system of linear equations is represented graphically in Figure 9.2 for the case
of the Hamming binary block code of length
n
=7
.
×
n
,where
m
=
n
−
Figure 9.2 - Graphic representation of a block code: example of a Hamming code of
length 7.
Such a representation is called the
bipartite graph
of the code. In this graph,
branches link two different classes of nodes to each other:
•
The first class of nodes called
variable nodes
, correspond to the bits of the
codewords
(
c
j
,j
∈{
1
,
···
,n
}
)
, and therefore to the columns of
H
.
•
The second class of nodes, called
parity check nodes
, correspond to the
parity check equations
(
e
p
,p
∈{
1
,
···
,m
}
)
, and therefore to the rows of
H
.
Thus, to each branch linking a variable node
c
j
to a parity check node
e
p
corre-
sponds the 1 that is situated at the intersection of the
j
-th column and the
p
-th
row of the parity check matrix.
By convention, we denote
P
(
j
)
(respectively
J
(
p
)
) all the indices of the
parity nodes (respectively variable nodes) connected to the variable with index
j
(respectively to the parity with index
p
). We denote by
P
(
j
)
\
p
(respectively
J
(
p
)
j
)
all the
P
(
j
)
not having index
p
(respectively, all the
J
(
p
)
not having
index
j
)
. Thus, in the example of Figure 9.2, we have
\
P
(5) =
{
1
,
3
}
and
J
(1)
\
5=
{
4
,
6
,
7
}
A
cycle
on a bipartite graph is a path on the graph which makes it possible to
leave a node and to return to this same node without passing twice through the
same branch. The size of a cycle is given by the number of branches contained
