How Does a Barcode Catch a Typing Mistake?

Play with the number above.

• a.Change one digit at a time. Is a mistake ever missed?
• b.Now press Swap with next and tap a digit: it swaps places with the digit to its right. Swap a few pairs. Are they all caught?

Why 3 and 8? Keep that question in mind. The answer is in how the check digit is worked out.

Each digit is multiplied by a weight: 1, 3, 1, 3, and so on along the number. Then the answers are added up. For a correct barcode, the total always ends in 0: it is a multiple of 10. The last digit, the check digit, is chosen to make that happen.

Here is the pen’s number, worked out:

The total is 4 + 0 + 0 + 18 + 3 + 24 + 1 + 9 + 3 + 9 + 9 + 9 + 1 = 90. It ends in 0, so the number passes.

Why one wrong digit is always caught

Suppose one digit is typed wrong: it is too big or too small by some amount, say by 4. If that digit has weight 1, the total changes by 4. If it has weight 3, the total changes by 3 × 4 = 12. Either way the total no longer ends in 0, so the mistake is caught.

Could the change ever be a whole 10, so that the total still ends in 0? A digit can only be wrong by 1 to 9. Times 1, that is 1 to 9: never 10. Times 3, that is 3, 6, 9, 12, 15, 18, 21, 24 or 27: never a multiple of 10 either. So every single wrong digit is caught.

Why some swaps slip through

Now swap two neighbors. One of them had weight 1 and the other weight 3, and after the swap each gets the other’s weight. If the two digits are 3 and 8:

• before: 3 × 1 + 8 × 3 = 3 + 24 = 27
• after: 8 × 1 + 3 × 3 = 8 + 9 = 17

The total drops by exactly 10, so it still ends in 0, and the swap is missed. A swap always changes the total by twice the difference between the two digits. 8 − 3 = 5, and 2 × 5 = 10. So the shop barcode misses a swap exactly when the two digits differ by 5: 0 and 5, 1 and 6, 2 and 7, 3 and 8, 4 and 9.

With blocks

Here is the till’s check as a block program. It asks for the 13 digits one at a time, adds up each digit times its weight, and at the end looks at the remainder when the total is divided by 10, which is its last digit. (The weight starts at 1. set weight to 4 − weight turns 1 into 3 and 3 back into 1.)

In Python (from Grade 8)

The same check in Python is a short function. A barcode is a string of 13 digits; code[i] is one digit, and int() turns it into a number.

def ean_valid(code):    total = 0    for i in range(13):        if i % 2 == 0:            weight = 1        else:            weight = 3        total = total + int(code[i]) * weight    return total % 10 == 0 print(ean_valid('4006381333931'))   # the penprint(ean_valid('4076381333931'))   # one digit wrongprint(ean_valid('4006831333931'))   # 3 and 8 swapped

TrueFalseTrue

i % 2 == 0 is true for places 0, 2, 4…, which get weight 1 (Python counts places from 0).

Try every mistake

Typing mistakes one at a time is slow. A program can make every possible mistake in a number and count how many are caught. This one tries every single wrong digit (each of the 13 places, each of the 9 other digits) and every swap of two different neighbors.

The second method in it is the one books used before 2007, the ISBN-10: ten digits, weights 10, 9, 8… down to 1, and the total must divide exactly by 11. Its check digit can come out as 10, which is written X.

def ean_valid(code):    total = 0    for i in range(13):        if i % 2 == 0:            weight = 1        else:            weight = 3        total = total + int(code[i]) * weight    return total % 10 == 0 def isbn_valid(code):    total = 0    for i in range(10):        if code[i] == 'X':            value = 10        else:            value = int(code[i])        total = total + value * (10 - i)    return total % 11 == 0 def try_mistakes(code, valid):    wrong = 0    wrong_caught = 0    for i in range(len(code)):        for d in '0123456789':            if d != code[i]:                mistake = code[:i] + d + code[i + 1:]                wrong = wrong + 1                if not valid(mistake):                    wrong_caught = wrong_caught + 1    swaps = 0    swaps_caught = 0    missed = []    for i in range(len(code) - 1):        if code[i] != code[i + 1]:            mistake = code[:i] + code[i + 1] + code[i] + code[i + 2:]            swaps = swaps + 1            if not valid(mistake):                swaps_caught = swaps_caught + 1            else:                missed.append(code[i] + code[i + 1])    print(code, ': wrong digits caught', wrong_caught, 'of', wrong)    print('   swaps caught', swaps_caught, 'of', swaps, ', missed:', missed) try_mistakes('4006381333931', ean_valid)try_mistakes('9780306406157', ean_valid)try_mistakes('0306406152', isbn_valid)

