Cambridge A-Level Computer Science (9618) · lesson 4 of 15 · 25 min
Why Error Detection?
Data transmitted over networks or stored on media can be corrupted by noise, hardware faults, or interference. Error detection techniques allow the receiver to identify (and sometimes correct) corrupted data.
Parity Bits
A parity bit is added to a group of bits to make the total number of 1s either even (even parity) or odd (odd parity).
Even parity example: Data = 1011001 (four 1s — even). Parity bit = 0. Transmitted: 10110010.
Limitation: Parity only detects an odd number of bit errors. If two bits flip, the parity is unchanged and the error goes undetected.
Add even parity bit to 1101010
Count 1s in 1101010: 1+1+0+1+0+1+0 = 4 (even)
Even parity → parity bit = 0
Transmitted: 11010100
Checksums
A checksum is calculated from the data values and transmitted alongside the data. The receiver recalculates the checksum and compares — a mismatch indicates corruption.
Simple checksum: sum all byte values, take modulo 256. More robust: CRC (Cyclic Redundancy Check) uses polynomial division and detects burst errors reliably.
ARQ — Automatic Repeat reQuest
When an error is detected, ARQ protocols request retransmission of the corrupted data. Used in TCP/IP. The receiver sends an ACK (acknowledgement) for correct data and a NAK (negative acknowledgement) or simply times out for corrupted data.
A byte 10110011 is transmitted with even parity. The parity bit should be:
- 0
- 1
- Either
- Not needed
- Answer: 0
10110011 has five 1s (odd). To make it even, add parity bit 1… wait: 1+0+1+1+0+0+1+1 = 5 ones. Add 1 to make 6 (even). Parity bit = 1.
What is the main limitation of a single parity bit?
- It cannot detect any errors
- It only detects an odd number of bit errors
- It corrects errors automatically
- It requires 8 extra bits
Answer: It only detects an odd number of bit errors
A single parity bit cannot detect an even number of bit errors (they cancel out).
CRC is preferred over simple checksums because:
- It uses less bandwidth
- It detects burst errors more reliably
- It corrects errors automatically
- It is simpler to implement
- Answer: 1
CRC uses polynomial division and is much better at detecting burst errors (consecutive bit flips).
Previous lesson: Floating-point representation and normalisation
Back to Cambridge A-Level Computer Science (9618)
Next lesson: Compression algorithms: RLE and Huffman coding