Methods of error detection

1. Overview

Data transmission is a crucial part of computer science, enabling devices to communicate and share information. However, data can be corrupted during transmission, leading to errors. Therefore, understanding methods to detect and correct these errors is essential for ensuring data integrity and reliability.

Key Definitions

• Data Integrity: The accuracy and consistency of data.
• Error Detection: The process of identifying errors in transmitted data.
• Parity Bit: An extra bit added to a data string to make the number of 1s either even or odd.
• Checksum: A calculated value representing the sum of the data values, used for error detection.
• Echo Check: A method of error detection where the receiver sends the received data back to the sender for comparison.
• Check Digit: A digit added to a number (like an ISBN) calculated from the other digits, used to validate data entry.
• Automatic Repeat Request (ARQ): An error control method where the receiver requests retransmission of data if an error is detected.
• Acknowledgement (ACK): A signal sent by the receiver to the sender indicating that the data was received correctly.
• Negative Acknowledgement (NAK): A signal sent by the receiver to the sender indicating that the data was received with errors.
• Transcription Error: An error occurring when entering data, such as typing a character incorrectly.
• Transposition Error: An error occurring when entering data, where two adjacent characters are switched (e.g., 123 becomes 132).

Core Content

Understanding the Need for Error Detection and Causes of Errors

• Data transmission can be affected by various factors leading to errors.
• Common causes of errors include:
  • Electrical Interference: External electromagnetic signals can disrupt the data signal.
  • Signal Degradation Over Distance: Signal strength weakens as it travels longer distances.
  • Hardware Faults: Malfunctioning hardware components can introduce errors.
  • Synchronization Issues: Problems in timing between sender and receiver can lead to incorrect data interpretation.

Parity Check (Odd and Even)

• A parity bit is added to a data string to make the total number of 1s either even (even parity) or odd (odd parity).
• Even Parity: The parity bit is set to ensure an even number of 1s in the data and parity bit combined.
  • Example: Data = 1011001. Number of 1s = 4 (even). Parity bit = 0. Transmitted data = 10110010
• Odd Parity: The parity bit is set to ensure an odd number of 1s in the data and parity bit combined.
  • Example: Data = 1011001. Number of 1s = 4 (even). Parity bit = 1. Transmitted data = 10110011
• The receiver counts the number of 1s in the received data (including the parity bit).
  • If the parity is incorrect (e.g., even parity expected but an odd number of 1s are found), an error is detected.
• Limitations: Parity checks can only detect single-bit errors (or an odd number of bit errors). If two bits are flipped, the parity will still be correct, and the error will go undetected. Example: Even and Odd Parity

Data Bits	Count of 1s	Even Parity Bit	Odd Parity Bit	With Even	With Odd
1011001	4 (even)	0	1	10110010	10110011
1101110	5 (odd)	1	0	11011101	11011100
0000000	0 (even)	0	1	00000000	00000001

Parity bit makes total count of 1s even (even parity) or odd (odd parity).

Checksum

• The sender calculates a checksum value based on the data being transmitted.
• The checksum is sent along with the data.
• The receiver recalculates the checksum based on the received data.
• The receiver compares the calculated checksum with the received checksum. If they match, the data is considered error-free. If they don't match, an error has occurred.
• Example (Simplified):
  1. Data: 10, 20, 30
  2. Checksum (Sender): 10 + 20 + 30 = 60
  3. Transmitted Data: 10, 20, 30, 60
  4. Checksum (Receiver): 10 + 20 + 30 = 60
  5. Compare: 60 (Receiver) == 60 (Transmitted). No error detected.
• Checksums can detect multiple bit errors, but more sophisticated methods are typically used.

Echo Check

• The receiver simply sends the received data back to the sender.
• The sender compares the original data with the echoed data.
• If the data matches, it is assumed the transmission was successful. If there's a difference, an error occurred.

Check Digit

