Reed-Solomon Code

How Reed-Solomon codes work

Hamming corrects one bit per block. That's not enough when a CD gets scratched, when cosmic rays carve a 50-bit streak through your spacecraft's downlink, or when a sticker covers a quarter of your QR code. Reed-Solomon, published in 1960 by Irving Reed and Gustave Solomon at MIT's Lincoln Laboratory, lifts error correction to the level of symbols — typically bytes — and corrects multiple symbol errors per block using a different mathematical machine: polynomial arithmetic over finite fields.

The encoding has two equivalent views.

The evaluation view (original 1960 construction). Treat the k data bytes as the coefficients of a polynomial P(x) of degree k-1 over GF(2^m). Evaluate P at n distinct points in the field, where n ≥ k. Transmit those n evaluations. The receiver can recover P from any k correct evaluations via polynomial interpolation (n - k extra evaluations are redundancy).

The generator view (BCH-style construction used in practice). Pick a generator polynomial g(x) of degree n-k whose roots are consecutive powers of a primitive element α. To encode, multiply the message polynomial m(x)·x^(n-k) by remainder against g(x), then append the remainder as parity bytes. The codeword is divisible by g(x) by construction; any error makes it non-divisible, and the syndrome (the remainder) tells you where and what.

Worked example — RS(7,4) over GF(2^3)

To keep arithmetic readable, we'll use the small field GF(8) instead of the standard GF(256). The field has 8 elements {0, 1, α, α², α³, α⁴, α⁵, α⁶} with primitive element α satisfying α³ + α + 1 = 0.

Parameters: n=7, k=4, so we can correct up to (7-4)/2 = 1 symbol error per block. Generator polynomial (degree 3):

g(x) = (x - α)(x - α²)(x - α³) = x³ + α³x² + αx + α³

Take the message m = [α, 1, α², 0] (treated as coefficients of m(x) = αx³ + x² + α²x + 0). Encode:

1. Shift left by n-k = 3: compute m(x) · x³.
2. Divide by g(x); the remainder r(x) is the 3 parity bytes.
3. Transmitted codeword: c(x) = m(x)·x³ + r(x).

Suppose noise corrupts position 4 — replacing the byte α² with α⁵. The decoder evaluates c(x) at the roots of g(x):

S1 = c(α),   S2 = c(α²),   S3 = c(α³)

All three are non-zero — the syndrome. From the syndrome, Berlekamp-Massey finds the error locator polynomial; Chien search identifies the error position (4); a final calculation gives the error magnitude (α² ⊕ α⁵). XOR the magnitude back into position 4 and the codeword is restored.

Key Reed-Solomon properties

Property	Formula / value	Implication
Block length n	≤ 2^m − 1 over GF(2^m)	GF(256) → max 255 bytes per block
Data bytes k	Choose freely < n	Trade rate vs correction power
Parity bytes	n − k	RS(255,223) → 32 parity
Error correction	⌊(n − k)/2⌋ symbols	RS(255,223) → 16 byte errors
Erasure correction	Up to n − k known erasures	2× erasures vs unknown errors
Minimum distance	n − k + 1 (MDS optimal)	No symbol code does better
Burst tolerance	(n − k)/2 × m bits	RS(255,223) → 128 contiguous bit errors

The "MDS" (Maximum Distance Separable) property is what makes Reed-Solomon canonical: no symbol-level code achieves a higher minimum distance for given (n, k). You can't do better — only differently. Modern LDPC codes beat Reed-Solomon in code-rate efficiency near the Shannon limit, but they don't share the MDS guarantee and require longer blocks to approach it.

Where Reed-Solomon shows up

• Compact Discs (1982). CIRC = Cross-Interleaved Reed-Solomon Code. Two layered RS codes (32,28) and (28,24) plus interleaving correct burst errors from scratches up to ~4000 bits long.
• DVD / Blu-ray. RS(208,192) and RS(182,172) at increasing data rates. Blu-ray's BD-J discs add an outer RS(216,200) layer for archival robustness.
• QR codes. RS over GF(256) with 4 levels of error correction (L=7%, M=15%, Q=25%, H=30% recoverable damage).
• DataMatrix / Aztec / PDF417. All 2D barcodes use Reed-Solomon variants tuned to their error profile.
• RAID-6. Two-parity RAID uses RS over GF(2^8) to survive any 2 disk failures from k+2 total disks.
• Distributed storage. Backblaze B2 (RS(20,17)), Facebook HDFS (RS(14,10)), Google Colossus (RS(9,6)) use Reed-Solomon for fault-tolerant block storage at ~1.5× overhead instead of 3× replication.
• Voyager / Mars rovers. CCSDS standard RS(255,223) concatenated with an inner Viterbi-decoded convolutional code. The reason 1977 Voyager data still arrives intact.
• DVB-T digital TV. Outer RS(204,188) shortened from RS(255,239).
• DSL and cable modems. RS(255,239) for forward error correction on the wire.

