Home Notes Papers

Methods of error detection

Paper 1Paper 2

This section is examined in Paper 1 and Paper 2.

Why Error Detection is Necessary
Data transmission involves sending bits from a sender to a receiver. Errors can occur during this process due to noise (electrical interference), crosstalk (signal leakage between wires), or attenuation (signal weakening). These physical factors can cause bit flips, where a 1 becomes a 0 or vice versa.

If corrupted data is processed without detection, it leads to logical errors in the system. Therefore, error detection methods are essential to verify that the received data matches the original transmitted data before any processing occurs.

Context: This topic bridges Computer Systems (how data moves) and Algorithms/Programming (how we verify logic). It is distinct from Data Validation, which checks if data makes sense before transmission (e.g., checking age > 0).
Parity Check

A parity check adds a single parity bit to each byte (8 bits) of data before transmission. This bit ensures the total number of 1s in the byte meets a specific condition: either odd or even.

  • Even Parity: The parity bit is set to 1 if the number of 1s in the data is odd, making the total count even. It is set to 0 if the count is already even.
  • Odd Parity: The parity bit is set to 1 if the number of 1s is even, making the total count odd. It is set to 0 if the count is already odd.
Limitation: Parity checks can only detect an odd number of bit flips in a byte. If two bits flip simultaneously (e.g., 1 \rightarrow 0 and 0 \rightarrow 1), the parity remains unchanged, and the error goes undetected.
Checksum
A checksum is a value calculated from the data being transmitted using a specific algorithm (often adding binary numbers or using modulo arithmetic). This checksum value is sent along with the original data.

Upon receipt, the recipient recalculates the checksum using the same algorithm on the received data. If the recalculated checksum matches the received checksum, the data is likely error-free. If they differ, an error has occurred.

Echo Check
In an echo check, the receiving device sends the received data back to the sender. The sender compares the original data with the echoed data. If they match, the transmission was successful. If not, the sender knows an error occurred and may retransmit.
Automatic Repeat Query (ARQ)

ARQ is a protocol that uses acknowledgements to ensure data integrity. It typically relies on Negative Acknowledgement (NACK):

  1. The receiver checks the data (e.g., using parity or checksum).
  2. If the data is correct, the receiver sends an Acknowledgement (ACK).
  3. If the data is incorrect, the receiver sends a Negative Acknowledgement (NACK) requesting retransmission.
  4. The sender waits for the ACK; if it receives a NACK or no response within a timeout period, it retransmits the data.
Check Digit
A check digit is a digit added to the end of a number (like an ISBN or barcode) to detect errors in data entry. It is calculated using a weighted algorithm applied to the preceding digits.

When the number is entered, the system recalculates the check digit. If the entered check digit does not match the calculated one, an input error is detected.

Parity Bit
A single bit added to a binary string to ensure the total number of 1s is either even or odd, depending on the parity scheme used.
Checksum
A small block of data derived from another block of raw data for the purpose of detecting errors that may have been introduced during its transmission or storage.
NACK (Negative Acknowledgement)
A signal sent by a receiver to indicate that the received data was corrupted or invalid, prompting the sender to retransmit.
Parity Check Calculation
Scenario: Transmit data 1011010 using Even Parity.

  1. Count the 1s in the data: There are four 1s (1, 1, 1, 1).
  2. Four is an even number.
  3. To keep the total even, the parity bit must be 0.
  4. Transmitted byte: 1011010\mathbf{0}.

Error Detection:
If the receiver gets 1011010\mathbf{1}, it counts five 1s (odd). Since even parity was expected, an error is detected.

Check Digit in ISBN
ISBN-10 Example: The last digit is a check digit.

For the ISBN 0-306-40615\mathbf{X}:

  1. Multiply each of the first 9 digits by its position (1 to 9).
  2. Sum the results.
  3. Calculate modulo 11.
  4. The check digit X is chosen so that the total sum including X is divisible by 11.

If a user enters 0-306-40615\mathbf{6} instead of X, the calculation will fail, detecting the typo.

⚠︎ Confusing Parity Limitations
Mistake: Stating that parity checks can detect any single-bit error but failing to mention they cannot detect two-bit errors.

Correction: Always specify that parity is limited to detecting an odd number of bit flips. If two bits in the same byte flip, the parity remains valid, and the error is missed.

⚠︎ Mixing Checksum and Check Digit

Mistake: Describing a check digit as being used for data transmission or a checksum as being used for barcode entry.

Correction:

  • Checksum is primarily for data transmission (sent with the data).
  • Check Digit is primarily for data entry (part of the identifier, like ISBN/Barcodes).
⚠︎ ARQ Acknowledgement Types
Mistake: Describing ARQ as sending a 'Positive Acknowledgement' for errors.

Correction: In standard Cambridge syllabus contexts, ARQ often relies on Negative Acknowledgement (NACK). The receiver only sends an ACK if the data is correct. If it sends nothing or a NACK, the sender retransmits.

Describing Parity Checks
When to use: When asked to describe how parity detects errors.

Why examiners accept this: Examiners look for the specific steps: counting 1s, determining the bit value, and checking after transmission. Generic answers lose marks.

Correct Phrasing: "A parity bit is added to each byte to make the total number of 1s even (for even parity). After transmission, the receiver counts the 1s. If the count is odd, an error is detected."

Describing Checksums
When to use: When asked to describe the checksum process.

Why examiners accept this: You must mention that the checksum is calculated using an algorithm and is transmitted with the data. Comparing values alone is insufficient.

Correct Phrasing: "The sender calculates a checksum value from the data using an algorithm. This value is sent with the data. The receiver recalculates the checksum from the received data. If the two values match, no error is detected."

Describing ARQ
When to use: When asked how ARQ ensures data is received without error.

Why examiners accept this: You must explicitly mention the NACK (or lack of ACK) triggering retransmission. Do not mix positive and negative acknowledgements in one description unless specified.

Correct Phrasing: "The receiver sends a Negative Acknowledgement (NACK) if an error is detected. The sender receives the NACK and retransmits the data packet."

Parity Check Application
Q:
Explain how an even parity check can detect errors in data transmission.
A:
  1. A parity bit is added to each byte.
  2. The parity bit is set to make the total number of 1s in the byte even.
  3. After transmission, the receiver counts the number of 1s in each byte.
  4. If the number of 1s is odd, an error has occurred.
Checksum Process
Q:
Describe how a checksum is used to detect errors in data transmission.
A:
  1. A checksum value is calculated from the original data using an algorithm.
  2. The checksum is transmitted along with the data.
  3. The recipient recalculates the checksum from the received data.
  4. If the recalculated checksum does not match the received checksum, an error is detected.
ARQ Mechanism
Q:
Describe how Automatic Repeat Query (ARQ) can be used to establish that data is received without error.
A:
  1. The receiver checks the data for errors (e.g., using parity or checksum).
  2. If the data is correct, the receiver sends an Acknowledgement (ACK).
  3. If the data is incorrect, the receiver sends a Negative Acknowledgement (NACK).
  4. Upon receiving a NACK, the sender retransmits the data.
Check Digit Context
Q:
Describe how a check digit is used to detect errors in data entry and give an example of where it is used.
A:
  1. A check digit is calculated from the other digits in a number using a specific algorithm.
  2. It is appended to the end of the number.
  3. When the number is entered, the system recalculates the check digit.
  4. If the entered check digit does not match the calculated one, an error is detected.
  5. Example: ISBN numbers or barcodes.
Beta v0.7.8 Free while we're in beta — it transitions to paid post launch. Thank you for supporting us at this stage!