Appearance
E2 · Error Detection and E3 · Error Correction
Spec reference: Sections E2 and E3 - How Data is Transmitted Key idea: Understand how errors in data transmission are detected and corrected.
Why errors occur in transmission
Data can be corrupted during transmission due to:
- Electrical interference (noise on the line).
- Signal degradation over distance.
- Hardware faults in network equipment.
- Collisions in shared network media.
Error detection and correction mechanisms allow receiving systems to identify and fix these problems.
Error detection methods
Parity schemes
A parity bit is added to each group of bits. The total number of 1s (including the parity bit) is made either even (even parity) or odd (odd parity).
Even parity example:
Data: 1011001 (four 1s, already even)
With parity bit: 1011001 0 (parity bit = 0, count stays even)
Data: 1011101 (five 1s, odd)
With parity bit: 1011101 1 (parity bit = 1, makes count even)Limitation: Parity only detects an odd number of bit errors. If two bits flip, the parity check still passes (the error is missed).
2D parity: Parity bits added to each row and each column of a block of data. Can detect and in some cases locate errors.
Checksum
A checksum is calculated by performing arithmetic on all the data bytes and appending the result. The receiver performs the same calculation and compares.
- If the checksums match: data is assumed correct.
- If they differ: an error has been detected.
Simple example:
Data: 45, 32, 11, 08
Sum: 45 + 32 + 11 + 08 = 96
Checksum sent: 96
Receiver calculates: 45 + 32 + 11 + 08 = 96 (matches, no error detected)Used in: TCP/IP packets, file downloads, disk storage.
Repetition schemes
The same data is sent multiple times. The receiver compares the copies.
- If all copies match: data accepted.
- If copies differ: an error is detected.
Limitation: Very inefficient. Tripling the data to send triples bandwidth usage.
Cyclic Redundancy Check (CRC)
CRC treats the data as a large binary number and divides it by a predetermined polynomial. The remainder is appended to the data as the CRC value.
The receiver performs the same division. If the remainder is zero, no error is detected.
CRC is much more powerful than simple parity and can detect burst errors (multiple consecutive corrupted bits). It is widely used in networking (Ethernet frames), storage (hard drives), and file formats.
Error correction methods
Error detection only tells you an error occurred. Error correction actually fixes it.
ARQ (Automatic Repeat reQuest)
When an error is detected, the receiver sends a request to the sender to retransmit the affected data.
Types of ARQ:
| Type | How it works |
|---|---|
| Stop-and-Wait ARQ | Sender sends one packet, waits for acknowledgement (ACK) before sending the next. Simple but slow. |
| Go-Back-N ARQ | Sender can send multiple packets before needing an ACK. If an error is detected, it goes back and resends from the error point. |
| Selective Repeat ARQ | Only the specific errored packet is resent. More efficient. |
Used in: TCP (which retransmits lost or corrupted segments).
FEC (Forward Error Correction)
FEC adds enough redundant data that the receiver can reconstruct the original data without requesting a retransmission.
How it works: Extra bits (parity or checksum data spread across the message) allow the receiver to identify and correct a limited number of errors.
Advantages over ARQ:
- No need to retransmit: faster for real-time applications.
- Works in scenarios where retransmission is impractical (e.g. satellite communication, space probes).
Disadvantage: Adds overhead to every transmission, even when no errors occur.
Used in: QR codes, deep space communication, streaming media, optical discs.
| Feature | ARQ | FEC |
|---|---|---|
| How errors are fixed | Retransmission | Using redundant data to reconstruct |
| Bandwidth overhead | Lower normally, high on errors | Always present |
| Latency | Higher (round trip needed) | Lower (no retransmit needed) |
| Use case | TCP/IP networks | Satellite links, QR codes, streaming |
Summary
| Term | Meaning |
|---|---|
| Parity bit | A bit added to make the total number of 1s even or odd |
| Checksum | A calculated value added to data so the receiver can verify integrity |
| CRC | Powerful error detection using polynomial division |
| ARQ | Error correction by requesting retransmission |
| FEC | Error correction using redundant data, no retransmission needed |
| Burst error | Multiple consecutive bits corrupted in a transmission |