Methods of Error Detection (Copy)

1. The Need for Error Checking in Data Transmission

• Why errors occur
  • During data transmission, signals can be affected by:
    • Electrical interference (e.g., from other devices, cables, or environmental noise)
    • Data loss (bits missing during transmission)
    • Data gain (extra bits added by mistake)
    • Data change (bits flipped from 0 to 1 or vice versa)
  • Errors can occur in wired and wireless communications.
• Importance of detection:
  • Ensures accuracy of transmitted data.
  • Prevents corruption of files and incorrect processing.
  • Enables retransmission if errors are detected.

2. Methods of Error Detection

2(a) Parity Check

• Definition: A simple error detection method where an extra bit (parity bit) is added to a string of data bits.
• Two types:
  1. Even parity – Parity bit is set so that the total number of 1s in the byte (including parity bit) is even.
  2. Odd parity – Parity bit is set so that the total number of 1s is odd.

Example – Even parity:
Data bits: 1010001 → Number of 1s = 3 (odd) → Parity bit = 1 (makes total number of 1s = 4, even).

Example – Odd parity:
Data bits: 1010001 → Number of 1s = 3 (odd) → Parity bit = 0 (keeps total number of 1s odd).

Parity Byte / Block Check

• For larger blocks of data (multiple bytes), a parity byte is added.
• Works like a parity bit but across multiple rows and columns of bits (forming a parity block).
• Allows detection of which bit is wrong when error occurs at intersection of incorrect row and column.

Advantages:

• Very simple and quick.
• Requires little extra data.

Disadvantages:

• Only detects odd numbers of bit errors; if two bits change, error may go undetected.

2(b) Checksum

• Definition: A value calculated from the sum of binary values in a block of data, then appended to the data before transmission.
• Process:
  1. Sender adds up all bytes in the message (using binary/hex addition).
  2. Sum is reduced (e.g., modulo 256) to fit in a single byte.
  3. This checksum value is sent with the data.
  4. Receiver performs the same calculation on received data and compares with checksum.
  5. If they match → data assumed correct; if not → error detected.
• Advantages:
  • More robust than parity check.
  • Can detect multiple-bit errors better.
• Disadvantages:
  • Still possible for some errors to go undetected (different errors producing same checksum).

2(c) Echo Check

• Definition: Data is sent to the receiver, which immediately sends it back to the sender for verification.
• Process:
  1. Sender transmits data.
  2. Receiver sends the exact data back to sender.
  3. Sender compares returned data with original.
  4. If identical → assumed no error; if different → retransmission requested.
• Advantages:
  • Very straightforward to implement.
• Disadvantages:
  • Doubles transmission time.
  • Does not protect against errors in the return path.

3. Check Digit

• Definition: An extra digit added to the end of a number to check data entry accuracy.
• Uses:
  • Detects typing errors or transposition of digits.
  • Common in ISBNs, barcodes, credit card numbers.

How it works – ISBN example:

• Example ISBN-10: 0-306-40615-2
  1. Each digit (excluding check digit) is multiplied by a weight (10 down to 2).
  2. Sum of results is calculated.
  3. Sum is divided by 11; remainder is subtracted from 11.
  4. Result is the check digit (if 10 → use ‘X’, if 11 → use 0).
• When entered, the same calculation is done to verify the check digit matches.

Barcode check digit example:

• Calculated using weighted sum of digits (odd/even positions) modulo 10.
• Helps detect:
  • Single-digit errors (wrong digit typed).
  • Transposition errors (swapping two digits).

4. Automatic Repeat reQuest (ARQ)

• Definition: Error control method where the receiver can request retransmission of corrupted or missing data packets.
• How it works:
  1. Sender transmits data and waits for acknowledgment.
  2. Receiver sends:
     • Positive Acknowledgement (ACK) – Data received without error.
     • Negative Acknowledgement (NAK) – Error detected; retransmit.
  3. Timeout – If sender receives no ACK/NAK within set time, it retransmits.
• Advantages:
  • Ensures reliable delivery.
• Disadvantages:
  • Increases transmission delay if retransmissions are frequent.
  • Requires extra control data (ACK/NAK signals).

ARQ Types:

• Stop-and-Wait ARQ – Sender sends one packet, waits for ACK before sending next.
• Continuous ARQ – Sender sends packets continuously but buffers them until ACKs are received; retransmits only the packets with errors.