Reed-Muller Codes

Imagine sending a one-bit message across a very noisy channel. The obvious defense is repetition: send the bit many times and let the receiver take a majority vote. But repetition wastes bandwidth badly — you spend $n$ bits to carry 1 bit of information.

Reed-Muller codes, invented by David E. Muller in 1954 and decoded by Irving S. Reed the same year, found a far richer idea: instead of repeating a single bit, evaluate a multivariate polynomial over the binary field at every possible input point. A message of $k$ bits becomes the coefficients of a degree-$r$ polynomial in $m$ variables over $\mathbb{F}_2$; the codeword is the $2^m$-bit string you get by evaluating that polynomial at every point in $\{0,1\}^m$.

The magic is that two distinct degree-$r$ polynomials in $m$ variables agree on at most $r \cdot 2^{m-1}$ inputs — the rest differ. So even if a noisy channel flips many bits, the received word is still closer (in Hamming distance) to the correct codeword than to any other, and majority logic can recover it one coefficient at a time.

The special case $r = 1$ is the celebrated Hadamard code (also called the first-order Reed-Muller code), which evaluates a linear polynomial. The Voyager 1 and Voyager 2 spacecraft used it in the late 1970s to transmit photographs from Jupiter and Saturn across billions of kilometers of space.

The demo below works with RM(1, 3) — the first-order Reed-Muller code in $m = 3$ variables. Every message is a 4-bit vector $(a_0, a_1, a_2, a_3)$; the codeword evaluates the linear polynomial $f(x_1, x_2, x_3) = a_0 + a_1 x_1 + a_2 x_2 + a_3 x_3$ (all arithmetic mod 2) at all $2^3 = 8$ points of $\{0,1\}^3$.

Pick a message, introduce noise by clicking individual codeword bits, then press Decode to watch Reed's majority-logic algorithm vote the errors away.

<!-- {{c_demo_title}} -->
<div class="rm-demo">
  <div class="controls">
    <div class="msg-row">
      <span class="label">{{label_message}}</span>
      <div id="msg-bits" class="bit-row"></div>
      <button id="rand-btn" type="button" class="ghost-btn">{{btn_random}}</button>
    </div>
    <div class="cw-row">
      <span class="label">{{label_codeword}}</span>
      <div id="cw-bits" class="bit-row clickable" title="{{cw_click_hint}}"></div>
    </div>
    <div class="noise-row">
      <span class="label">{{label_errors}}</span>
      <span id="error-count">0</span>
    </div>
  </div>
  <div class="btn-row">
    <button id="decode-btn" type="button">{{btn_decode}}</button>
    <button id="reset-btn" type="button" class="ghost-btn">{{btn_reset}}</button>
  </div>
  <div id="result" class="result hidden"></div>
  <div id="steps" class="steps hidden"></div>
  <p class="hint-text">{{hint_text}}</p>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.rm-demo { padding: .5rem; max-width: 480px; }
