Computer Science (9645) | Error detection and correction

Study Notes: Error Detection and Correction (9645)

Welcome to the chapter on how computers keep data safe! Imagine sending a crucial email or downloading a massive game file. If even one bit (a 0 or a 1) gets flipped during transmission due to electrical noise or interference, the data becomes corrupted. This is why we need robust methods for Error Detection (spotting that an error occurred) and sometimes Error Correction (fixing the error without re-sending the data).

In this section, we will explore three fundamental techniques that ensure the integrity of the binary data representing all our information.

---

3.5.8 Error detection and correction

When data is transmitted across networks or stored on media, it is vulnerable to errors. These errors cause bits to flip (a 0 becomes a 1, or a 1 becomes a 0). We study methods that add redundancy—extra information—to the original data so that corruption can be identified or repaired.

---

Method 1: Parity Bits (Simple Detection)

The Parity Bit method is one of the simplest and fastest ways to detect a single error in a data unit, usually a byte (8 bits).

Concept of Parity

A single bit is added to a block of data (often 7 or 8 bits) to ensure that the total number of '1's in the resulting block satisfies a predefined rule (either even or odd).

There are two types of parity:

1. Even Parity: The parity bit is set so that the total count of 1s in the data block (including the parity bit itself) is even.
2. Odd Parity: The parity bit is set so that the total count of 1s in the data block (including the parity bit itself) is odd.

Step-by-Step Mechanism (Even Parity Example)

Assume the system uses Even Parity.

Step 1: Sender calculates the Parity Bit
Data to be sent (8 bits): 1 0 1 1 0 0 1 0
Count of 1s in the data: 4 (Even)
To keep the total count Even, the sender adds a Parity Bit of 0.
Transmitted data (9 bits): 1 0 1 1 0 0 1 0 0

Step 2: Transmission and Error
Imagine the third bit flips during transmission due to noise:

Received data: 1 0 0 1 0 0 1 0 0

Step 3: Receiver checks the Parity
Receiver counts the 1s in the received 9 bits.
Count of 1s in received data: 3 (Odd)
Since the expected parity was Even, but the result is Odd, the receiver immediately knows an error has occurred.

Limitations (Why Parity Bits are only for Detection)

• Cannot correct errors: The receiver knows where in the block the error occurred (the entire 9-bit block), but not which bit flipped. The data must be requested again.
• Cannot detect even errors: If two bits flip (a 2-bit error), the total count of 1s remains the same (either even or odd), and the error goes completely undetected.

---

Method 2: Majority Voting (Correction Capability)

Majority Voting (also known as Triple Modular Redundancy or TMR, when three copies are used) is an error correction technique that relies on heavy repetition.

Concept and Mechanism

Instead of sending extra checking bits, the sender transmits the entire data block multiple times (usually three or five times).

Analogy: Imagine a voting committee of three machines. If two machines vote 1 and one machine votes 0, the majority (the 1) is accepted as the correct answer.

Step-by-Step Mechanism (3-Copy Example)

Data to be sent (D): 101

Step 1: Sender transmits redundancy
The sender sends D three times: 101 101 101

Step 2: Transmission and Errors
Assume the first copy gets corrupted (a 1-bit error):

• Copy 1 (Corrupted): 100
• Copy 2 (Correct): 101
• Copy 3 (Correct): 101

Step 3: Receiver votes for the majority
The receiver compares the bits column by column:

Bit Position:	1	2	3
Copy 1:	1	0	0
Copy 2:	1	0	1
Copy 3:	1	0	1
Result (Majority):	1	0	1

The receiver successfully corrects the error in Copy 1, outputting the original data 101.

Effectiveness and Trade-offs

• High Effectiveness: Majority voting is very effective and allows for Error Correction, provided that the number of corrupted copies is less than the total number of copies sent (e.g., if 3 copies are sent, it can handle 1 corrupted copy).
• Major Disadvantage (Overhead): This method requires sending 3, 5, or more times the amount of data. This means it has very high time and space complexity, making it impractical for general-purpose data transmission but useful in mission-critical systems (like spacecraft or military hardware) where accuracy is paramount.

---

Method 3: Checksums (Block Detection)

Checksums offer a more robust error detection method than parity bits, especially for checking the integrity of a large block of data or a whole message.

Concept and Mechanism

The Checksum is a calculated value derived from summing up all the data being transmitted. This sum is sent alongside the data.

Step-by-Step Mechanism (Simplified)

Step 1: Sender calculates the Checksum
The data is broken into fixed-size chunks (e.g., 8-bit bytes). These chunks are treated as numerical values and added together. (In real-world systems, often the sum is limited to a fixed length, like 16 bits, using modular arithmetic).

Example Data Chunks (in decimal for simplicity):
Chunk 1: 15
Chunk 2: 20
Chunk 3: 10

Total Sum (Checksum): 15 + 20 + 10 = 45

The sender transmits the chunks (15, 20, 10) followed by the checksum (45).

Step 2: Transmission and Error
Imagine Chunk 2 gets corrupted from 20 to 22 during transmission.

Received Chunks: (15, 22, 10)
Received Checksum: 45

Step 3: Receiver verifies the Checksum
The receiver adds up the received chunks:
15 + 22 + 10 = 47

The receiver compares its calculated sum (47) with the received checksum (45). Since 47 ≠ 45, the receiver knows the data is corrupted and requests retransmission.

Effectiveness and Trade-offs

• Good Detection: Checksums are excellent at detecting most random errors across large blocks of data.
• Cannot Correct Errors: Like parity bits, checksums only flag that an error occurred, requiring retransmission.
• Limitation (Compensating Errors): A major weakness is the possibility of compensating errors. If one chunk increases by 2 and another chunk decreases by 2, the total sum (checksum) remains the same, and the error goes undetected.
  Example: Chunk 2 (20 -> 22) and Chunk 3 (10 -> 8). New sum: 15 + 22 + 8 = 45. Checksum passes despite data corruption.

---

Comparison of Error Methods

You must be able to compare the use and effectiveness of these three methods.

Use and Effectiveness Comparison

Method	Primary Use	Overhead (Data Size Increase)	Effectiveness
Parity Bit	Simple detection in short transmission (e.g., character transmission).	Very Low (1 bit per 8 bits).	Poor: Only detects odd number of bit flips. Cannot correct.
Checksum	Robust detection across a message block (e.g., networking data packets).	Low (a few bytes per block).	Good: Detects most errors, but vulnerable to compensating errors. Cannot correct.
Majority Voting	Critical systems requiring correction without retransmission (e.g., radiation-exposed hardware).	Very High (300% to 500% data increase).	Excellent: Allows error correction if the majority of copies are intact.

Key Takeaway Points

• For standard data transmission (like web browsing), Checksums are generally preferred over parity bits because they provide detection over a larger block of data with relatively low overhead.
• Parity Bits are the simplest but the least effective form of error detection, primarily used for very basic communication checks.
• Majority Voting is the only technique here that offers Error Correction capabilities, but its enormous overhead restricts its use to situations where immediate data correction is more vital than transmission speed.

Don't worry if this seems tricky at first! The key distinction is remembering that Parity and Checksums are about spotting corruption, while Majority Voting is about fixing it through brute-force repetition.