Reed-Solomon vs other codes

Code	Symbol size	Errors per block	Burst tolerance	Decode complexity
Hamming(127,120)	1 bit	1	1 bit	O(n) XOR
BCH(255,231)	1 bit	3	3 bits	O(n²)
RS(255,223)	8 bits	16 symbols	128 bits	O(n²) classical
Convolutional + Viterbi	Continuous	Variable	Stream-tolerant	O(n) trellis
Turbo codes	Continuous	Near Shannon	Iterative	O(n) per iteration
LDPC (5G/Wi-Fi 6)	1 bit	Near Shannon	Burst via interleaving	O(n) belief propagation
Polar codes (5G control)	1 bit	Provably optimal	Burst via interleaving	O(n log n)

Reed-Solomon dominates at the "moderate block length, byte-aligned channel, burst errors" sweet spot. LDPC and polar codes beat it on raw rate efficiency for very long blocks at high SNR, but the byte-oriented MDS guarantee keeps Reed-Solomon as the standard for storage and barcodes — where you want exact "16 byte errors per 255-byte block, period" promises.

Pseudo-code — RS encode

// Reed-Solomon encode over GF(256) with generator polynomial g(x).
// k = data symbols, n-k = parity symbols.

function rsEncode(message, n, k):
    g = makeGenerator(n - k)                  // degree n-k generator
    msg_shifted = message + [0] * (n - k)     // multiply by x^(n-k)
    remainder = msg_shifted
    for i in 0..k-1:
        coef = remainder[i]
        if coef != 0:
            for j in 1..n-k:
                remainder[i + j] = remainder[i + j] XOR gf_mul(g[j], coef)
    parity = remainder[k..n-1]
    return message + parity                   // codeword of length n

// Decode (high level).
function rsDecode(received, n, k):
    syndromes = [eval(received, alpha^i) for i in 1..n-k]
    if all_zero(syndromes): return received[0..k-1]   // no errors
    locator = berlekampMassey(syndromes)
    positions = chienSearch(locator)
    magnitudes = forneyAlgorithm(syndromes, locator, positions)
    for p, m in zip(positions, magnitudes):
        received[p] = received[p] XOR m
    return received[0..k-1]

JavaScript implementation

// Reed-Solomon over GF(256) with primitive polynomial 0x11D.
// Standard CCSDS / QR / Reed-Solomon basis.

const GF_EXP = new Uint8Array(512);
const GF_LOG = new Uint8Array(256);

(function initGF() {
  let x = 1;
  for (let i = 0; i < 255; i++) {
    GF_EXP[i] = x;
    GF_LOG[x] = i;
    x <<= 1;
    if (x & 0x100) x ^= 0x11D;
  }
  for (let i = 255; i < 512; i++) GF_EXP[i] = GF_EXP[i - 255];
})();

function gfMul(a, b) {
  if (a === 0 || b === 0) return 0;
  return GF_EXP[GF_LOG[a] + GF_LOG[b]];
}

function makeGenerator(nsym) {
  let g = [1];
  for (let i = 0; i < nsym; i++) {
    g = polyMul(g, [1, GF_EXP[i]]);
  }
  return g;
}
function polyMul(p, q) {
  const r = new Array(p.length + q.length - 1).fill(0);
  for (let i = 0; i < p.length; i++)
    for (let j = 0; j < q.length; j++)
      r[i + j] ^= gfMul(p[i], q[j]);
  return r;
}

function rsEncode(msg, nsym) {
  const gen = makeGenerator(nsym);
  const out = msg.concat(new Array(nsym).fill(0));
  for (let i = 0; i < msg.length; i++) {
    const coef = out[i];
    if (coef !== 0) {
      for (let j = 1; j < gen.length; j++) {
        out[i + j] ^= gfMul(gen[j], coef);
      }
    }
  }
  return msg.concat(out.slice(msg.length));
}

