Error Detection Methods

Watch this lesson Video 2.2.1 · 11:25 · Parity, checksums, echo checks, ARQ and check digits — and which one actually repairs the data

Error Detection

Five methods for checking that data survived transmission or entry intact

Data can be corrupted on its way from one place to another. Interference on a cable, a weak wireless signal or a fault in the hardware can flip a bit from 0 to 1 or from 1 to 0. The receiving device has no way of knowing the data is wrong just by looking at it — a corrupted byte is still a perfectly valid byte. So extra information is sent alongside the data, calculated from it, and the receiver recalculates that same value and compares. If the two disagree, an error has occurred.

1. The Parity Bit (Single Byte)

One bit in each byte is reserved as the parity bit. Before transmission the sender counts the 1s in the data bits and sets the parity bit so that the total follows an agreed rule. Both devices must agree on which rule they are using before any data is sent.

Even parity: the parity bit is set so the total number of 1s in the byte is even.
Odd parity: the parity bit is set so the total number of 1s in the byte is odd.

Bit 7	Bit 6	Bit 5	Bit 4	Bit 3	Bit 2	Bit 1	Parity (P)
1	0	1	1	0	1	0	0

There are four 1s in the data bits. Under even parity, 4 is already even, so the parity bit is 0. Under odd parity the same data would need a parity bit of 1, making five 1s in total.

The limitation: a single parity bit detects an odd number of flipped bits. If two bits in the same byte are corrupted, the count returns to its original parity and the error passes undetected. It also tells you only that a byte is wrong, never which bit.

2. The Parity Block (Horizontal & Vertical)

Sending a block of bytes allows a much stronger check. Each byte still carries its own parity bit covering its row. An extra parity byte is then sent at the end of the block, and its bits enforce parity down each column. Every bit is now covered twice — once horizontally, once vertically.

Below is a block as received, using even parity. One bit was corrupted in transit.

	B7	B6	B5	B4	B3	B2	B1	P (Row)
Byte 1	1	0	0	1	1	0	1	0
Byte 2	1	1	0	0	1	0	1	1
Byte 3	0	1	1	0	1	1	0	0
Parity Byte	0	0	1	0	1	1	0	1

How the receiver finds it:

Check every row. Byte 1 has four 1s plus a parity bit of 0 — even, so it passes. Byte 3 likewise. Byte 2 has four 1s plus a parity bit of 1, giving five — odd, so it fails.
Check every column. Only column B4 fails: it holds 1, 0, 0 with a parity bit of 0, giving a single 1 — odd.
The faulty bit lies where the failing row meets the failing column: Byte 2, column B4 — the red cell.
Because a bit can only be 0 or 1, the receiver flips it from 0 back to 1 and the data is repaired.

Why this is the only method here that corrects: one failing row gives the byte, one failing column gives the bit position, and together they identify a single cell exactly. This works for one corrupted bit in the block. If two bits are corrupted, two rows and two columns fail, giving four possible intersections and no way to tell which two are wrong — the error is detected but can no longer be corrected.

3. Checksum

A checksum is a single value calculated from an entire block of data. The sender calculates it and transmits it with the block; the receiver recalculates it from the data that arrived and compares. If the two values differ, the data was corrupted and a re-send is requested.

Example algorithm (sum modulo 256):
Suppose a packet contains three bytes: 200, 100, 45.

1 Add the byte values: $200 + 100 + 45 = 345$
2 Take the remainder after dividing by 256: $345 \div 256 = 1 \text{ remainder } 89$
3 The checksum is 89. This value is sent with the packet.

The modulo step exists so the checksum always fits in one byte. A total of 345 will not fit in eight bits, so it wraps round.

Application: TCP/IP packets, file downloads (.iso, .exe)

At the receiving end the same sum is performed on the bytes that arrived. If any byte changed, the total changes, the remainder changes, and the mismatch reveals the error.

4. Echo Check

An echo check takes a different approach: rather than calculating anything, the receiver simply sends the data straight back to the sender. The sender then compares what it received back with what it originally transmitted. If the two are identical, the transmission is assumed to have been successful. If they differ, an error occurred and the data is re-sent.

The weakness examiners test: if the returned data differs from the original, the sender cannot tell where the error happened. The data may have been corrupted on the way out, or it may have arrived perfectly and been corrupted on the way back. Echo check is also slow and wasteful, because every piece of data is transmitted twice.

5. Automatic Repeat Query (ARQ)

An automatic repeat query is not a way of spotting corruption — it is the system that decides what to do about it. It combines an error-detection method (usually a checksum) with acknowledgements and a timeout.

The sender transmits a data packet and starts a timer.
The receiver checks the packet for errors using an error-detection method.
If no error is found, the receiver returns a positive acknowledgement (ACK). The sender moves on to the next packet.
If an error is found, the receiver returns a negative acknowledgement (NAK) and the sender re-transmits that packet.
If no acknowledgement of any kind arrives before the timer runs out — a timeout — the sender assumes the packet was lost entirely and re-transmits it automatically.
This repeats until an acknowledgement is received or a set re-send limit is reached, which stops the process looping forever on a broken link.

The timeout is the part most often left out of exam answers. Without it, a packet that vanished completely would produce neither an ACK nor a NAK, and the sender would wait indefinitely.

Application: mobile phone networks, Wi-Fi, TCP

6. Check Digit

Every method so far checks data that has been transmitted. A check digit checks data that has been entered — typed in by a person or read by a scanner. It is an extra digit placed at the end of a code, calculated from the digits before it.

It is designed to catch the mistakes humans actually make: mistyping a digit, and transposing two adjacent digits (typing 57 as 75), which a simple total would not notice.

Example: ISBN-10 (weighted sum)
Number to check: 0-306-40615-?

1 Assign weights: multiply each digit by its position value, counting down from 10.
$(0\times10) + (3\times9) + (0\times8) + (6\times7) + (4\times6) + (0\times5) + (6\times4) + (1\times3) + (5\times2)$
$0 + 27 + 0 + 42 + 24 + 0 + 24 + 3 + 10 = 130$

2 Find the remainder after dividing by 11: $130 \div 11 = 11 \text{ remainder } 9$

3 Subtract the remainder from 11: $11 - 9 = 2$
The check digit is 2. The full number is 0-306-40615-2.

The descending weights are what catch transposition: swapping two digits changes the total, because each digit is multiplied by a different amount.

Application: barcodes (EAN/UPC), ISBNs, vehicle identification numbers (VIN)

7. Comparing the Methods

Method	What it checks	Detects	Corrects?
Parity bit	One byte after transmission	An odd number of flipped bits in the byte	No
Parity block	A block of bytes after transmission	A single flipped bit, and its exact position	Yes — one bit
Checksum	A block or packet after transmission	Any change to the total of the bytes	No
Echo check	Data returned to the sender	Any difference between sent and returned data	No
ARQ	Whether a packet arrived and was accepted	Errors (via ACK/NAK) and lost packets (via timeout)	No — it re-sends
Check digit	Data entered by a person or scanner	Mistyped and transposed digits	No

Summary for the exam:

Parity block is the only method here that corrects as well as detects — and only for a single-bit error.
Checksum is calculated from the data; echo check sends the data back instead, and cannot tell which direction the error happened in.
ARQ is the response system, not a detection method. Always mention the timeout as well as ACK and NAK.
Check digit catches human entry errors, especially transposed digits. The others check transmitted data.

2.2 Methods of error detection