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

Author

Tang, Yuansheng ; Huang, Xinmei

Author_Institution

Coll. of Math. Sci., Yangzhou Univ., Yangzhou

Volume

55

Issue

3

fYear

2009

fDate

3/1/2009 12:00:00 AM

Firstpage

1047

Lastpage

1050

Abstract

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.

Keywords

AWGN channels; error correction codes; maximum likelihood decoding; additive white Gaussian noise channels; bounded-distance decoding; error-correction radius; limited-trial chase-like algorithms; reliability-order-based decoding algorithm; soft-decision decoder; AWGN; Additive white noise; Algorithm design and analysis; Block codes; Density functional theory; Error probability; Gaussian channels; H infinity control; Hamming distance; Maximum likelihood decoding; Algebraic binary decoder; Chase-like algorithm; asymptotical optimality; bounded-distance (BD) decoding; maximum-likelihood (ML) decoding; reliability-order-based decoding algorithm (ROBDA);

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2008.2011523

Filename

4787631