Cryptography Reference
In-Depth Information
Specific constructions
Coding with a sparse generator matrix
One idea proposed by Oenning
et al.
[9.45] involves directly building a sparse
systematic generator matrix, so the coding is performed by simple multiplication
and the parity check matrix remains sparse. These codes are called Low-Density
Generator-Matrix (LDGM) codes. Their performance is however poor [9.36],
even if it is possible to optimize their construction [9.22] and lower the error
floor.
Encoding by solving the system
cH
T
=0
obtained by substitution
Mackay
et al.
[9.40] propose to constrain the parity matrix so that it is
composed of the three sub-matrices
A, B
and
C
arranged as in Figure 9.6.
Figure 9.6 - Specific construction of parity check matrix H facilitating the encoding.
Systematic encoding is performed by solving Equation (9.16), which means
solving (
n
δ
) equations by substitution. Each row of the parity matrix
containing a low number of 1s, this operation is linear with
n
. The remaining
δ
equations are solved by inversion of matrix
C
defined in Figure 9.4. That
leads to multiplication by a non-sparse matrix and therefore a complexity in
−
k
−
O
δ
2
.Bond
et al.
[9.7] and Hu
et al.
[9.29] have proposed building parity
check matrices with
δ
=0
. In [9.25] Haley
et al.
define a class of codes enabling
equation 9.12 to be solved by an iterative algorithm similar to the one used for
the decoding.
Cyclic coding
The classes of LDPC codes defined by finite geometry or by projective ge-
ometry [9.29, 9.46, 9.34, 9.1, 9.58] enable cyclic or pseudo-cyclic codes to be
obtained (see Section ?? for further details about this type of construction).The
codes thus obtained can be encoded eciently by using shift registers. In ad-
dition, they offer good properties in terms of the distribution of cycle length
(
6
). The main drawback is that the cardinal of these classes of code is rela-
