Error Detection

Introduction

Scientists and engineers have worked very hard to make satellites that travel very far from Earth. Voyager 1 is now 13 billion miles away from Earth. When a satellite captures information about space, it must then transmit this data back to a satellite dish back on Earth. Perhaps this data is a photo of Jupiter's great red spot? Or perhaps it's data about the temperature on Neptune? Or movement data of asteroids? Regardless of what the message is we received, how do we know that the data we've received is accurate?

Unforuntately, our atmosphere gets in the way of our messages. Just like looking through a glass of water distorts the image of what's behind it, the charged particles in our atmosphere might distort some of the signals coming from the satellite.

When we receive a message, transmitted as many packets of binary numbers, there is a chance that some of the bits may be incorrect. We need a way to figure out (a) if any bits are incorrect and (b) which ones. Just like if you write a letter to someone and send it in the mail. If some of the words are blurred, you might be able to infer the original message from context -- but with 0s and 1s, we don't have any way to understand the context.

Let's think about some ways we could possibly make sure that we know the correct message.

This message-encoding scheme would consume a lot of space! Imagine if you bought a state-of-the-art smartphone with 96 GB of memory which used this type of error correction. Two thirdsOne thirdOne half of the space would be redundant data. The phone would only be able to hold less than GB of memory!

There must be a better way.

Parity Bit

One very simple and cost-effective way to detect an error in a sequences of numbers is with a parity bit. The parity bit is added to the end of the message to tell us something about the rest of the message.

For example we can add one more bit to the end of a sequence of binary numbers depending on the sum of the first bits.

If the sum is even, the parity bit is 0.

If the sum is odd, the parity bit is 1.

With this scheme, after the parity bit has been appended, the sum of the entire encoded number will be evenodd.

Adding one parity bit will not always allow the receiver to detect an error. If an evenoddprime number of bits have flipped, the parity will still be even, and no error will be detected.

This simple method of adding a parity bit gives us a hint into how we can build more complex error detection and correction schemes. Before we do that, let's look at an example that we experience quite often.

Bar Codes

We encounter error-detecting codes every time we go to the supermarket, in the form of bar codes. Bar codes are also used for identifying all sorts of things like driver's licenses or babies in hospitals. And in the last decade, 2-dimensional barcodes (QR codes) have been adapted for ticketing at events like concerts or airplane flights.

Barcodes are used for many things!

Bar codes were invented as a way to make it easier for stores to track which items a customer is buying. Numbers are easy for us humans to read, but it's much harder for computers. For example, 1 and 7 or 6 and 8 might look almost the same to a low-resolution camera. A new system was needed, so that cashiers or nurses didn't have to manually type all these numbers into a computer.

Transition: similar to morse code. Joe Woodland, one of the inventors of Bar Code was sitting on the beach, trying to think of a way to encode information for a light scanner to understand.

Woodland used his knowledge of Morse Code as a foundation to invent a new type of code. By learning about different types of codes, we can build our own knowledge foundation and perhaps invent our own codes!

The original barcode was invented as a circle, but in the 1970s an IBM engineer figured out that a rectangle would be more compact than a bulls-eye.

An early use of barcodes was for tracking train cars.

So how does it work?

Each bar code is a 12-digit number. See here that we can read the numbers written on the bottom. But how does a computer read it?

There are 95 columns, each of which can be black or white. The computer uses a laser to identify each stripe's color, based on how much light is reflected. These 95 columns are grouped into 15 groups of columns. (continue below)

Bar code values

NEW BARCODE

The guards are on the outside and in the center. The first six digits are on the left. The last six digits are on the right.

The Guards

LEFT	CENTER	RIGHT
101	01010	101

The Digits

why is left and right different?

DIGIT	LEFT SIDE	RIGHT SIDE
0
1
2
3
4
5
6
7
8
9

There are a few interesting patterns we can recognize here. First, notice that the codes on the left side are different from the codes on the right side. This allows the bar code to be read upside down or backwards.

Barcodes in different countries

These barcodes with 12 digits are how they work in the US. In Europe, there are 13 digits. And other countries have different protocols for how barcodes. work.

Digit Value

• The first digit represents what type of object it is (0 - Standard; 2 - Weighted item like fruit; 3 - Pharmacy; 5 - Coupon)
• Digits 2-6 (highlight) represent the Manufacturer's Code
• The 7-11 (highlight) represent the Product Code
• The final, 12th digit (highlight) is the Error-Detection digit, also called the Modulo Check Character

Different between Left and Right

Every binary representation of digits on the left begins with a 0 and ends with a 1, and every digit on the right begins with a 1 and ends with a 0. This results in a pattern: there will always be a 10 (on the left side) or a 01 (on the right side) on the edge between digits.

Error Checking.

Just like our case with the satellite signals, there is a chance that the laser reading the barcode can make a mistake. Perhaps there is some dirt, or a scratch, or the laser reads it incorrectly. For that reason, barcodes have a special way of determining whether there's been a mistake.

The 12th digit is dependent on the first 11 digits, so that if any of the digits is wrong, we will know (most of the time). Can you guess how the 12th digit can indicate information about the first 11?

The odd digit places are summed and multiplied by three. Then we calculate the sum of the even places, and sum these two values together. The Modulo Check Character is 10 minus the ones digit of this number.

Calculating the Error-Check Digit

When the computer scans the digits of a barcode, it performs this calculation. If the modulo check doesn't match up, we immediately know that the barcode hasn't been read correctly. In a supermarket, the cash register won't beep, and you can try again -- or, as a last resort, enter the numbers manually.

Pick the barcodes that have a valid error-check character.

ACTIVITY: Look around you for something with a barcode (pretty much anything you can buy at a store). Hide the numbers with paper or tape, and try to decode the numbers. After you've written down your answer, see if you're correct! And then you can try the error detection formula and confirm that it is correct. (PHOTOS also)

Barcode Conclusion

These are only the UPC bar codes. There are many other types of bar codes listed here: http://www.makebarcode.com/specs/barcodechart.html

Hamming Codes

Let's go back to our original problem of how we might detect errors in a message received from a satellite. We don't know the message the satellite intended to send, and unlike with barcodes there is no way to find it, such as a cashier who can look at the number and type it into the computer.

A mathematician named Richard Hamming encountered a very similar problem not with data from satellites, but with mechanical computers.

If the computer can tell when an error has occurred, surely there is a way of telling where the error is so that the computer can correct the error itself. - Richard Hamming

How can we detect and correct an error in a messaage that is just a sequence of binary numbers? A Hamming Code can be used to do just this. The solution involves inserting new bits into the message that will tell us information about the values of those original bits. If we know the location of where an error occurred, then we know the original value of that bit because binary digits can only have two valueswe can just look at the number under the barcode.

Encoding a Hamming Code

Click through the slides to see how to encode a string of bits using a Hamming Code.

Did you notice anything about how the bits for each parity group are selected? The answer has to do with the binary valuedivisibility of each digit position.

Here is how to select the digits to include in a parity group.

1. Convert the place numbers to binary.
2. Identify the parity groups. Each will be a power of 2.
3. For each parity group, select any digit whose binary place number has a **1** in that position.

Continue

Some table formatting would be nice.

Decoding a Hamming Code

Now that we have an encoded message, how can we extract the data from it? We must reverse the process.

Click through the slides to see how to decode a string of bits using Hamming Codes.

This is not a perfect system. This type of code will not correctly detect an error when there are more than errors.

Other Error Detection and Correction

PHOTO? Software applications often include a MD5 or SHA-1 checksum that indicates they came from a valid source.