Cryptography Reference
In-Depth Information
tively small. These classes therefore offer only a very limited number of possible
size - rate - irregularity profile
combinations.
Summary
Table 9.1 summarizes the different possible types of coding encountered in the
literature. In practice, the conventional encoding of block codes by a generator
matrix is not used for LDPC codes due to the large the length of the codewords.
The codes obtained by projective or finite geometry cannot be optimized (opti-
mal design of the irregularity profiles). There therefore remain only codes built
to facilitate the encoding by solving the equation
cH
T
=0
by substitution, such
as the one chosen for the DVB-S2 standard.
Type of encoding
Complexity
Remarks
O(
n
2
)
Generator
matrix
∼
Not used in practice
Generic
Pseudo-linear
encoding
∼
O(
n
)
A lot of preprocessing
Solving
cH
T
=0
by
substitution
∼
O(
n
)
(si
δ
=0
)
Possible loss of
performance
Ad hoc
construction
∼
O(
n
)
Cyclic or
pseudo-cyclic
Limited number of
possible combinations of
the different parameters
Table 9.1 - Summary of the different possible encodings.
Analogy between an LDPC code and a turbo code
Figure 9.7 presents a turbo code in the form of a bipartite graph proposed by
Tanner [9.53], thus showing the very close relation which links the family of
turbo codes and that of LDPC codes.
In the case of a turbo code, the constraints are greater than in the case of
an LDPC code since elementary codes are convolutional codes. But in the same
way as for LDPC codes, a word is a codeword if and only if the two constraints
of the graph are respected. Note here that the degree of the bits of a turbo code
is two for the information bits and one for the redundancy bits.
Similarly, a product code can also be represented by a bipartite graph. The
number of constraint nodes is then
2
√
n
(compared with 2 for the turbo code
and
n/
2
foranLDPCcodewithrate0,5)andthelatterhaveanintermediate
complexity between that of the turbo code and that of the LDPC code. Turbo
codes and LDPC codes are thus the two extremities of the spectrum of "com-
posite" codes. The former contain only two very complex constraint nodes, the
