2.2 Methods of Error Detection

Question Bank · 19 Questions

Objectives: Students should be able to —

  • 1 Explain why error checking methods are needed.
  • 2 Show the understanding of "error checking methods" following data transmission: Parity checks, Checksum, Echo check.
  • 3 Demonstrate the use of Check-digits to detect data entry errors.
  • 4 Describe the use of Automatic Repeat Request (ARQ) to detect and recover data errors.

Data Error in Communication

  • Data error occurs when information received by a system does not match with the information sent by the other system.
  • Digital signals suffer from channel noise, attenuation or distortion that can introduce errors in the binary bits travelling from one system to another.
  • That means a bit 0 may change to 1, or a bit 1 may change to 0.

Data communication error — i.e. some of the bits may get corrupt while travelling through computer channels like wire — due to:

Reason Description
1) Attenuation
  • Refers to any reduction in the signal strength.
  • Skewing of data could occur during parallel data transmission and can cause data corruption if the bits arrive out of synchronisation.
2) Distortion
  • Accidental change in data bits during transmission because of electric interference.
  • All types of cables can suffer from electric interference.
3) Channel noise
  • Refers to the disturbance or noise pick-up in the communication system.
  • This can lead to data loss or gain of data during packet switching.
Single-bit error Burst error
Only one bit gets corrupted. More than one bit gets corrupted.
Common in parallel transmission. Very common in serial transmission of data. This error occurs when the duration of noise is long.
Data Security Data Integrity
Data security refers to the protection of data against unauthorised access or accidental damage or loss. Data integrity refers to the validity (consistency) and accuracy (correctness) of data stored in the computer.
Concerned with preventing unauthorised access. Each time data is replicated or transferred, it should remain error-free, intact and unaltered.

Methods of Error Detection

  • Error can be detected by adding some extra information or bits with the data before transmission. Additional bits allow the receiver to detect the error.
  • Error correction is done by detection of error and re-transmission or re-construction of data to its original form.

1) Parity check:

  • A single bit called the parity bit is added with each byte of data in such a way that the number of 1's is either even (called Even parity check) or odd (called Odd parity check), before transmission.
  • At the receiver end, the parity bit is re-calculated and compared with the received one.
  • If it matches, then the data is considered error-free.

2) Checksum:

  • An extra data value called the Checksum is added with the block of data before transmission to check its integrity.
  • It is calculated by using an agreed algorithm by the sender and receiver of the data.
  • At the receiver end, the checksum is re-calculated and compared with the received one. If it matches, the data is assumed error-free.

3) Check digit:

  • A single digit called the Check digit is added with the numerical data to check its integrity while entering data into the computer.
  • It is calculated by adding other digits of the number using some algorithm.
  • At the receiver end, the check digit is re-calculated and compared with the received one. If it matches, the number is assumed error-free.

4) Automatic Repeat reQuest (ARQ):

  • An Error-detection scheme is combined with Acknowledgement and Timeout.
  • The data is checked using some Error-detecting code; if no error is detected, a positive Acknowledgement is sent before timeout.
  • If Acknowledgement is not received before timeout, the data is automatically re-transmitted.
  • This process repeats until error-free data is received.

5) Echo check:

  • An error-checking technique where the data received is stored and also transmitted back to the sender.
  • The sender compares the two sets of data to check if any error occurred during the transmission process.
  • If there are no differences, the data was sent without error.
  • If the two sets of data are different, the data is re-transmitted.
  • This method is not very reliable, because it is not possible to know whether the error occurred when sending the data or while receiving back the data.

1) Parity Check

(a) Parity Check:

  • A single bit called the parity bit is added with each byte of data to check its integrity before transmission.
  • The parity bit is calculated in such a way that the number of 1-bits should be either even (called Even parity check) or odd (called Odd parity check), depending on the type of check used.
  • At the receiver end, the parity bit is re-calculated and compared with the received one. If it matches, the data is considered error-free.

