IEEE International Symposium on Information Theory (ISIT)

A general class of LDPC finite geometry codes and their performance

Jun Jim Xu, Heng Tang, Yu Kou, Shu Lin, Khaled Abdel-Ghaffar

Published Jun 25, 2003• 9 citations

Abstract

We present a general class of finite geometry LDPC codes which perform well with iterative decoding although their Tanner graphs may contain many cycles of length 4. A hybrid two-stage decoding algorithm is proposed that combines iterative and multi-step majority-logic decodings to achieve good performance with low decoding complexity.

DOI: 10.1109/isit.2002.1023581

Related papers

Iterative Algorithms for Decoding a Class of Two-Step Majority-Logic Decodable Cyclic Codes

Li Guo Zhang, Qin Huang, Shu Lin

Codes constructed based on finite geometries form a large class of cyclic codes with large minimum distances which can be decoded with simple majority-logic decoding in one or multiple steps. In 2001, Kou, Lin and Fossorier showed that the one-step majority-logic decodable finite geometry codes form a class of cyclic LDPC codes whose Tanner graphs are free of cycles of length 4. These cyclic finite geometry LDPC codes perform very well over the AWGN channel using iterative decoding based on belief propagation (IDBP) and have very low error-floors. However, the standard IDBP is not effective for decoding other cyclic finite geometry codes because their Tanner graphs contain too many short cycles of length 4 which severely degrade the decoding performance. This paper investigates iterative decoding of two-step majority-logic decodable finite geometry codes. Three effective algorithms for decoding these codes are proposed. These algorithms are devised based on the orthogonal structure of the parity-check matrices of the codes to avoid or reduce the degrading effect of the short cycles of length 4. These decoding algorithms provide significant coding gains over the standard IDBP using either the sum-product or the min-sum algorithms.

IEEE Transactions on CommunicationsDec 22, 20106 citations

Iterative decoding of a class of cyclic codes

Li Guo Zhang, Qin Huang, Shu Lin

Among the classes of LDPC codes that have been constructed and designed, the only class of LDPC codes that are cyclic is the class of codes constructed based on the incidence vectors of lines of finite geometries, called finite geometry LDPC codes. Cyclic finite geometry LDPC codes are known to have large minimum distances and can provide good error performance with very low error-floors using iterative decoding based on belief propagation. Their cyclic structure allows them to be efficiently and systematically encoded with simple shift-registers in linear time with linear complexity. An obvious question is whether, besides cyclic finite geometry LDPC codes, there are other cyclic codes with large minimum distances that can be efficiently decoded iteratively using channel soft information. In this paper, we present one such class of cyclic codes. Codes in this class are two-step majority-logic decodable and they are also constructed based on finite geometries. Two iterative decoding algorithms are devised for this class of cyclic codes and they provide significant coding gain over the two-step majority-logic decoding of codes in this class.

Information Theory and Applications Workshop (ITA)Jan 1, 20104 citations

Codes on finite geometries

Heng Tang, Jun Xu, Shu Lin +1 more

New algebraic methods for constructing codes based on hyperplanes of two different dimensions in finite geometries are presented. The new construction methods result in a class of multistep majority-logic decodable codes and three classes of low-density parity-check (LDPC) codes. Decoding methods for the class of majority-logic decodable codes, and a class of codes that perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs, are presented. Most of the codes constructed can be either put in cyclic or quasi-cyclic form and hence their encoding can be implemented with linear shift registers.

IEEE Transactions on Information TheoryJan 24, 2005176 citations

Low-density parity-check codes based on finite geometries: a rediscovery and new results

Y. Kou, Shu Lin, M.P.C. Fossorier

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.

IEEE Transactions on Information TheoryJan 1, 20011,303 citations

On the stopping distance of finite geometry ldpc codes

Shu‐Tao Xia, Fang‐Wei Fu

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.

IEEE Communications LettersMay 1, 200629 citations

Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and More

Yu Kou, Shu Lin, M.P.C. Fossorier

Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.

Oct 20, 199989 citations