Reed-Muller codes for random erasures and errors

DOI10.1145/2746539.2746575MaRDI QIDQ2941518zbMATH OpenOpenAlexWikidataFDO

Authors Emmanuel Abbe, Amir Shpilka, A. Wigderson

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4590

zbMATH Keywords

channel capacitymultivariate polynomialsReed-Muller codesweight enumerator

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear codes (general theory) (94B05)

Abstract: This paper studies the parameters for which Reed-Muller (RM) codes over $GF(2)$ can correct random erasures and random errors with high probability, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate $GF(2)$ polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about $E(m,r)$, the matrix whose rows are truth tables of all monomials of degree $leqr$ in $m$ variables. What is the most (resp. least) number of random columns in $E(m,r)$ that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees $r$, which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code $C$ of sufficiently high rate we construct a new code $C^{\prime }$, also of very high rate, such that for every subset $S$ of coordinates, if $C$ can recover from erasures in $S$, then $C^{\prime }$ can recover from errors in $S$. Specializing this to RM codes and using our results for erasures imply our result on unique decoding of RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent cite{KLP} bounds from constant degree to linear degree polynomials.

Recommendations

• On the performance of Reed-Muller codes with respect to random errors and erasures
• Efficiently decoding Reed-Muller codes from random errors
• Reed-Muller Codes
• Reed-Muller codes achieve capacity on erasure channels
• scientific article; zbMATH DE number 1594297

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(17)

• Decoding of Reed-Muller codes with a large number of errors
• Recursive error correction for general Reed--Muller codes
• Trellis codes for periodic erasures
• Reed–Muller Codes for Random Erasures and Errors
• Using Reed–Muller ${\hbox{RM}}\,(1, m)$ Codes Over Channels With Synchronization and Substitution Errors
• Random-error correcting capability of the Iwadare codes and the Berlekamp-Preparata-Massey codes (Corresp.)
• Random codes: minimum distances and error exponents
• scientific article; zbMATH DE number 7434644 (Why is no real title available?)
• Erasures Repair for Decreasing Monomial-Cartesian and Augmented Reed-Muller Codes of High Rate
• On the bias of Reed-Muller codes over odd prime fields
• On the performance of Reed-Muller codes with respect to random errors and erasures
• Efficiently decoding Reed-Muller codes from random errors
• Reed-Muller codes achieve capacity on erasure channels
• Reed-Muller Codes
• Extremal eigenvalues of random kernel matrices with polynomial scaling
• Hadamard square of linear codes and the generalized minimal distance of Reed-Muller code of order 2
• Random matrices and codes for the erasure channel

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Reed-Muller codes for random erasures and errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941518)