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 Conference on Advanced Computer Science and Electronics Information (ICACSEI)

On Chase-Like Bound-Distance Decoding Algorithms

Ling bin Yan, Li rong Yu, Wei jia Lu, Hai Feng Xu, Yuan sheng Tang

Published Jan 1, 2013• 0 citations
Publisher

Abstract

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 

DOI
10.2991/icacsei.2013.60

Related papers

Chase-3-like algorithms achieving bounded-distance decoding

Tingsu Yan, Yuansheng Tang, Ming Chen

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.

International Workshop on Signal Design and its Applications in Communications•Oct 1, 2009•1 citation

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

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
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 
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.
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.