How Does a Scratched QR Code Still Scan?

Scratch the code at level M until the decoder says Doesn’t scan. Then, without cleaning it, tap L, Q and H. The scratches stay where they are; only the code under them changes.

• At which levels does the same damage still scan?
• Watch Damaged bytes / can fix. The code doesn’t fail when a certain number of squares is spoiled. It fails when a certain number of bytes is.
• Press Show the bytes. Each byte is a little patch of 8 squares, outlined. A long scratch crosses many squares but spoils only the few bytes it passes through.
• Scratch across one of the three big squares in the corners, and nothing else.

You may have met the first step in Grades 6–8: in Which Card Was Flipped? an extra row and an extra column of cards, each making its line’s count of dark cards even, show where a single turned card is. Grade 11’s Noticing a flipped bit does the same with bytes. A parity bit is a bit added to make a group’s count of 1s even; one flipped bit makes the count odd.

The rows and columns cost 11 extra cards for 25. Richard Hamming found in 1950 that far fewer will do, if each check bit watches a cleverer group of bits.

Three circles

Here are 7 bits, numbered 1 to 7. Bits 3, 5, 6 and 7 carry a message of 4 bits. Bits 1, 2 and 4 are check bits: each makes the count of 1s inside its own circle even.

Flip one bit, any bit, and the circles that hold it go odd. The odd circles always point at exactly one place, and that is the bit that flipped.

Why the odd circles spell the place

Look at the small binary numbers beside the bits. Bit 5 is 101: a 4, no 2, a 1. Now look where bit 5 sits: inside Check 4’s circle and Check 1’s, outside Check 2’s. That is no accident. The circles were drawn so that:

• Check 1 watches every bit whose number has a 1 in its ones place: 1, 3, 5, 7.
• Check 2 watches every bit with a 1 in its twos place: 2, 3, 6, 7.
• Check 4 watches every bit with a 1 in its fours place: 4, 5, 6, 7.

So when bit 5 flips, Checks 4 and 1 go odd and Check 2 stays even: odd, even, odd, which written as binary digits is 101, the number 5. Add the odd checks, 4 + 1, and you get the same answer. The pattern of failed checks is called the syndrome, and in Hamming’s code it is the wrong bit’s number written in binary.

Three checks can each be odd or even: 2 × 2 × 2 = 8 patterns. One means “nothing wrong” (all even), and that leaves exactly 7 patterns to name bits 1 to 7. That is why the code is 7 bits long: 4 for the message, 3 to say where any one mistake is.

Where it fails

Flip two bits in the circles above. The circles still go odd, so you know something is wrong, but they point at a third bit, and Fix it makes it worse. Hamming’s code promises to fix one flipped bit in each 7, no more.

That is a problem for a QR code. A scratch doesn’t flip one bit here and one bit there. It spoils squares that sit side by side, a run of neighboring bits called a burst. Two of those in one group of 7, and Hamming’s code is fooled.

Repairing whole bytes

In 1960 Irving Reed and Gustave Solomon found a code that repairs damage a byte at a time. To it, a byte is one number from 0 to 255. If a scratch spoils one bit of a byte or all eight, it is one damaged byte either way. That is exactly what you saw in the widget at the top.

Their idea uses something from maths you already know: two points fix a straight line. Through any two points there is exactly one line.

Send the message as two points, and add two more points on the same line as extra numbers. Now one number can be scratched, any one, message or extra, and the receiver still finds it: three of the four points lie on one line, and the odd one out doesn’t (Figure 19.1). If the receiver knows which number was scratched (a smudge that can be seen), two lost numbers can be rebuilt, since any two good points give the line back. Not knowing where the damage is costs twice as much: each unknown error needs two extra numbers. Denso Wave, which made the QR code, says the same: Reed–Solomon needs twice as many extra bytes as the bytes it is to correct.

A longer message needs a curve instead of a line. Three points fix one curve shaped like a parabola (one with an x²), and in general any 5 points fix exactly one curve with up to an x⁴ in it. So a message of 5 numbers is the heights of one such curve at places 1 to 5; send its heights at places 6, 7, 8 and 9 as well, and any 2 scratched numbers can be repaired.

You will build Hamming’s code, send a message through noise, then build the byte-repairing code and scratch it.

Step 1: add the check bits

