Error detection: parity, checksums, echo checks and check digits
When data is sent, interference can change bits along the way, so data can be lost, gained or changed. This topic covers the ways a receiver can tell that data arrived wrong, and what happens next.
Parity checks
Sender and receiver agree to use odd or even parity. The sender sets one bit, the parity bit, so the byte has an odd (or even) number of 1s. The receiver counts the 1s; if the count is wrong, an error has happened.
A single parity bit misses errors where two bits flip, because the count stays odd or even. A parity block check sends a parity bit for every byte and a parity byte for every column. The row and column that both fail point to the exact bit that changed.
Checksum
The sender uses an agreed calculation to work out a value from the block of data, and sends it with the data. The receiver does the same calculation on what arrived. If the two values differ, the data has changed and is sent again.
Echo check
The receiver sends the data it received straight back to the sender, which compares it with what it sent. A difference means an error, and the data is sent again. It can’t tell whether the error happened on the way there or on the way back.
Check digits
A check digit is an extra digit calculated from the other digits of a number, such as a barcode or ISBN. It is added when the number is created. When the number is typed in or scanned later, the digit is recalculated; if it doesn’t match, the number was entered wrongly. It catches mistakes such as a wrong digit or two digits swapped.
Automatic repeat request (ARQ)
With ARQ, the receiver checks each piece of data and sends a positive acknowledgement when it arrives correctly. The sender waits a set time (a timeout). If no acknowledgement arrives in time, or a negative one does, it sends the data again, and keeps doing so until it is acknowledged.
Where marks go
- Saying a parity check can find which bit is wrong: a single parity bit can’t, only a parity block check can.
- Missing that a parity check fails to spot an even number of bits flipping.
- Mixing up check digits (catching mistakes when data is entered) with checksums (catching errors when data is sent).
- Describing ARQ without the timeout, or without the data being sent again.
- Writing “the data is checked” without saying what is compared with what.