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 Transactions on Information Theory

Error performance analysis for reliability-based decoding algorithms

M.P.C. Fossorier, Shu Lin

Published Jan 1, 2002• 62 citations
Publisher

Abstract

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.

DOI
10.1109/18.971758

Related papers

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, 2002•3 citations

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 Theory•Aug 1, 2002•9 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 Letters•May 1, 2001•57 citations

On the reliability-order-based decoding algorithms for binary linear block codes

Yuansheng Tang, San Ling, Fang‐Wei Fu

In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.

IEEE Transactions on Information Theory•Dec 28, 2005•8 citations

Chase-type and GMD coset decodings

M.P.C. Fossorier, Shu Lin

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.

IEEE Transactions on Communications•Mar 1, 2000•31 citations

Geometrical and performance analysis of GMD and Chase decoding algorithms

Eran Fishler, Ofer Amrani, Yair Be'ery

The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N/sub 0,eff/=N/sub 0/+N/sub BDD/. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N/sub BDD/ points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2/sup d-1/ less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2/sup [d/2]-1/, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.

IEEE Transactions on Information Theory•Jul 1, 1999•10 citations
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.
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.
In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.
The overall number of nearest neighbors in bounded distance decoding (BDD) algorithms is given by N/sub 0,eff/=N/sub 0/+N/sub BDD/. Where NBDD denotes the number of additional, non-codeword, neighbors that are generated during the (suboptimal) decoding process. We identify and enumerate the nearest neighbors associated with the original generalized minimum distance (GMD) and Chase (1972) decoding algorithms. After careful examination of the decision regions of these algorithms, we derive an approximated probability ratio between the error contribution of a noncodeword neighbor (one of N/sub BDD/ points) and a codeword nearest neighbor. For Chase algorithm 1 it is shown that the contribution to the error probability of a noncodeword nearest neighbor is a factor of 2/sup d-1/ less than the contribution of a codeword, while for Chase algorithm 2 the factor is 2/sup [d/2]-1/, d being the minimum Hamming distance of the code. For Chase algorithm 3 and GMD, a recursive procedure for calculating this ratio, which turns out to be nonexponential in d, is presented. This procedure can also be used for specifically identifying the error patterns associated with Chase algorithm 3 and GMD. Utilizing the probability ratio, we propose an improved approximated upper bound on the probability of error based on the union bound approach. Simulation results are given to demonstrate and support the analytical derivations.