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

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

Yuansheng Tang, San Ling, Fang‐Wei Fu

Published Dec 28, 2005• 8 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2005.860451

Related papers

On Chase-Like Bound-Distance Decoding Algorithms

Ling bin Yan, Li rong Yu, Wei jia Lu +2 more

For the decoding of a binary linear block code of Hamming distance of d over AWGN channels, a soft-decision decoder is said to be bounded-distance (BD) decoding if its squared error-correction radius is equal to d .A Chase-like algorithm outputs the best (most likely) codeword in a list of candidates generated by a conventional algebraic binary decoder whose input vectors are determined by the reliability order of the hard-decisions.Let ) (d 

International Conference on Advanced Computer Science and Electronics Information (ICACSEI)•Jan 1, 2013•0 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

Generalization of chase algorithms for soft decision decoding of binary linear codes

Nandakumar Nityananda Tendolkar, Carlos R. P. Hartmann

Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require a\lfloor (d- 1)/2 \rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less than\lfloor ( d - 1)/2 \rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.

IEEE Transactions on Information Theory•Sep 1, 1984•29 citations

Asymptotically optimum soft decision decoding

Nandakumar Nityananda Tendolkar

This dissertation develops a set of new algorithms for soft decision decoding of binary linear block codes. The performance (i.e. the probability of error) of these algorithms is asymptotically optimum for high signal-to-noise ratio for binary linear block codes transmitted over the additive white gaussian (AWGN) channel using antipodal signalling. Among the algorithms proposed are the generalized Chase algorithms. In contrast to Chase algorithms, which require a {(d-1)/2} hard error-correcting decoder for decoding a binary linear block code of minimum distance d, the generalized Chase algorithms can use a binary decoder that can correct less than {(d-1)/2} hard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. Modified generalized Chase algorithm 2 and 3 are proposed for codes that have an overall parity check. These algorithms use fewer test patterns than the generalized Chase algorithms and they also have asymptotically optimum performance for high signal-to-noise ratio. The erasure information decoding algorithm of Tanaka and Kakigahara is generalized so that any hard decoder that corrects only up to t errors, 0 (LESSTHEQ) t (LESSTHEQ) {(d-1)/2} can be used to obtain asymptotically optimal performance for high signal-to-noise ratio. The modified erasure information decoding algorithm is proposed for codes that have an overall parity check. The modified erasure information decoding algorithm requires fewer test patterns than the erasure information decoding algorithm and its performance is also asymptotically optimum for high signal-to-noise ratio. The algorithms proposed by Dorsch and, Baumert and McEliece are analyzed to determine the conditions under which their performance would be asymptotically optimum for high signal-to-noise ratio. Simulation results for the (47,23) Quadratic Residue code are shown to demonstrate the performance of the algorithms. The results indicate that even for low signal-to-noise ratio the performance of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.

•Jan 1, 1983•1 citation

A unified method for evaluating the error-correction radius of reliability-based soft-decision algorithms for linear block codes

M.P.C. Fossorier, Shu Lin

This paper presents a unified method for evaluating the error-correction radii of many reliability-based soft-decision decoding algorithms for binary linear block codes. Based on this unified method, these decoding algorithms as well as their potential improvements can be compared directly. The error-correction radius for each of these decoding algorithms is determined by finding the closest point on the boundary of the decision region of the soft-decision decoder to the transmitted signal sequence. It is shown that this problem can be formulated as a constrained optimization problem. Although no general closed-form expression is possible, a simple algorithm that always converges to the optimum solution of this optimization problem is presented. Based on these results, the error-correction radii of some well-known reliability-based soft-decision decoding algorithms are revisited and compared.

IEEE Transactions on Information Theory•Mar 1, 1998•31 citations

A Note on Limited-Trial Chase-Like Algorithms Achieving Bounded-Distance Decoding

Yuansheng Tang, Xinmei Huang

For the decoding of a binary linear block code of minimal Hamming distancedover additive white Gaussian noise (AWGN) channels, a soft-decision decoder achieves bounded-distance (BD) decoding if its squared error-correction radius is equal tod. A Chase-like algorithm outputs the best (most likely) codeword in a list of candidates generated by a conventional algebraic binary decoder in a few trials. It is of interest to design Chase-like algorithms that achieve BD decoding with as least trials as possible. In this paper, we show that Chase-like algorithms can achieve BD decoding with onlyO(d1/2+epsiv) trials for any given positive numberepsiv.

IEEE Transactions on Information Theory•Feb 26, 2009•3 citations
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 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.
Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require a\lfloor (d- 1)/2 \rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less than\lfloor ( d - 1)/2 \rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.
This dissertation develops a set of new algorithms for soft decision decoding of binary linear block codes. The performance (i.e. the probability of error) of these algorithms is asymptotically optimum for high signal-to-noise ratio for binary linear block codes transmitted over the additive white gaussian (AWGN) channel using antipodal signalling. Among the algorithms proposed are the generalized Chase algorithms. In contrast to Chase algorithms, which require a {(d-1)/2} hard error-correcting decoder for decoding a binary linear block code of minimum distance d, the generalized Chase algorithms can use a binary decoder that can correct less than {(d-1)/2} hard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. Modified generalized Chase algorithm 2 and 3 are proposed for codes that have an overall parity check. These algorithms use fewer test patterns than the generalized Chase algorithms and they also have asymptotically optimum performance for high signal-to-noise ratio. The erasure information decoding algorithm of Tanaka and Kakigahara is generalized so that any hard decoder that corrects only up to t errors, 0 (LESSTHEQ) t (LESSTHEQ) {(d-1)/2} can be used to obtain asymptotically optimal performance for high signal-to-noise ratio. The modified erasure information decoding algorithm is proposed for codes that have an overall parity check. The modified erasure information decoding algorithm requires fewer test patterns than the erasure information decoding algorithm and its performance is also asymptotically optimum for high signal-to-noise ratio. The algorithms proposed by Dorsch and, Baumert and McEliece are analyzed to determine the conditions under which their performance would be asymptotically optimum for high signal-to-noise ratio. Simulation results for the (47,23) Quadratic Residue code are shown to demonstrate the performance of the algorithms. The results indicate that even for low signal-to-noise ratio the performance of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.
This paper presents a unified method for evaluating the error-correction radii of many reliability-based soft-decision decoding algorithms for binary linear block codes. Based on this unified method, these decoding algorithms as well as their potential improvements can be compared directly. The error-correction radius for each of these decoding algorithms is determined by finding the closest point on the boundary of the decision region of the soft-decision decoder to the transmitted signal sequence. It is shown that this problem can be formulated as a constrained optimization problem. Although no general closed-form expression is possible, a simple algorithm that always converges to the optimum solution of this optimization problem is presented. Based on these results, the error-correction radii of some well-known reliability-based soft-decision decoding algorithms are revisited and compared.
For the decoding of a binary linear block code of minimal Hamming distancedover additive white Gaussian noise (AWGN) channels, a soft-decision decoder achieves bounded-distance (BD) decoding if its squared error-correction radius is equal tod. A Chase-like algorithm outputs the best (most likely) codeword in a list of candidates generated by a conventional algebraic binary decoder in a few trials. It is of interest to design Chase-like algorithms that achieve BD decoding with as least trials as possible. In this paper, we show that Chase-like algorithms can achieve BD decoding with onlyO(d1/2+epsiv) trials for any given positive numberepsiv.