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

A Generalized Parity-Check Transformation for Iterative Soft-Decision Decoding of Binary Cyclic Codes

Oluwaseyi Paul Babalola, Olayinka Olaolu Ogundile, D.J.J. Versfeld

Published Dec 2, 2019• 4 citations
Publisher

Abstract

The conventional parity-check matrix transformation algorithm (PTA) requires matrix inversion to transform matrices of maximum distance separable (MDS) codes. However, such matrix transformation is not always guaranteed for the class of non-MDS codes. Hence, the PTA fails for binary cyclic (BC) codes. To overcome this limitation, we developed a generalized parity-check matrix transformation (GPT) algorithm for binary cyclic codes. The GPT avoids the matrix inversion step of the PTA. It permutes the columns of the parity-check matrix based on the reliability information from the channel. Results show a significant bit error rate (BER) performance gain as compared to the existing PTA. It also presents a reasonable BER performance as compared to the other soft-decision (SD) decoding algorithms. In addition, the decoder functions within a practical decoding time complexity, particularly at the message passing stage.

DOI
10.1109/lcomm.2019.2956935

Related papers

Iterative Soft-Decision Decoding of Binary Cyclic Codes Based on Extended Parity-Check Transformation Algorithm

Oluwaseyi Paul Babalola, D.J.J. Versfeld

In this paper, an iterative soft-decision (SD) decoding algorithm for cyclic codes based on extended parity-check equations is developed. The algorithm does not necessarily utilize the algebraic properties of the code, but operates on transforming the systematic parity-check matrix using the soft reliability information matrix obtained from the received vector. Results show a significant performance gain when compared with the hard decision Berlekamp-Massey(B-M) and belief propagation (BP) algorithms, but present a similar bit error rate (BER) performance when compared to the adaptive belief propagation (ABP) algorithm. An important feature of the decoder is that it functions within a practical decoding time complexity, and can be generally implemented for the class of linear block codes.

Conference proceedings - Canadian Conference on Electrical and Computer Engineering•May 1, 2018•3 citations

Iterative soft-decision decoding of binary cyclic codes based on spread parity-check matrices

Marco Baldi, Giovanni Cancellieri, Franco Chiaraluce

Binary cyclic codes achieve good error correction performance and allow the implementation of very simple encoder and decoder circuits. Among them, BCH codes represent 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 soft-decision 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 method, based on "Spread Parity-Check Matrices", that has the same complexity, but can achieve better correction performance in many practical cases.

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)•Jan 1, 2007•5 citations

Baseline parity‐check matrix for iterative soft‐decision decoding of binary cyclic codes

Oluwaseyi Paul Babalola, Olayinka Olaolu Ogundile, D.J.J. Versfeld

Belief propagation (BP) is a soft‐decision (SD) decoder that is commonly used to obtain near‐optimal decoding performance for linear codes defined over sparse parity‐check matrix. Nevertheless, the BP yields poor performance when used in the decoding of algebraic block codes, usually described by a dense parity‐check matrix. Hence, enhanced BP decoders transform the parity check matrix of such codes at each iteration for efficient decoding. In this article, the performance of the transformed parity‐check matrix of the iterative SD decoder is analysed for the class of binary cyclic codes using a perfect knowledge model (PKM). The PKM computes a list of candidate matrices and selects a baseline parity‐check matrix according to a distance metric. The selected matrix is optimal since it minimizes the probability of error over various choices in the list. Results show that, for a given channel condition, the conventional transformed matrix obtained by Gaussian elimination is sub‐optimal and does not necessarily contain unitary weighted columns at corresponding columns of the unreliable bits. Moreover, PKM can be used to verify the performances of newly developed iterative SD decoders for binary cyclic codes based on parity‐check equations instead of maximum‐likelihood decoding.

IET Communications•Apr 17, 2020•1 citation

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

A matrix-theoretic approach for analyzing quasi-cyclic low-density parity-check codes

Qiuju Diao, Qin Huang, Shu Lin +1 more

A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.

IEEE Transactions on Information Theory•Jan 18, 2012•82 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
The conventional parity-check matrix transformation algorithm (PTA) requires matrix inversion to transform matrices of maximum distance separable (MDS) codes. However, such matrix transformation is not always guaranteed for the class of non-MDS codes. Hence, the PTA fails for binary cyclic (BC) codes. To overcome this limitation, we developed a generalized parity-check matrix transformation (GPT) algorithm for binary cyclic codes. The GPT avoids the matrix inversion step of the PTA. It permutes the columns of the parity-check matrix based on the reliability information from the channel. Results show a significant bit error rate (BER) performance gain as compared to the existing PTA. It also presents a reasonable BER performance as compared to the other soft-decision (SD) decoding algorithms. In addition, the decoder functions within a practical decoding time complexity, particularly at the message passing stage.
In this paper, an iterative soft-decision (SD) decoding algorithm for cyclic codes based on extended parity-check equations is developed. The algorithm does not necessarily utilize the algebraic properties of the code, but operates on transforming the systematic parity-check matrix using the soft reliability information matrix obtained from the received vector. Results show a significant performance gain when compared with the hard decision Berlekamp-Massey(B-M) and belief propagation (BP) algorithms, but present a similar bit error rate (BER) performance when compared to the adaptive belief propagation (ABP) algorithm. An important feature of the decoder is that it functions within a practical decoding time complexity, and can be generally implemented for the class of linear block codes.
Binary cyclic codes achieve good error correction performance and allow the implementation of very simple encoder and decoder circuits. Among them, BCH codes represent 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 soft-decision 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 method, based on "Spread Parity-Check Matrices", that has the same complexity, but can achieve better correction performance in many practical cases.
Belief propagation (BP) is a soft‐decision (SD) decoder that is commonly used to obtain near‐optimal decoding performance for linear codes defined over sparse parity‐check matrix. Nevertheless, the BP yields poor performance when used in the decoding of algebraic block codes, usually described by a dense parity‐check matrix. Hence, enhanced BP decoders transform the parity check matrix of such codes at each iteration for efficient decoding. In this article, the performance of the transformed parity‐check matrix of the iterative SD decoder is analysed for the class of binary cyclic codes using a perfect knowledge model (PKM). The PKM computes a list of candidate matrices and selects a baseline parity‐check matrix according to a distance metric. The selected matrix is optimal since it minimizes the probability of error over various choices in the list. Results show that, for a given channel condition, the conventional transformed matrix obtained by Gaussian elimination is sub‐optimal and does not necessarily contain unitary weighted columns at corresponding columns of the unreliable bits. Moreover, PKM can be used to verify the performances of newly developed iterative SD decoders for binary cyclic codes based on parity‐check equations instead of maximum‐likelihood decoding.
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.
A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing 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.