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

Ilya Dumer, Grigory Kabatiansky, Cédric Tavernier

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

Abstract

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 ln2T). 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 ε.

Original languageEnglish
Title of host publicationProceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007
Pages1346-1349
Number of pages4
DOIs
Publication statusPublished - 2007
Externally publishedYes
Event2007 IEEE International Symposium on Information Theory, ISIT 2007 - Nice, France
Duration: 24 Jun 200729 Jun 2007

Publication series

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

Conference

Conference2007 IEEE International Symposium on Information Theory, ISIT 2007
Country/TerritoryFrance
CityNice
Period24/06/0729/06/07

Fingerprint

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

Cite this