Error checking

​Think of the game 'Chinese Whispers'  the message that the first person whispers has to be transmitted, through a group of people until it reaches its final destination.  It is not very often that the message will reach its destination completely intact and unchanged... this is an error in transmission.  Transmission errors can also occur when one digital device attempts to transmit data to another, this can have a huge impact on productivity and as such methods have been designed to spot and correct these errors.

What causes errors in transmission?

When data does not arrive correctly we know that there has been some sort of error.  Come of the causes of these errors are:

Power Surges
Synchronization issues
Broken or damaged cables
Electrical interference

Sometimes these issues can cause the bits to transpose - flip from 1 to 0 or 0 to 1

Checking for Errors

It is important that any errors in transmission are spotted to prevent miscommunication. Computers have a number of methods of spotting errors, these are:

Parity Checks
Check Digits
Check Sums
ARQ (Automatic Repeat reQuests)
​Echo Checking
  • Parity Checks
  • Check Digits
  • Check Sums
  • ARQ
  • Echo Checking
<
>

parity checking

Parity Bits

When transferring data from one location to another, one method of error checking that can be used is the parity bit system.

The parity bit system involves first deciding whether odd or even parity will be used.  This means that the number of ones and zeros in a string of bits will even or odd.

When sending data, one single bit is added to ensure that the data has an odd or even number of 1s or 0s.
Example:
If a computer system had decided to use odd parity, it means that the number of 1s and 0s must be odd.  

​So if we take the binary number:
1
1
O
1
O
O
1
The parity bit system means that we will now add an additional bit to the right side of the binary number. This bit is called a parity bit and it is used to set the number of 1s and 0s to either odd or even.

​In this case we are using an odd system there for we need the parity bit to be 1:
Parity Bit
   
1
1
1
O
1
O
O
1
Now with the addition of our parity bit we can see that there are a total of 5 x 1s and 3 x 0s in the binary number, both 5 and 3 are odd numbers so the odd parity criteria is met.

How Parity Bits Work


Before data is transmitted, both parties agree to use either odd or even parity.

The parity bit is set by the sending party and checked by the receiver

If the number of bits do not match the even or odd system it is clear that there could have been an error.

The receiver notifies the sender that the parity check failed and asks for the data to be reset.
Warning
The parity check is not perfect, it will fail to detect an error in transmission if more than one bit is altered as the re still could be the correct (odd or even) parity, however the bits could be in the wrong order.

Parity Blocks

A parity block uses the same odd and even system to detect errors in data, however rather than focusing on a single binary value, the block system will allow errors to be detected within a virtual table of data.

Applying a parity bit to each row and each column of the data table will allow any error to be detected quickly and the erroneous value to be found.

A parity block might look something like this:
​
In the table above you can see that there are 8 bytes being transmitted. Column 1 and Row 8 have been designated to hold the parity bits in the parity block.

In this system you can see that the Even parity system has been used, this means that:

Row 8 - The bits in row 8 are designated as 1 or 0 to ensure that the total number of 1s and 0s in each Column is EVEN
Column 1 - The bits in Column 1 are designated as 1 or 0 to ensure that the total number of 1s and 0s in each Row is EVEN

In the table above, all data is correct and all parity bits are correct.

Finding an error

If the data in the table above was sent across a network and one of the bits transposed then there is an easy way to find it using the table.
Step 1
Manually check each column to ensure that there still remains an even number of 1s and 0s according to the even system that we are using. Work your way through each column until you find one that is odd.
​
In the diagram above you can see that Column 5 has been discovered as incorrect.  There are 5 1s and 3 0s therefore it has failed the parity check.  At this point we do not know specifically which bit has transposed.

Step 2
To find the specific error we now need to work through each row of bytes searching for any byte that may fail the even parity check.
In the above diagram you can see that Row 5 was discovered to fail the even parity check.  This byte has 3 1s and5 0s.

The bit in which the incorrect column and incorrect row intersect will be the specific incorrect bit.  In this case the bit flipped from a 1 to a 0.

Check Digits

A check digit is an additional digit that is added to the end of a string of numbers.  The check digit is calculated by processing each number in the string through an algorithm, the result is then simply added to the end.  

After the string of numbers is transmitted or input to a system, the same algorithm will be followed on the numbers. If the algorithm produces the same number that is the check digit, you can safely assume that the data was transmitted / input correctly.  If the check digits do not match, you know that an error has occurred.
Check digits are commonly used in barcodes, In the bar code below you can see that the check digit is the right most digit - 3
The barcode check digit is calculated by following the Modulo 10 algorithm. This is explained using the below example.
Example:

