Origin and wider use
Reed–Solomon codes were described by Irving S. Reed and Gustave Solomon in 1960. They work on whole symbols, usually bytes, rather than single bits, which makes them good at handling bursts of damage such as a scratch or a smudge.
The same family of codes protects data on CDs, DVDs and Blu-ray discs, in some digital television and satellite links, and in other 2D barcodes including Data Matrix ECC 200, Aztec code and PDF417.
How QR codes use it
A QR code treats each 8-bit codeword as an element of the finite field GF(256), built with the primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 (hex 0x11D). The data codewords are divided by a generator polynomial, and the remainder becomes the error correction codewords appended to them.
Larger codes split their data into several blocks, each with its own error correction codewords. The blocks are then interleaved when the codewords are placed in the grid, so a single patch of damage is spread across many blocks instead of overwhelming one.
How much it can fix
With n error correction codewords in a block, a decoder can correct up to n/2 codewords whose position is unknown, or up to n codewords whose position is known, called erasures. Mixed cases follow the rule that each error counts twice and each erasure once.
This is why a code with a clean, flat area covered by a logo can still scan: a smart reader may treat the covered region as erasures, while random damage is harder to fix because the decoder first has to find it.
- Unknown errors: up to half the number of EC codewords
- Erasures (known positions): up to the number of EC codewords
- Field: GF(256), polynomial 0x11D
- Blocks are interleaved to spread burst damage