← All Posts 📖 The Human DeveloperEarly access → what makes developers irreplaceable in the age of AI

Math Hiding in Plain Sight

How QR codes work, and why the one with a logo in the middle still scans

Reading time: ~15 minutes

I needed a QR code for this site. Just one. Print it on a card, paste it on a slide, drop the octopus in the middle so it didn't look like a crime scene. Five minutes of work.

I'd never spent a moment thinking about how a QR code worked. If you'd asked me, I'd have shrugged and said something about "encoding the URL as black and white squares" — some trivial bijection between bytes and a grid. I would have been confidently, embarrassingly wrong.

Because the QR code I made has my octopus avatar sitting square in the middle of it. And every phone I've pointed at it scans it instantly. No struggle, no "move the camera," no second attempt. Whatever's encoded in that grid must be robust enough to survive a hole in the middle, and the scanner has to reassemble the missing pieces from what's left.

A QR code for nazquadri.com with an octopus-and-lightsaber logo masking part of the data region. Try scanning it with your phone — it works.

Point a phone at it; it'll open nazquadri.com. The octopus is sitting on top of real data modules. The scanner won't notice.

I had to know how that worked. So I went down the rabbit hole. The bytes get reassembled using mathematics developed for deep-space probes, polynomials from high-school algebra, and the unfinished writing of a French teenager who died in a duel in 1832. That's the story.

The grid is not what you think it is

A QR code looks like random noise. It isn't. Before a scanner decodes a single bit of your payload, it has to find four specific structures:

Three finder patterns. The three big squares with eyes in the corners — top-left, top-right, bottom-left. Each is seven modules on a side: a black square, then a white ring, then a smaller black square. Why three? Because three points define orientation. The missing fourth corner tells the scanner which way is up. A scanner sweeps the image looking for any line that crosses one of these patterns — dark, light, dark-dark-dark, light, dark in the ratio 1:1:3:1:1. That ratio is rotation-invariant. You can tilt the phone, photograph the code upside down, take it at a 45-degree angle — the ratio holds.

Alignment patterns. Smaller 5×5 squares scattered through the interior, starting at version 2. They help the scanner correct for perspective when you photograph the code at an angle. Without them, a QR code on a curved coffee cup wouldn't reliably decode.

Timing patterns. A row of alternating black and white modules running between the top-left and top-right finders, and a matching column running between top-left and bottom-left. These give the scanner a clock — the spacing between transitions tells it exactly how wide one module is in the photographed image.

Format information. 15 bits, duplicated at two separate locations near the finders, that encode the error-correction level (L, M, Q, or H) and which of eight mask patterns was used. Before the scanner can read any data, it has to read these 15 bits. They are themselves error-corrected — BCH code, not Reed-Solomon, because the payload is tiny — so the scanner can recover them even if part of the finder area is damaged.

Anatomy of a real QR code (version 3, 29x29 modules, error-correction H, encoding nazquadri.com): finder pattern, alignment pattern, timing pattern, format information L-shape, and the data + parity region.

Everything else — the grid of seemingly random dots — is your data, plus enough redundancy to survive being partially destroyed.

The payload is a polynomial

Before I get to the redundancy, what's actually encoded?

QR codes support four modes, chosen per-segment for density:

Mode Density
Numeric (0-9) 3.33 bits per digit
Alphanumeric (45-char set) 5.5 bits per character
Byte (raw 8-bit, usually UTF-8) 8 bits per byte
Kanji (Shift-JIS) 13 bits per 2-byte character

A 4-bit mode indicator and a character count prefix each segment. You can concatenate segments with different modes in one code if mixing saves space. A URL like https://nazquadri.com/qr would encode in byte mode — 24 bytes — plus the prefix and terminator.

Once you have those bytes, you don't treat them as a stream. You treat them as coefficients of a polynomial over a finite field. This is not a metaphor. The QR encoder literally does polynomial division. To understand why, you have to understand the field.

Galois fields: arithmetic in a finite universe

A two-paragraph life worth pausing on. Évariste Galois was 20 years old when he died in a duel in 1832. The night before — believing he was about to die, which he was — he stayed up writing letters that sketched what we now call group theory and the conditions under which polynomial equations are solvable in radicals. His manuscripts were dismissed by the French Academy and sat unread for over a decade until Joseph Liouville recognised them and published in 1846. The fields named after Galois then sat in pure mathematics for another 114 years, doing nothing useful in any practical sense, until Irving Reed and Gustave Solomon found a use for them in 1960. Every QR code, every CD, every Voyager photograph rides on math an angry French teenager wrote down before getting shot in a field at dawn. Galois gets his own chapter in my book — what he means for the way a developer should think about ideas that look pointless until they're indispensable.

