TY - GEN

T1 - Soft-decision list decoding with linear complexity for the first-order Reed-Muller codes

AU - Dumer, Ilya

AU - Kabatiansky, Grigory

AU - Tavernier, Cédric

PY - 2007

Y1 - 2007

N2 - Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM(1,m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj - cj. J taken over all n positions. We obtain a tight upper bound Lt on the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O(n ln2 L̂T). In particular, all possible error weights wj equal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM(1, m) and requires ö(nln2 n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4 - 1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed ε ∈ (0,1/2), our algorithm outputs the complete list of codewords within the decoding radius n(1/2-ε) with linear complexity of order n ln2 ε.

AB - Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM(1,m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj - cj. J taken over all n positions. We obtain a tight upper bound Lt on the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O(n ln2 L̂T). In particular, all possible error weights wj equal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM(1, m) and requires ö(nln2 n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4 - 1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed ε ∈ (0,1/2), our algorithm outputs the complete list of codewords within the decoding radius n(1/2-ε) with linear complexity of order n ln2 ε.

UR - http://www.scopus.com/inward/record.url?scp=51649125198&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2007.4557410

DO - 10.1109/ISIT.2007.4557410

M3 - Conference contribution

AN - SCOPUS:51649125198

SN - 1424414296

SN - 9781424414291

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1346

EP - 1349

BT - Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007

T2 - 2007 IEEE International Symposium on Information Theory, ISIT 2007

Y2 - 24 June 2007 through 29 June 2007

ER -