IEEE Transactions on Communications

Chase-type and GMD coset decodings

M.P.C. Fossorier, Shu Lin

Published Mar 1, 2000• 31 citations

Abstract

In this letter, Chase decoding algorithms are generalized into a family of bounded distance decoding algorithms, so that the conventional Chase algorithm-2 and Chase algorithm-3 become the two extremes of this family. Consequently, more flexibility in the tradeoffs between error performance and decoding complexity is provided by this generalization, especially for codes with large minimum distance. Finally this approach is extended to decoding with erasures.

DOI: 10.1109/26.837034

Related papers

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

Error performance analysis for reliability-based decoding algorithms

M.P.C. Fossorier, Shu Lin

The statistical approach proposed by Agrawal and Vardy (see ibid., vol.46, no.1, p.60-83, 2000) to evaluate the error performance of the generalized minimum distance (GMD) decoding is extended to other reliability-based decoding algorithms for binary linear block codes, namely Chase (1972) type, combined GMD and Chase type, and order statistic decoding (OSD). In all cases, tighter and simpler bounds than those previously proposed have been obtained with this approach.

IEEE Transactions on Information TheoryJan 1, 200262 citations

Low-complexity chase-like bounded-distance decoding algorithms

Jos H. Weber

A soft-decision decoder for an error-correcting block code of Hamming distance d is said to achieve bounded-distance (BD) decoding if its error-correction radius is equal to that of a complete Euclidean distance decoder. The Chase decoding algorithms are reliability-based algorithms achieving BD decoding. The least complex version of the original Chase algorithms ("Chase-3") uses about d/2 trials of a conventional binary decoder. In this paper, we propose two Chase-like decoding algorithms which also achieve BD decoding: a static method requiring about d/6 trials, and a dynamic method requiring only about d/12 trials. Hence, the complexity is reduced by factors of three and six, respectively, compared to the Chase-3 algorithm.

GlobecomApr 12, 200510 citations

Error performance analysis for reliability-based decoding algorithms

M.P.C. Fossorier, S. Liu

The statistical approach proposed by D. Agrawal and A. Vardy (see IEEE Trans. Inform. Theory, vol.46, pp.60-83, Jan. 2000) to evaluate the error performance of the generalized minimum distance (GMD) decoding is extended to other reliability based decoding algorithms for binary linear block codes, namely Chase-type, combined GMD and Chase-type, and ordered statistic decoding. In all cases, tighter and simpler bounds than previously proposed ones have been obtained with this approach.

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

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

Asymptotic optimality of the GMD and Chase decoding algorithms

Yuansheng Tang, Toru Fujiwara, Tadao Kasami

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.

IEEE Transactions on Information TheoryAug 1, 20029 citations