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 Information Theory Workshop (ITW)

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

Li Zhang, Qin Huang, Shu Lin

Published Jan 1, 2010• 0 citations
Publisher

Abstract

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.

DOI
10.1109/itwksps.2010.5503173

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

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 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

Efficient Decoding of Short Length Linear Cyclic Codes

Mohamed Ismail, Stojan Z. Denic, Justin P. Coon

Iterative soft decision decoding of linear block codes is a practical necessity when working with even modest block lengths. A number of algorithms have been proposed in the literature which use the permutation group of a code and the belief propagation (BP) algorithm for decoding. A novel soft-input, soft-output algorithm is presented that can be used for efficiently decoding of linear cyclic codes. Utilising the automorphism property of cyclic codes the permutation is incorporated into the belief propagation algorithm resulting in faster convergence and better error correcting performance. Performance of the new approach is analysed using a (63,45) BCH code and a (72,36) quadratic residue code. Simulation results show significant reduction in the average number of required decoding iterations and some improvement in error correcting performance over published algorithms.

IEEE Communications Letters•Jan 14, 2015•5 citations

Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

Cornelius T. Healy

Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.

•Jul 1, 2014•4 citations

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
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.
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.
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.
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.
Iterative soft decision decoding of linear block codes is a practical necessity when working with even modest block lengths. A number of algorithms have been proposed in the literature which use the permutation group of a code and the belief propagation (BP) algorithm for decoding. A novel soft-input, soft-output algorithm is presented that can be used for efficiently decoding of linear cyclic codes. Utilising the automorphism property of cyclic codes the permutation is incorporated into the belief propagation algorithm resulting in faster convergence and better error correcting performance. Performance of the new approach is analysed using a (63,45) BCH code and a (72,36) quadratic residue code. Simulation results show significant reduction in the average number of required decoding iterations and some improvement in error correcting performance over published algorithms.
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.