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

International Workshop on Signal Design and its Applications in Communications

Chase-3-like algorithms achieving bounded-distance decoding

Tingsu Yan, Yuansheng Tang, Ming Chen

Published Oct 1, 2009• 1 citation
Publisher

Abstract

For the decoding of a binary block code of Hamming distance of d over AWGN channels, a soft-decision decoder is said to achieve bounded-distance (BD) decoding if its squared error-correction radius is equal to d. A Chase-3-like algorithm outputs the best (most likely) codeword in a list of candidates generated by a conventional algebraic binary decoder whose input sequences have nonzero entries confined in the most unreliable positions. Let ¿(d) denote the smallest size of input sequence sets of Chase-3-like algorithms which achieve BD decoding. In this paper, we show that there are positive numbers C1and C2such that C1¿ ¿(d)d-1/2¿ C2for sufficiently large d.

DOI
10.1109/iwsda.2009.5346444

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

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

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

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

A bounded-distance decoding algorithm for binary linear block codes achieving the minimum effective error coefficient

Ba-Zhong Shen, Kenneth K. Tzeng, Chun Wang

A new bounded-distance (BD) decoding algorithm is presented for binary linear (n, k, d) block codes on additive white Gaussian noise channels. The algorithm is based on the generalized minimum distance (GMD) decoding algorithm of Forney (1989) using the acceptance criterion of Taipale and Pursley (GMD/TP) proposed in 1991. It is shown that the GMD/TP decoding algorithm is a BD decoding algorithm with effective error coefficient (/sup n//sub d/). It is also shown that the decision regions of GMD/TP are good inner approximations of those of full GMD decoding, and therefore full GMD decoding is BD and has an effective error coefficient that is well approximated by (/sup n//sub d/). Moreover, by adding a d-erasure-correction step to GMD decoding, the effective error coefficient can be reduced to A/sub d/, the number of minimum-weight codewords, which is the same as the effective error coefficient of maximum-likelihood decoding. The decoding algorithm is mainly based on algebraic errors-and-erasures decoding and therefore has polynomial rather than exponential complexity.

IEEE Transactions on Information Theory•Jan 1, 1996•15 citations
For the decoding of a binary block code of Hamming distance of d over AWGN channels, a soft-decision decoder is said to achieve bounded-distance (BD) decoding if its squared error-correction radius is equal to d. A Chase-3-like algorithm outputs the best (most likely) codeword in a list of candidates generated by a conventional algebraic binary decoder whose input sequences have nonzero entries confined in the most unreliable positions. Let ¿(d) denote the smallest size of input sequence sets of Chase-3-like algorithms which achieve BD decoding. In this paper, we show that there are positive numbers C1and C2such that C1¿ ¿(d)d-1/2¿ C2for sufficiently large d.
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.
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.
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 new bounded-distance (BD) decoding algorithm is presented for binary linear (n, k, d) block codes on additive white Gaussian noise channels. The algorithm is based on the generalized minimum distance (GMD) decoding algorithm of Forney (1989) using the acceptance criterion of Taipale and Pursley (GMD/TP) proposed in 1991. It is shown that the GMD/TP decoding algorithm is a BD decoding algorithm with effective error coefficient (/sup n//sub d/). It is also shown that the decision regions of GMD/TP are good inner approximations of those of full GMD decoding, and therefore full GMD decoding is BD and has an effective error coefficient that is well approximated by (/sup n//sub d/). Moreover, by adding a d-erasure-correction step to GMD decoding, the effective error coefficient can be reduced to A/sub d/, the number of minimum-weight codewords, which is the same as the effective error coefficient of maximum-likelihood decoding. The decoding algorithm is mainly based on algebraic errors-and-erasures decoding and therefore has polynomial rather than exponential complexity.