You point a phone at a square of black and white dots and a web address appears. It still works when the code is creased, smudged, or half-covered by a logo. That robustness is not luck: inside the pattern sits an algebraic error-correcting code from 1960, wrapped in a layout designed in 1994 for reading fast from any angle.

This post builds a QR code from the ground up: text to bits, bits to codewords, codewords to pixels. At each step it shows the mathematics that makes the step work. Everything marked as a demo is live, and runs on a small encoder I wrote for this page, so you can type, click, and break things.

Type anything. Hover (or tap) a module to see what it is. Tick “Colour the parts” to see the structure we are about to dissect.

The big picture

Producing a symbol is a pipeline:

  1. Choose a mode and encode the text as bits (numbers, letters and bytes are packed differently).
  2. Split the bits into 8-bit codewords and add error-correction codewords computed with a Reed–Solomon code.
  3. Draw the fixed patterns a scanner needs to find and orient the symbol.
  4. Place the codeword bits in a zig-zag through the free modules.
  5. Mask: XOR the data area with one of eight patterns, whichever scans best.
  6. Write the format information: which error-correction level and mask were used, protected by its own small code.

Two pieces of algebra do the heavy lifting: arithmetic in the finite field with 256 elements (for the error correction), and a pair of short BCH codes (for the metadata). Everything else is bookkeeping, and cleverly chosen bookkeeping at that.

Anatomy of a symbol

A QR code comes in 40 versions. Version \(v\) is a square grid of

\[N = 17 + 4v\]

modules per side: 21 × 21 for version 1, 25 × 25 for version 2, up to 177 × 177 for version 40. A quiet zone of four light modules must surround it.

The same symbol, with its parts coloured. Hover to identify them.

Not every module carries your data. The rest are function patterns:

  • Finder patterns are the three big squares in the corners. A line through the centre of one, in any direction, crosses dark, light, dark, light, dark in the ratio 1 : 1 : 3 : 1 : 1. That ratio is rare in ordinary images, so a scanner can find a candidate in a single pass over the picture, at any rotation. Three corners (not four) tell the scanner which way is up.
  • Separators are a light margin around each finder.
  • Timing patterns are the alternating dark/light lines between the finders. They let the scanner count modules accurately even if the image is slightly warped.
  • Alignment patterns (from version 2) are small squares that correct for perspective distortion on larger symbols. Version 7, for example, has them centred at coordinates 6, 22 and 38.
  • Format information (15 bits, stored twice) and, from version 7 up, version information (18 bits, stored twice).
  • One always-dark module next to the lower-left finder.

Everything left is the data region, filled with data codewords, then error-correction codewords, then possibly a few “remainder” bits that don’t make up a full byte.

From text to bits

Modes

QR codes pack text differently depending on what it contains. Our encoder picks the most compact mode that can represent the whole string:

Mode Characters Packing
Numeric 0–9 3 digits → 10 bits
Alphanumeric 0–9, A–Z, space and $ % * + - . / : 2 characters → 11 bits
Byte anything (we use UTF-8) 1 byte → 8 bits

(A fourth mode packs Kanji at 13 bits per character; this post skips it.)

The packing is just information theory in miniature: you need \(\lceil \log_2 q^n \rceil\) bits to write down \(n\) symbols from an alphabet of size \(q\). Three digits take \(\lceil \log_2 1000 \rceil = 10\) bits; two alphanumeric characters take \(\lceil \log_2 45^2 \rceil = \lceil \log_2 2025 \rceil = 11\) bits. For the alphanumeric mode, a pair of characters with values \(a\) and \(b\) is stored as the single number \(45a + b\). The letters HE become \(17 \cdot 45 + 14 = 779\), which is 01100001011.

The bit stream

The bits are assembled in a fixed order:

  1. a 4-bit mode indicator (0001 numeric, 0010 alphanumeric, 0100 byte),
  2. a character count, whose width depends on mode and version (for example 9 bits for alphanumeric in versions 1–9, 11 bits in versions 10–26),
  3. the payload itself,
  4. a terminator of up to four 0 bits,
  5. zeros up to a byte boundary, and
  6. pad bytes 11101100 and 00010001 (236 and 17) alternating until every data codeword slot is full.

“HELLO WORLD” at level M: 74 bits of real content, padded out to 16 data codewords. Change the text and watch the mode and version change.

Why the version matters here. The character-count field is wider in larger versions, so the encoder cannot pick the version first and the bits second; it checks whether the bits fit in each version in turn and takes the smallest that works.

