Cryptography Reference
In-Depth Information
Figure 9.9 -
Simple illustration of finite geometry
Kou, Lin and Fossorier's Euclidian / Projective Geometry LDPC
These LDPC codes are built on finite geometry [9.34]. Finite geometry is based
on
n
points and
m
rows, such that each row contains
k
points and each point
is on
j
lines. Two lines are either parallel or they have only one common point.
A parity check matrix
H
=(
h
ij
)
can be built by assuming that
h
ij
=1
if and
only if the
i
-th row contains the
j
-th point. Of course,
j
and
k
have to be small
compared to
m
and
n
in order to build an LDPC code that is called
type I
.An
example of simple finite geometry is illustrated in Figure 9.9.
These codes are cyclic. When considering the transposed version of
H
,we
can obtain quasi-cyclic LDPC codes which are referred to as
type II
codes.
Two kinds of finite geometry are used: Euclidean geometry (EG) and projective
geometry (PG).
Constructions based on permutation matrices
Tanner
et al.
have proposed an algebraic construction of LDPC parity-check
matrices based on an idea of Tanner [9.54]. A regular
(
j, k
)
code of length
n
=
kp
and
m
=
jp
parity checks can be obtained, assuming that
p
is a prime
number and
j, k
are chosen among the prime factors of
p
−
1
. The structure of
the parity check matrix is:
⎛
⎝
⎞
⎠
I
1
I
a
I
a
2
···
I
a
k−
1
I
b
I
ab
I
a
2
b
···
I
a
k−
1
b
H
=
.
.
.
.
.
.
.
I
b
j−
1
I
ab
j−
1
I
a
2
b
j−
1
···
I
a
k−
1
b
j−
1
where
I
x
is the identity matrix whose columns have been right-shifted
x
times,
and where
a
and
b
are two non-zero elements in
F
p
of order
j
and
k
respectively.