4006381333931 : wrong digits caught 117 of 117   swaps caught 8 of 9 , missed: ['38']9780306406157 : wrong digits caught 117 of 117   swaps caught 11 of 12 , missed: ['61']0306406152 : wrong digits caught 90 of 90   swaps caught 9 of 9 , missed: []

(code[:i] is the part of the string before place i, and code[i + 1:] the part after it.)

• Every single wrong digit was caught, in every number: 117 of 117, and 90 of 90. (The widget below also tries an X in the book number’s last place, so it counts 91 of 91.)
• The shop barcode missed a swap in both of its numbers: 3 and 8 in the pen’s number, 6 and 1 in the barcode on a book. Both pairs differ by 5.
• The old book number, the ISBN-10, caught every swap.

Why does ISBN-10 do better? A swap of two neighbors changes its total by exactly the difference between the two digits (their weights differ by 1). The difference is 1 to 9 (or 10 with an X), and none of those divides by 11. Dividing by 11 instead of 10 is what makes it work, but it costs something: the check “digit” can be 10, which needs the letter X.

This little program checks every pair of digits at once, in any barcode:

missed = []for a in range(10):    for b in range(10):        if a != b:            before = a * 1 + b * 3    # a has weight 1, b has weight 3            after = b * 1 + a * 3     # swapped            if (after - before) % 10 == 0:                missed.append(str(a) + str(b))print(len(missed), 'of 90 swaps are missed:', missed)

10 of 90 swaps are missed: ['05', '16', '27', '38', '49', '50', '61', '72', '83', '94']

So the shop barcode catches 80 of the 90 kinds of swap, about 9 in 10, and every wrong digit. For a till, where the shopkeeper can see the product’s name on the screen, that is good enough.

Many numbers in your life end in a check digit. Try the same mistakes on each kind.

• Shop barcodes (EAN-13): weights 1 and 3, total ends in 0. Since 1 January 2007 every new book’s number, its ISBN, is a 13-digit barcode number starting with 978 or 979, checked the same way.
• Old book numbers (ISBN-10): weights 10 down to 1, total divides by 11.
• Bank cards: the long number on a debit or credit card ends in a check digit worked out by the Luhn method, invented by Hans Peter Luhn at IBM (patented in 1960). It doubles every second digit. It catches every wrong digit and almost every swap of neighbors; the one swap it misses is 09 and 90.
• Verhoeff’s method: in 1969 the Dutch mathematician Jacobus Verhoeff published the first check for ordinary digits that catches every wrong digit and every swap of neighbors. Instead of weights, it mixes the digits with a table built from the ways a regular pentagon can be turned and flipped. India’s Aadhaar numbers use it.

A check digit says that, not where. If a barcode fails the check, can the till work out which digit is wrong and fix it? Try it in the first widget: make one mistake, then think about every way to change one digit of the wrong number so that it passes. How many are there? (Challenge ★★★ asks a program to find them all.)

Other kinds of mistakes. People also type “twin” mistakes (22 for 55) and jumps (swapping two digits with one between them, 123 → 321). Change the try_mistakes program to try these. Which methods catch them?

★ Make the check digit (blocks)

Finish the program so that, after the 12 digits are typed, it says the check digit and nothing else (for 400638133393 it says 1). Then press Test.

★★ The smudged book number (Python, from Grade 8)

One digit of an ISBN-10 is smudged and shows as ?. Write missing_isbn(isbn) that gives back the digit that must have been there, as a string ('0' to '9', or 'X' if it is the last place and must be 10). Every test has exactly one answer.

def missing_isbn(isbn):    # isbn is 10 characters, one of them '?'    return '0' print(missing_isbn('?306406152'))

★★★ Every possible fix (Python, from Grade 8)

A barcode has failed the check. Write fixes(code) that gives back a list of every valid barcode that differs from code in exactly one digit. Any order is fine. What do you notice about how many there are?

def fixes(code):    # code is 13 digits; give back every valid barcode one digit away    return [] print(len(fixes('4006381333932')))

• Grade 6, Zeros and Ones: how a computer stores numbers and text as bits.
• Grade 8, Functions: writing functions like ean_valid that answer a question.
• Grade 9, Data in Depth: more on how data is stored and checked.
• Which card was flipped? Add one row and one column of cards, and you can find and fix a mistake, not just spot it.