(b) Calculating the Parity-bit for 1 0 0 1 0 0 0 1:

Even parity:

  • Count the number of 1's in the data which is 3 — an odd value.
  • If we add 1 as the parity bit, the number of 1's will become even. Hence, 1 would be the parity bit.
1 0 0 1 0 0 0 1 [1] ← Parity-bit

Odd parity:

  • Count the number of 1's in the data which is 3 — an odd value.
  • If we add 0 as the parity bit, the number of 1's will remain odd. Hence, 0 would be the parity bit.
1 0 0 1 0 0 0 1 [0] ← Parity-bit

(a) Two-dimensional parity check:

  • The data to be sent is arranged in rows and columns in a block.
  • The parity bit is calculated horizontally and vertically and is added with each row and column.
  • An additional row with only parity bits is generated, called the parity byte, which is also sent and indicates the end of the parity block of data.
  • Two-dimensional parity check not only identifies that an error has occurred but also indicates the error bit.

(b) Nine-byte data block with Parity Byte (Odd parity):

Parity Bit Bit-2 Bit-3 Bit-4 Bit-5 Bit-6 Bit-7 Bit-8
Byte-101100010
Byte-210111111
Byte-310011000
Byte-4 ⚠0110(0)100
Byte-511100110
Byte-610000101
Byte-701110000
Byte-800000001
Byte-901111010
Parity Byte10111100

(b)(i) The corrupt bit:

The corrupt bit is Byte-4, Bit-5 (currently 0, should be 1). It is circled in the table above.

(b)(ii) How the corrupted bit was found:

  • Count the number of 1's along the row to find the error byte if it is in even numbers (odd parity should give odd 1-count). Byte-4 has 4 ones (even) → this is the error row.
  • Count the number of 1's along the column (including the parity byte) to find the error bit column if it is in even numbers. Bit-5 column has 4 ones (even) → this is the error column.
  • The intersection of the error byte row and error bit column gives the error bit → Byte-4, Bit-5.

(a) Usage of Parity Check:

  1. Parity bits are generally applied to the smallest units of a communication protocol, usually 8-bits or 1 byte of data.
  2. A 7-bit ASCII character adds up a parity bit to accommodate each character in an 8-bit byte.
  3. Parity check is performed on memory every time a byte of data is read.
  4. Parity is used in many hardware applications, like the SCSI (Small Computer System Interface) and PCI (Peripheral Component Interconnect) buses to detect transmission errors.

(b) Situations where Parity check may not identify an error:

  1. Parity check cannot detect even number of bit errors called Transcription error, because it does not change the parity.
  2. Error cannot be detected if two or more bits interchange their position called Transposition error, because it does not change the parity.
  • Parity-byte check cannot detect the interchange of bits or even numbers of bit-errors.
  • But Parity-block check can identify the interchange of bits or any bit-errors.
  • Parity-block check not only identifies that an error has occurred but also indicates the error bit at the intersection of the error row and error column.

2) Checksum

(a) Checksum:

  • An extra data or value called Checksum is added with the block of data to be transmitted before transmission, to check its integrity.
  • Checksum is calculated from the block of data using an agreed algorithm by the sender and receiver.
  • At the receiver end, the checksum is re-calculated and compared with the received one. If it matches, the data is considered error-free.
  • If two checksums are not the same, then an error in the data is detected and re-transmission of data is requested.

(b) Three uses of Checksum:

  1. To check data integrity (data error) during transmission.
  2. To check data integrity of stored data to see if the data has been modified or changed.
  3. To verify data burned to CD or DVD is appropriate.

(a) How Checksum is calculated:

  1. The Checksum is calculated by adding the decimal value of each character in the message.
  2. If the sum of the bytes is less than or equal to 255, then the byte-sum is taken as the Checksum.
  3. If the byte-sum is greater than 255, then it is divided by 255 to get the remainder.
  4. And the remainder is then taken as the Checksum.

