Methods of error detection

The need to check for errors When data is transmitted, there is always a risk that it may be corrupted, lost or even gained.

Errors can occur during data transmission due to:

» Interference (all types of cable can suffer from electrical interference, which can cause data to be corrupted or even lost)

» Problems during packet switching (this can lead to data loss – or it is even possible to gain data!)

» Skewing of data (this occurs during parallel data transmission and can cause data corruption if the bits arrive out of synchronization).

Error checking is such an important part of computer technology. The following section considers a number of ways that can be used to check for errors.

There are a number of ways data can be checked for errors following transmission:

» parity checks

» checksum

» echo check.

Parity checks Parity checking is one method used to check whether data has been changed or corrupted following data transmission. This method is based on the number of 1-bits in a byte of data. The parity can be either called EVEN (that is, an even number of 1-bits in the byte) or ODD (that is, an odd number of 1-bits in the byte). One of the bits in the byte (usually the most significant bit or left-most bit) is reserved for a parity bit. The parity bit is set according to whether the parity being used is even or odd. For example, consider the byte:

A careful study of Table 2.3 shows the following: » byte 8 (row 8) now has incorrect parity (there are three 1-bits) » bit 5 (column 5) also now has incorrect parity (there are five 1-bits). First of all, the table shows that an error has occurred following data transmission (there has been a change in parity in one of the bytes).

Secondly, at the intersection of row 8 and column 5, the position of the incorrect bit value (which caused the error) can be found.

The 1-bit at this intersection should be a 0-bit; this means that byte 8 should have been:

0 0 0 1 0 0 1 0 which would also correct column 5 giving an even vertical parity (now has four 1-bits).

This byte could therefore be corrected automatically as shown above, or an error message could be relayed back to the sender asking them to re-transmit the block of data.

Checksum A checksum is a method used to check if data has been changed or corrupted following data transmission.

Data is sent in blocks, and an additional value, called the checksum, is sent at the end of the block of data. The checksum process is as follows:

» When a block of data is about to be transmitted, the checksum is calculated from the block of data

» The calculation is done using an agreed algorithm (this algorithm has been agreed by sender and receiver)

» The checksum is then transmitted with the block of data

» At the receiving end, the checksum is recalculated by the computer using the block of data (the agreed algorithm is used to find the checksum)

» The re-calculated checksum is then compared to the checksum sent with the data block

» If the two checksums are the same, then no transmission errors have occurred; otherwise a request is made to re-send the block of data.

Echo check With echo check, when data is sent to another device, this data is sent back again to the sender.

The sender’s computer compares the two sets of data to check if any errors occurred during the transmission process. As you will have no doubt worked out, this isn’t very reliable. If the two sets of data are different, it isn’t known whether the error occurred when sending the data in the first place, or if the error occurred when sending the data back for checking.

However, if no errors occurred, then it is another way to check that the data was transmitted correctly. In summary:

» A copy of the data is sent back to the sender

» The returned data is compared with the original data by the sender’s computer

» If there are no differences, then the data was sent without error

» If the two sets of data are different, then an error occurred at some stage during the data transmission.

Check digits A check digit is the final digit included in a code; it is calculated from all the other digits in the code.

Check digits are used for barcodes on products, such as International Standard Book Numbers (ISBN) and Vehicle Identification Numbers.

(VIN). Check digits are used to identify errors in data entry caused by mis-typing or mis-scanning a barcode. They can usually detect the following types of error:

» An incorrect digit entered, for example 5327 entered instead of 5307 .

» Transposition errors where two numbers have changed order, for example 5037 instead of 5307.

» Omitted or extra digits, for example 537 instead of 5307 or 53107 instead of 5307.

» Phonetic errors, for example 13 (thirteen), instead of 30 (thirty).

There are a number of different methods used to generate a check digit. Two common methods will be considered here: » ISBN 13 » Modulo-11.

Sample barcode (ISBN 13 code with check digit)

The modulo-11 method can have varying lengths of number which makes it suitable for many applications, such as product codes or VINs.

The first calculation is the generation of the check digit. The second calculation is a verification of the check digit (that is, a recalculation).

Calculation 1 – Generation of the check digit from the other digits in a number (In this example, we will assume the original number contained only 7 digits.)

The following algorithm generates the check digit from the other 7 digits:

1 each digit in the number is given a weighting of 8, 7, 6, 5, 4, 3 or 2 starting from the left (weightings start from 8 since the number will become eight-digit when the check digit is added)

2 the digit is multiplied by its weighting and then each value is added to make a total.

3 the total is divided by 11.

4 the remainder is then subtracted from 11 to find the check digit (note if the remainder is 10 then the check digit ‘X’ is used)

The example to be used has the following seven-digit number:

1- 7-digit number: 4 1 5 6 7 1 0 weighting values: 8 7 6 5 4 3 2

2- sum: (8 × 4) + (7 × 1) + (6 × 5) + (5 × 6) + (4 × 7) + (3 × 1) + (2 × 0) = 32 + 7 + 30 + 30 + 28 + 3 + 0 total = 130

3- divide total by 11: 130/11 = 11 remainder 9.

4 subtract remainder from 11: 11 – 9 = 2 (check digit) So we end up with the following eight-digit: 4 1 5 6 7 1 0 2.

Calculation 2 – Re-calculation of the check digit from the eight-digit number (which now includes the check digit)

To check that the eight-digit number is correct, including its check digit, a similar process is followed:

1- each digit in the number is given a weighting of 8, 7, 6, 5, 4, 3, 2 or 1 starting from the left

2- the digit is multiplied by its weighting and then each value is added to make a total

3- the total is divided by 11

4- the number is correct if the remainder is zero

Using the 8-digit number: 4 1 5 6 7 1 0 2

1- weighting values: 8 7 6 5 4 3 2 1

2- sum: (8 × 4) + (7 × 1) + (6 × 5) + (5 × 6) + (4 × 7) + (3 × 1) + (2 × 0) + (1 × 2) = 32 + 7 + 30 + 30 + 28 + 3 + 0 + 2 total = 132

3- divide total by 11: 132/11 = 12 remainder 0

4- remainder is 0, therefore number is correct.

2.2.4Automatic Repeat Requests (ARQs) We have already considered parity checks and echo checks as methods to verify that data has arrived at its destination unchanged. An Automatic Repeat Request (ARQ) is a third way used to check data following data transmission. This method can best be summarised as follows:

» ARQ uses positive and negative acknowledgements (messages sent to the receiver indicating that data has/has not been received correctly) and timeout (this is the time interval allowed to elapse before an acknowledgement is received)

» the receiving device receives an error detection code as part of the data transmission (this is typically a Cyclic Redundancy Check – refer to Section 2.1.1); this is used to detect whether the received data contains any transmission errors

» if no error is detected, a positive acknowledgement is sent back to the sending device

» however, if an error is detected, the receiving device now sends a negative acknowledgement to the sending device and requests re-transmission of the data

» a time-out is used by the sending device by waiting a pre-determined amount of time ….

» ... and if no acknowledgement of any type has been received by the sending device within this time limit, it automatically re-sends the data until a positive acknowledgement is received ….

» ... or until a pre-determined number of re-transmissions has taken place.

» ARQ is often used by mobile phone networks to guarantee data integrity.