Reed-Muller codes, introduced independently by David Muller (1954) and Irving Reed (1954), are a family of linear error-correcting codes with exceptionally large minimum Hamming distances, making them among the most powerful codes for high-noise channels. The first-order Reed-Muller code R(1, m) encodes k = m + 1 information bits into n = 2ᵐ codeword bits using a (2ᵐ) × (m+1) generator matrix whose columns represent all 2ᵐ binary vectors; the minimum distance between any two codewords is exactly 2^(m−1), meaning the code can correct up to 2^(m−2) − 1 errors. Their most celebrated real-world use was the transmission of the first colour photographs of Mars by NASA's Mariner 9 spacecraft in 1972, using R(1, 5): a 32-bit codeword carrying 6 bits of image data over a noisy deep-space radio link.
This simulator visualises the full encoding pipeline: choose m (2 to 5), enter a message, watch the generator-matrix multiplication over GF(2), then inject random bit errors or burst errors and observe the majority-logic decoder reconstruct the original message. A Hamming-distance display shows how far the received word is from each valid codeword, and a BER (bit error rate) curve plots correction capability versus error count.
What is the minimum Hamming distance of R(1, m) and how many errors can it correct?
The first-order Reed-Muller code R(1, m) has minimum Hamming distance d = 2^(m−1). A code with minimum distance d can detect up to d − 1 errors and correct up to ⌊(d−1)/2⌋ errors. For R(1, 5): d = 16, so it can correct up to 7 bit errors in any received 32-bit word. For R(1, 4): d = 8, correcting up to 3 errors in a 16-bit word. This large distance relative to block length is exceptional — many common codes achieve much smaller distance-to-length ratios.
How does majority-logic decoding work for R(1, m)?
Reed's 1954 majority-logic decoder computes m+1 independent parity-check equations for each of the m+1 message bits, each equation involving 2^(m−1) received-word positions. If more than half of the 2^(m−1) estimates agree (majority vote), that bit is decoded as the majority value. Because the minimum distance is 2^(m−1), up to 2^(m−2) − 1 errors cannot swing the majority against the correct bit. This decoding runs in O(m · 2ᵐ) operations — linear in block length for fixed m — and is simple enough to implement in early 1970s spacecraft hardware.
What are the parameters (n, k, d) of common Reed-Muller codes?
For R(1, m): block length n = 2ᵐ, dimension k = m + 1, minimum distance d = 2^(m−1). Examples: R(1,2) = (4, 3, 2) — a single parity-check code; R(1,3) = (8, 4, 4) — equivalent to the extended Hamming code; R(1,4) = (16, 5, 8); R(1,5) = (32, 6, 16) — the Mariner code. The code rate k/n = (m+1)/2ᵐ decreases rapidly with m: R(1,5) has rate 6/32 ≈ 0.19, meaning 81% of transmitted bits are redundancy for error correction.
Mariner 9, launched in 1971 and the first spacecraft to orbit another planet, used R(1, 5) to transmit 64×64-pixel images with 64 grey levels (6 bits per pixel) across 100 million kilometres. Each pixel was encoded as a 32-bit codeword; the 37.5 kbps downlink with its inherent noise and bit flips was corrected on the ground before image reconstruction. Without error correction the received images would have been severely degraded; with R(1,5) correction capability, the scientists received clear enough images to map over 7,000 Martian features.
The general Reed-Muller code R(r, m) has parameters: n = 2ᵐ, k = Σᵢ₌₀ʳ C(m, i), d = 2^(m−r). The parameter r is the "order": R(0, m) is the simple repetition code (1 bit, rate 1/2ᵐ, maximum distance), R(1, m) is first-order (discussed above), R(m−1, m) is the extended Hamming code (rate (2ᵐ − 1)/2ᵐ, distance 4), R(m, m) is the trivial no-redundancy code. Each R(r, m) contains R(r−1, m) as a subcode. This nested structure is used in recursive decoding algorithms and in constructing polar codes (Arıkan, 2009), which are used in 5G standards.
Classic Reed-Muller codes are not widely used in modern high-rate links because their low code rate (especially first-order) wastes too much bandwidth. However, their mathematical structure is foundational. Polar codes — used in 5G NR control channels (TS 38.212) — are provably related to Reed-Muller codes and share their recursive structure; in fact R(1, m) is a special case of a polar code. Second-order Reed-Muller codes are used in some CDMA spreading sequences, and RM(1, 5) remains a benchmark in academic channel coding research.
Majority-logic decoding for R(1, m) assumes errors are independently distributed — it corrects any pattern of up to t = 2^(m−2) − 1 errors regardless of position. A burst error (consecutive flipped bits) of length b affects b positions in the received word; if b ≤ t, it is corrected normally. If b > t but the burst is concentrated in a single parity-check equation rather than spread across all equations, majority voting may still succeed. However, long burst errors that span many equations can flip the majority, causing decoding failure. Interleaving (shuffling codeword bits across transmissions) is the standard mitigation for bursty channels.
There is a direct bijection: each codeword of R(r, m) corresponds to the truth table of a Boolean function of m variables with algebraic degree at most r. The first-order code R(1, m) corresponds to affine Boolean functions (linear functions plus a constant). This connection means decoding R(1, m) is equivalent to approximating an arbitrary Boolean function with the nearest affine function — a problem central to learning theory (Goldreich-Levin theorem) and cryptanalysis (Walsh-Hadamard transform attacks on stream ciphers).
For R(1, m), the (m+1) × 2ᵐ generator matrix G has a first row of all 1s (the all-ones vector) and m additional rows, where row i+1 is the binary representation of column index j in bit position i (the "bit mask" rows). To encode a (m+1)-bit message vector u, compute the codeword c = u · G over GF(2) (binary field arithmetic — addition is XOR, multiplication is AND). The resulting 2ᵐ-bit codeword is a superposition of all-zeros, all-ones, and XOR combinations of the m "mask" rows selected by the message bits.
The first-order Reed-Muller code R(1, m) and the Hadamard code of length 2ᵐ are closely related: R(1, m) consists of exactly those rows (and their complements) of the 2ᵐ × 2ᵐ Hadamard matrix. The Hadamard code is the set of all 2^(m+1) ± 1 vectors from the matrix rows, which matches the 2^(m+1) codewords of R(1, m) (since each message has one codeword and its complement). Majority-logic decoding of R(1, m) is equivalent to computing the Fast Walsh-Hadamard Transform, achievable in O(2ᵐ · m) = O(n log n) operations.
First-order Reed-Muller codes do not achieve Shannon capacity: their rate (m+1)/2ᵐ shrinks to zero as m grows, whereas capacity-achieving codes maintain non-zero rate. However, Reeves and Pfister (2021) proved that higher-order Reed-Muller codes R(r, m) with r/m → constant approach Shannon capacity on the binary erasure channel as m → ∞. Polar codes (a RM-related family) were the first explicitly constructed codes proved to achieve Shannon capacity on all symmetric binary-input channels. Reed-Solomon codes (a different family) approach capacity on q-ary channels.