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 Decoding Algorithms for a Class of Non-Binary Two-Step Majority-Logic Decodable Cyclic Codes

Hsiu-Chi Chang, Hsie-Chia Chang

Published Apr 25, 2014• 1 citation
Publisher

Abstract

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.

DOI
10.1109/tcomm.2014.2320508

Related papers

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

Hsiu-Chi Chang, Hsie-Chia Chang

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.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2014•0 citations

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

An efficient architecture for iterative soft reliability-based majority-logic non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

Non-binary low-density parity-check (NB-LDPC) codes have better error-correcting performance than their binary counterparts at the cost of higher decoding complexity when the code length is moderate. Compared to other NB-LDPC decoding algorithms, the iterative reliability-based majority-logic decoding can achieve better performance-complexity tradeoff. In this paper, an efficient partial-parallel shift-message decoder architecture is proposed for cyclic NB-LDPC codes based on the iterative soft reliability-based majority-logic decoding (ISRB-MLGD) algorithm. The message shifting is implemented by memories concatenated with variable node units to reduce the area. Although the accumulated soft reliabilities in the ISRB algorithm require longer word length, and accordingly longer critical path and larger memory, the decoder architecture and control logic can be simplified. Particularly, the check node units are modified so that the message switching network can be eliminated. Compared to the iterative hard reliability-based decoder for a (255, 175) NB-LDPC code over GF(28), the proposed ISRB decoder can achieve around 0.8dB coding gain with less than three times hardware complexity.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2011•5 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
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.
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.
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.
Non-binary low-density parity-check (NB-LDPC) codes have better error-correcting performance than their binary counterparts at the cost of higher decoding complexity when the code length is moderate. Compared to other NB-LDPC decoding algorithms, the iterative reliability-based majority-logic decoding can achieve better performance-complexity tradeoff. In this paper, an efficient partial-parallel shift-message decoder architecture is proposed for cyclic NB-LDPC codes based on the iterative soft reliability-based majority-logic decoding (ISRB-MLGD) algorithm. The message shifting is implemented by memories concatenated with variable node units to reduce the area. Although the accumulated soft reliabilities in the ISRB algorithm require longer word length, and accordingly longer critical path and larger memory, the decoder architecture and control logic can be simplified. Particularly, the check node units are modified so that the message switching network can be eliminated. Compared to the iterative hard reliability-based decoder for a (255, 175) NB-LDPC code over GF(28), the proposed ISRB decoder can achieve around 0.8dB coding gain with less than three times hardware complexity.
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.