What is Reed-Solomon Error Correction?

A non-binary BCH polynomial error correction algorithm used in QR codes to mathematically reconstruct damaged or missing data codewords.

Reed-Solomon error correction is the mathematical engine that makes QR codes resilient to physical damage, dirt, occlusion, and printing defects. Invented in 1960 by Irving S. Reed and Gustave Solomon at MIT Lincoln Laboratory, it was originally developed for deep-space communication and satellite telemetry — environments where data corruption is unavoidable and retransmission is impossible.

Algebraic Foundation: Galois Field GF(2⁸)

QR codes implement Reed-Solomon over the finite field GF(2⁸) — also called Galois Field 256. In this algebraic system:

• Elements are integers from 0 to 255 (representing 8-bit bytes, or codewords)
• Addition is XOR (bitwise exclusive-or)
• Multiplication uses the primitive polynomial p(x) = x⁸ + x⁴ + x³ + x² + 1

The irreducible primitive polynomial defines how multiplications "wrap around" beyond 255 — analogous to how clock arithmetic wraps 13 back to 1. This wrap-around property guarantees that every non-zero multiplication result stays within the 0–255 range.

Encoding: Generating Parity Codewords

Given k data codewords, the encoder generates n-k parity (error correction) codewords. The complete codeword array has length n = k + (n-k). The encoding process:

1. Treat the k data codewords as coefficients of polynomial D(x)
2. Multiply by x^(n-k) to make room for the remainder
3. Divide x^(n-k)·D(x) by the generator polynomial g(x):

g(x) = (x - α⁰)(x - α¹)...(x - α^(n-k-1)) where α is a primitive root (typically α = 2 in GF(2⁸))

1. The remainder polynomial R(x) contains the n-k parity codewords

These parity codewords are appended after the data codewords in the final QR code payload.

Decoding: Error Detection and Correction

When a received codeword array R'(x) is evaluated at points α⁰ through α^(n-k-1), the resulting values (called syndromes) reveal whether any errors occurred:

• All zero syndromes → no errors detected
• Non-zero syndromes → errors present; the syndrome polynomial encodes location and magnitude

The decoder uses algorithms such as the Berlekamp-Massey or Euclidean algorithm to solve for the error locator polynomial, then applies the Chien search to find error positions, and finally applies Forney's algorithm to compute error magnitudes. Up to t = ⌊(n-k)/2⌋ full random errors can be corrected.

QR Code Error Correction Levels

Diagram description: Block diagram showing the Reed-Solomon encoder pipeline: data codewords → polynomial division → parity codeword generation → interleaved final codeword stream.