Error detection techniques

Data is transmitted from one device and received by another.

We need to be able to detect if there are errors when receiving data. Fortunately, when transmitting and receiving data, there are techniques to detect errors and correct them.

Parity check method

Another ingenious method for error detection when transmitting data is to include a parity bit with the data.

The transmitting and receiving systems can agree which kind of parity check they are going to use: even parity or odd parity.

Let's agree that we will use even parity.

The following data is going to be transmitted:

0 1 1 0 1 0 0

How many 1s are there? 3. Which parity check method are we using? Even parity. Is 3 an even number? No. So, let's add a parity bit to the data:

0 1 1 0 1 0 0 1

The data is sent and the receiving system counts all of the 1s in the data. If it is an even number (becuase we agreed to use even parity), no error is detected.

Look at the following data:

1 0 1 0 0 0 0

We are still using the even parity system. What data will be transmitted?

click me

What if we had decided to use odd parity check on the above data? What data would be sent?

click me

How will the system receiving the information know that the data is correct?

Is it possible for the receiving system to count the correct number of 1s but still receive the incorrect information?

Checksum method

This is quite a simple method.

The device sending the data creates a value by doing a calculation on the data.

This value is transmitted along with the data.

The receiving device does the same calculation on the data.

The value that was sent is then compared with the value that the receiving device calculated.

If they do not match, it means an error has been detected!

Check Digit method

You go to the library and you check out a book. The librarian scans the book's ISBN number into the computer system.

How can the computer system confirm that the scanner sent the correct information?

ISBN technology uses a Check Digit method of error detection and this is how it works:

The book has the following ISBN:

978-0-306-406157

This data is sent to the computer system and the computer does the following calculation:

• Starting on the left, multiply the first number by 1, the next number by 3, the next number by 1 etc until the last-but-one number is reached.
• Add the results together.
• Divide the result by 10 and find the remainder
• Minus the remainder from 10

So, using the above information, here is the calculation:

• 9*1 + 7*3 + 8*1 + 0*3 + 3*1 + 0*3 + 6*1 + 4*3 + 0*1 + 6*3 + 1*1 + 5*3
• = 9 + 21 + 8 + 0 + 3 + 0 + 6 + 12 + 0 + 18 + 1 + 15
• = 93
• 93/10 = 9 and the remainder is 3
• 10-3 = 7

So, the Check Digit is 7. The computer looks at the final digit in the ISBN number and compares it with the check digit. If they are the same, the computer is confident that it received the ISBN correctly from the scanner.

978-0-306-40615-7

If the information is not the same, the computer will send a signal back to the scanner and perhaps a beep will sound and the librarian will have to rescan the ISBN.

Many different algorithms have been designed for the check digit method of error detection. This method is also used in barcodes in a supermarket or checking details on a bank card at an ATM.

Note: in an exam question, you would be given the algorithm to use to calculate the check digit and possibly the method for checking that the digit is correct.