A Galois field, $\text{GF}(p^n)$, is a finite set with addition and multiplication that behave like the arithmetic you know — associative, commutative, distributive, every nonzero element has an inverse — but the set has only finitely many elements. For QR codes, the field is $\text{GF}(2^8)$, also written $\text{GF}(256)$: exactly 256 elements, corresponding one-to-one with the 256 possible values of a byte.

Why this field? Because each "number" in $\text{GF}(256)$ fits perfectly in one byte, so a codeword and a field element are the same physical object. And because the field's arithmetic is beautifully simple to implement in silicon: addition is XOR. That's not an oversimplification or an analogy. In $\text{GF}(256)$, adding two elements means XORing the bytes.

Multiplication is slightly more involved but also cheap. Each element of $\text{GF}(256)$ can be written as a power of a primitive element $\alpha$ (conventionally, $\alpha = 2$ under the right polynomial basis). Every nonzero byte is $\alpha^i$ for some $i$ between 0 and 254. Multiplication then becomes addition of exponents: $\alpha^i \cdot \alpha^j = \alpha^{(i+j) \bmod 255}$. Implementations precompute a 256-entry log table and a 256-entry antilog table, and multiplication is two table lookups and an add. Modern CPUs do this in a few nanoseconds. The field that was abstract algebra in 1830 is now hardware-friendly.

The specific polynomial basis for $\text{GF}(256)$ used in QR codes is $x^8 + x^4 + x^3 + x^2 + 1$ (hex 0x11D). This determines how overflow wraps when polynomial multiplication produces a result of degree 8 or higher. Different Reed-Solomon applications (CDs, DVDs, Voyager) use different primitive polynomials; the math is identical, only the table contents differ.

GF(256) arithmetic: XOR as addition, log/antilog tables as multiplication, primitive polynomial 0x11D.

Reed-Solomon: the error correction

With the field in hand, the encoder does the following: it treats the data bytes as coefficients of a polynomial $D(x)$ of degree $k-1$, where $k$ is the number of data codewords. It then multiplies $D(x)$ by $x^{n-k}$ (shifting it left to make room for parity) and computes the remainder when divided by a generator polynomial $G(x)$:

$$P(x) = D(x) \cdot x^{n-k} \mod G(x)$$

The generator is a product of consecutive minimal polynomials over $\text{GF}(256)$, chosen so that any error pattern produces a detectable, locatable residue. The final codeword is $D(x) \cdot x^{n-k} - P(x)$ — the original data followed by the computed parity. This is Reed-Solomon encoding.

The number of parity bytes $n-k$ determines how many errors you can correct. The rule is: $t = (n-k)/2$ errors are correctable if you don't know where they are (an error can be in any position), and $2t$ erasures are correctable if you do know where they are (an erasure is an "I couldn't read this module" signal). QR codes use the error-correcting form because damage isn't pre-flagged.

Four error-correction levels trade data capacity against resilience:

Level Parity ratio Recoverable
L ~7% up to 7% of codewords
M ~15% up to 15%
Q ~25% up to 25%
H ~30% up to 30%

Level H is the one that lets you put a logo in the middle.

Decoding: how the scanner corrects errors

The decoder receives a possibly-corrupted polynomial $R(x) = C(x) + E(x)$, where $C(x)$ is the correct codeword and $E(x)$ is the error polynomial. It computes syndromes — the values of $R(x)$ at specific roots of $G(x)$. If all syndromes are zero, $R = C$: no errors, decoding is done. If any are non-zero, the syndromes encode the error polynomial's structure.

From the syndromes, the Berlekamp-Massey algorithm finds the error locator polynomial — a polynomial whose roots indicate which positions in $R(x)$ are corrupt. Then Forney's algorithm computes the error values — what to XOR into each corrupt position to recover the original byte. The decoder applies the corrections and hands back the corrected data.

This is the same algorithm used by every CD player, every DVD drive, every satellite downlink. The Voyager probes use a variant to send pictures from the outer solar system. Your grocery store uses it to print UPC codes. It's 1960s mathematics that your phone is still running every time you point it at a menu.

Reed-Solomon flow: data polynomial, generator division for parity, corruption, and recovery via Berlekamp-Massey and Forney.

Masking: making the noise actually noise

Once the codeword is built, there's a problem. Some payloads — especially short URLs or numeric data — produce codewords with long runs of the same color, or large blocks of solid black, or patterns that look like finder patterns. Any of these will confuse a scanner, because the scanner's heuristics assume the data region is visually "balanced."

