Reed-Muller Codes: Error Correction Built From Boolean Polynomials

A code built from Boolean functions, not just bit patterns

Most error-correcting codes are described purely as sets of bit vectors. Reed-Muller codes, introduced independently by Muller in 1954 and Reed the same year, are unusual because they start from Boolean polynomials. The code RM(r, m) consists of every binary string that is the truth table of a Boolean function of m variables written as a polynomial of degree at most r — and Reed's contribution was a decoding algorithm, majority-logic decoding, that exploits that polynomial structure directly.

RM(r, m):  length n = 2^m,  dimension k = sum_(i=0..r) C(m, i),  min distance d = 2^(m-r)
RM(1, m):  the classic case — length 2^m, dimension m+1, distance 2^(m-1)

RM(1, m): first-order codes and the Hadamard connection

RM(1, m) encodes m+1 message bits — one constant bit plus m linear coefficients — into a length-2^m codeword by evaluating a degree-1 Boolean polynomial at every one of the 2^m input points. Every non-zero codeword differs from every other in exactly half its bits (distance 2^(m-1)), which makes RM(1,m) equivalent to an augmented Hadamard code. This is precisely the code NASA used on the Mariner 9 and Mariner deep-space probes in the early 1970s: RM(1,5), 32 bits encoding 6 message bits, chosen because its huge relative distance tolerated the very high bit-error rates of a weak interplanetary radio link.

Recursive structure: the |u|u+v| construction

Reed-Muller codes are built recursively from smaller ones via the |u|u+v| construction: given a codeword u from RM(r, m-1) and a codeword v from RM(r-1, m-1), the concatenation (u, u+v) is a valid codeword of RM(r, m). This doubles the length each time you go from m-1 to m, and it is exactly what makes both encoding and decoding tractable as fast recursive algorithms rather than brute-force table lookups — the same idea that underlies the fast Hadamard transform and, decades later, the construction of polar codes for 5G.

Majority-logic decoding: voting your way to the right bit

Reed's original decoder recovers each polynomial coefficient by constructing many different linear combinations of received bits that all, in a noise-free codeword, evaluate to the same coefficient — then takes a majority vote across all of them. Because a degree-r polynomial in m variables has a highly redundant structure, each coefficient can be checked by dozens or hundreds of independent parity sums, and as long as fewer than half of those sums are corrupted, the majority vote still recovers the correct bit. This lets RM(r,m) correct up to ⌊(d−1)/2⌋ = 2^(m-r-1) − 1 bit errors, with a decoder that is simple XOR-and-count arithmetic rather than the algebraic machinery Reed-Solomon or BCH codes require.

corrected bit = majority_vote( parity_sum_1, parity_sum_2, ..., parity_sum_k )
error tolerance:  t = 2^(m-r-1) - 1  bit flips, guaranteed correctable

Why RM codes still matter

Reed-Muller codes were largely superseded for deep-space and storage applications by Reed-Solomon and later LDPC and turbo codes, which pack more message bits per transmitted bit at the same error tolerance. But RM(1,m) never went away — it is mathematically identical to the first-order code used in CDMA spreading sequences, and the general RM(r,m) family reappeared prominently in 2016 as the near-optimal building block for polar codes, the channel codes standardised for 5G control channels. The recursive |u|u+v| structure that made 1950s majority-logic decoding practical is the same structure that makes modern successive-cancellation polar decoders fast.

Frequently asked questions

Try it live

Everything above runs in your browser — open Reed-Muller Codes and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.