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

Limited-trial chase decoding

G. Arico, Jos H. Weber

Published Nov 1, 2003• 12 citations
Publisher

Abstract

Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance d. The least complex version of the original Chase algorithms uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels, this approach achieves asymptotically the same performance as maximum-likelihood (ML) decoding. In this correspondence, the performance of Chase-like decoders with even less trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a version which uses only about d/4 trials.

DOI
10.1109/tit.2003.818397

Related papers

Dynamic Chase decoding algorithm

C.B. Vicente, Jos H. Weber

Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance, d. The least complex version of the original Chase algorithms ("Chase-3") uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels (e.g., AWGN, Rayleigh fading), this approach achieves asymptotically the same performance as maximum likelihood decoding. The performance of Chase-like decoders with even fewer trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a dynamic version which uses only about d/8 trials.

IEEE Information Theory Workshop (ITW)•Mar 2, 2004•4 citations

Limited-Trial Chase-Like Algorithms Achieving Bounded-Distance Decoding

Jos H. Weber, M.P.C. Fossorier

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 O(d) trials of a conventional binary decoder. In this correspondence, we propose classes of Chase-like BD decoding algorithms of lower complexity than the original Chase-3 algorithm. In particular, the least complex members of these classes require only O(d/sup 2/3/) trials.

IEEE Transactions on Information Theory•Nov 30, 2004•8 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.

Globecom•Apr 12, 2005•10 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

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
Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance d. The least complex version of the original Chase algorithms uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels, this approach achieves asymptotically the same performance as maximum-likelihood (ML) decoding. In this correspondence, the performance of Chase-like decoders with even less trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a version which uses only about d/4 trials.
Chase decoders permit flexible use of reliability information in algebraic decoding algorithms for error-correcting block codes of Hamming distance, d. The least complex version of the original Chase algorithms ("Chase-3") uses roughly d/2 trials of a conventional binary decoder, after which the best decoding result is selected as the final output. On certain channels (e.g., AWGN, Rayleigh fading), this approach achieves asymptotically the same performance as maximum likelihood decoding. The performance of Chase-like decoders with even fewer trials is studied. Most strikingly, it turns out that asymptotically optimal performance can be achieved by a dynamic version which uses only about d/8 trials.
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 O(d) trials of a conventional binary decoder. In this correspondence, we propose classes of Chase-like BD decoding algorithms of lower complexity than the original Chase-3 algorithm. In particular, the least complex members of these classes require only O(d/sup 2/3/) trials.
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.
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.
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.