(b) Calculate the Checksum for byte-sum 1185:

  • Since byte-sum 1185 > 255: divide 1185 by 255 to get the remainder.
1185 ÷ 255 = 4 remainder 165
Checksum = 165

Hence, 165 is the Checksum.

3) Check Digit

(a) Check digit:

  • Check digit is a single digit added at the right-most end of a code number to check its integrity while entering numerical data into the computer.
  • It is calculated by adding other digits of the code using some check-digit algorithm.
  • At the receiver end, it is recalculated using the same algorithm and compared with the received one. If it matches, the code number is accepted, else rejected.

(b) Two uses of check digits:

Check digit is used as a Validation check while entering data into a database. Examples of its use:

  1. Barcode Number.
  2. ISBN Number.
  3. Credit Card Number.
  4. Bank Account Number.
  5. Vehicle Identification Number.
  6. Tax and Social ID Number.

(c) Types of error detected by Check-digit:

  1. If two digits of the number interchange their position — called Transposition error. Example: 1 5 2 8 instead of 5 1 2 8.
  2. If any digits are entered incorrectly — called Transcription error. Example: 5 4 2 8 instead of 5 1 2 8.
  3. If any digits are omitted or any extra digits are added. Example: 5 3 7 instead of 5 3 0 7, or 5 3 1 0 7 instead of 5 3 0 7.
  4. If any phonetic error occurs. Example: 1 3 (thirteen), instead of 3 0 (thirty).
  1. Checksum is used to spot error in transmitted data, whereas check digit is used to spot human error on data entry.
  2. Checksum could be of any size, but check digit is a single digit.
  3. Checksum could be used to verify all types of data, but check digit can only verify numerical data for change in digits.

Modulus-11 weighted check digit system works as follows:

  • Each number input is 'weighted' by multiplying it by its position + 1 (check-digit position).
  • The weightings are added together which is then divided by the prime number 11.
  • The remainder is then subtracted from 11 to get the check digit.
  • The check digit is then added to the end of the number.
Note: If the remainder is 10, then the check digit is set to X.

Working:

10-digit ISBN : 1 8 5 8 1 3 4 1 5 ?
Digit position:10987654321
Weighted Sum:10+72+40+56+6+15+16+3+10=228
228 ÷ 11 = 20 remainder 8
Check-digit = 11 − 8 = 3

Valid 10-digit ISBN number is: 1 8 5 8 1 3 4 1 5 3

ISBN-13 check digit system works as follows:

  • Add all the odd-numbered digits together, excluding the check digit.
  • Add all the even-numbered digits together and multiply the result by 3.
  • Add the results from steps 1 and 2 together and divide by 10.
  • Take the remainder; if it is zero use this value, otherwise subtract the remainder from 10 to find the check digit.

Figure: Digits 9 7 8 0 3 4 0 9 8 3 8 2 with an empty circle for the check digit. Arrows point from "Odd digits" and "Even digits" to their respective positions.

Working:

Step-1 : 9 + 8 + 3 + 0 + 8 + 8 = 36
Step-2 : (7 + 0 + 4 + 9 + 3 + 2) × 3 = 25 × 3 = 75
Step-3 : (36 + 75) ÷ 10 = 111 ÷ 10 = 11 remainder 1
Step-4 : 10 − 1 = 9 — the Check digit.

Valid 13-digit ISBN number is: 9 7 8 0 3 4 0 9 8 3 8 2 9

To check that an ISBN-13 digit code is correct or not, a similar process is followed:
  • Add all the odd-numbered digits together, including the check digit.
  • Add all the even-numbered digits together and multiply the result by 3.
  • Add the results from steps 1 and 2 together and divide by 10.
  • The number is correct if the remainder is zero (0).

Using the ISBN above with its check-digit: 9 7 8 0 3 4 0 9 8 3 8 2 9