The mathematics of error correction

Now the part that makes QR codes survive damage. The idea: do not store the 16 data bytes alone. Store a longer list of bytes in which the extra ones are carefully computed from the data, so that if some bytes get destroyed, the rest still determine the original uniquely.

Bytes as polynomials: the field GF(256)

Start with the two-element field \(\mathbb{F}_2 = \{0, 1\}\), where addition is XOR and multiplication is AND. A byte \(b_7 b_6 \dots b_0\) is read as a polynomial with coefficients in \(\mathbb{F}_2\):

\[b(x) = b_7 x^7 + b_6 x^6 + \dots + b_1 x + b_0 .\]

Addition is coefficient-wise, so it is XOR of the bytes. Every element is its own negative (\(a + a = 0\)), which means subtraction and addition are the same operation, a fact that simplifies every formula below.

Multiplication is polynomial multiplication, which can produce degree up to 14, followed by reduction modulo a fixed polynomial of degree 8. QR codes use

\[p(x) = x^8 + x^4 + x^3 + x^2 + 1 \qquad (\text{0x11D}).\]

Because \(p\) is irreducible over \(\mathbb{F}_2\), the quotient \(\mathbb{F}_2[x] / (p(x))\) is a field: every non-zero byte has a multiplicative inverse. This field has \(2^8 = 256\) elements and is written GF(256) or \(\mathbb{F}_{256}\).

The polynomial \(p\) is also primitive: the element \(\alpha = x\) (the byte 00000010) has multiplicative order 255, so its powers \(\alpha^0, \alpha^1, \dots, \alpha^{254}\) run through all 255 non-zero bytes exactly once. Reducing \(x^8\) modulo \(p\) gives \(\alpha^8 = x^4 + x^3 + x^2 + 1 = \text{0x1D} = 29\), and from there every power is “multiply by 2, and XOR in 0x11D if the byte overflowed”.

That gives a second way to multiply, using logarithms:

\[a \cdot b = \alpha^{(\log_\alpha a + \log_\alpha b) \bmod 255} .\]

Try 87 and 131: their XOR is 212, their product in GF(256) is 49, and the logarithm route (189 + 247 ≡ 181 mod 255, and α^181 = 49) agrees.

Here is the whole multiplication, in the shift-and-add form that the demo (and the tests) use:

// Multiply two bytes in GF(256) modulo x^8 + x^4 + x^3 + x^2 + 1 (0x11D)
function gfMul(x, y) {
  let z = 0;
  for (let i = 7; i >= 0; i--) {
    z = (z << 1) ^ ((z >>> 7) * 0x11d); // z * x, reduced if it overflowed
    z ^= ((y >>> i) & 1) * x;           // add x when bit i of y is set
  }
  return z;
}

Reed–Solomon codes

A Reed–Solomon code takes the message bytes \(m_{k-1}, \dots, m_0\) as coefficients of a polynomial \(m(x)\) over GF(256) and appends \(n\) extra bytes so that the resulting polynomial \(c(x)\) vanishes at the first \(n\) powers of \(\alpha\):

\[c(\alpha^i) = 0 \qquad \text{for } i = 0, 1, \dots, n-1 .\]

Equivalently, \(c(x)\) is divisible by the generator polynomial

\[g(x) = \prod_{i=0}^{n-1} (x - \alpha^i) = (x - 1)(x - \alpha)(x - \alpha^2) \cdots (x - \alpha^{n-1}) .\]

For \(n = 2\) this is \((x + 1)(x + 2) = x^2 + 3x + 2\), because here \(\alpha = 2\), addition is XOR, and \(1 \oplus 2 = 3\). The encoder simply computes the remainder of \(m(x)\, x^{n}\) divided by \(g(x)\) and appends it; because addition and subtraction coincide, adding that remainder makes the result divisible by \(g\):

\[c(x) = m(x)\, x^{n} + \bigl( m(x)\, x^{n} \bmod g(x) \bigr) .\]

For “HELLO WORLD” at level M the 16 data codewords produce \(n = 10\) error-correction codewords: 196 35 39 119 235 215 231 226 93 23.

Why this corrects errors

The key fact is a statement about distance. Suppose a non-zero codeword had only \(w \le n\) non-zero coefficients, at positions \(p_1, \dots, p_w\). The conditions \(c(\alpha^i) = 0\) for \(i = 0, \dots, w-1\) would read

