Reed-Solomon Error Correction in QR Codes
Reed-Solomon coding is what allows a damaged symbol to decode at all. The encoder appends redundant codewords to the data, and a code carrying 2t correction codewords can locate and reconstruct up to t corrupted ones, whether the corruption came from dirt, scratches, fading or a deliberately placed logo. The operations run over GF(256), the Galois field of 256 elements, in which each element is one byte, addition is XOR and multiplication follows the primitive polynomial x^8 + x^4 + x^3 + x^2 + 1, decimal 285. Encoding, syndrome calculation and correction all use that same field arithmetic.
Reed-Solomon Error Correction in QR Codes
Error correction is what makes QR codes remarkably resilient. The mathematical engine behind this resilience is Reed-Solomon (RS) error correction, a block code based on finite field arithmetic.
What Reed-Solomon Does
RS codes add redundant codewords to your data. If some codewords are corrupted — by dirt, scratches, fading, or intentional logo placement — the decoder can locate the corrupted positions and reconstruct the original data. An RS code that adds 2t error correction codewords can correct up to t corrupted codewords.
Galois Field Arithmetic
RS codes in QR codes operate over GF(256) — the Galois field with 256 elements. Each element corresponds to one byte (0-255), and the field defines special addition (XOR) and multiplication (using a primitive polynomial) operations. The primitive polynomial for QR codes is:
x^8 + x^4 + x^3 + x^2 + 1 (decimal 285)
All codeword arithmetic — encoding, syndrome calculation, and error correction — uses GF(256) operations.
Generator Polynomials
The encoder creates a generator polynomial whose roots are consecutive powers of the primitive element. For n error correction codewords, the generator polynomial has degree n. The data polynomial is divided by the generator polynomial, and the remainder becomes the error correction codewords.
Codeword Interleaving
Large QR codes split data into multiple blocks, each with its own RS error correction. The codewords from different blocks are then interleaved in the final bit stream. This distributes the impact of localised damage across multiple blocks, improving recovery from large contiguous damage areas.
The Decode Side
When decoding, the scanner:
- Calculates syndromes — if all syndromes are zero, no errors exist
- Uses the Berlekamp-Massey algorithm to find the error locator polynomial
- Applies Chien search to find error positions
- Uses Forney's algorithm to calculate error magnitudes
- Corrects the erroneous codewords
Practical Implications
| EC Level | EC Codewords (%) | Correctable Codewords (%) |
|---|---|---|
| L | ~20% | ~7% |
| M | ~38% | ~15% |
| Q | ~55% | ~25% |
| H | ~65% | ~30% |
The "correctable" percentage is approximately half the EC codeword percentage because each error requires two EC codewords to locate and fix. If the error positions are already known (erasures), one EC codeword per position suffices.
Key Takeaways
- Reed-Solomon codes add redundant codewords for error detection and correction
- Arithmetic operates in GF(256) using the primitive polynomial x^8+x^4+x^3+x^2+1
- Each correctable error consumes two EC codewords
- Interleaving across blocks distributes localised damage
- RS decoding uses syndromes, Berlekamp-Massey, Chien search, and Forney's algorithm