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

For the decoding of a binary linear block code of minimal Hamming distance d over additive white Gaussian noise (AWGN) channels, a soft-decision decoder achieves 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 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 only O(d ^1/2+epsiv) trials for any given positive number epsiv.