TY - GEN

T1 - Soft-decision list decoding of Reed-Muller codes with linear complexity

AU - Dumer, Ilya

AU - Kabatiansky, Grigory

AU - Tavernier, Cédric

PY - 2011

Y1 - 2011

N2 - Let a binary Reed-Muller code RM(s,m) of length n be used on a memoryless channel with an input alphabet ±1 and a real-valued output ℝ. Given a received vector y in ℝn; we define its generalized distance T to any codeword c as the sum ∑|yj| taken over all positions j, in which vectors y, c have opposite signs. We then consider the list LT of codewords located within distance T from the received vector y and estimate the size LT of this list using the generalized Johnson bound. For any RM code RM(s,m) of fixed order s, the algorithm is proposed that performs list decoding beyond the error-correcting radius with linear complexity in length n and retrieves the code list LT with complexity of order nsL T for any decoding radius T within the generalized Johnson bound.

AB - Let a binary Reed-Muller code RM(s,m) of length n be used on a memoryless channel with an input alphabet ±1 and a real-valued output ℝ. Given a received vector y in ℝn; we define its generalized distance T to any codeword c as the sum ∑|yj| taken over all positions j, in which vectors y, c have opposite signs. We then consider the list LT of codewords located within distance T from the received vector y and estimate the size LT of this list using the generalized Johnson bound. For any RM code RM(s,m) of fixed order s, the algorithm is proposed that performs list decoding beyond the error-correcting radius with linear complexity in length n and retrieves the code list LT with complexity of order nsL T for any decoding radius T within the generalized Johnson bound.

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

U2 - 10.1109/ISIT.2011.6033973

DO - 10.1109/ISIT.2011.6033973

M3 - Conference contribution

AN - SCOPUS:80054805478

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2303

EP - 2307

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

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -