What Are Reed-Muller Codes?

Reed-Muller codes are a family of binary linear block error-correcting codes constructed from the evaluation of multivariate Boolean polynomials over a binary field. Introduced by David Muller and Irving Reed in 1954, they are among the oldest known families of error-correcting codes with a systematic mathematical structure and have served for decades as a testbed for coding theory ideas. An RM(r, m) code is defined by an order parameter r and a length parameter m, producing a codeword length of 2^m bits and a dimension of the sum of binomial coefficients from 0 to r. Their highly regular algebraic structure connects them to combinatorics, Boolean function analysis, and Fourier analysis over the binary hypercube.

Reed-Muller codes draw on finite field algebra, combinatorics, and information theory. They were used by NASA's Mariner 9 spacecraft in 1971 to transmit images of Mars, demonstrating practical utility in deep space communication. Renewed research interest in Reed-Muller codes arose after 2009 when connections to polar codes showed that RM codes and polar codes share the same generator matrix structure, differing only in which rows are selected.

Code Structure and Parameters

A first-order Reed-Muller code RM(1, m) has length 2^m, dimension m+1, and minimum Hamming distance 2^(m-1). Higher-order codes RM(r, m) are formed by adding all Boolean monomials of degree at most r, increasing the dimension at the cost of reduced minimum distance. The minimum distance of RM(r, m) is 2^(m-r), and this inverse relationship between order and distance gives designers a direct control over the error-correction capability. The dual of an RM(r, m) code is RM(m-r-1, m), a symmetric property that simplifies both analysis and decoding.

The recursive structure of Reed-Muller codes is particularly important: RM(r, m) can be expressed as the combination of RM(r, m-1) and RM(r-1, m-1), a decomposition that directly supports recursive decoding algorithms. This structure appears extensively in modern treatments such as the theory and algorithms survey on arXiv by Abbe, Shpilka, and Ye, which unifies classical results with recent breakthroughs on capacity achievement.

Decoding Methods

Classical decoding of Reed-Muller codes uses majority-logic decoding, which reads off the values of polynomial coefficients by majority vote over suitably chosen subsets of received bits. This algorithm has complexity linear in the block length and achieves bounded-distance decoding up to half the minimum distance. Recursive decoding based on the code's recursive structure improves performance: the Plotkin construction partitions each codeword into two halves, decodes each half separately, and combines the results.

List decoding and successive cancellation decoding approaches, borrowed from polar code theory, have brought Reed-Muller codes much closer to their theoretical performance limits. The paper Reed-Muller Codes Polarize in IEEE Transactions on Information Theory proved that Reed-Muller codes achieve capacity on binary erasure channels, settling a decades-old conjecture. Permutation-based decoding, which runs successive cancellation on multiple permutations of the factor graph and takes a majority vote, is one practical route to good error-correction performance without sacrificing the code's algebraic structure.

Relationship to Polar Codes

Reed-Muller codes and polar codes are generated by the same Kronecker product matrix, the m-fold tensor product of a 2-by-2 kernel matrix. RM codes select the 2^m rows with the highest Hamming weights; polar codes select rows based on channel reliability, choosing the positions with the highest bit-channel mutual information for the specific channel in use. This shared structure means that decoding algorithms for Reed-Muller and polar codes are largely interchangeable, and research on one code family regularly informs the other. The 5G NR standard adopted polar codes for the control channel, using their capacity-achieving properties on short blocks and their close connection to Reed-Muller codes.

Applications

Reed-Muller codes have applications in a wide range of disciplines, including:

• Deep space telemetry as used in NASA's Mariner and Voyager missions
• 5G NR control channel coding through their relationship to polar codes
• Quantum error correction in quantum Reed-Muller code constructions
• Cryptography and multiparty computation protocols based on RM code structure
• Combinatorial testing and experimental design exploiting their orthogonality properties
• Theoretical computer science proofs in property testing and circuit complexity