Decoding Reed-Muller Codes beyond Half the Minimum Distance

Agnes E. Heydtmann () and Thomas Jakobsen ()
Additional contact information
Agnes E. Heydtmann: Technical University of Denmark, Department of Mathematics
Thomas Jakobsen: IO Interactive APS

A chapter in Finite Fields and Applications, 2001, pp 232-250 from Springer

Abstract: Abstract Inspired by Sudan’s recent algorithm for Reed-Solomon codes we propose an efficient method for decoding r-th order Reed-Muller codes of length 2 m which can correct errors beyond half the minimum distance. This procedure involves interpolating $$ Q \in \mathbb{F}{_{2}}[{x_{1}},...,{x_{m}},y] $$ , a polynomial vanishing when evaluated at points in $$ \mathbb{F}_{2}^{m} $$ joint with the corresponding received bits. To obtain a list of codewords closest to the received word we need to factor Q considered as an element of the quotient ring of boolean polynomials which is not a unique factorization domain. Therefore we introduce a novel, yet simple polynomial-time factorization algorithm for multivariate boolean polynomials that produces generators for the coset of factors. Let p = 2−λ be the probability of algorithm failure and assume that the weights of a Reed-Muller code are approximately binomially distributed. This assumption is supported by known weight distributions for some short Reed-Muller codes. Then with probability at least 1 − p, the algorithm corrects $$ \tau \leqslant \mathop{{\max }}\limits_{{0 \leqslant \rho \leqslant m}} {\text{ min}}\left\{ {{2^{m}} - \sum\limits_{{i = 0}}^{{r + \rho }} {\left( {\begin{array}{*{20}{c}} m \\ i \\ \end{array} } \right) - \lambda ,\sum\limits_{{i = 0}}^{\rho } {\left( {\begin{array}{*{20}{c}} m \\ i \\ \end{array} } \right) - 1} } } \right\}{\text{ }} "$$ independently and uniformly distributed errors. For the RM(2, 9) code for example, the algorithm corrects up to 122 errors with probability at least 0.99 whereas half the minimum distance is 64. Under the above assumption, we can correct up to half the block length asymptotically for fixed r.

Keywords: Minimum Distance; Error Position; Block Cipher; Error Pattern; Quotient Ring (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-56755-1_19

Ordering information: This item can be ordered from
http://www.springer.com/9783642567551

DOI: 10.1007/978-3-642-56755-1_19

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().