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

Efficient Decoding of Short Length Linear Cyclic Codes

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

Published Jan 14, 2015• 5 citations
Publisher

Abstract

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.

DOI
10.1109/lcomm.2015.2392114

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

Multiple-Bases Belief-Propagation for Decoding of Short Block Codes

Thorsten Hehn, Johannes B. Huber, Stefan Laendner +1 more

A novel soft-decoding method for algebraic block codes is presented. The algorithm is designed for soft-decision decoding and is based on belief-propagation (BP) decoding using multiple bases of the dual code. Compared to other approaches for high-performance BP decoding, this method is conceptually simple and does not change at each stage of the decoding process. With its multiple BP decoders the proposed scheme achieves the performance of a standard BP algorithm with a significantly lower number of iterations per decoder realization. By this means the data delay introduced by decoding is reduced. Moreover, a significant improvement in decoding performance is achieved while keeping the data delay small. It is shown that for selected codes the proposed scheme approaches near maximum likelihood (ML) performance for very small data processing delays.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•48 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

An Iterative Soft-Decision Decoding Algorithm

Shu Wen Lin, Takuya Koumoto, Toyoo Takata +1 more

This paper presents a new minimum-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. Simulation results for the RM(64,22), EBCH(64,24), RM(64,42) and EBCH(64,45) codes show that the proposed decoding algorithm achieves practically (or near) optimal error performance with significant reduction in decoding computational complexity. The average number of search iterations is also small even for low signal-to-noise ratio.

•Jul 10, 1996•7 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

Multiple-bases belief-propagation decoding of high-density cyclic codes

Thorsten Hehn, Johannes B. Huber, Olgica Milenković +1 more

We introduce a new method for decoding short and moderate-length linear block codes with dense parity check matrix representations of cyclic form. This approach is termed multiple-bases belief-propagation. The proposed iterative scheme makes use of the fact that a code has many structurally diverse parity-check matrices, capable of detecting different error patterns. We show that this inherent code property leads to decoding algorithms with significantly better performance when compared to standard belief-propagation decoding. Furthermore, we describe how to choose sets of parity-check matrices of cyclic form amenable for multiple-bases decoding, based on analytical studies performed for the binary erasure channel. For several cyclic and extended cyclic codes, the multiple-bases belief propagation decoding performance can be shown to closely follow that of the maximum-likelihood decoder.

arXiv:0905.0079•IEEE Transactions on Communications•Jan 1, 2010•49 citations
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.
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.
A novel soft-decoding method for algebraic block codes is presented. The algorithm is designed for soft-decision decoding and is based on belief-propagation (BP) decoding using multiple bases of the dual code. Compared to other approaches for high-performance BP decoding, this method is conceptually simple and does not change at each stage of the decoding process. With its multiple BP decoders the proposed scheme achieves the performance of a standard BP algorithm with a significantly lower number of iterations per decoder realization. By this means the data delay introduced by decoding is reduced. Moreover, a significant improvement in decoding performance is achieved while keeping the data delay small. It is shown that for selected codes the proposed scheme approaches near maximum likelihood (ML) performance for very small data processing delays.
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.
We introduce a new method for decoding short and moderate-length linear block codes with dense parity check matrix representations of cyclic form. This approach is termed multiple-bases belief-propagation. The proposed iterative scheme makes use of the fact that a code has many structurally diverse parity-check matrices, capable of detecting different error patterns. We show that this inherent code property leads to decoding algorithms with significantly better performance when compared to standard belief-propagation decoding. Furthermore, we describe how to choose sets of parity-check matrices of cyclic form amenable for multiple-bases decoding, based on analytical studies performed for the binary erasure channel. For several cyclic and extended cyclic codes, the multiple-bases belief propagation decoding performance can be shown to closely follow that of the maximum-likelihood decoder.