📱 Scan Me If You Can — From Bits to QR Codes

Ages: 11–14  ·  Duration: 105 minutes  ·  Topics: Binary encoding, ASCII, Unicode, Error detection & correction, Galois fields, Reed-Solomon codes, QR code structure

Part 0 — Warm-Up: Twenty Questions with a Computer (10 min)

The Big Idea

"You've scanned hundreds of QR codes — restaurant menus, concert tickets, WiFi passwords. But have you ever stopped to ask: how does a camera turn a jumble of tiny squares into a website? Today, we find out — and by the end, you'll know enough to build one by hand."

Let's start with a game you already know.

🗣️ "I'm thinking of a number between 1 and 100. You can ask yes-or-no questions. How many questions do you need to guarantee you find it?"

The trick: cut the possibilities in half each time. Seven questions suffice for 1–100 because $2^7 = 128 > 100$.

Each yes/no answer is one bit of information (from binary digit). A bit has exactly two values: 0 or 1 — like a light switch, a coin flip, or a black-vs-white square.

Quick Practice

Part 1 — ASCII: Every Letter Has a Secret Number (≈ 15 min)

Setting the Scene

In 1963, American engineers agreed on a standard code called ASCII — the American Standard Code for Information Interchange. The idea: assign each character a number from 0 to 127.

The One-Bit Trick

Compare 'A' and 'a' bit by bit:

'A' = 0 1 0 0 0 0 0 1   (65)
'a' = 0 1 1 0 0 0 0 1   (97)
            ^
      Only this bit differs!

The difference: $97 - 65 = 32 = 2^5$. Exactly one bit — bit 5 — controls uppercase vs. lowercase.

Quick Detour: Unicode

Unicode is the modern standard with over 150,000 characters. ASCII is a perfect subset of UTF-8 — everything we learn today still works! The 🎉 emoji takes 4 bytes (32 bits).

Part 2 — The QR Code Challenge ⭐ (≈ 20 min)

You're given an empty $21 \times 21$ grid. Your mission: fill in the squares to encode the letter 'A' so a phone camera can read it. Then show what changes for 'B' and 'a'.

Anatomy of a QR Code

A Version 1 QR code is a $21 \times 21$ grid of modules. Not all carry data — some are fixed furniture:

The Encoding Recipe — Byte Mode

The Big Reveal: Swapping Letters

☕ Break (5 min)

Part 3 — Error Correction: Mathematics to the Rescue (≈ 10 min)

The Noisy Channel Problem

Hamming Distance

The Hamming distance between two bit strings = the number of positions where they differ.

QR Error Correction Levels

Solution 1 — Repetition: Say It Three Times 🥉

The simplest fix: send every bit three times. Decode by majority vote.

Original:   0  1  0  0  0  0  0  1
Tripled:  000 111 000 000 000 000 000 111   (24 bits for 8!)

Solution 2 — Parity Bits: The Cheapest Detector 🥈

Add one extra bit that makes the total number of 1s always even.

For 'A' = 01000001: two 1s (even) → parity bit = 0 → send 01000001 0.

For 'a' = 01100001: three 1s (odd) → parity bit = 1 → send 01100001 1.

If any single bit flips, the total becomes odd → error detected!

Solution 3 — Hamming(7,4): Find AND Fix 🥇

4 data bits + 3 parity bits = 7 total. Parity bits sit at positions 1, 2, 4 (powers of 2). Each covers positions whose binary representation has a 1 in that column.

Worked Example

Protect the first nibble of 'A' = 0100:

$d_1=0, d_2=1, d_3=0, d_4=0$

Parity bits: $p_1 = 0 \oplus 1 \oplus 0 = 1$, $p_2 = 0 \oplus 0 \oplus 0 = 0$, $p_3 = 1 \oplus 0 \oplus 0 = 1$.

Codeword: 1 0 0 1 1 0 0

If noise flips position 5 → received 1 0 0 1 0 0 0.

Syndrome: $s_3 s_2 s_1 = 101_2 = 5$ → error at position 5! Flip it back. ✓

Solution 4 — Reed-Solomon: QR's Polynomial Shield 🎓

Hamming codes correct single-bit errors. But a coffee stain on a QR code doesn't flip one lonely bit — it obliterates entire bytes in a cluster. QR codes need something far more powerful: Reed-Solomon codes.

The Core Insight: Polynomials as Data

Forget bits for a moment. Think about polynomials.

A polynomial of degree $n$ is uniquely determined by $n + 1$ points. A straight line (degree 1) passes through 2 points. A parabola (degree 2) needs 3. If you have more points than the minimum, you can afford to lose some and still recover the curve.

Analogy: Imagine you want to transmit a straight line $y = 3x + 5$. Only 2 points define it — but you send 5 points instead. Even if 1 point gets corrupted, 4 correct points still overdetermine the line. With enough redundancy, you can find and fix the bad point.

Wait — Why Not Regular Numbers?

Here's the catch. Ordinary arithmetic breaks polynomial codes:

• Multiplying two bytes can give a result > 255 — it doesn't fit in a byte anymore.
• Division often gives non-integers — and we need exact byte values.

We need a number system where:

1. There are exactly 256 elements (one for each byte: 0x00 – 0xFF).
2. You can add, subtract, multiply, and divide and always stay within those 256 values.
3. Division by any nonzero element is exact — no fractions, no remainders.

Such a system exists. Mathematicians call it a Galois field.

GF(256) — The Secret Number System Inside Every QR Code

