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

Conference proceedings - Canadian Conference on Electrical and Computer Engineering

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

Oluwaseyi Paul Babalola, D.J.J. Versfeld

Published May 1, 2018• 3 citations
Publisher

Abstract

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.

DOI
10.1109/ccece.2018.8447536

Related papers

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

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

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.

IEEE Communications Letters•Dec 2, 2019•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

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

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

Architectural Issues of Soft-Decision Iterative Decoders for Binary Cyclic Codes

Robert H. Morelos-Zaragoza

The Tanner graph associated with an extended parity-check (EPC) matrix of a cyclic code is shown to be useful in effectively implementing soft decision iterativedecoding procedures based on belief propagation. Decoding with an EPC matrix has the advantage that is universal, in the sense that it does not depend on the specific family of cyclic codes being used. It is shown that there is no need to store the complete EPC matrix, i.e., the structure of the Tanner graph over which iterative decoding is implemented. The length, dimension and parity-check polynomial are all that is needed as input parameters to the decoder. Iterative soft decision decoding can be implemented with a pair of processing elements, to pass messages between nodes in the graph, with edges specified by the parity-check polynomial. By identifying received word positions with high reliability, using a designed threshold, decoding complexity can be reduced drastically while maintaining good error performance. Keywords --- Iterative decoding, cyclic codes, Tanner graphs. 1 1

•Jan 1, 2000•5 citations

Iterative reliability-based decoding of low-density parity check codes

M.P.C. Fossorier

In this paper, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between belief propagation decoding which remains suboptimum, and maximum likelihood decoding which is too complex to be implemented for the codes considered. Trade-offs between decoding complexity and error performance are also investigated. In particular, a stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is proposed for this combined decoding approach. Simulation results for several Gallager (1963, 1968) LDPC codes and different set cyclic codes of hundreds of information bits are given and elaborated.

IEEE Journal on Selected Areas in Communications•May 1, 2001•167 citations
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.
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.
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.
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.
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.
The Tanner graph associated with an extended parity-check (EPC) matrix of a cyclic code is shown to be useful in effectively implementing soft decision iterativedecoding procedures based on belief propagation. Decoding with an EPC matrix has the advantage that is universal, in the sense that it does not depend on the specific family of cyclic codes being used. It is shown that there is no need to store the complete EPC matrix, i.e., the structure of the Tanner graph over which iterative decoding is implemented. The length, dimension and parity-check polynomial are all that is needed as input parameters to the decoder. Iterative soft decision decoding can be implemented with a pair of processing elements, to pass messages between nodes in the graph, with edges specified by the parity-check polynomial. By identifying received word positions with high reliability, using a designed threshold, decoding complexity can be reduced drastically while maintaining good error performance. Keywords --- Iterative decoding, cyclic codes, Tanner graphs. 1 1
In this paper, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between belief propagation decoding which remains suboptimum, and maximum likelihood decoding which is too complex to be implemented for the codes considered. Trade-offs between decoding complexity and error performance are also investigated. In particular, a stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is proposed for this combined decoding approach. Simulation results for several Gallager (1963, 1968) LDPC codes and different set cyclic codes of hundreds of information bits are given and elaborated.