The solution is masking. The encoder XORs the entire data region with one of eight fixed mask patterns — simple functions of $(i, j)$ module coordinates like (i + j) mod 2 == 0 or (i*j) mod 2 + (i*j) mod 3 == 0. The choice of mask is XOR'd back out at decode time, so no information is lost.

Which mask? The encoder tries all eight, scores each one with a penalty function, and picks the mask with the lowest score. The penalty function punishes:

  1. Long runs of five or more same-colored modules in a row or column.
  2. 2×2 blocks of same-colored modules.
  3. Finder-pattern-like sequences — anything that matches the 1:1:3:1:1 ratio in the data region and could mislead the scanner.
  4. Imbalance — too many dark modules or too many light.

The chosen mask number (0-7) is written into the format information bits, so the decoder knows which pattern to XOR back out before Reed-Solomon decoding.

The eight QR mask patterns with formulas, one highlighted as selected for lowest penalty score.

Why the logo in the middle works

The QR on nazquadri.com/qr uses error-correction level H: 30% of its codewords are parity. The octopus logo sits on a chunk of the data region — well inside that 30% recovery budget. Scanners treat the modules under the logo as errors. They can't read them, so they either guess or flag them as unreadable. The Reed-Solomon decoder sees a codeword with some bytes wrong, computes the syndromes, runs Berlekamp-Massey to find the error locations, runs Forney to recover the values, and hands back the original bytes.

Three things have to stay visible for this to work:

The logo sits in the data region, which has the most redundancy. The structural elements — which have less redundancy but are essential — are outside it.

This is why branded QR codes exist at all. It's not a feature the QR spec added; it's a side effect of how the error correction was designed for a different problem (dirty factory floors, smudged printing), which happens to also tolerate deliberate artwork. The 1994 engineers at Denso Wave did not plan for Starbucks to put their logo in the middle. They planned for oil to splash on the barcode. The math doesn't care which.

The read path, compactly

Putting it all together, here's what happens in the 200 milliseconds between pointing your camera at a QR code and getting a URL:

  1. Locate. Scan the image for three 1:1:3:1:1 ratio patterns. Those are the finders. Their positions define a rough bounding quadrilateral.
  2. Rectify. Perspective-transform the image so the QR grid is square and axis-aligned. Use alignment patterns to correct distortion in the interior.
  3. Sample. At each module's calculated center, decide whether it's dark or light. This is now a 2D array of bits.
  4. Read format information. 15 bits at a fixed offset. BCH-decode them. Now you know the error-correction level and the mask number.
  5. Unmask. XOR the data region with the chosen mask pattern.
  6. Read codewords in the zigzag order defined by the spec — up and down 2-module-wide columns starting from the bottom-right.
  7. De-interleave. Data and parity are shuffled across multiple Reed-Solomon blocks to distribute damage. Undo the interleaving.
  8. Reed-Solomon decode each block. Syndromes → locator polynomial → error values → correct.
  9. Parse the payload. Read the mode indicator, character count, data — extract the URL.
  10. Open the URL.

Nine of those ten steps happen below the visible layer. You see only the tenth.

The history, very quickly

QR codes were invented in 1994 by Masahiro Hara at Denso Wave, a Toyota subsidiary. The problem: barcodes held too little data to track car parts through the manufacturing pipeline, and scanning 1D barcodes required precise alignment. Hara wanted a 2D code that a camera could find at any rotation, any reasonable angle, even if it was partly obscured by grease.

He is said to have gotten the idea for the finder patterns from the game of Go — the board's alternating arrangement of dark and light stones suggested the 1:1:3:1:1 ratio that's rare in printed text and signage. The three-corner design solves orientation. Reed-Solomon was already 30 years old and freely available, so error correction was a solved problem; Hara just needed to pick the field and the generator.

Denso Wave holds patents on QR codes but has kept the standard free to use. ISO/IEC 18004 was published in 2000. The format was adopted for URL-scanning when smartphone cameras got good enough in the late 2000s, and in 2020 the COVID pandemic made scanning QR menus a global habit in six months.

The math is older than the format. The format is older than the habit. And the habit is now so deep that three generations will have grown up never knowing a world without square dots that become URLs.

The math is hiding in plain sight.

I'm writing a book about what makes developers irreplaceable in the age of AI. Join the early access list →

Naz Quadri has generated more QR codes than he's scanned, which is probably the wrong ratio. He blogs at nazquadri.com. Rabbit holes all the way down 🐇🕳️.

Further Reading