Introduction

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 nn 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 kk bits becomes the coefficients of a degree-rr polynomial in mm variables over F2\mathbb{F}_2; the codeword is the 2m2^m-bit string you get by evaluating that polynomial at every point in {0,1}m\{0,1\}^m.

The magic is that two distinct degree-rr polynomials in mm variables agree on at most r⋅2m−1r \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=1r = 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.

Decode by Voting

The demo below works with RM(1, 3) — the first-order Reed-Muller code in m=3m = 3 variables. Every message is a 4-bit vector (a0,a1,a2,a3)(a_0, a_1, a_2, a_3); the codeword evaluates the linear polynomial f(x1,x2,x3)=a0+a1x1+a2x2+a3x3f(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 23=82^3 = 8 points of {0,1}3\{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.

<!-- Reed-Muller RM(1,3) interactive majority-logic decoder -->
<div class="rm-demo">
  <div class="controls">
    <div class="msg-row">
      <span class="label">Message (4 bits):</span>
      <div id="msg-bits" class="bit-row"></div>
      <button id="rand-btn" type="button" class="ghost-btn">New message</button>
    </div>
    <div class="cw-row">
      <span class="label">Codeword (8 bits):</span>
      <div id="cw-bits" class="bit-row clickable" title="Click a codeword bit to flip it (introduce noise)"></div>
    </div>
    <div class="noise-row">
      <span class="label">Errors introduced:</span>
      <span id="error-count">0</span>
    </div>
  </div>
  <div class="btn-row">
    <button id="decode-btn" type="button">Decode</button>
    <button id="reset-btn" type="button" class="ghost-btn">Reset noise</button>
  </div>
  <div id="result" class="result hidden"></div>
  <div id="steps" class="steps hidden"></div>
  <p class="hint-text">Click any green codeword bit to flip it and introduce noise. RM(1,3) can correct 1 error; try flipping 1, 2, or 3 bits and see how decoding fares.</p>
</div>

/* Styles for the Reed-Muller majority-logic decoder demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Reed-Muller RM(1,3) majority-logic decoder demo
// RM(1,3): length 8, dimension 4, min distance 4 — corrects 1 error, detects up to 3
// Encode: evaluate f(x1,x2,x3) = a0 + a1*x1 + a2*x2 + a3*x3 (mod 2) at all 8 binary points

// All 8 points in {0,1}^3, enumerated in binary order
const POINTS = [];
for (let i = 0; i < 8; i++) {
  POINTS.push([(i>>2)&1, (i>>1)&1, i&1]);
}

// Encode a 4-bit message as a RM(1,3) codeword (length 8)
function encode(msg) {
  // msg = [a0, a1, a2, a3]
  // Evaluate the linear polynomial f = a0 + a1*x1 + a2*x2 + a3*x3 (mod 2)
  return POINTS.map(([x1, x2, x3]) =>
    (msg[0] ^ (msg[1] & x1) ^ (msg[2] & x2) ^ (msg[3] & x3)) & 1
  );
}

// Majority-logic decode a (possibly noisy) received word back to a 4-bit message
// Reed's algorithm: decode each linear coefficient a1..a3 first, then a0
function decode(received) {
  const log = [];
  const est = [0, 0, 0, 0]; // estimated message bits

  // Decode a1, a2, a3 using coordinate differences (XOR with standard basis vector)
  // a1: majority over pairs (i, i XOR e1) where e1 = (0,0,1) -> index 1
  // a2: majority over pairs (i, i XOR e2) where e2 = (0,1,0) -> index 2
  // a3: majority over pairs (i, i XOR e3) where e3 = (1,0,0) -> index 4
  const masks = [4, 2, 1]; // XOR masks: a1 toggles x1 (bit2 of i)->4, a2 toggles x2 (bit1)->2, a3 toggles x3 (bit0)->1
  for (let bit = 1; bit <= 3; bit++) {
    let votes0 = 0, votes1 = 0;
    const mask = masks[bit - 1];
    // For each pair of indices (i, j=i XOR mask), vote: received[i] XOR received[j] = a_bit
    for (let i = 0; i < 8; i++) {
      const j = i ^ mask;
      if (i < j) { // each unordered pair counted once
        const xorVal = received[i] ^ received[j];
        if (xorVal === 0) votes0++;
        else votes1++;
      }
    }
    est[bit] = votes1 > votes0 ? 1 : 0;
    log.push(fmt('a%bit%: %votes1% votes for 1 vs %votes0% votes for 0 → a%bit% = %v%', { bit: bit, votes1: votes1, votes0: votes0, v: est[bit] }));
  }

  // Decode a0: majority vote of (received[i] XOR linear_part)
  // a0 = majority of (received[i] XOR a1*x1 XOR a2*x2 XOR a3*x3) over all i
  let cnt0 = 0, cnt1 = 0;
  for (let i = 0; i < 8; i++) {
    const [x1, x2, x3] = POINTS[i];
    const linear = (est[1] & x1) ^ (est[2] & x2) ^ (est[3] & x3);
    const v = received[i] ^ linear;
    if (v === 0) cnt0++; else cnt1++;
  }
  est[0] = cnt1 > cnt0 ? 1 : 0;
  log.push(fmt('a0: %cnt1% votes for 1 vs %cnt0% votes for 0 → a0 = %v%', { cnt1: cnt1, cnt0: cnt0, v: est[0] }));

  return { est, log };
}

// Application state: current message, its codeword, and the (possibly flipped) received word
let currentMsg = [0, 0, 0, 0];
let currentCW = encode(currentMsg);
let receivedCW = [...currentCW];

function countErrors() {
  return receivedCW.reduce((s, b, i) => s + (b !== currentCW[i] ? 1 : 0), 0);
}

function renderMsg() {
  const container = document.getElementById('msg-bits');
  container.innerHTML = '';
  currentMsg.forEach((b, i) => {
    const d = document.createElement('div');
    d.className = 'bit msg-bit';
    d.textContent = b;
    container.appendChild(d);
  });
}

function renderCW() {
  const container = document.getElementById('cw-bits');
  container.innerHTML = '';
  receivedCW.forEach((b, i) => {
    const d = document.createElement('div');
    d.className = 'bit cw-bit' + (b !== currentCW[i] ? ' flipped' : '');
    d.textContent = b;
    d.addEventListener('click', () => {
      receivedCW[i] ^= 1;
      document.getElementById('result').classList.add('hidden');
      document.getElementById('steps').classList.add('hidden');
      renderCW();
      document.getElementById('error-count').textContent = countErrors();
    });
    container.appendChild(d);
  });
}

function randomMsg() {
  currentMsg = Array.from({length: 4}, () => Math.random() < 0.5 ? 0 : 1);
  currentCW = encode(currentMsg);
  receivedCW = [...currentCW];
  document.getElementById('error-count').textContent = '0';
  document.getElementById('result').classList.add('hidden');
  document.getElementById('steps').classList.add('hidden');
  renderMsg();
  renderCW();
}

document.getElementById('rand-btn').addEventListener('click', randomMsg);

document.getElementById('decode-btn').addEventListener('click', () => {
  const { est, log } = decode(receivedCW);
  const ok = est.every((v, i) => v === currentMsg[i]);
  const res = document.getElementById('result');
  res.className = 'result ' + (ok ? 'ok' : 'fail');
  res.textContent = ok
    ? fmt('Decoded: [%est%] — correct!', { est: est.join(', ') })
    : fmt('Decoded: [%est%] — wrong! Original was [%currentMsg%]', { est: est.join(', '), currentMsg: currentMsg.join(', ') });
  res.classList.remove('hidden');
  const stepsEl = document.getElementById('steps');
  stepsEl.innerHTML = fmt('<p><strong>Majority-logic voting steps:</strong></p>%map%', { map: log.map(l => `<p>${l}</p>`).join('') });
  stepsEl.classList.remove('hidden');
});

document.getElementById('reset-btn').addEventListener('click', () => {
  receivedCW = [...currentCW];
  document.getElementById('error-count').textContent = '0';
  document.getElementById('result').classList.add('hidden');
  document.getElementById('steps').classList.add('hidden');
  renderCW();
});

// Initialize with a random message on load
randomMsg();
Result
Console

Notice: the code is a [8,4,4]2[8, 4, 4]_2 code — length 8, dimension 4, minimum distance 4 — so it can correct any single error (distance ⌊(4−1)/2⌋=1\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.

The Real Complexity

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

  • rr — the maximum degree of the polynomial (the order).
  • mm — the number of variables.

The resulting code has:

Parameter Value
Block length n=2mn = 2^m
Dimension k=∑i=0r(mi)k = \sum_{i=0}^{r} \binom{m}{i}
Minimum distance d=2m−rd = 2^{m-r}

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

The total decoding complexity is O(m⋅2m)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:

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

Duality connects the ends: RM(r,m)⊥=RM(m−r−1,m)\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.

Where It Matters

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[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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/reed-muller-codes/Content licensed under CC BY-NC 4.0.