Cryptography Reference
In-Depth Information
Matrices based on Pseudo random generators
An important drawback of random constructions is that the parity check ma-
trix has to be saved in memory, which takes up a lot of room for long codes.
Prabhakar and Narayanan [9.47] found an interesting solution to circumvent this
issue by using linear congruential sequences to design the parity-check matrix.
Hence, after a non-complex computation, the generator outputs the address
of the non-zero entries of the matrix. This solution has been implemented by
Verdier
et al.
[9.62]. Girths of at least
6
can be obtained by correctly choosing
the parameters of the generator.
Array-based LDPC
Array codes are two-dimensional codes that have been proposed for detecting
and correcting burst errors [9.6]. When viewed as binary codes, the parity check
matrix of array codes exhibit sparseness, which can be exploited for decoding
them as LDPC codes using the BP algorithm [9.19]. Therefore, array codes
provide the framework for defining a family of LDPC codes that lend themselves
to deterministic constructions [9.18]. The parity check matrix of an array-based
LDPC code is:
⎛
⎞
I
I
I
···
I
⎝
⎠
2
α
k−
1
I
α
···
H
=
.
.
.
.
.
.
.
Iα
j−
1
α
2(
j−
1)
α
(
j−
1)(
k−
1)
···
where
I
is the
p
p
identity matrix,
p
being an odd prime number,
α
is the
I
matrix whose rows have been shifted once, and
j, k
×
≥
p
.
BIBDs, Latin rectangles
A block design is an incidence system [9.63]
(
v, k, λ, r, b
)
in which a set
X
of
v
points is partitioned into a family
A
of
b
subsets (blocks) in such a way that
any two points determine
λ
blocks with
k
points in each block, and each point
is contained in
r
different blocks. It is also generally required that
k<v
,which
leads to a balanced incomplete block design (BIBD) of the LDPC code. The
five parameters are not independent, but satisfy the two relations
vr
=
bk
λ
(
v
−
1)
=
r
(
k
−
1)
A BIBD is therefore commonly simply written as
(
v, k, λ
)
,since
b
and
r
are
given in terms of
v
,
k
,and
λ
by
v
(
v
−
1)
λ
λ
(
v
−
1)
b
=
r
=
k
(
k
−
1)
k
−
1