GF(256) — also written $\mathbb{F}_{256}$ or $\text{GF}(2^8)$ — is a finite field with exactly 256 elements. "GF" stands for Galois Field, named after Évariste Galois, the French mathematician who invented the theory at age 18 (and tragically died in a duel at 20).

Elements: Bytes as Polynomials

Each element of GF(256) is a byte — a value from 0 to 255. But we think of it as a polynomial with binary coefficients of degree ≤ 7:

For example:

Addition in GF(256): XOR

Addition is the simplest part — it's just bitwise XOR! Since coefficients are binary (0 or 1) and $1 + 1 = 0$ in binary arithmetic (no carrying!), adding two polynomials is pure XOR:

In polynomial form: $(x^4 + x + 1) + (x + 1) = x^4$. The $x$ and constant terms cancel!

Multiplication in GF(256): Polynomial Multiplication mod a Special Polynomial

Multiplication is trickier. We multiply the polynomials normally, but then reduce modulo an irreducible polynomial of degree 8:

This polynomial is to GF(256) what a prime number is to modular arithmetic — it can't be factored, and dividing by it gives well-behaved remainders.

Example: Multiply $3 \times 7$ in GF(256).

$3 = x + 1$ and $7 = x^2 + x + 1$.

(Remember: $x^2 + x^2 = 0$ and $x + x = 0$ — they cancel.) The result is 9, already below degree 8, so no reduction needed.

When do we reduce? When the product has degree ≥ 8, we divide by $p(x)$ and keep the remainder — just like clock arithmetic, but with polynomials. This guarantees the result is always a valid byte (0–255).

The Generator Element $\alpha = 2$

GF(256) has a special property: the element $\alpha = 2$ (i.e., $x$) is a generator. If you keep multiplying by 2:

The powers cycle through all 255 nonzero elements before returning to 1 at $\alpha^{255} = 1$. This means:

• Every nonzero byte can be written as $\alpha^k$ for some $k$ from 0 to 254.
• Multiplication becomes addition of exponents: $\alpha^i \cdot \alpha^j = \alpha^{(i+j) \bmod 255}$.
• Division becomes subtraction of exponents: $\alpha^i / \alpha^j = \alpha^{(i-j) \bmod 255}$.

This is how QR decoders multiply efficiently: just look up the exponents in a table, add them, and look up the result. A $256 \times 256$ multiplication table compressed into two 256-entry tables!

Why 256?

This is no coincidence. $256 = 2^8$, and one byte is 8 bits. By working in GF($2^8$), every field element fits in exactly one byte. No overflow, no fractions, no wasted space. This is why Reed-Solomon is so natural for digital data: the math and the hardware speak the same language.

Reed-Solomon Encoding: Step by Step

Now we have our number system. Here's how Reed-Solomon actually protects a QR message.

Step 1: Form the Message Polynomial

Your $k$ data codewords $d_0, d_1, \ldots, d_{k-1}$ become coefficients of a polynomial:

For a Version 1-L QR code: $k = 19$ data codewords, so $m(x)$ has degree 18.

Step 2: Build the Generator Polynomial

To produce $t$ error correction codewords, we build a generator polynomial $g(x)$ of degree $t$:

Remember: subtraction = XOR in GF(256), so $x - \alpha^i = x + \alpha^i$ here. For Version 1-L with $t = 7$:

Multiplying these out (in GF(256) arithmetic) gives a degree-7 polynomial with known coefficients.

Step 3: Polynomial Long Division

Shift $m(x)$ up by multiplying by $x^t$, then divide by $g(x)$:

The remainder $r(x)$ has degree < $t$ — its coefficients are your error correction codewords!

Step 4: Transmit Everything

The full transmitted codeword is:

By construction, $g(x)$ divides $c(x)$ evenly. The receiver checks this: if the remainder isn't zero, errors occurred — and the math can pinpoint exactly which bytes are wrong.

Worked Example: Encoding "A" with 4 EC Bytes

Let's trace a small example with $k = 1$ data byte and $t = 4$ EC bytes.

Data: ASCII 65 = 0x41. Message polynomial: $m(x) = 65$.

Generator: $g(x) = (x + 1)(x + 2)(x + 4)(x + 8)$ — a degree-4 polynomial in GF(256).

Shift: $x^4 \cdot m(x) = 65\,x^4$.

Divide $65\,x^4$ by $g(x)$ in GF(256) arithmetic → remainder $r(x) = r_3 x^3 + r_2 x^2 + r_1 x + r_0$.

Those four remainder coefficients are the error correction bytes. The transmitted block is: [65, r₃, r₂, r₁, r₀].

Decoding: Finding and Fixing Errors

When the receiver gets a (possibly corrupted) message, the Reed-Solomon decoder:

1. Computes syndromes: Evaluate the received polynomial at $\alpha^0, \alpha^1, \ldots, \alpha^{t-1}$. If all zero → no errors!
2. Locates errors: Uses the Berlekamp-Massey algorithm (or Euclid's algorithm) to find which byte positions are wrong.
3. Fixes them: Computes the correct values using Forney's algorithm.

QR Code EC in Practice

Here's what each QR error correction level allocates for Version 1 (21×21, 26 total codewords):

At level H, 17 out of 26 codewords are error correction — you can obliterate nearly a third of the code and it still scans. This is why companies can slap logos right in the middle of QR codes!

Summary

Encoding Chain

Method Comparison

Extensions & Challenge Problems 🧩

Answer Key

← Back to all lectures