on the cumulative nature of science and technology, through the example of the qr code

Japan. Denso Wave — a subsidiary of Denso, part of the Toyota group — is looking for something to track automotive parts with. A barcode holds about ~20 characters, and that is not enough.

The engineers design a square pattern: a grid of black and white modules. It will be called the QR code.

And look at the corners of the design:

A large nested square in three corners. A smaller one at the bottom right. Three plus one.

The shapes in the corners are not aesthetics. They are the dimensions of a system of equations.

One branch puts the grid in place, the other repairs the damage in the grid. Projective geometry makes it readable, finite fields make it recoverable. Both were taken ready-made off the shelf — the engineers needed to concern themselves with neither Galois's equations nor Poncelet's captivity.

The thirteen things that happen in half a second

There is a laminated sheet of paper on a street vendor's stall. The edge is torn, there is a grease stain on it, it has faded in the sun. You hold your phone at an angle — nobody holds it straight — and half a second later the payment screen opens.

Here is what happens in that half second:

 1. Greyscale
2. Thresholding                ← the contrast decision happens here
3. Find the 3 finder squares   (the 1:1:3:1:1 ratio)
4. Orientation / rotation
5. Timing pattern              → how many modules there are
6. Alignment patterns          → perspective correction
7. Build the grid, read the centre of each module

────────────  the geometry scene ends here  ────────────

8. Format information
9. Remove the mask
10. Read the data modules in zigzag order
11. De-interleave the blocks
12. Reed-Solomon
13. Decode the text

────────────  this is the algebra scene  ────────────

Now let's look a little more closely inside these steps — because the fingerprints of both scenes are everywhere.

Small code, small error

Version 1 (21×21) has no alignment pattern at all. The code is so small that the error made by an affine fit doesn't exceed half a module even in the furthest corner. The grid still lands on the right cell. Adding a fourth point would be wasting space.

As the code grows, the drift accumulates:

In large codes the patterns form a grid of their own. At that point even a single global homography is no longer enough — a separate local transformation is computed for each region. The reason is practical: the code may not be flat. It may be printed on a bottle label, on crumpled paper, on curved packaging. No single transformation can flatten a curved surface — but approximating it piece by piece works.

And the reader climbs Klein's hierarchy one rung at a time. In real decoders such as ZXing the order goes: first find the three finder squares; fit an affine transform and predict where the fourth corner ought to be; search a small area around that prediction for the alignment pattern; once found, step up to a homography.

Affine isn't an intermediate step that gets thrown away. You need a rough map before you can find the fourth point.

Pappus's grandchild

There is a chicken-and-egg problem here: to find the finder squares you need to know the transformation, and to compute the transformation you need to find the finder squares.

The answer is hidden in the geometry itself. Along any line through the centre of a finder square, the run lengths of the colours are always in the same ratio:

Which is to say: the pattern is designed to be recognisable before the transformation is known. The scanner sweeps the image line by line looking for that ratio — whether the code is upside down, skewed or far away makes no difference at all. The ratio is there.

"The image may change, but some ratios stay fixed." Pappus wrote that in 320. In 1994 someone turned the same idea into a design decision: what matters is not how this shape looks, but which of its properties stays fixed.

What is inside the squares

The grid is fitted; now for the reading. One square carries exactly one bit: black is 1, white is 0. There are two points where people get stuck.

Pixel ≠ square. The smallest unit is called a module, and on screen or in print it is usually more than one pixel:

1 module (1 bit) =  ████
                  ████    ← may be 16 pixels on screen
                  ████
                  ████

The reason is simple: so the camera can tell them apart comfortably. So it isn't that "one pixel carries more than one bit" — many pixels come together to carry a single bit. Exactly the opposite direction.

Bit ≠ letter. A letter doesn't fit in one square:

"A" =  01000001
     ░█░░░░░█   ← 8 separate squares

A code holding a 100-letter address needs at least 800 squares. The smallest QR code is 21×21 = 441 squares; once the fixed markers are taken out, 26 bytes are left for data, and 7 of those are check bytes. What remains: around 19 letters. The largest code is 177×177 = a little over 31 thousand squares, and can still only carry a few thousand characters.

