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

Ilya Dumer, Grigory Kabatiansky, Cédric Tavernier

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages2303-2307
Number of pages5
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: 31 Jul 20115 Aug 2011

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104

Conference

Conference2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/TerritoryRussian Federation
CitySt. Petersburg
Period31/07/115/08/11

Fingerprint

Dive into the research topics of 'Soft-decision list decoding of Reed-Muller codes with linear complexity'. Together they form a unique fingerprint.

Cite this