The Mathematics Behind QR Codes

Put a logo in the middle of a QR code, smudge a corner, or tear off a strip, and your phone will often scan it anyway. At the highest error-correction level, a QR code can lose about 30% of its data and still decode perfectly.

That isn't the scanner guessing. The lost information is rebuilt exactly using polynomial algebra over a finite field, a branch of math that sounds abstract but is hiding in every restaurant menu and boarding pass.

Damage Is Planned For

A QR code isn't just your data turned into black and white squares. A large share of the squares carry redundant data, extra information calculated from the message so that missing pieces can be reconstructed.

It's like sending a message along with a set of mathematical "checksums" so powerful that the checksums alone can rebuild the damaged parts.

A Bit of History

The QR ("Quick Response") code was invented in 1994 by Masahiro Hara and his team at Denso Wave, a Toyota group company. Factory barcodes could hold only about 20 characters, and workers had to scan several barcodes on each box of car parts.

Hara reportedly took inspiration from the game of Go, a grid of black and white stones. Denso Wave chose not to enforce its patent, which helped QR codes spread worldwide.

The Geometry: Versions and Modules

A QR code is a square grid of modules (the small black and white squares). The size depends on the version, from 1 to 40:

Modules per side = 4 × version + 17

A version 40 code can hold up to 7,089 numeric digits or about 2,953 bytes of binary data at the lowest error-correction level.

Finding the Code: Finder Patterns

The three large squares in the corners are finder patterns. Each one has a ratio of dark to light modules along any line through its center of:

1 : 1 : 3 : 1 : 1

That ratio stays the same no matter the viewing angle or distance, because ratios are preserved under scaling. A scanner sweeps across the image looking for this ratio, finds three corners, and works out the code's position, size and rotation.

Real photos are taken at an angle, so the scanner corrects for perspective distortion with a projective transformation, a 3 × 3 matrix mapping the tilted square back to a flat grid. You can practice the matrix operations with the matrix multiplication calculator.

Encoding the Data

Data is converted into bits using the most compact mode available:

• Numeric mode: groups of 3 digits become 10 bits (since 999 < 2¹⁰ = 1,024)
• Alphanumeric mode: pairs of characters from a 45-character set become 11 bits (since 45² = 2,025 ≤ 2¹¹ = 2,048)
• Byte mode: 8 bits per byte

Numeric mode uses about 3.33 bits per digit, while storing digits as text bytes would use 8. That's why QR codes holding only numbers can be much smaller. See the power-of-2 cutoffs on the binary to decimal converter.

Error Correction: Reed–Solomon Codes

QR codes use Reed–Solomon codes, published in 1960 by Irving Reed and Gustave Solomon at MIT Lincoln Laboratory. There are four levels:

Here's the core idea. Treat the data bytes as the coefficients of a polynomial. A polynomial of degree k − 1 is completely determined by any k of its points, just as two points determine a line. If you store more than k values, you can lose some and still recover the polynomial.

Reed–Solomon does this in GF(256), a finite field with exactly 256 elements, one for each possible byte. In this field, addition is XOR and every non-zero element has a multiplicative inverse, so all the usual algebra works with bytes. With 2t error-correction bytes, the code can repair up to t corrupted bytes whose positions are unknown.

Masking: Avoiding Bad Patterns

Raw data could accidentally create large blank areas or fake finder patterns that confuse scanners. So the encoder tries 8 different mask patterns, each defined by a simple formula on the row i and column j:

Mask 0: (i + j) mod 2 = 0
Mask 1: i mod 2 = 0
Mask 2: j mod 3 = 0
…

Each mask flips modules where its formula is true. The encoder scores all 8 results with penalty rules and picks the best one. The mask number is stored in the code's format information, which is itself protected by a separate error-correcting code.

Two Concepts Worth Knowing

Finite Fields

A finite field is a number system with a finite number of elements where you can add, subtract, multiply and divide (except by zero). Finite fields exist only when the size is a prime power: 2, 3, 4, 5, 7, 8, 9, and so on. GF(256) = GF(2⁸) is ideal for computers.

Polynomial Interpolation

Interpolation means finding the polynomial through a set of points. The same idea underlies secret-sharing schemes, where a secret can be rebuilt from any k of n shares.

Quick Answer: How Do QR Codes Work?

A QR code encodes data as binary modules on a square grid. Three finder patterns let a camera locate and straighten the grid. Reed–Solomon error correction, based on polynomials over the finite field GF(256), adds redundant data so the code can still be read with up to 30% of it damaged.

Try Them Yourself

• Binary to Decimal Converter: see how digits pack into bits
• Binary to Hexadecimal Converter: bytes in GF(256) notation
• Matrix Multiplication Calculator: the math behind perspective correction
• Algebra Formulas: polynomial basics
• Number Theory Formulas: modular arithmetic for masks
• How Error-Correcting Codes Make Digital Communication Possible: the bigger picture

Generate a QR code, cover a corner with your thumb, and scan it. Then cover a finder pattern and try again. You'll see which parts are protected by math and which ones aren't.