\[\sum_{j=1}^{w} c_{p_j} \, (\alpha^{p_j})^{\,i} = 0 \qquad (i = 0, \dots, w-1),\]

a linear system whose coefficient matrix is a Vandermonde matrix in the distinct numbers \(\alpha^{p_1}, \dots, \alpha^{p_w}\). Such a matrix is invertible, so the only solution is \(c_{p_j} = 0\), a contradiction. Hence every non-zero codeword has at least \(n + 1\) non-zero bytes: the code has minimum distance \(d = n + 1\), the best possible for its size (it meets the Singleton bound).

Two codewords therefore differ in at least \(n + 1\) positions, so if at most

\[t = \left\lfloor \frac{n}{2} \right\rfloor\]

bytes are wrong, the damaged word is still closer to the original than to any other codeword, and the original can be recovered. (If you know where the bytes are missing, called erasures, you can recover up to \(n\) of them.)

Recovery is a small algebra problem. The decoder computes the syndromes \(S_i = r(\alpha^i)\) of what it received: all zero means no detectable error. Otherwise the syndromes are the power sums of the unknown error values, and Berlekamp–Massey finds the error-locator polynomial whose roots are the error positions; a Chien search finds those roots, and Forney’s formula gives the error values to XOR away. The demo below runs exactly that algorithm, written from scratch for this page.

Click bytes to corrupt them. Up to ⌊n/2⌋ = 5 are repaired exactly; one more and the decoder reports that it is overloaded. (With far more errors than the budget, a decoder usually notices it is overloaded, but it can occasionally be fooled into “repairing” to a different valid codeword.)

The four levels

The symbol records which of four error-correction levels was used. They are named for the rough share of codewords that can be restored:

Level Nominal recovery Version 1: EC codewords Version 1: damaged codewords repairable
L ~7 % 7 3 of 26
M ~15 % 10 5 of 26
Q ~25 % 13 6 of 26
H ~30 % 17 8 of 26

Higher levels spend more of the symbol on redundancy, so they hold less data and need a bigger version for the same text.

Blocks and interleaving

A Reed–Solomon codeword over GF(256) is at most 255 bytes long, and large symbols hold more than that. They are split into several blocks, each with its own error correction. The blocks are then interleaved, first byte of every block, second byte of every block, and so on. The reason is geometry: damage from a scratch or a coffee stain is concentrated in one region, and interleaving spreads it thinly over many blocks instead of destroying one.

Version 5 at level Q, for example, has 134 codewords in four blocks of 15 + 18, 15 + 18, 16 + 18 and 16 + 18 (data + error correction), so each block can repair 9 bytes.

Use the demo below to see this in a real symbol. It covers a growing square in the middle with damage and runs the decoder:

Raise the slider. For this address, the largest centred square that still decoded covered roughly 2 % of the symbol at level L, 6 % at M, 10 % at Q and 16 % at H (the exact numbers depend on which codewords the square happens to hit). Each block has its own error budget, shown by the bars.

A caveat. The reader in this demo already knows where the corner patterns are. A real phone has to find them in a photograph first, so a logo placed over a finder pattern ruins a code far sooner than the same area elsewhere.

Placing the bits, then masking

The zig-zag

Codeword bits are written into the free modules in a two-module-wide column, starting at the bottom right, moving upward, then turning around at the edge and coming back down the next column pair, skipping the vertical timing pattern. Function patterns are simply stepped over. The path is fixed, so the decoder can read the bits back in the same order.

Why mask?

Any data, such as a run of identical letters, can produce large blank or solid areas, or accidentally reproduce a finder pattern, and both confuse scanners. So the encoder XORs the data region with one of eight fixed patterns, defined by simple formulas in the row \(i\) and column \(j\) of a module (flip the module when the condition holds):

  • mask 0: \((i + j) \bmod 2 = 0\)
  • mask 1: \(i \bmod 2 = 0\)
  • mask 2: \(j \bmod 3 = 0\)
  • mask 3: \((i + j) \bmod 3 = 0\)
  • mask 4: \((\lfloor i/2 \rfloor + \lfloor j/3 \rfloor) \bmod 2 = 0\)
  • mask 5: \((ij) \bmod 2 + (ij) \bmod 3 = 0\)
  • mask 6: \(\bigl((ij) \bmod 2 + (ij) \bmod 3\bigr) \bmod 2 = 0\)
  • mask 7: \(\bigl((i + j) \bmod 2 + (ij) \bmod 3\bigr) \bmod 2 = 0\)

