Globecom

Low-complexity chase-like bounded-distance decoding algorithms

Jos H. Weber

Published Apr 12, 2005• 10 citations

Abstract

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.

DOI: 10.1109/glocom.2003.1258509

Related papers

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 TheoryNov 30, 20048 citations

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 CommunicationsOct 1, 20091 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 TheoryFeb 26, 20093 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, 20130 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, 20044 citations

Limited-trial chase decoding

G. Arico, 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 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.

IEEE Transactions on Information TheoryNov 1, 200312 citations