Error Detection and Correction

This lesson covers methods for detecting (and sometimes correcting) errors that occur during data transmission or storage. You need to understand parity bits, majority voting, checksums, check digits, and Hamming codes for the OCR H446 specification.

---

Why Errors Occur

When data is transmitted over a network or stored on a medium, errors can be introduced by:

Cause	Description
Electrical interference	Electromagnetic noise from nearby devices
Signal degradation	Signal weakening over long distances
Hardware faults	Faulty cables, connectors, or storage media
Cosmic rays	High-energy particles flipping bits (rare but real)
Crosstalk	Signals from adjacent wires interfering

An error means one or more bits have been flipped (0 changed to 1 or vice versa).

---

Parity Bits

A parity bit is an extra bit added to a group of data bits to make the total number of 1s either even or odd.

Even Parity

The parity bit is set so that the total number of 1s (including the parity bit) is even.

Data Bits	Number of 1s	Parity Bit	Total 1s
1010110	4 (even)	0	4
1010111	5 (odd)	1	6
0000000	0 (even)	0	0
1111111	7 (odd)	1	8

Odd Parity

The parity bit is set so that the total number of 1s is odd.

Data Bits	Number of 1s	Parity Bit	Total 1s
1010110	4 (even)	1	5
1010111	5 (odd)	0	5

How Parity Detects Errors

The receiver counts the 1s in the received data (including the parity bit). If the count does not match the expected parity (even or odd), an error has been detected.

Limitations of Parity

Limitation	Explanation
Cannot detect even numbers of errors	If 2 bits flip, the parity is still correct — the error goes undetected
Cannot correct errors	Parity only tells you something is wrong, not which bit is wrong
Cannot detect all errors	Multiple bit errors may cancel out

---

Majority Voting

Majority voting is a simple error-detection and correction method where each bit is sent three times (or more, always an odd number). The receiver takes the majority value for each bit.

How It Works

Sent:     1 1 1   0 0 0   1 1 1   0 0 0
Received: 1 1 0   0 0 0   1 0 1   0 1 0
Majority: 1       0       1       0

In the first group (1 1 0), the majority is 1, which is correct. The error in the third bit is corrected.

Advantages and Disadvantages

Advantage	Disadvantage
Can correct single-bit errors within each group	Triples (or more) the data to be transmitted
Simple to implement	Cannot correct errors if 2+ bits in a group are wrong
No complex calculations needed	Very high bandwidth overhead

---

Checksums

A checksum is a value calculated from a block of data and sent alongside it. The receiver recalculates the checksum and compares it to the one received.

How Checksums Work

1. The sender calculates a checksum from the data (e.g., sum of all byte values, modulo 256).
2. The checksum is appended to the data and transmitted.
3. The receiver recalculates the checksum from the received data.
4. If the calculated checksum does not match the received checksum, an error is detected.

Worked Example

Data bytes: 45, 67, 89, 123, 210

Sum = 45 + 67 + 89 + 123 + 210 = 534

Checksum (mod 256) = 534 mod 256 = 22

The sender transmits: 45, 67, 89, 123, 210, 22

If any byte changes during transmission, the recalculated checksum will (very likely) differ from 22, revealing the error.

Limitations

Limitation	Explanation
Cannot identify which byte is wrong	Only detects that an error exists somewhere
Cannot correct errors	No information about the location or nature of the error
Some errors can cancel out	Two changes that compensate each other may produce the same checksum

---

Check Digits

A check digit is a digit added to a number (e.g., barcode, ISBN) that is calculated from the other digits using a specific formula. It is used to detect transcription errors (e.g., typing a wrong digit, swapping two digits).

ISBN-13 Check Digit Example

ISBN-13 uses alternating weights of 1 and 3:

ISBN: 978-0-13-468599-?