Tanner R. Michael. LDPC-коды основанные на квази-циклических блочных кодах
Подождите немного. Документ загружается.
ISIT 2002, Lausanne, Switzerland, June 30 – July 5, 2002
A Construction for Low Density Parity Check Convolutional
Codes Based on Quasi-Cyclic Block Codes
Arvind Sridharan, Daniel J. Costello Jr.,
Deepak Sridhara, Thomas E. Fuja
1
University of Notre Dame
IN 46556, U.S.A.
{asridhar, costello.2, dsridhar, tfuja}@nd.edu
R. Michael Tanner
Department of Computer Science
University of California, Santa Cruz
Santa Cruz, CA 95064, U.S.A.
tanner@cse.ucsc.edu
Abstract — A set of convolutional codes with low
density parity check matrices is derived from a class
of quasi-cyclic low density parity check block codes.
Their performance when decoded using the belief
propagation algorithm is investigated.
I. Introduction
Tanner designed a [155,64,20] sparse graph (LDPC) code
based on permutation matrices [1]. This construction can be
generalized to give a class of sparse graph (LDPC) codes [2],
well suited to decoding with the belief propagation (BP) algo-
rithm. These LDPC codes are quasi-cyclic and hence admit
a convolutional representation, obtained by unwrapping the
quasi-cyclic block code.
II. Code Construction
The quasi-cyclic codes constructed in [2] are (j, k) regular
LDPC codes, where j and k are among the prime factors of
m − 1, m a prime. Their parity check matrices consist of
blocks of circularly shifted identity matrices. Each circulant
matrix can equivalently be described by a polynomial. The
corresponding convolutional code is obtained by interpreting
the block code’s polynomial-form parity check matrix as the
analogous convolutional code construct, with the change in
the polynomials’ indeterminate to ’D’ as is the convention for
convolutional codes [3]. Thus, LDPC convolutional codes de-
scribed by j × k parity check matrices of the form
H(D) =
1 D
a−1
. . . D
a
k−1
−1
D
b−1
D
ab−1
. . . D
a
k−1
b−1
. . . . . . . . . . . .
D
b
j−1
−1
D
ab
j−1
−1
. . . D
a
k−1
b
j−1
−1
(j×k)
are obtained. Here a and b are non-zero elements of GF (m)
with multiplicative orders k and j respectively, and all
powers are taken modulo m, i.e., by D
a
p
b
q
−1
, we mean
D
(a
p
b
q
−1) mod m
.
III. Decoding and Simulation Results
The rate R = 1 − j/k LDPC convolutional codes constructed
in this fashion typically have large constraint lengths, which
makes the use of trellis based decoding impractical. Sequen-
tial decoding, although close to maximum likelihood, is com-
putationally feasible only for rates below the channel cut-off
rate. An alternative to these methods is decoding based on
graphs. The convolutional codes can be represented by con-
straint graphs, which are essentially the same as that of the
1
This work was supported in part by NSF Grant CCR00-75514,
NSF Grant CCC99-96222, NASA Grant NAG5-10503, and MIT
Lincoln Laboratory Grant CX-24535.
0.5 1 1.5 2 2.5 3
10
−7
10
−6
10
−5
10
−4
10
−3
10
−2
10
−1
10
0
Eb/No
Bit error rate
Performance of rate 2/5 LDPC convolutional codes with BP
[1055,424] QC code, 50 iters.
R = 2/5 conv code, 15 iters. ([1055,424])
R = 2/5 conv code, 50 iters. ([1055,424])
[2105,844] QC code,50 iters.
R = 2/5 conv code, 15 iters. ([2105,844])
R = 2/5 conv code, 50 iters. ([2105,844])
0.965
2.19
Threshold limit for (3,5) LDPCs Cut−off rate limit
quasi-cyclic code, but with the period of the quasi-cyclic code
extended to infinity. Hence, they are equally well suited to
decoding with the BP algorithm. Further, as in [4], the codes
can be decoded in a continuous fashion, so that after an ini-
tial delay decoding results are output continuously, an ad-
vantage derived from using the convolutional representation.
The above figure shows simulation results obtained for rate
R = 2/5 convolutional codes and the corresponding block
codes, with j = 3, k = 5. The (3, 5) block LDPC codes were
constructed by choosing primes, m = 211 and m = 421 re-
spectively, from which the convolutional codes were obtained
as described. The convolutional codes show good performance
beyond the cut-off rate limit with BP decoding. Interestingly,
they outperform their block code counterparts, which is pos-
sibly due to the higher free distance of the convolutional code.
Moreover, the sparse graph nature of these algebraically con-
structed codes makes them well suited for high speed VLSI
implementations.
References
[1] R. M. Tanner, “A [155,64,20] sparse graph (LDPC) code.” Pre-
sented at the recent results session, IEEE Intl. Symposium on
Information Theory, Sorrento, Italy, June 2000.
[2] D. Sridhara, T. Fuja, and R. M. Tanner, “Low density parity
check matrices from permutation matrices,” in Proceedings of
2001 Conference on Information Sciences and Systems, p. 142,
Johns Hopkins University, Baltimore, MD, March 2001.
[3] R. M. Tanner, “Convolutional codes from quasi-cyclic codes:
A link between the theories of block and convolutional codes.”
Technical Report, Computer Research Laboratory, UC Santa
Cruz, November 1987.
[4] A. J. Felstrom and K. S. Zigangirov, “Time-varying peri-
odic convolutional codes with low-density parity-check matrix,”
IEEE Transactions on Information Theory, vol. 45, pp. 2181–
2191, September 1999.