Cryptography Reference
In-Depth Information
in the cycle. The graph being bipartite, the size of the cycles is even. The
size of the shortest cycle in a graph is called the
girth
. The presence of cycles
in the graph may degrade the decoding performance by a phenomenon of self-
confirmation during the propagation of the messages. Figure 9.3 illustrates two
cycles of sizes 4 and 6.
Figure 9.3 - Cycles in a bipartite graph.
Low density parity check codes
LDPC codes are linear block codes, the term low density coming from the fact
that parity check matrix
H
contains a low number of non null values: it is
a
sparse
matrix. In the particular case of binary LDPC codes studied here,
the parity check matrix contains a small number of 1s. In other words, the
associated bipartite graph contains a small number of branches. The adjective
"low" mathematically means that when the length
n
of a codeword increases,
the number of 1s in the matrix increases in
O
(
n
)
(compared to an increase in
O
(
n
2
)
of the number of elements of the matrix if the rate remains fixed).
The class of LDPC codes generates a very large number of codes.
It is
convenient to divide them into two sub-classes:
•
regular LDPC codes
•
irregular LDPC codes
An LDPC code is said to be regular in the particular case where parity
check matrix
H
contains a constant number
d
c
of 1s in each row, and a constant
number
d
v
of 1s in each column. We then say that the variables are of degree
d
v
and that the parities are of degree
d
c
. The code is denoted a (
d
v
,
d
c
)regular
LDPC code. For example, the parity check matrix of a regular LDPC code
(3,6) contains only 3 non zero values in each column, and 6 non zero values in
each row. Figure 9.4 presents an example of a regular (3,6) code of size
n
= 256
obtained by drawing randomly the non zero positions. Out of the 256x128 inputs
of the matrix, only 3x256 are non zero, that is, around
2
.
3%
. This percentage
tends towards 0 if the size of the code, for a fixed rate, tends towards infinity.
The irregularity profile of the variables of an irregular LDPC code is defined
by the polynomial
λ
(
x
)=
λ
j
x
j−
1
where coecient
λ
j
is equal to the ratio
between the accumulated number of 1s in the columns (or variable) of degree
j
