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

International Symposium on Turbo Codes and Iterative Information Processing

Iterative multi-step decoding for a class of multi-step majority-logic decodable cyclic codes

Hsiu-Chi Chang, Hsie-Chia Chang

Published Aug 1, 2014• 0 citations
Publisher

Abstract

This paper presents an iterative multi-step decoding algorithm for a class of multi-step majority-logic (MS-MLG) decodable cyclic codes. The proposed algorithm is capable of efficient decoding the MS-MLG decodable cyclic codes with large number of short cycles of length 4. In addition, we decompose the parity-check matrices into several submatrices by utilizing the orthogonal structure of the codes. The decomposition scheme allows efficient decoding for MS-MLG decodable cyclic codes. Simulation results demonstrate that the MS-MLG decodable cyclic codes decoded with the proposed algorithm outperform BCH codes with similar lengths and rates decoded with the hard-decision algorithm.

DOI
10.1109/istc.2014.6955080

Related papers

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

An Iterative Weighted Reliability Decoding Algorithm for Two-Step Majority-Logic Decodable Cyclic Codes

Hsiu-Chi Chang, Chih-Lung Chen, Hsie-Chia Chang

An {iterative weighted reliability two-step majority logic decoding} (IWRTS-MLGD) algorithm for two-step majority-logic (TS-MLG)-decodable cyclic codes is presented. In contrast to other message passing decoding algorithms that utilize real number operations, our proposed decoding algorithm requires only logical operations and integer additions. Therefore, large computational complexities can be reduced. For moderate-length TS-MLG-decodable cyclic codes, the proposed algorithm aided with soft information and a scaling factor outperforms the hard-decision TS-MLGD algorithm and hard-decision BCH codes with similar length by 1.2- and 1.0-dB, respectively.

IEEE Communications Letters•Aug 29, 2013•3 citations

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

Iterative Decoding of L-step Majority-Logic Decodable Codes Based on Belief Propagation

Suquan Ding

Iterative decoding of L-step Majority-Logic decodable (LSMLD) codes based on belief propagation (BP) is presented. The orthogonal Tanner graph of LSMLD codes is derived based on the L-step orthogonalized parity checks. The BP decoding algorithm based on the orthogonal Tanner graph (BP-O) is also designed. As the orthogonal Tanner graph is sparse and free of 4- cycles, LSMLD codes perform well under BP-O decoding. Simulation results show that BP-O decoding of LSMLD codes achieves a good soft-decision decoding gain over hard-decision decoding and the performance of LSMLD codes under BP-O decoding is equally well as that of LDPC codes with the same block length and rate under BP decoding.

International Conference on Wireless Communications, Networking and Mobile Computing•Sep 1, 2007•0 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, 2010•4 citations

Iterative Soft-Decision Decoding of Binary Cyclic Codes

Marco Baldi, Giovanni Cancellieri, Franco Chiaraluce

Binary cyclic codes achieve good error correction performance and allow the implementation of very simpleencoder and decoder circuits. Among them, BCH codesrepresent a very important class of t-error correcting codes, with known structural properties and error correction capability. Decoding of binary cyclic codes is often accomplished through hard-decision decoders, although it is recognized that softdecision decoding algorithms can produce significant coding gain with respect to hard-decision techniques. Several approaches have been proposed to implement iterative soft-decision decoding of binary cyclic codes. We study the technique based on “extended parity-check matrices”, and show that such method is not suitable for high rates or long codes. We propose a new approach, based on “reduced parity-check matrices” and “spread parity-check matrices”, that can achieve better correction performance in many practical cases, without increasing the complexity.

Journal of Communications Software and Systems•Jun 22, 2008•3 citations
This paper presents an iterative multi-step decoding algorithm for a class of multi-step majority-logic (MS-MLG) decodable cyclic codes. The proposed algorithm is capable of efficient decoding the MS-MLG decodable cyclic codes with large number of short cycles of length 4. In addition, we decompose the parity-check matrices into several submatrices by utilizing the orthogonal structure of the codes. The decomposition scheme allows efficient decoding for MS-MLG decodable cyclic codes. Simulation results demonstrate that the MS-MLG decodable cyclic codes decoded with the proposed algorithm outperform BCH codes with similar lengths and rates decoded with the hard-decision algorithm.
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.
An {iterative weighted reliability two-step majority logic decoding} (IWRTS-MLGD) algorithm for two-step majority-logic (TS-MLG)-decodable cyclic codes is presented. In contrast to other message passing decoding algorithms that utilize real number operations, our proposed decoding algorithm requires only logical operations and integer additions. Therefore, large computational complexities can be reduced. For moderate-length TS-MLG-decodable cyclic codes, the proposed algorithm aided with soft information and a scaling factor outperforms the hard-decision TS-MLGD algorithm and hard-decision BCH codes with similar length by 1.2- and 1.0-dB, respectively.
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.
Iterative decoding of L-step Majority-Logic decodable (LSMLD) codes based on belief propagation (BP) is presented. The orthogonal Tanner graph of LSMLD codes is derived based on the L-step orthogonalized parity checks. The BP decoding algorithm based on the orthogonal Tanner graph (BP-O) is also designed. As the orthogonal Tanner graph is sparse and free of 4- cycles, LSMLD codes perform well under BP-O decoding. Simulation results show that BP-O decoding of LSMLD codes achieves a good soft-decision decoding gain over hard-decision decoding and the performance of LSMLD codes under BP-O decoding is equally well as that of LDPC codes with the same block length and rate under BP decoding.
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.
Binary cyclic codes achieve good error correction performance and allow the implementation of very simpleencoder and decoder circuits. Among them, BCH codesrepresent a very important class of t-error correcting codes, with known structural properties and error correction capability. Decoding of binary cyclic codes is often accomplished through hard-decision decoders, although it is recognized that softdecision decoding algorithms can produce significant coding gain with respect to hard-decision techniques. Several approaches have been proposed to implement iterative soft-decision decoding of binary cyclic codes. We study the technique based on “extended parity-check matrices”, and show that such method is not suitable for high rates or long codes. We propose a new approach, based on “reduced parity-check matrices” and “spread parity-check matrices”, that can achieve better correction performance in many practical cases, without increasing the complexity.