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 Communications

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

Li Guo Zhang, Qin Huang, Shu Lin

Published Dec 22, 2010• 6 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2010.120710.090624

Related papers

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

Two-stage iterative decoding algorithms for a class of cyclic codes

Li Zhang, Qin Huang, Shu Lin

This paper presents a class of iteratively decodable cyclic codes. Codes in this class have large minimum distance; however, their Tanner graphs contain many short cycles of length 4. With the conventional iterative decoding based on belief propagation, these short cycles significantly degrade the error performance of the codes. To avoid the degrading effect of these short cycles in performance, two-stage iterative decoding algorithms are devised. Cyclic codes have encoding advantage over other linear block codes. Encoding of a cyclic code in systematic form can be implemented with a single feedback shift-register.

IEEE Information Theory Workshop (ITW)•Jan 1, 2010•0 citations

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

Hsiu-Chi Chang, Hsie-Chia Chang

This paper presents two iterative decoding algorithms for a class of non-binary two-step majority-logic (NB-TS-MLG) decodable cyclic codes. A partial parallel decoding scheme is also introduced to provide a balanced trade-off between decoding speed and storage requirements. Unlike non-binary one-step MLG decodable cyclic codes, the Tanner graphs of which are 4-cycle-free, NB-TS-MLG decodable cyclic codes contain a large number of short cycles of length 4, which tend to degrade decoding performance. The proposed algorithms utilize the orthogonal structure of the parity-check matrices of the codes to resolve the degrading effects of the short cycles of length 4. Simulation results demonstrate that the NB-TS-MLG decodable cyclic codes decoded with the proposed algorithms offer coding gains as much as 2.5 dB over Reed-Solomon codes of the same lengths and rates decoded with either hard-decision or algebraic soft decision decoding.

IEEE Transactions on Communications•Apr 25, 2014•1 citation

A general class of LDPC finite geometry codes and their performance

Jun Jim Xu, Heng Tang, Yu Kou +2 more

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•9 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 Theory•Jan 24, 2005•176 citations

Near Optimum Majority-Logic Based Decoding of Low-Density Parity-Check Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.

International Conference on Communications•Jun 1, 2011•3 citations
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.
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.
This paper presents a class of iteratively decodable cyclic codes. Codes in this class have large minimum distance; however, their Tanner graphs contain many short cycles of length 4. With the conventional iterative decoding based on belief propagation, these short cycles significantly degrade the error performance of the codes. To avoid the degrading effect of these short cycles in performance, two-stage iterative decoding algorithms are devised. Cyclic codes have encoding advantage over other linear block codes. Encoding of a cyclic code in systematic form can be implemented with a single feedback shift-register.
This paper presents two iterative decoding algorithms for a class of non-binary two-step majority-logic (NB-TS-MLG) decodable cyclic codes. A partial parallel decoding scheme is also introduced to provide a balanced trade-off between decoding speed and storage requirements. Unlike non-binary one-step MLG decodable cyclic codes, the Tanner graphs of which are 4-cycle-free, NB-TS-MLG decodable cyclic codes contain a large number of short cycles of length 4, which tend to degrade decoding performance. The proposed algorithms utilize the orthogonal structure of the parity-check matrices of the codes to resolve the degrading effects of the short cycles of length 4. Simulation results demonstrate that the NB-TS-MLG decodable cyclic codes decoded with the proposed algorithms offer coding gains as much as 2.5 dB over Reed-Solomon codes of the same lengths and rates decoded with either hard-decision or algebraic soft decision decoding.
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.
A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.