encode takes 4 message bits and gives back the 7-bit code word. It keeps the word as a list w with room for places 1 to 7 (w[0] is never used, so a bit’s place and its index are the same). The test (p // k) % 2 == 1 asks whether place p has a 1 in the ks place of its binary number: p // k drops the smaller places, and % 2 reads the last digit (Grade 9’s Number systems does this by hand).

def encode(data):    w = [0] * 8                  # w[1] to w[7]; w[0] is not used    w[3], w[5], w[6], w[7] = data    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if p != k and (p // k) % 2 == 1:                ones = ones + w[p]        w[k] = ones % 2          # 1 if the count is odd, to make it even    return w[1:] for data in [[1, 0, 1, 1], [0, 0, 0, 0], [1, 1, 1, 1], [0, 1, 1, 0]]:    print(data, '->', encode(data))

[1, 0, 1, 1] -> [0, 1, 1, 0, 0, 1, 1][0, 0, 0, 0] -> [0, 0, 0, 0, 0, 0, 0][1, 1, 1, 1] -> [1, 1, 1, 1, 1, 1, 1][0, 1, 1, 0] -> [1, 1, 0, 0, 1, 1, 0]

Step 2: find the wrong bit, every time

wrong_bit does the checks again on what arrived and adds up the ones that are odd: the syndrome. Then the program tries every mistake: each of the 16 possible messages with each of its 7 bits flipped, then with every pair of bits flipped.

def encode(data):    w = [0] * 8    w[3], w[5], w[6], w[7] = data    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if p != k and (p // k) % 2 == 1:                ones = ones + w[p]        w[k] = ones % 2    return w[1:] def wrong_bit(word):    place = 0    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if (p // k) % 2 == 1:                ones = ones + word[p - 1]        if ones % 2 == 1:            place = place + k    return place messages = []for n in range(16):    messages.append([n // 8 % 2, n // 4 % 2, n // 2 % 2, n % 2]) found = 0tried = 0for data in messages:    for p in range(1, 8):        word = encode(data)        word[p - 1] = 1 - word[p - 1]        tried = tried + 1        if wrong_bit(word) == p:            found = found + 1print('One bit flipped:', found, 'of', tried, 'found') tried = 0noticed = 0right = 0for data in messages:    for p in range(1, 8):        for q in range(p + 1, 8):            word = encode(data)            word[p - 1] = 1 - word[p - 1]            word[q - 1] = 1 - word[q - 1]            tried = tried + 1            place = wrong_bit(word)            if place != 0:                noticed = noticed + 1                word[place - 1] = 1 - word[place - 1]            if word == encode(data):                right = right + 1print('Two bits flipped:', tried, 'tried,', noticed, 'noticed,', right, 'put right')

One bit flipped: 112 of 112 foundTwo bits flipped: 336 tried, 336 noticed, 0 put right

(word[p - 1] because a list counts from 0 and the places from 1.)

Step 3: a message through a noisy line

Now send real text. Each letter is a number (Grade 7: text is numbers), written as 8 bits, and every 4 bits become a 7-bit code word. The send function is the noisy line: each bit has a 2 in 100 chance of flipping. A letter that comes out as no printable letter at all is shown as ?. random.seed(2083) makes the same “random” noise every run, so your output matches this page.

import random def encode(data):    w = [0] * 8    w[3], w[5], w[6], w[7] = data    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if p != k and (p // k) % 2 == 1:                ones = ones + w[p]        w[k] = ones % 2    return w[1:] def wrong_bit(word):    place = 0    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if (p // k) % 2 == 1:                ones = ones + word[p - 1]        if ones % 2 == 1:            place = place + k    return place def to_bits(text):    bits = []    for letter in text:        n = ord(letter)        for value in [128, 64, 32, 16, 8, 4, 2, 1]:            bits.append(n // value % 2)    return bits def to_text(bits):    text = ''    for i in range(0, len(bits), 8):        n = 0        for b in bits[i:i + 8]:            n = n * 2 + b        if 32 <= n <= 126:            text = text + chr(n)        else:            text = text + '?'    return text def send(bits, chance):    out = []    for b in bits:        if random.random() < chance:            out.append(1 - b)        else:            out.append(b)    return out def hamming_send(bits):    sent = []    for i in range(0, len(bits), 4):        sent = sent + encode(bits[i:i + 4])    return sent def hamming_read(received):    bits = []    for i in range(0, len(received), 7):        word = received[i:i + 7]        place = wrong_bit(word)        if place != 0:            word[place - 1] = 1 - word[place - 1]        bits = bits + [word[2], word[4], word[5], word[6]]    return bits message = 'MEET AT THE BHAKTAPUR DURBAR SQUARE AT 4.'random.seed(2083)bits = to_bits(message)print('Plain: ', to_text(send(bits, 0.02)))print('Hamming:', to_text(hamming_read(send(hamming_send(bits), 0.02)))) wrong_plain = 0wrong_hamming = 0letters = 0for trial in range(50):    plain = to_text(send(bits, 0.02))    fixed = to_text(hamming_read(send(hamming_send(bits), 0.02)))    for i in range(len(message)):        letters = letters + 1        if plain[i] != message[i]:            wrong_plain = wrong_plain + 1        if fixed[i] != message[i]:            wrong_hamming = wrong_hamming + 1print('Letters sent:', letters)print('Wrong without a code:', wrong_plain)print('Wrong with Hamming:  ', wrong_hamming)

Plain:  MEUT AT$THE BHAKT@PuR LU?BAR!SQUA?E AT $.Hamming: MEET AT THE BHAKTAPUR DURBAR SQUARE AT 4.Letters sent: 2050Wrong without a code: 300Wrong with Hamming:   33

Change 0.02 to 0.001 or 0.1 and run it again: a code that helps a lot on a slightly noisy line can’t keep up on a very noisy one.

Step 4: a message on a curve

Now Reed and Solomon’s code, on the clock of 251. value_at(points, x) gives the height at x of the one curve through the given points. You can use it without following every line: for each point it builds a piece that is that point’s height at that point and 0 at all the others, and adds the pieces up (this is called Lagrange interpolation, after the mathematician Joseph-Louis Lagrange). Dividing on the clock is pow(bottom, -1, P): the number that, multiplied by bottom, leaves 1.

add_extra puts the message’s 5 numbers at places 1 to 5 and adds the curve’s heights at 6, 7, 8 and 9. repair tries every way of choosing 5 of the 9 numbers it received (combinations from Python’s itertools lists them, 126 ways), draws the curve through them, and counts how many of the 9 lie on it. Two different curves of this kind can share at most 4 points, so if at most 2 numbers were damaged, the true curve passes through at least 7, and no wrong curve can.

from itertools import combinations P = 251 def value_at(points, x):    total = 0    for i in range(len(points)):        xi, yi = points[i]        top = 1        bottom = 1        for j in range(len(points)):            if j != i:                xj = points[j][0]                top = top * (x - xj) % P                bottom = bottom * (xi - xj) % P        total = (total + yi * top * pow(bottom, -1, P)) % P    return total def add_extra(message):    points = []    for x in range(1, 6):        points.append((x, message[x - 1]))    return message + [value_at(points, x) for x in [6, 7, 8, 9]] def repair(received):    for xs in combinations(range(1, 10), 5):        points = [(x, received[x - 1]) for x in xs]        curve = [value_at(points, x) for x in range(1, 10)]        agree = 0        for x in range(9):            if curve[x] == received[x]:                agree = agree + 1        if agree >= 7:            return curve[:5]    return None def text(numbers):    if numbers is None:        return "can't repair"    return ''.join(chr(n) for n in numbers) sent = add_extra([ord(letter) for letter in 'NEPAL'])print('Sent:                 ', sent)damaged = sent[:]damaged[1] = 0damaged[6] = 200print('Two bytes scratched:  ', damaged, '->', text(repair(damaged)))damaged[3] = 7print('Three bytes scratched:', damaged, '->', text(repair(damaged)))

Sent:                  [78, 69, 80, 65, 76, 12, 121, 247, 81]Two bytes scratched:   [78, 0, 80, 65, 76, 12, 200, 247, 81] -> NEPALThree bytes scratched: [78, 0, 80, 7, 76, 12, 200, 247, 81] -> can't repair

The first five numbers are the letters of NEPAL; the last four are the extra numbers. Two scratched numbers, one in the message and one extra, are repaired. Three are too many for four extra numbers, and here the program says so rather than guessing. (With more damage than it can repair, a code can also be fooled: three unlucky scratches might happen to lie on a different curve with four of the true numbers. That is why each level promises only so many.)

Step 5: scratches in a row

Last, the test that matters for a QR code. NEPAL is sent both ways: with Hamming’s code (70 bits) and with the curve’s 9 numbers as bytes (72 bits). The program scratches a run of neighboring bits, flipping every one, at every place it could start, and counts how often each code still gives back NEPAL.

from itertools import combinations P = 251 def encode(data):    w = [0] * 8    w[3], w[5], w[6], w[7] = data    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if p != k and (p // k) % 2 == 1:                ones = ones + w[p]        w[k] = ones % 2    return w[1:] def wrong_bit(word):    place = 0    for k in [1, 2, 4]:        ones = 0        for p in range(1, 8):            if (p // k) % 2 == 1:                ones = ones + word[p - 1]        if ones % 2 == 1:            place = place + k    return place def value_at(points, x):    total = 0    for i in range(len(points)):        xi, yi = points[i]        top = 1        bottom = 1        for j in range(len(points)):            if j != i:                xj = points[j][0]                top = top * (x - xj) % P                bottom = bottom * (xi - xj) % P        total = (total + yi * top * pow(bottom, -1, P)) % P    return total def add_extra(message):    points = [(x, message[x - 1]) for x in range(1, 6)]    return message + [value_at(points, x) for x in [6, 7, 8, 9]] def repair(received):    for xs in combinations(range(1, 10), 5):        points = [(x, received[x - 1]) for x in xs]        curve = [value_at(points, x) for x in range(1, 10)]        agree = 0        for x in range(9):            if curve[x] == received[x]:                agree = agree + 1        if agree >= 7:            return curve[:5]    return None def to_bits(numbers):    bits = []    for n in numbers:        for value in [128, 64, 32, 16, 8, 4, 2, 1]:            bits.append(n // value % 2)    return bits def to_numbers(bits):    numbers = []    for i in range(0, len(bits), 8):        n = 0        for b in bits[i:i + 8]:            n = n * 2 + b        numbers.append(n)    return numbers def hamming_read(received):    bits = []    for i in range(0, len(received), 7):        word = received[i:i + 7]        place = wrong_bit(word)        if place != 0:            word[place - 1] = 1 - word[place - 1]        bits = bits + [word[2], word[4], word[5], word[6]]    return to_numbers(bits) def scratch(bits, start, length):    out = bits[:]    for i in range(start, start + length):        out[i] = 1 - out[i]    return out message = [ord(letter) for letter in 'NEPAL']plain = to_bits(message)hamming = []for i in range(0, len(plain), 4):    hamming = hamming + encode(plain[i:i + 4])as_bytes = to_bits(add_extra(message))print('Bits sent: Hamming', len(hamming), ', bytes', len(as_bytes)) for length in [1, 2, 9, 10]:    ham_ok = 0    for start in range(len(hamming) - length + 1):        if hamming_read(scratch(hamming, start, length)) == message:            ham_ok = ham_ok + 1    byte_ok = 0    for start in range(len(as_bytes) - length + 1):        if repair(to_numbers(scratch(as_bytes, start, length))) == message:            byte_ok = byte_ok + 1    unit = 'bit ' if length == 1 else 'bits'    print(f'{length:2} {unit} in a row: Hamming survives {ham_ok:2} of {len(hamming) - length + 1},',          f'bytes survive {byte_ok:2} of {len(as_bytes) - length + 1}')

Bits sent: Hamming 70 , bytes 72 1 bit  in a row: Hamming survives 70 of 70, bytes survive 72 of 72 2 bits in a row: Hamming survives  9 of 69, bytes survive 71 of 71 9 bits in a row: Hamming survives  0 of 62, bytes survive 64 of 6410 bits in a row: Hamming survives  0 of 61, bytes survive 56 of 63

• a.Three check bits find any one flipped bit among seven: 112 of 112, every message, every place (Step 2). The odd checks, added up, are the place.
• b.Two flips are always noticed and never put right: 336 of 336 noticed, 0 repaired. “Fixing” them makes three wrong bits.
• c.On a noisy line, the code turns 300 wrong letters into 33 (Step 3), for 7 bits sent where 4 would do.
• d.Against scratches, bytes win (Step 5). Hamming’s code, with almost the same number of bits, is beaten by most scratches only 2 bits long: it survives only the 9 that happen to fall across the border between two of its 7-bit groups. The byte code survives every scratch up to 9 bits long, wherever it lands, because 9 neighboring bits can touch at most 2 bytes. At 10 bits it starts to fail: 7 of the 63 places touch 3 bytes.

That is why QR codes use Reed–Solomon codes. The widget at the top is the same idea, bigger. Its code is 70 bytes, and textbooks/make_scratch_qr.py, the program that made it for this page, reads from the code’s own tables how many of them are extra at each level:

Each level repairs half as many bytes as it has extra ones (rounded down), as your repair does: errors in unknown places cost two extra bytes each. Denso Wave gives the levels as about 7%, 15%, 25% and 30%; for this small code they come out a little higher. At Q and H the code is split into two blocks, each repaired on its own, with their bytes woven between each other across the code (press Show the bytes at Q: blue and green). And each byte’s 8 bits sit together in a compact patch, so a scratch spoils few whole bytes rather than a bit of many. The same program checked all four codes with two real decoders: each one still read when a block had as many damaged bytes as the table says it can repair, and failed with one more.

Longer Hamming codes. With 4 checks there are 2 × 2 × 2 × 2 = 16 patterns: “nothing wrong” and 15 places. So 4 check bits, at places 1, 2, 4 and 8, guard 11 message bits, 15 bits in all. Each check watches the places with a 1 in its own binary digit. That is Challenge ★★ below. With 5 checks, 26 message bits in 31; the longer the code, the smaller the share of check bits, and the more likely two flips land in one code word.

Two flips, noticed for sure. Add one more parity bit over all 7 bits. One flip makes the count of all 8 odd; two flips leave it even but still make some circles odd. Now one flip is fixed and two are reported as two, never “fixed” wrongly. Many computers’ memory uses this kind of code, SECDED (single error correction, double error detection). That is Challenge ★★★.

Weaving. Hamming’s code survives a scratch better if its code words are woven together: send the first bit of every word, then the second of every word, and so on. A scratch of 10 neighboring bits then flips at most one bit in each word. Try it: change Step 5 so that hamming is sent woven, and count again.

A question to think about: a QR code at level H can repair 22 of its 70 bytes. Could a cleverer code of 70 bytes carry the same message and repair 40? How would you show that some number is impossible? (Your repair gives a hint: why must the true curve agree with more points than any wrong one?)

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. The examples show what your function should give; there are more tests you can’t see.

★ Read the message

Write decode(word): word is a 7-bit Hamming code word (places 1 to 7, as a list of 7) with at most one bit flipped. Give back the 4 message bits, as they were sent, as a list.

def decode(word):    # word is 7 bits, places 1 to 7; at most one is wrong    return [0, 0, 0, 0] print(decode([0, 1, 1, 0, 1, 1, 1]))

★★ Fifteen bits

Write wrong_bit_15(word): word is a 15-bit Hamming code word (places 1 to 15) whose check bits are at places 1, 2, 4 and 8, each making the count of 1s even among the places with a 1 in its binary digit. Give back the place of the one flipped bit, or 0 if none.

def wrong_bit_15(word):    # word is 15 bits, places 1 to 15    return 0 print(wrong_bit_15([1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0]))

★★★ One fixed, two reported

Write check_8(word). word is 8 bits: word[1] to word[7] are a 7-bit Hamming code word (place p at index p), and word[0] is an extra parity bit that makes the count of 1s in all 8 even. Give back 'fine' if nothing is wrong, the index (0 to 7) of the wrong bit if exactly one is wrong, or 'two' if two bits are wrong.

def check_8(word):    # word[0] is the extra parity bit; word[1] to word[7] are places 1 to 7    return 'fine' print(check_8([0, 0, 1, 1, 0, 1, 1, 1]))

• Which Card Was Flipped? (Grades 6–8): the row-and-column trick, and the story of Hamming’s weekends.
• How Does a Barcode Catch a Typing Mistake? (Grades 6–8): one check digit that notices a mistake but can’t say where.
• Grade 9, Number systems: place values in binary, the digits this code’s checks read.
• Grade 11, How TCP makes delivery reliable: parity bits, checksums and CRCs, which mostly notice damage and ask for the data again instead of repairing it.
• Grade 9, Hashing: a different kind of extra number, one that shows a file was changed but can’t repair it.