In plain language: two things happen to your data after it is turned into bits. First, extra repair bits are computed from it, so that a scanner can fix squares it misreads. Second, a fixed checkerboard-like pattern is laid over the result so that the code never has big empty patches or stripes that confuse the camera. This article shows both, with the actual formulas.
Why a mask is needed
Imagine a message that happens to encode to a long run of zeros. The code would have a large white area. A scanner lays its grid over the image using the finder patterns and timing patterns, and a big featureless region gives it nothing to check the grid against. Worse, a run of data might by chance form the 1:1:3:1:1 dark-light pattern of a finder, and the scanner would lock on to the wrong place.
A mask prevents both. It is one of eight fixed patterns that the encoder XORs over the data area. XOR means: where the mask is dark, flip the module; where it is light, leave it. Function patterns, meaning the finders, timing lines, alignment squares and format bits, are never masked. The scanner reads which mask was used from the format information, applies the same XOR to undo it, and decodes.
The eight masks
Each mask is a rule on the row i and column j of a module, counted from the top-left corner. Where the rule is true, the module is flipped.
| Mask | Rule (flip where true) | What it looks like |
|---|---|---|
| 000 | (i + j) mod 2 = 0 | Checkerboard |
| 001 | i mod 2 = 0 | Horizontal stripes every other row |
| 010 | j mod 3 = 0 | Vertical stripes every third column |
| 011 | (i + j) mod 3 = 0 | Diagonal stripes |
| 100 | (floor(i/2) + floor(j/3)) mod 2 = 0 | Chunky checkerboard of 2 by 3 blocks |
| 101 | (i × j) mod 2 + (i × j) mod 3 = 0 | Grid lines every 2 rows and 3 columns |
| 110 | ((i × j) mod 2 + (i × j) mod 3) mod 2 = 0 | Dense woven pattern |
| 111 | ((i + j) mod 2 + (i × j) mod 3) mod 2 = 0 | Sparse woven pattern |
Choosing a mask: the four penalty rules
The encoder builds the code eight times, once with each mask, and scores each result. Lower is better. The four rules, with the standard’s weights, are:
- Runs. Any row or column with 5 or more adjacent modules of the same colour scores 3 points, plus 1 point for each module beyond 5. A run of 7 dark modules costs 5 points.
- Blocks. Every 2 by 2 block of four modules of the same colour scores 3 points. Overlapping blocks each count.
- Fake finders. The pattern dark, light, dark, dark, dark, light, dark (the finder’s 1:1:3:1:1 ratio) with 4 light modules on either side scores 40 points each time it appears in a row or column. This is the rule that protects the scanner from locking on to the wrong place, so it is weighted heavily.
- Balance. Work out the percentage of dark modules. For every full 5% the total is away from 50%, add 10 points. A code that is 62% dark is 12% off, which is two full steps, so 20 points.
The mask with the lowest total is used, and its three-bit number is written into the format information. Two figures below show real codes for links of the same length that ended up with different masks.
- Version 3, 29×29 modules, error correction M, mask 0. Tap a label to isolate it.
- Version 3, 29×29 modules, error correction M, mask 7. Tap a label to isolate it.
Note
The penalty rules explain a common observation: a QR code never has a big white hole in it, and never has a fourth finder pattern by accident. Both would score badly, so the encoder chooses a mask that avoids them.
Reed-Solomon: the intuition
Before masking, the data codewords are extended with repair codewords. The maths is Reed-Solomon coding, and the idea behind it is easier than the arithmetic.
Think of a straight line. Two points fix it exactly. Give someone five points that all lie on the line and they can lose any three and still draw the same line. Now think of your 16 data codewords as the coefficients of a polynomial. Evaluate that polynomial at extra points and send those values too. A receiver who gets some values wrong can still find the one polynomial that fits most of them, because a wrong value stands out as the odd one that fits nothing.
Concretely: with r repair codewords in a block, the decoder can correct up to r/2 codewords whose positions it does not know. A version 1 code at error-correction level M has 16 data codewords and 10 repair codewords. Any 5 of the 26 can be wrong. If the scanner already knows which codewords are unreadable, called erasures, it can fix up to r of them, but a camera rarely knows, so the working figure is r/2.
Three consequences follow for a printed code:
- A single wrong module spoils its whole codeword. Eight modules in different codewords cost eight repairs. Eight modules in one codeword cost one. Solid blobs of damage are cheaper than scattered specks.
- Damage to a finder is not repairable. Reed-Solomon works on codewords in the data area. If the scanner cannot find the grid, it never gets as far as decoding.
- The repair budget is the logo budget. A logo covering modules is deliberate damage. The error correction article covers how much to allow.
GF(256) in one paragraph
Reed-Solomon needs arithmetic on 8-bit codewords where addition and multiplication always give another 8-bit value and every non-zero value has an inverse. Ordinary integer arithmetic fails this, since 200 + 100 does not fit a byte. The fix is the Galois field GF(256). Addition is XOR, so a byte plus itself is zero and there is no carry. Multiplication is polynomial multiplication where each bit is a coefficient, followed by taking the remainder modulo a fixed prime polynomial, which QR specifies as x⁸ + x⁴ + x³ + x² + 1 (decimal 285). Every non-zero element is a power of the generator α = 2, so implementations keep a 256-entry log table and multiply by adding logs. That is the whole toolkit the decoder needs.
Interleaving
Larger codes split their codewords into several blocks, each with its own repair codewords. A version 5 code at level M has 134 codewords in 2 blocks of 43 data and 24 repair. Rather than placing block 1 then block 2 on the grid, the encoder interleaves them: first codeword of block 1, first of block 2, second of block 1, and so on. A scratch across the middle of the code then damages a few codewords in every block rather than many codewords in one, and each block stays inside its r/2 limit. At version 40 level H there are 81 blocks, so a scuff has to be very unlucky to defeat the code.
Common mistake
Assuming that error correction percentage means “this much of the picture can be covered”. It means this share of codewords can be wrong, at best, when the damage is spread evenly across blocks. A sticker over one corner concentrates damage and also risks the finder underneath it.
▸The generator polynomial and how repair codewords are computed
For r repair codewords the encoder uses a generator polynomial g(x) of degree r, defined as the product (x − α⁰)(x − α¹)…(x − α^(r−1)) over GF(256). The data codewords are treated as a polynomial m(x) with the first codeword as the highest coefficient. The encoder multiplies m(x) by x^r, divides by g(x), and the remainder is the r repair codewords. Because g(x) has α⁰ to α^(r−1) as roots, the complete codeword polynomial c(x) = m(x)·x^r + remainder evaluates to zero at each of those roots. The decoder evaluates the received polynomial at the same roots; the r results, called syndromes, are all zero if nothing is wrong. If not, the Berlekamp-Massey or Euclidean algorithm turns the syndromes into an error-locator polynomial whose roots say which codewords are wrong, and Forney’s formula says by how much. Up to r/2 errors can be located and fixed this way. The generator polynomial for 10 repair codewords, used by version 1 level M, is x¹⁰ + α²⁵¹x⁹ + α⁶⁷x⁸ + α⁴⁶x⁷ + α⁶¹x⁶ + α¹¹⁸x⁵ + α⁷⁰x⁴ + α⁶⁴x³ + α⁹⁴x² + α³²x + α⁴⁵.
Try it yourself
Type a message and watch the mask number in the legend. Add one character at a time and notice how often the winning mask changes, and how the whole pattern changes with it.