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

Robert H. Morelos-Zaragoza

Published Jan 1, 2000• 5 citations

Abstract

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

Related papers

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 SystemsJun 22, 20083 citations

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 EngineeringMay 1, 20183 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, 20075 citations

A comparison of adaptive belief propagation and the best graph algorithm for the decoding of linear block codes

A. Kothiyal, O.Y. Takeshita

In this paper, two iterative message passing algorithms based on belief propagation proposed for the decoding of any binary linear block code are compared. The innovation of these algorithms lies in the fact that the structure of the graph of the parity check matrix is adaptively modified to render it suitable to belief propagation decoding. The modification is done such that the least reliable bits received from the channel are leaves of the graph. These algorithms perform favorably when compared with existing hard and iterative soft decision decoding algorithms in terms of error rate while maintaining a complexity polynomial in block length. It was found that while these two algorithms are conceptually similar, their performance in terms of word error rate (as a function of signal-to-noise ratio), decoding time (average number of iterations) and the updated bit reliabilities are very different

IEEE International Symposium on Information Theory (ISIT)Jan 1, 200517 citations

Iterative soft decoding of binary linear codes using a generalized Tanner graph

Eirik Rosnes

In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner graph. A generalized Tanner graph is constructed from the code's Tanner graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.

IEEE Information Theory Workshop (ITW)Oct 1, 20110 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 CommunicationsApr 17, 20201 citation