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+epsilon)) trials for any given positive number epsilon.
chase-like algorithm bounded-distance (bd) decoding algebraic binary decoder asymptotical optimality maximum-likelihood (ml) decoding reliability-order-based decoding algorithm (robda)