Cryptography Reference
In-Depth Information
n
, the number of information bits is then
k
=
n
−
m
and the coding rate is
R
=(
n
m/n
. Note that in the case where the
m
rows are not
independent (for example, two identical rows), the number of constrained bits
is lower than
m
.Wethenhave
R>
1
−
m
)
/n
=1
−
m/n
.
In the case of a regular LDPC code (
d
v
,
d
c
), each of the
m
rows has
d
c
non zero
values, that is, a total of
E
=
md
c
non zero values in matrix
H
. Symetrically,
each of the
n
columns contains
d
v
non zero values. We deduce from this that
E
satisfies
E
=
nd
v
=
md
c
,thatis,
m/n
=
d
v
/d
c
. The rate of such a code then
satisfies
R
−
d
v
/d
c
)
.
In the case of an irregular code, the expression of the rate is generalized,
taking into account each degree weighted by:
(1
−
p
ρ
p
/
p
j
λ
j
/
j
R
1
−
(9.15)
Equality is reached if matrix
H
is of rank
m
.
9.1.3 Encoding
Encoding an LDPC code can turn out to be relatively complex if matrix
H
does
not have a particular structure. There exist generic encoding solutions, including
an algorithm with complexity in
O
(
n
)
, requiring complex preprocessing on the
matrix
H
. Another solution involves directly building matrix
H
so as to obtain
a systematic code very simple to encode. It is this solution, in particular, that
was adopted for the standard DVB-S2 code for digital television transmission
by satellite.
Generic encoding
Encoding with a generator matrix
LDPC codes being linear block codes, the coding can be done via the gen-
erator matrix
G
of size
k
n
of the code, such as defined in Chapter 4. As
we have seen, LDPC codes are defined from their parity check matrix
H
,which
is generally not systematic. A transformation of
H
into a systematic matrix
H
sys
is possible, for example with the Gaussian elimination algorithm. This
relatively simple technique, however, has a major drawback: the generator ma-
trix
G
sys
of the systematic code is generally not sparse. The coding complexity
×
increases rapidly in
O
n
2
, which makes this operation too complex for usual
length codes.
Coding with linear complexity
Richardson
et al.
[9.49] proposed a solution enabling quasi-linear complexity
encoding, as well as
greedy
algorithms making it possible to preprocess parity
check matrix
H
. The aim of the preprocessing is to put
H
as close as possible
to a lower triangular form, as illustrated in Figure 9.5, using only permutations
