Reed–Solomon error correction in QR codes, made readable

The idea in one paragraph

Treat your data codewords as coefficients of a polynomial. Divide that polynomial by a fixed generator polynomial and append the remainder (t extra codewords), to the message. Any valid message is now exactly divisible by the generator. A decoder that receives a corrupted message divides, gets a non-zero remainder, and (this is the remarkable part) can use that remainder (the syndromes) to work out which codewords are wrong and what they should have been. That is Reed–Solomon coding, the same family used on CDs, DVDs and deep-space links.

The arithmetic: GF(256)

Ordinary arithmetic overflows; QR codes instead work in the finite field GF(256), where every value is one byte and every operation returns one byte. Addition is XOR (so addition and subtraction are the same operation), and multiplication wraps using the fixed primitive polynomial x⁸ + x⁴ + x³ + x² + 1 (binary 100011101, 0x11D). Two useful consequences:

• byte in, byte out, the maths never leaves 8 bits, which is why the whole scheme runs comfortably on a 1990s barcode scanner;
• every non-zero element has an inverse, so "divide" is always defined.

The generator polynomial for t check codewords is (x − α⁰)(x − α¹)⋯(x − α^(t−1)), where α = 2 is the field's generator. Its degree (and therefore the remainder's size) is exactly t.

What "recovers up to 30%" actually means

Each error-correction level fixes how many check codewords each block carries. The repair budget is:

2 × (unknown errors) + (erasures) ≤ t

• An erasure is damage at a known position: the decoder can see the region is obliterated (a hole, a logo, a glare patch) and only needs the value restored. Cost: 1.
• An error is a codeword that is wrong without warning, misread modules that look plausible. The decoder must find it before fixing it. Cost: 2.

So t check codewords repair up to t erasures, or t/2 errors, or a mix. The headline percentages are codeword fractions in the pure-error case: a version 1-H block has 26 codewords of which 17 are checks, repairing 8 unknown errors, 8/26 ≈ 30%. Level L's "7%" comes from the same arithmetic with 2 checks per 26.

This is why a crisp, solid logo (an erasure-like defect, position obvious) is roughly twice as survivable as the same area of scattered print speckle (errors), and why logo coverage guidance stays under ~20% even at H's 30% budget: real scans add errors on top of the erasure.

What it cannot fix

Reed–Solomon operates on the data region only. It cannot help when finder patterns are covered, when the quiet zone is gone, or when format information (which has its own separate BCH code) is destroyed, because in those cases decoding never reaches the stage where syndromes exist. It also assumes damage is spread across blocks, which the standard engineers deliberately via interleaving.

The budget is also consumed invisibly by design choices: low contrast, tinted modules and heavy styling all convert clean modules into borderline reads. Error correction spent on your design is unavailable for real-world damage: measure what remains by decoding the final artwork.

FAQ

How does QR code error correction work?

The encoder appends Reed–Solomon check codewords, the remainder of dividing the data polynomial by a fixed generator polynomial over GF(256). A decoder uses the mismatch pattern (syndromes) to locate and repair corrupted codewords without any retransmission.

How much damage can Reed–Solomon repair in a QR code?

With t check codewords per block: up to t erasures (damage at known positions), or t/2 errors at unknown positions, or a weighted mix. Levels L, M, Q and H set t so the pure-error budget is roughly 7%, 15%, 25% and 30% of codewords.

What is GF(256) in QR codes?

The finite field of 256 elements in which all the error-correction arithmetic happens. Every value is one byte, addition is XOR, and multiplication wraps via the fixed polynomial 0x11D, so the maths is fast, exact, and never overflows.

Why can a logo cover more area than random damage?

A logo is erasure-like: its position is obvious, so each ruined codeword costs 1 from the budget instead of the 2 an unknown error costs. Scattered noise gives the decoder no location hints and burns the budget twice as fast.