IEEE International Symposium on Information Theory (ISIT)

An Algorithm For Soft Decoding Of Block Codes

Jan Nilsson

Published Aug 24, 2005• 1 citation

Abstract

A well known soft decoding algorithm that can make use of algebraic decoding techniques is the GMD algorithm introduced by Forney. This algorithm is based on several error-erasure decoding trails where unreliable positions are successively erased. Chase proposed a closely related family of algorithms for binary codes where unreliable positions are switched', i.e. different estimates for the positions are used in intermediate steps during the decoding process. In our algorithm, suitable for non binary codes, we try to combine erasures and switchings in a favourable way. A version of the algorithm comparable in complexity with the GMD algorithm is investigated. Simulations show that our algorithm in many cases has a somewhat better error correcting capability then the GMD algorithm.

DOI: 10.1109/isit.1991.695247

Related papers

Difference between two soft-decisiondecoding algorithms

Jan Nilsson

A relationship between two well-known soft-decision decoding algorithms is derived; the generalised minimum distance (GMD) algorithm and the Chase algorithm. The relation shows, in the case of soft-decision decoding of binary block codes, that the weakest third version of the Chase algorithm is more powerful than the GMD algorithm.

Electronics LettersSep 29, 19941 citation

with Threshold Erasing

Khaled A. S. Abdel-Ghaffarl, Jos H. Weber

The error-correction capability and the performance of generalized minimum distance decod- ing based on threshold erasing is studied as a function of the number of decoding trials and of the allowable reliability values. Generalized Minimum Distance (GMD) decoding, as intro- duced by Forney (l), is a multitrial decoding algorithm that combines reliability information, represented by numbers in the closed interval (0,1), with algebraic decoding algorithms for error correction. In each trial, a fixed number of the most unreliable symbols in the received sequence is erased. If a cer- tain distance criterion is satisfied, Forney has shown that the transmitted codeword can be retrieved in at most (d/2) trials, where d is the Hamming distance of the code. In this work, we study a variation on Forney's scheme where, in each trial, symbols whose reliabilities are below a certain threshold are erased, and hence there is no need to sort the received symbols according to reliability values be- fore erasing as in Forney's GMD decoding. Furthermore, we consider limiting the allowable reliability values to the set R, = u~=mo/2'{1 - 2i/m}, where m = 1,2,3,. . .. This covers the simple cases of taking only hard decisions (m = l), allow- ing erasures (m = 2), or accommodating the full range (0,1) of reliability values as in Forney's GMD decoding (m + 00). Limiting the reliability values may be of importance since, in any digital implementation, the reliability values need to be quantized. Moreover, in some applications, e.g., GMD decod- ing of concatenated codes over discrete channels, the reliabil- ity values are discrete in nature (2). The maximum number of trials is kept as a parameter. Limiting the reliability values and the number of trials leads to the concept of reduced GMD decoding.

Jan 1, 20010 citations

An improvement to GMD-like decoding algorithms

H. Tokushiga, Takuya Koumoto, Tadao Kasami

For binary linear block codes, we introduce a multiple generalized minimum distance (GMD) decoding algorithm, where GMD-like decoding is iterated around a few appropriately selected search centers. Compared with the original GMD decoding by Forney (1966), this decoding algorithm provides better error performance by increasing the number of iterations of erasure and error correction moderately. To reduce the number of iterations, we derive new effective sufficient conditions on the optimality of decoded codewords.

IEEE International Symposium on Information Theory (ISIT)Nov 7, 20022 citations

On combining Chase-2 and GMD decoding algorithms for nonbinary block codes

H. Tang, Y. Liu, M.P.C. Fossorier +1 more

In this letter, a class of algorithms that combines Chase-2 and GMD (generalized minimum distance) decoding algorithms is presented for nonbinary block codes. This approach provides additional trade-offs between error performance and decoding complexity. Reduced-complexity versions of the algorithms with practical interests are then provided and simulated.

IEEE Communications LettersMay 1, 200157 citations

Adaptive Combined Chase-GMD Algorithms for Block Codes

Ashraf M. Mahran, Mohammed Benaissa

This work proposes a new adaptive approach to the soft decision decoding of the so-called combined Chase-GMD class of algorithms (CGA). A reliability threshold is used to match the decoding performance to the channel conditions. As a result, a significant reduction in decoding complexity can be achieved by reducing the number of required algebraic decodings. The proposed adaptive application can achieve the upper performance limit of the CGA with significant complexity reduction.

IEEE Communications LettersApr 1, 20047 citations

Reduced GMD decoding of concatenated codes

Jos H. Weber, Khaled Abdel-Ghaffar

We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.

GlobecomNov 13, 20020 citations