// Encode 4 data bytes with 3 parity bytes (RS(7,4)).
const codeword = rsEncode([0x48, 0x65, 0x6C, 0x6F], 3);
console.log(codeword.map(b => b.toString(16).padStart(2, '0')).join(' '));
// Example output: 48 65 6c 6f ?? ?? ?? — three parity bytes appended

Python implementation

# Minimal Reed-Solomon encoder over GF(2^8) with primitive poly 0x11D.

GF_EXP = [0] * 512
GF_LOG = [0] * 256
x = 1
for i in range(255):
    GF_EXP[i] = x
    GF_LOG[x] = i
    x <<= 1
    if x & 0x100: x ^= 0x11D
for i in range(255, 512):
    GF_EXP[i] = GF_EXP[i - 255]

def gf_mul(a, b):
    if a == 0 or b == 0: return 0
    return GF_EXP[GF_LOG[a] + GF_LOG[b]]

def poly_mul(p, q):
    r = [0] * (len(p) + len(q) - 1)
    for i, pi in enumerate(p):
        for j, qj in enumerate(q):
            r[i + j] ^= gf_mul(pi, qj)
    return r

def make_generator(nsym):
    g = [1]
    for i in range(nsym):
        g = poly_mul(g, [1, GF_EXP[i]])
    return g

def rs_encode(msg, nsym):
    gen = make_generator(nsym)
    out = list(msg) + [0] * nsym
    for i in range(len(msg)):
        coef = out[i]
        if coef:
            for j in range(1, len(gen)):
                out[i + j] ^= gf_mul(gen[j], coef)
    return list(msg) + out[len(msg):]

codeword = rs_encode([0x48, 0x65, 0x6C, 0x6F], 3)
print(' '.join(f'{b:02x}' for b in codeword))
# Encodes 4 data bytes as 7-byte RS(7,4) codeword.

Common Reed-Solomon bugs and edge cases

• Wrong primitive polynomial. GF(256) has multiple choices of irreducible polynomial — CCSDS uses 0x187, classic Reed-Solomon papers use 0x11D, QR codes use 0x11D. Mismatched primitives produce decoders that silently fail. Always document the polynomial in the spec.
• Erasure decoding vs error decoding. Erasures (known-bad positions) cost half as much as unknown errors. Use erasure decoding when your physical layer can flag suspect bytes (e.g., CD's analog signal-strength threshold).
• Burst beyond capacity. RS(255,223) correctly handles up to 128 contiguous bad bits. A 200-bit burst overflows the code and produces undetected corruption. Use interleaving to disperse bursts across multiple codeblocks.
• Buffer alignment. RS operates on fixed-size blocks; partial blocks must be zero-padded with care. Padding bytes count toward k; the encoder/decoder must agree on which bytes are padding.
• Decoding failure misclassified as success. When the number of errors exceeds (n-k)/2, the decoder may produce some valid codeword that differs from the original — silent failure. Always check the post-decode syndrome to detect over-capacity corruption.
• Performance on long codes. Classical O(n²) decoding becomes painful at n=1000+. Use FFT-over-GF or Reed-Solomon-Erasure (Vandermonde matrix) techniques for high-throughput storage systems.

Performance in real systems

• CD playback: CIRC decoder runs at ~1.4 Mbps in early-1980s silicon — Reed-Solomon over GF(256) on a chip you can buy for under $5.
• QR code scanning: Decoder runs in < 5 ms on smartphone CPUs; handles Level H codes (30% damage) easily.
• Voyager downlink: RS(255,223) at the outer layer; entire deep-space link operates at ~160 bps with concatenated Viterbi inner code — Reed-Solomon delivers 5+ dB coding gain over uncoded BPSK.
• RAID-6 throughput: ~3-5 GB/s on modern x86 with the PCLMULQDQ instruction used for GF(2^8) multiplication; Intel ISA-L library reaches 8+ GB/s.
• Backblaze B2 erasure coding: ~1 GB/s/core for RS(20,17) encoding; ~5× cheaper than 3× replication for the same durability.

Reed-Solomon is 65 years old, still the textbook example of bringing serious math (finite fields, polynomial division) to bear on a practical engineering problem. The trade-off it makes — moderate computational cost for guaranteed burst tolerance — is the right trade for almost every storage and barcode application built since the 1980s.