Why is the format information read first?

Another chicken-and-egg problem. To read the data modules you need to know which mask was used; to learn the mask you have to read something.

The answer: a small 15-bit area sitting right beside the top-left finder square. It holds only 5 bits of real information — 2 bits of error correction level, 3 bits of mask number. The remaining 10 bits are pure protection. This area uses a BCH code rather than Reed-Solomon and can correct a 3-bit error. On top of that it is copied to two separate places. It looks excessive for 5 bits — but if this area goes, the whole code dies.

The mask's job is visual. The data area isn't written raw; it is XORed with a fixed pattern. The aim: to stop large flat black or white areas forming inside the code (the camera would lose the grid) and to stop a shape resembling a finder square appearing in the data area by accident. The encoder tries all eight masks, picks the most balanced image and writes its number into the format bits.

The data modules are then read in two-module-wide columns, starting at the bottom right and zigzagging up and down. The resulting byte sequence doesn't go straight to Reed-Solomon — it is de-interleaved first: in large codes the data is split into blocks and the blocks are written interleaved with one another. The aim: a large stain in one place should take one byte from many blocks rather than killing a single block outright.

Incidentally, the GF(256) polynomial QR uses is 0x11D — the multiplication tables in the algebra scene were computed with that polynomial.

How much protection, at what price

What you give up in return is space. The check numbers live in squares too. In the smallest code (26 bytes in total) the split goes like this:

At level H two thirds of the code is check bytes. This table also explains why codes with a logo in the middle are always at level H: the logo is deliberate damage eating the centre of the code.

Why it won

Denso Wave took out the patent — and chose not to enforce it. Anyone who follows the standard can generate them for free and read them for free. No licence, no royalties, no permission. Most rival 2D barcodes were not this open. A thing that is free almost always beats a thing that is good.

The technical decisions were right too. It reads from any angle: thanks to the three finder squares you can hold the code upside down; a barcode you have to line up. Capacity: thousands of characters instead of twenty. It survives rough handling: a dirty, crumpled, scratched code still reads. It scales: the same pattern prints at the size of a fingernail or across the side of a building.

But the real force is economic:

Generating a code : free, a few milliseconds
Printing a code   : ink, a few mm²
On the code's side: no power, no battery, no chip, no network
The reader        : already in everybody's pocket

It is the cheapest known way to bridge the physical world and the digital one. NFC wants a chip, an app, a compatible phone. QR wants only ink. It can be printed on paper, on a screen, on glass, on fabric, on bread.

Two waves turned it into infrastructure. China: from 2014 onwards WeChat and Alipay built payments entirely on QR — the street vendor needs no card terminal, a laminated sheet of paper is enough. The pandemic: in 2020 menus, entry logs and vaccination certificates moved to QR, and the rest of the world made scanning a code a reflex too.

Closing: 1674 years and 162 years

Let's put the two scenes on a single timeline:

The geometry branch starts with Pappus in 320 and ends in 1994: 1674 years. The algebra branch starts with Galois in 1832 and ends in 1994: 162 years.

Things look to have sped up recently. But it is the length of the geometry branch that says the real thing:

Nobody knows when an idea will turn out to be useful.

There was no camera when Pappus wrote down the cross-ratio. Poncelet had no application in mind while rebuilding geometry in prison. There was no digital communication when Galois built finite fields — there was no electricity. When Reed and Solomon wrote their paper there wasn't even an algorithm that could decode their own code.

Not one of them had to defend "what this will one day be good for" — or if they did, they could not have given the right answer. The answer turned up centuries later, in a Japanese car factory, on plastic parts.

Back to the beginning. A list arrives corrupted; two extra numbers bring the truth back. You look at a square from an angle; nothing stays where it was, and yet something remains. Two questions, two separate centuries, two separate traditions.

The grease-stained sheet of paper opens in half a second. Both of them are in there.