Barcodes, Check Digits and Error Correction

克里斯——在这个节目的听众have been getting in touch with their shopping product barcodes, Matt asked for the first numbers of the barcode and then managed to predict the last number. So Matt, time to reveal all. How do you do it?

马特,我做同样的计算the checkout does at the supermarket when you scan a product because we deliberately put a pattern into the digits in barcodes. So what you need to do is as the person is calling out the numbers, initially, you need to remember and then add together every second digit. So ignore the first one, remember the second one, ignore the 3rd one, add on the 4th one. And so, you add every 2nd digit together, you then get this total, you multiply that by 3 and then you add on the the digits you skipped over, and the grand total in all UK product barcodes, if you add every 2nd digit, multiply by 3, add on the other digits, it's always a multiple of 10. And so, if I do that calculation, I know the last digit is whatever is required to bring the total up to the nearest whole multiple of 10.

If you were listening earlier, I sounded a bit uncertain when I predicted the last digit was a zero on someone's barcode and that's because I already had a multiple of 10 without the final digit. But thankfully, it was a zero because it didn't have to increase it. It's a bit tricky in your head to keep track of two different totals and then multiply one by 3 and add them together. It depends how much free time you're prepared to throw at learning it, I guess. I am a hoot at parties, but a lot of people wonder why is that pattern there?

It's actually because of the very last digit in your barcode. All the other digits are the actual product code and the last digit is added on afterwards, just to make that pattern work. It's called a check digit and because you have this check digit, that completes the pattern.

A checkout can double-check the pattern is there when it scans the barcode and it knows when the laser reader has misscanned a barcode. So this way, we catch most of the mistakes that would otherwise be entered when barcodes are misscanned at the checkout.

Chris - So, this is effectively a way of making sure that the scan has occurred correctly by just reading one number rather than having to read the whole lot again. You've actually got the whole thing in one number in order to check your work.

Matt - Yep, so it can check straightaway because people get upset if it was just entering a number without checking if it's right or not. You might scan a packet of crisps and get charged for a big screen television, and people get very emotional about these things, unless it's the other way around I guess. But this way, the checkout knows if it's a real barcode number or if it's just a random misscanned number.

Chris - It's not just barcodes that this science applies to though, does it because this same technology can be used to rebuild data that's missing from things. We famously on the Naked Scientists drilled a hole in a CD and it still played beautifully. Because of this sort of redundancy, you can use the numbers in these check digits to work out what would've been there previously.

Matt - Yes, CDs use what I think is the Reed-Solomon form of error correction. Text messages do this, digital television does this. They all work pretty much like a Sudoku where with the Sudoku, if you know the mathematical patterns in a grid of numbers, you can recreate all the missing numbers just using the patterns.