Which of the eight is best? The standard defines a penalty score, and the encoder keeps the mask with the lowest:

  • N1: 3 points for every run of five same-coloured modules in a row or column, plus 1 for each extra module.
  • N2: 3 points for every 2 × 2 block of one colour.
  • N3: 40 points for every pattern that looks like a finder (dark, light, dark, light, dark in the ratio 1 : 1 : 3 : 1 : 1) with four light modules on one side.
  • N4: 10 points for every 5 % by which the proportion of dark modules differs from 50 %.

The starred mask wins. Tick the box to see the eight patterns on their own.

Mask choice is a heuristic, not a necessity. Every mask yields a perfectly valid symbol; the penalty only predicts which will be easiest to scan. The rule is also deterministic, so two correct encoders agree: ours matches the production library behind this site’s /api/qr module for module.

Format and version information: BCH codes

There is a chicken-and-egg problem. To read the data a decoder needs to know the error-correction level and the mask (to undo it), but those facts cannot be stored in the masked, error-corrected data area. So they live in the corners, protected by a different, much smaller code.

The format information is 15 bits: 2 bits for the level (01 L, 00 M, 11 Q, 10 H), 3 bits for the mask number, and 10 check bits. The check bits come from a BCH code: treat the 5 data bits as a polynomial \(d(x)\) over \(\mathbb{F}_2\) and take the remainder of \(d(x)\, x^{10}\) modulo

\[g(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 \qquad (\text{0x537}).\]

Finally the 15 bits are XORed with the fixed string 101010000010010, so that no combination is ever all zeros.

A worked example: level L (01) with mask 4 (100) gives the data bits 01100. Their BCH remainder is 1000111101, so the codeword is 011001000111101, and after the XOR the stored bits are 110011000101111.

Of the \(2^{15}\) possible 15-bit strings only 32 are valid format words, and any two of them differ in at least 7 bits. A word with up to 3 flipped bits is therefore still closest to the right one. The symbol stores two copies, in different corners, as a second layer of protection.

From version 7 on the decoder also needs the version. It is stored the same way: 6 data bits plus 12 BCH check bits from the generator \(x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^5 + x^2 + 1\) (0x1F25). Across all 34 version words (7 to 40) the minimum distance is 8. Version 7 is 000111110010010100.

Capacity

Capacity depends on the version, the error-correction level and the mode:

Version Level Data codewords Numeric Alphanumeric Byte
1 (21 × 21) L 19 41 25 17
1 (21 × 21) H 9 17 10 7
40 (177 × 177) L 2956 7089 4296 2953
40 (177 × 177) H 1276 3057 1852 1273

So the largest code stores about 7,000 digits, or about 3,000 bytes, with minimal error correction.

What I built, and what I checked

The demos on this page run on a small encoder, qr-core.js, about 600 lines (a third of them comments and lookup tables) with no dependencies. It follows the standard’s structure: modes, bit stream, blocks, Reed–Solomon, placement, masks, penalties, format bits, and it exposes every intermediate result so the demos can show them. Then I wrote a test suite whose job is to prove it wrong:

  • Its output matches the production library behind this site’s QR generator module for module on 300 random inputs across all three modes and all four levels, on every mask, and at the extremes (version 40).
  • An independent decoder (jsQR) reads its symbols back to the exact input.
  • GF(256) arithmetic is cross-checked three ways (shift-and-add, log tables, and the field axioms), and the format and version codes match the standard’s published values.
  • The Reed–Solomon decoder repairs random errors up to the limit and, beyond it, reports overload in the large majority of trials (it can occasionally be fooled, as noted above).

One of the tests failed on my first try, and the failure was my own mistake: I had written that the format code has minimum distance 8. The test measured 7. That is why this post says 7: a BCH(15, 5) code corrects exactly three bit errors.

It does not implement everything in the standard: no Kanji mode, no mixed-mode segments, no ECI headers, no Micro QR. For real use, use a real library, which is exactly what this site does.

Further reading

  • ISO/IEC 18004, the QR Code standard itself.
  • I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields”, Journal of the Society for Industrial and Applied Mathematics, 1960.
  • Project Nayuki’s QR Code generator library, the clearest reference implementation I know. The two block-count tables in qr-core.js are copied from it (MIT licence), as redistributed by the uqr library; the rest is original.
  • Thonky’s QR code tutorial, a patient step-by-step walkthrough.