For this example we will attempt to calculate the check digit for the bar code image above.  If the check digit is correct we should produce the number 3.

As already mentioned, check digits are often calculated using the Modulo 10 algorithm.  Here are the steps of the algorithm:
1.  Starting from the left most number multiply each bar code digit by 1 and 3 alternating.  in this example it would mean the following:
2.   The next step is to add every multiplication result, in this case the result is 47:
3.   Now that we have this total we must divide it by 10 and take note of the remainder, in this case the remainder is 7
4.  The final step is to take the remainder and subtract it from 10.  In this case it produces the number 3:
The final result here is 3 which matches the original check digit therefore we can conclude that the data is correct.

CheckSums

A check sum is very similar to a check digit, however instead of being used on a string of numbers e.g. a bar code, the check sum is calculated by processing all of the data through an algorithm and it produces a "hash" code that is more than one digit long.

2 very common check sum algorithms are MD5 and SHA1

Checksums are used for many things including downloading of software or the processing of credit card numbers.

How it works:
  1. The first step is that all of the data in a file or program is processed through an algorithm.  This algorithm will produce a checksum that could look like this "fSrfk12!£%sdfr$fs"
  2. The data / file is then sent to the recipient, the check sum is also sent to the recipient
  3. The recipient will run the received data / file through the same algorithm to produce a check sum. 
  4. The recipient will now compare the checksum sent from the sender to the one that they have produced themselves. If they match it is safe to assume that the data is error free.  If the checksums do not match a request should be sent to re-send the data.

Visualise the process

Follow the diagrams below step by step to help visualize how checksums can be used in data transmission.

1. In the scenario below you can see that the red character has a file that they wish to send to the blue character:
​
2. The two parties have agreed to implement a checksum for safety.  This now means that before the file is sent, the red character will process the blue file through a check sum algorithm which will produce a checksum...

3. Now that the sender has generated a checksum for the blue file, they will send the file AND the check sum to the receiver:

4. The receiver will not open the file yet.  Before they can be sure that no errors have occurred during transmission, the received file must be processed through the same checksum algorithm used by the sender.  This will produce a second version of the checksum:

5. Now that the file recipient has generated a checksum for the received file they can compare it to the checksum that they received from the file sender.
If the two checksums are identical then the receiver can be confident that the file has not been altered / corrupted in transmission.
If the two checksums are not identical then the receiver should be weary that the file has been altered or corrupted during transmission.​
​

ARQ - Automatic Repeat Request

ARQ is the 4th error checking method that we will look at.  ARQ is simply a system that is set up between sender and recipient to ensure that both parties are aware  of any errors that occurred during transmission and that the correct steps are taken to fix the errors.

How it works:
  1. At the start of the transmission a timer is set e.g. 10 seconds
  2. Data is then sent
  3. If the data is received within 10 seconds, the recipient will send an acknowledgement to the sender and the transmission is complete
  4. If the timer reaches 10 seconds and no acknowledgement of recipt has been recieved,  the sender will resend the data to the recipient

Echo Checking

The Echo Checking method is designed for the sender to check if the data has been correctly sent to / received by the recipient.

How does it work
Echo checking works using the following steps:
  1. The sender will send the data to the recipient
  2. The data received by the recipient is automatically sent back to the sender
  3. The sender will compare the data that they sent with the data that was returned to them
  4. If the two sets of data do not match than an error in transmission has been identified.

​Visualizing the process
​1. The sender will send the data to the recipient
2. The data received by the recipient is automatically sent back to the sender
3. The sender will compare the data that they sent with the data that was returned to them
4. If the two sets of data do not match than an error in transmission has been identified.
If the files do match then the sender can be confident that the data reached the recipient succesfully.

Possible issues?

One limitation of the Echo Checking system is that data has to be transmitted twice before a check is complete.

This means that once the original sender has sent their original data and received a returned copy of the data, there would have been two transmission processes. If an error is detected, the sender will not know if the error occurred during the original transmission or if it occurred during the transmission of the returned copy.

If the transmission occurred during the transmission of the returned copy back to the sender, a comparison of the original data and the returned data will lead the sender to believe that an error has occurred.  In fact it is possible that the recipient received the data with no problems but now the sender will attempt to re send the data anyway.