• A check digit is calculated from the other digits in a number using a specific algorithm.
• Used primarily for data entry validation, not data transmission.
• Helps detect transcription and transposition errors.
• Examples:
  • ISBN-10/13 (International Standard Book Number): Used to uniquely identify books. Has a check digit to validate the ISBN.
  • EAN Barcodes (European Article Number): Commonly used for product identification at retail stores. The last digit is a check digit.
  • Credit Card Numbers (Luhn Algorithm): The last digit of a credit card number is a check digit calculated using the Luhn algorithm.
• Example (Simplified ISBN-10):
  • ISBN: 0-306-40615-?
  • Calculation: (10 * 0) + (9 * 3) + (8 * 0) + (7 * 6) + (6 * 4) + (5 * 0) + (4 * 6) + (3 * 1) + (2 * 5) = 0 + 27 + 0 + 42 + 24 + 0 + 24 + 3 + 10 = 130
  • Check digit: 130 mod 11 = 9. 11 - 9 = 2. If result is 10, use X.
  • Complete ISBN: 0-306-40615-2

Automatic Repeat Request (ARQ)

• Sender transmits data with an error detection code (e.g., checksum, parity).
• Receiver checks for errors using the error detection code.
• If no errors are detected:
  • Receiver sends an ACK (acknowledgement) signal to the sender.
• If errors are detected:
  • Receiver sends a NAK (negative acknowledgement) signal to the sender, or sends no response.
• If the sender receives a NAK or does not receive an ACK within a specified timeout period:
  • The sender retransmits the data.

Method	Description	Advantages	Disadvantages
Parity Check	Adds a parity bit to ensure an even or odd number of 1s.	Simple to implement.	Only detects single-bit errors or odd number of bit errors.
Checksum	Calculates a sum of data values and sends it with the data; receiver recalculates to verify.	More effective than parity check at detecting multiple bit errors.	Can be computationally expensive; less secure than more sophisticated methods
Echo Check	Receiver sends data back to the sender for comparison.	Simple to implement and understand.	Inefficient; can be affected by errors in both directions.
Check Digit	A digit calculated from other digits using an algorithm to detect data entry errors.	Useful for validating data entry, preventing simple errors.	Only detects certain types of errors (transcription, transposition); not for transmission.
Automatic Repeat Request (ARQ)	Sender transmits data with error check; receiver requests retransmission if an error is detected (ACK/NAK).	Ensures reliable data transmission through retransmission.	Can be slower due to retransmissions.

Exam Focus

• Understand the causes of data transmission errors (electrical interference, signal degradation, etc.).
• Be able to describe the operation of parity check (odd and even), checksum, echo check, check digits, and ARQ.
• Be able to identify the advantages and disadvantages of each error detection method.
• Remember that check digits are used for data entry, not data transmission.
• When describing ARQ, clearly state the conditions for ACK, NAK, and retransmission.
• Use technical terminology accurately: parity bit, checksum, acknowledgement, negative acknowledgement, check digit, transcription error, transposition error.
• Provide sufficient detail in your explanations, showing a clear understanding of the processes involved.

Common Mistakes to Avoid

• ❌ Wrong: Check digits are used to detect errors during data transmission. ✓ Right: Check digits are used to detect errors during data entry.
• ❌ Wrong: Only describing ACK in ARQ and not mentioning NAK and Retransmission ✓ Right: Describe the full ARQ process, including ACK, NAK (or lack of response) and retransmission.
• ❌ Wrong: Providing a generic description of error detection without specifying the method. ✓ Right: Always clearly identify the error detection method you are describing (e.g., "Using a checksum...").
• ❌ Wrong: Claiming parity checks can detect all types of errors. ✓ Right: Parity checks only detect single-bit errors (or an odd number of bit errors).

Exam Tips

• When asked to describe an error detection method, provide a step-by-step explanation of the process.
• Use diagrams to illustrate your answers, especially for ARQ.
• Clearly differentiate between error detection methods used for data transmission and those used for data entry.
• Pay attention to the command words in the question (e.g., "describe," "explain," "compare").