2.2 Methods of Error Detection

Why?

  • Computers expect data in certain formats

  • If a computer is not given the data in the correct format, it will fail to complete the task

  • An error of corruption occurs when data is not received as expected

How?

  • Errors can occur due to interference such as wire degradation or electrical fields changing the signal

  • Data loss, gain or change can occur if interference occurs

  • Physical barriers can block wireless technology such as radio signals and Wi-Fi

Detection Methods

There are 3 ways that data can be checked for errors:

  1. Parity checks

  2. Checksums

  3. Echo checks

Parity Check

A parity check determines whether bits in a transmission have been corrupted. Every byte that is sent has one of its bits allocated as a parity bit. Both the sender and receiver must agree on whether they will use odd or even parity. If the numbers do not match the agreed parity, then an error has occurred.

A parity will only check that an error has occurred not where it occurred.

Even Parity

If even parity is used, then the total number of 1s including the parity bit must equal an even number.

As an example:

0 1 0 1 1 0 1 0
The most left bit is the parity bit.

Adding all of the 1s together (including the parity bit) gives a total is 4. If the
parity bit was 1, then the total would be 5 which is an odd number and odd parity
would have been used.

Odd Parity

If odd parity is used, then the total number of 1s including the parity bit must equal an odd number.

As an example:

1 0 1 0 0 1 0 0
The most left bit is the parity bit.

Adding all of the 1s together (including the parity bit) gives a total is 3. If the
parity bit was 0, then the total would be 2 which is an even number and even parity
would have been used.

Errors

An error can occur when the total number of bits does not match the agreed parity. Bits can be flipped or changed due to interference to the wire or the wireless signal.

As an example:
Agreed parity -> ODD

Original:
1 0 1 0 1 0 1 1

Received:
1 1 0 0 0 0 0 1

The sender sent a total of 5 bits. The reciever only received 3 bits. However, the
parity check fails to detect bit swaps that cause the parity to remain the same. In
this case, the computer will receive incomplete information yet it will fail to
recognise that an error has occurred.

Parity Bytes & Blocks

These can be used to check if an error has occurred and where it is located.

  • A parity block consists of a block of data with the number of 1s totalled horizontally and vertically

  • A parity byte is also sent with the data which contains the parity bits from the vertical parity calculation

In the above image, 9 bytes have been transmitted. It has been agreed that even parity will be used. The parity byte has been sent. By calculating the number of bits, we find that there is an error with byte 8, bit 5.

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

Checksum

This is a method used to check it data has been 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. Checksums can check for errors but cannot say where they occurred.

If the sum of all the bytes is <= 255, then the checksum is the sum of all the bytes

If the sum of all the bytes is > 255, then the checksum is calculated with the algorithm below

Algorithm:

X = sum of all the bytes Y = X / 256 Round Y down to the nearest whole number Z = Y x 256 Checksum = X - Z

Echo Check

When the data is sent to another device, the data is sent back again to the sender. The sender will then compare the two sets of data and determine if there is an error.

This is not very reliable as if an error does occur, it is unknown whether the error occurred on the way to the receiver or on the way back. However, if no errors occur, then it shows that the data was transmitted correctly.

Check Digits

Check digits determine if data has been corrupted but not where the error occurred. Data is sent in blocks and an additional check digit value is added at the end.

Check digits are custom user-created algorithms that perform mathematical calculations on data. An example of this is ISBN and barcodes.

Sample answer:

It's a validation method It's used to check data entry The digit is calculated from the data and added to it The digit is recalculated once the data has been inputted The two digits are compared If they match, then there are no errors but if they do not match, then an error is detected

ISBN

  • Each book has an ISBN that identifies the book

  • Check digit value is the final number

  • The check digit number is specifically chosen so that when the algorithm is completed as a whole, the sum is a whole number (an integer) with no remainders.

  • If when a check digit algorithm is performed on an ISBN and the result is a whole number, then the ISBN is valid.

The algorithm: Multiply each ISBN digit by 1 to 10 and add them all up Take the total number and divide it by 11

As an example:

ISBN Value -> 965-448-765-9

9 x 1 =  9
6 x 2 =  12
5 x 3 =  15
4 x 4 =  16
4 x 5 =  20
8 x 6 =  48
7 x 7 =  49
6 x 8 =  48
5 x 9 =  45
9 x 10 = 90

9 + 12 + 15 + 16 + 20 + 48 + 49 + 48 + 45 + 90 = 352

352 / 11 = 32

The answer is a whole number so the ISBN is valid.

Barcodes

  • Barcodes consist of black and white lines

  • Barcode scanners shine a laser on the lines which reflects light into the scanner. The scanner reads the distance between these lines as number and can identify the item.

  • Check digit value is the final number

  • To check if a barcode is valid, and algorithm is performed and the check digit (final number) should be the difference between the sum and the closest multiple of 10 that is larger or equal to the sum.

The algorithm: Multiply each digit by 1 or 3 alternating between both (not including the check digit) Add all the values together (not including the check digit) Round the answer to nearest 10 Work out the difference between the rounded answer and the original answer

An an example:

Barcode Value -> 9780201379624

9 x 1 =  9
7 x 3 = 21
8 x 1 =  8
0 x 3 =  0
2 x 1 =  2
0 x 3 =  0
1 x 1 =  1
3 x 3 =  9
7 x 1 =  7
9 x 3 = 27
6 x 1 =  6
2 x 3 =  6

9 + 21 + 8 + 0 + 1 + 0 + 2 + 9 + 7 + 27 + 6 + 6 = 96
96 = 100

100 - 96 = 4

Since the check digit (the last number) is also 4, this barcode value is valid.

Note that if they ask you to work out a check digit but its a custom calculation, refer to the checksum header here.

ARQ

When a user receives data, it must check for errors. Errors can be easily detected but not always pinpointed.

ARQ stands for Automatic Repeat Request. It is a protocol that notifies the sender than an error has occurred and that the data is not correct.

It follows this:

  • The receiver sends a negative acknowledgment to indicate that the data is corrupted (error)

  • The receiver sends a positive acknowledgement to indicate that the data is complete (no error)

  • No acknowledgment transmission from the receiver, the sender waits for time-out before automatically resending the data.

  • This process is repeated until all data has been received and acknowledged.

Sample answer:

ARQ uses acknowledgement and timeout When data is sent, a timer is started If there are no errors, a positive acknowledgement will be sent to the sender If there is an error, a negative acknowledgement will be sent to the sender and the data will be resent. If no acknowledgement is sent, then the sender will wait for timeout before resending the data again until an acknowledgement is recieved

Exam Questions

Previous2.1 Types & Methods of Data TransmissionNext2.3 Symmetric & Asymmetric Encryption

Last updated