Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

On majority-logic decoding of finite geometry codes

Chin-Long Chen

Published May 1, 1971• 17 citations
Publisher

Abstract

In this paper, an improved decoding algorithm for codes that are constructed from finite geometries is introduced. The application of this decoding algorithm to Euclidean geometry (EG) and projective geometry (PG) codes is further discussed. It is shown that these codes can be orthogonalized in less than or equal to three steps. Thus, these codes are majority-logic decodable in no more than three steps. Our results greatly reduce the decoding complexity of EG and PG codes in most cases. They should make these codes very attractive for practical use in error-control systems.

DOI
10.1109/tit.1971.1054629

Related papers

Construction of New Finite Geometry Non-Binary LDPC Codes With Reduced Alphabets

Zakaria M’rabet, Fouad Ayoub, Mostafa Belkasmi +1 more

The finite Euclidean and Projective geometry codes are the most known among One-Step Majority-Logic Decodable codes that are Low-Density Parity-Check codes as well. Unfortunately, these codes are rare, and we do not have a great diversity when designing communication systems with a fixed code-length and code rate. Regarding the non-binary Euclidian and projective geometric Codes, each code is restricted to a unique alphabet. To offer a bigger range of possible alphabets for each code, we propose new construction by redefining the incidence vector of the lines of Euclidean and projective geometries over finite fields. This approach leads to an enrichment of the class of EG and PG codes. An error performance study of some new codes has been carried out and shows good results.

International Conference on Advanced Communication Technologies and Networking (CommNet)•Dec 11, 2023•1 citation

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 Communications•Dec 22, 2010•6 citations

Finite-Geometry LDPC Codes

W.E. Ryan, Shu Lin

Finite geometries, such as Euclidean and projective geometries, are powerful mathematical tools for constructing error-control codes. In the 1960s and 1970s, finite geometries were successfully used to construct many classes of easily implementable majority-logic decodable codes. In 2000, Kou, Lin, and Fossorier [1–3] showed that finite geometries can also be used to construct LDPC codes that perform well and close to the Shannon theoretical limit with iterative decoding based on belief propagation. These codes are called finite-geometry (FG) -LDPC codes. FG-LDPC codes form the first class of LDPC codes that are constructed algebraically. Since 2000, there have been many major developments in construction of LDPC codes based on various structural properties of finite geometries [4–18]. In this chapter, we put together all the major constructions of LDPC codes based on finite geometries under a unified frame. We begin with code constructions based on Euclidean geometries and then go on to discuss those based on projective geometries. Construction of LDPC Codes Based on Lines of Euclidean Geometries This section presents a class of cyclic LDPC codes and a class of quasi-cyclic (QC) LDPC codes constructed using lines of Euclidean geometries. Before we present the constructions of these two classes of Euclidean-geometry (EG)-LDPC codes, we recall some fundamental structural properties of a Euclidean geometry that have been discussed in Chapter 2.

Cambridge University Press eBooks•Sep 17, 2009•1 citation

Iterative majority logic decoding of a class of Euclidean Geometry codes

Andrew Thangaraj, S.W. McLaughlin

Hard decision decoding of low density parity check (LDPC) codes has potential applications in practical settings like data storage. For this purpose, it is important for the code to have an assured minimum distance and, hence, guaranteed error correction capability. In this paper, we show that with very high probability the guaranteed error correction capability of Euclidean geometry (EG) codes using threshold-optimized, iterative majority logic (ML) decoding is much greater than the usual single iteration ML decoding, making these codes much more attractive for hard decision decoding. For instance, the (262143, 242461, t/spl ges/256) EG code (a (512, 512)-regular LDPC code) can correct t=580 bit errors with probability better than 1-1/spl times/10/sup -58/.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•1 citation

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, 2010•4 citations

On the construction of a class of majority-logic decodable codes

Tadao Kasami, Shu Lin

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.

IEEE Transactions on Information Theory•Sep 1, 1971•6 citations
In this paper, an improved decoding algorithm for codes that are constructed from finite geometries is introduced. The application of this decoding algorithm to Euclidean geometry (EG) and projective geometry (PG) codes is further discussed. It is shown that these codes can be orthogonalized in less than or equal to three steps. Thus, these codes are majority-logic decodable in no more than three steps. Our results greatly reduce the decoding complexity of EG and PG codes in most cases. They should make these codes very attractive for practical use in error-control systems.
The finite Euclidean and Projective geometry codes are the most known among One-Step Majority-Logic Decodable codes that are Low-Density Parity-Check codes as well. Unfortunately, these codes are rare, and we do not have a great diversity when designing communication systems with a fixed code-length and code rate. Regarding the non-binary Euclidian and projective geometric Codes, each code is restricted to a unique alphabet. To offer a bigger range of possible alphabets for each code, we propose new construction by redefining the incidence vector of the lines of Euclidean and projective geometries over finite fields. This approach leads to an enrichment of the class of EG and PG codes. An error performance study of some new codes has been carried out and shows good results.
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.
Finite geometries, such as Euclidean and projective geometries, are powerful mathematical tools for constructing error-control codes. In the 1960s and 1970s, finite geometries were successfully used to construct many classes of easily implementable majority-logic decodable codes. In 2000, Kou, Lin, and Fossorier [1–3] showed that finite geometries can also be used to construct LDPC codes that perform well and close to the Shannon theoretical limit with iterative decoding based on belief propagation. These codes are called finite-geometry (FG) -LDPC codes. FG-LDPC codes form the first class of LDPC codes that are constructed algebraically. Since 2000, there have been many major developments in construction of LDPC codes based on various structural properties of finite geometries [4–18]. In this chapter, we put together all the major constructions of LDPC codes based on finite geometries under a unified frame. We begin with code constructions based on Euclidean geometries and then go on to discuss those based on projective geometries. Construction of LDPC Codes Based on Lines of Euclidean Geometries This section presents a class of cyclic LDPC codes and a class of quasi-cyclic (QC) LDPC codes constructed using lines of Euclidean geometries. Before we present the constructions of these two classes of Euclidean-geometry (EG)-LDPC codes, we recall some fundamental structural properties of a Euclidean geometry that have been discussed in Chapter 2.
Hard decision decoding of low density parity check (LDPC) codes has potential applications in practical settings like data storage. For this purpose, it is important for the code to have an assured minimum distance and, hence, guaranteed error correction capability. In this paper, we show that with very high probability the guaranteed error correction capability of Euclidean geometry (EG) codes using threshold-optimized, iterative majority logic (ML) decoding is much greater than the usual single iteration ML decoding, making these codes much more attractive for hard decision decoding. For instance, the (262143, 242461, t/spl ges/256) EG code (a (512, 512)-regular LDPC code) can correct t=580 bit errors with probability better than 1-1/spl times/10/sup -58/.
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.
The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.