Reed–Solomon error correction

Reed–Solomon codes work on whole symbols rather than single bits. In a QR code each symbol is an 8-bit codeword, treated as an element of a finite field with 256 values. The data codewords are read as the coefficients of a polynomial, and the error correction codewords are the remainder after dividing it by a generator polynomial. A reader recomputes that relationship; if it does not hold, the mathematics locates the wrong codewords and their correct values.

A block with n − k error correction codewords can correct up to (n − k) ÷ 2 codewords whose positions are unknown, or up to n − k whose positions are known. Because a codeword is wrong whether one of its bits flipped or all eight did, the method suits burst damage, such as a scratch or a smudge, that wrecks a small area completely.

Larger codes split their data into several blocks, each with its own error correction, up to 81 blocks for version 40 at level H. The codewords of all blocks are interleaved across the symbol, so a local stain spreads its damage thinly over many blocks instead of overwhelming one.

Reed–Solomon coding is what lets a QR code survive wear, glare, a fold, or a logo placed over its center. It is the same family of codes used on CDs and DVDs, by deep-space probes such as Voyager, and in other 2D barcodes such as Data Matrix.

The budget is finite, and the error correction level sets it. When damage exceeds it, a well-built decoder reports a failure rather than returning wrong text. The standard sets aside a few codewords in the smallest codes purely to detect such misreads. The QR code’s small fixed fields use a different code: format information is protected by a BCH code.

A version 1 code at level H has 26 codewords: 9 for data and 17 for error correction. That lets a scanner correct up to 8 misread codewords, about 30% of the code, which is where level H’s figure comes from.