Step-1 : 9 + 8 + 3 + 0 + 8 + 8 + 9 = 45
Step-2 : (7 + 0 + 4 + 9 + 3 + 2) × 3 = 75
Step-3 : (45 + 75) ÷ 10 = 120 ÷ 10 = 12 remainder 0

Remainder is 0, therefore the number is correct.

4) Echo Check

(a) How Echo checks are used:

  • An error-checking technique where the data received is stored and also transmitted back to the sender.
  • The sender compares the two sets of data to check if any error occurred during the transmission process.
  • If an error has occurred, then the data is re-transmitted again.

(b) Why is Echo check not reliable:

This method is not very reliable, because:

  1. It is not possible to know whether the error occurred when sending the data or while receiving back the data.
  2. Echo checks require a lot of extra data to be transmitted.

5) Automatic Repeat reQuest (ARQ)

  • ARQ is an error control technique where an error-detection scheme is combined with Acknowledgement and Timeout.
  • At the receiver end, the error-detection scheme 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.
  • If an Acknowledgement isn't sent back to the sender before timeout occurs, then the message is automatically re-sent.
  • This may be done repeatedly, until the error-free data is received.
Note:
  • An ACKNOWLEDGEMENT is a message sent by the receiver indicating that the data has been received correctly.
  • The TIMEOUT is the time allowed to elapse before an Acknowledgement is received.

Exam-style Questions

(a)(i) How echo checks work — suitability for vending machine data:

  • The data received is stored and also transmitted back to the sender.
  • The sender compares the two sets of data to check if any error occurred during the transmission process.
  • If an error has occurred, then the data is re-transmitted again.
  • This method is not very reliable, because it is not possible to know whether the error occurred when sending the data or while receiving back the data. Echo checks also require a lot of extra data to be transmitted.

(a)(ii) How automatic repeat request (ARQ) works:

  • ARQ is an error control technique where an error-detection scheme is combined with Acknowledgement and Timeout.
  • At the receiver end, the error-detection scheme is used to detect whether the received data contains any errors.
  • If no error is detected, a positive acknowledgement is sent to the sending device.
  • If an acknowledgement is not received by the sender before timeout occurs, then the message is automatically re-sent.
  • This may be done repeatedly, until the error-free data is received.

(b) Three differences between Checksum and Check digit:

  1. Checksum is used to spot error in transmitted data, whereas check digit is used to spot human error on data entry.
  2. Checksum could be of any size, but check digit is a single digit.
  3. Checksum could be used to verify all types of data, but check digit can only verify numerical data for change in digits.

Revision: Statements and Key Computing Terms

Key Term Statement
Parity checkA method used to check if data has been transferred correctly; it makes use of even parity (an even number of 1-bits) or odd parity (an odd number of 1-bits).
Parity bitA bit (either 0 or 1) added to a byte of data in the most significant bit position; this ensures that the byte follows the correct even parity or odd parity protocol.
Parity blockA horizontal and vertical parity check on a block of data being transmitted.
Parity byteAn extra byte of data sent at the end of a parity block; it is composed of the parity bits generated from a vertical parity check of the data block.
ChecksumA verification method used to check if data transferred has been altered or corrupted; calculated from the block of data being sent; the checksum value is sent with each block of data.
Automatic Repeat Request (ARQ)A method of checking transmitted data for errors; it makes use of acknowledgement and timeout to automatically request re-sending of data if the time interval before positive acknowledgement is too long.
AcknowledgementA message sent to the receiver indicating that data has been received correctly (used in the ARQ error detection method).
TimeoutThe time interval allowed to elapse before an acknowledgement is received (in the ARQ error detection method).
Echo checkA method used to check if data has been transferred correctly; data is sent to a receiver and then immediately sent back to the sender; the sender then checks if the received data matches the sent data.
Check digitAn additional digit appended to a number to check if the entered number is error-free; check digit is a data entry check and not a data transmission check.