.controls { display: flex; flex-direction: column; gap: .6rem; margin-bottom: .8rem; }
.msg-row, .cw-row, .noise-row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.label { font-size: .8rem; font-weight: 600; color: #555; min-width: 90px; }
.bit-row { display: flex; gap: 4px; flex-wrap: wrap; }
.bit {
  width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
  font: 700 15px ui-monospace, monospace; border-radius: 6px; user-select: none;
}
.bit.msg-bit { background: #dbeafe; color: #1e3a8a; border: 1px solid #93c5fd; }
.bit.cw-bit { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.bit.cw-bit.flipped { background: #fee2e2; color: #991b1b; border-color: #fca5a5; }
.clickable .bit { cursor: pointer; transition: background .1s; }
.clickable .bit:hover { filter: brightness(.93); }
#error-count { font: 700 15px ui-monospace; color: #b45309; }
.btn-row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
button {
  font: 600 13px system-ui; padding: .4rem .85rem; border-radius: 7px; cursor: pointer;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
}
button.ghost-btn { background: #fff; color: #1d3557; }
.result {
  font-size: .95rem; font-weight: 600; padding: .45rem .7rem; border-radius: 7px;
  margin-bottom: .6rem;
}
.result.ok { background: #dcfce7; color: #166534; }
.result.fail { background: #fee2e2; color: #991b1b; }
.hidden { display: none; }
.steps { font-size: .8rem; color: #444; border-top: 1px solid #e5e7eb; padding-top: .5rem; }
.steps p { margin: .2rem 0; }
.hint-text { font-size: .78rem; color: #666; margin-top: .6rem; line-height: 1.5; }

// Code not found

Notice: the code is a $[8, 4, 4]_2$ code — length 8, dimension 4, minimum distance 4 — so it can correct any single error (distance $\lfloor(4-1)/2\rfloor = 1$) and detect up to 3 errors. Flip two bits and it still decodes correctly; flip three and it may fail.

A Reed-Muller code RM(r, m) is defined by two parameters:

• $r$ — the maximum degree of the polynomial (the order).
• $m$ — the number of variables.

The resulting code has:

The minimum distance is the key insight. Two degree-$r$ polynomials that differ on even one coefficient must differ on at least $2^{m-r}$ inputs. That large gap is what makes majority voting work: Reed's algorithm decodes by computing $2^{m-1}$ inner-product tests for each coefficient $a_i$, and the majority of those tests tells you whether $a_i = 0$ or $1$ — even if up to $\lfloor(2^{m-r} - 1)/2\rfloor$ bits were flipped.

The total decoding complexity is $O(m \cdot 2^m)$, which is near-linear in the block length — a beautiful match between algebraic structure and algorithmic efficiency.

The extremes of the family are well-known codes:

• $\text{RM}(0, m)$ — the repetition code: one information bit, all-0 or all-1 codeword of length $2^m$.
• $\text{RM}(1, m)$ — the first-order / Hadamard code: evaluates a linear polynomial; distance $2^{m-1}$, corrects up to $2^{m-2} - 1$ errors.
• $\text{RM}(m-1, m)$ — the even-weight code: all codewords with even Hamming weight.
• $\text{RM}(m, m)$ — the trivial code: every binary string of length $2^m$ is a codeword.

Duality connects the ends: $\text{RM}(r, m)^{\perp} = \text{RM}(m - r - 1, m)$. This means the dual of the Hadamard code is a repetition code and vice versa — a striking algebraic symmetry.

Reed-Muller codes are also intimately linked to boolean satisfiability: the codeword of RM(1, m) is precisely the truth table of a linear Boolean function, and the minimum distance measures how far two Boolean functions can be from each other. This connection is exploited in the PAC learning framework when learning linear threshold functions.

Reed-Muller codes appear wherever strong, structured error correction is needed:

• Deep-space communication: NASA's Mariner 9 (1971) used RM(1, 5) — a $[32, 6, 16]_2$ code — to transmit images of Mars. Voyager 1 and 2 used a related Hadamard code for the iconic Jupiter and Saturn photographs.
• Wireless standards: RM codes underlie the control-channel encoding in 5G NR (New Radio). The Polar codes standardized in 5G are constructed by a pruning process on the RM generator matrix.
• Theoretical computer science: RM codewords are low-degree tests in disguise. The PCP theorem (Probabilistically Checkable Proofs) — which shows that every NP proof can be verified by reading only a constant number of bits — relies on low-degree polynomial tests that are essentially Reed-Muller encoding.
• Cryptography: the bent-function analysis that underlies the security of some stream ciphers uses the distance properties of RM codes.
• PAC learning: learning a noisy linear Boolean function from examples is equivalent to decoding a received RM(1, m) codeword — a direct algorithmic connection between learning theory and coding theory.

The story does not end at classic Reed-Muller codes: in 2016 Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry Pfister, Eren Sasoglu, and Rüdiger Urbanke proved that Reed-Muller codes achieve the Shannon capacity of the binary erasure channel, settling a long-standing conjecture.

Reed-Muller codes are one of the oldest families in coding theory, yet they keep appearing at the frontier. The key insight is almost embarrassingly simple: evaluate a low-degree polynomial everywhere, and two distinct polynomials must differ on many points — which means majority voting can always find the truth.

That geometric intuition — distance in Hamming space mirrors degree in polynomial space — connects error correction to algebra, to learning theory, to the PCP theorem, and now to the capacity of the binary erasure channel.

The next time you watch a decades-old photo of Jupiter's Great Red Spot transmitted by Voyager, remember: those pixels survived billions of kilometers of cosmic noise because Irving S. Reed realized in 1954 that polynomials vote better than repetition.