4.5.5.3 - Error checking and correction

Parity bits and parity blocks

A parity bit is an extra bit chosen so that a transmitted group contains an agreed odd or even number of ones.

With even parity, the total number of ones, including the parity bit, must be even. The seven data bits 1101001 contain four ones, so the even parity bit is 0 and the complete group is 11010010. With odd parity, its parity bit would be 1. Sender and receiver must agree on both the parity rule and which bit is the parity bit.

If one bit changes during transmission, the count switches between odd and even, so the receiver detects a failure. It can reject the data and request retransmission. A single parity bit does not identify which bit is wrong, so it normally detects rather than corrects the error. An even number of flipped bits leaves parity unchanged and can pass the check. Odd numbers of flips fail. The parity bit itself may be the changed bit.

A two-dimensional parity block adds checks to rows and columns. In this original even-parity block every displayed row and column has an even count of ones; the bottom-right bit also makes the parity row and column even.

Suppose only row 2, column 2 changes from 1 to 0. Row 2 then fails and column 2 fails. Their intersection locates the bit, which can be flipped back under the assumption of one erroneous bit. Multiple-bit patterns can make correction ambiguous, or escape detection: flipping the four corners of a rectangle changes two bits in each affected row and column, leaving all parities even. Redundancy improves protection, but its guarantees depend on the error model.

Majority voting can correct an error

Majority voting sends repeated copies and reconstructs each bit from the value that occurs most often.

For three copies of a bit, 0, 1, 0 are decoded as 0. The receiver does not merely notice disagreement: it chooses a reconstructed value. For a multi-bit message, voting takes place at each corresponding bit position, rather than selecting a whole copy that looks most plausible.

These received copies reconstruct 1010. Three-copy voting corrects a bit position if no more than one copy is wrong there. If two copies change to the wrong value, that wrong value wins. Errors common to all copies are especially dangerous. The method uses three transmitted bits per original bit, increasing transmission time or bandwidth demand for the same useful data. It may be useful when immediate correction matters and retransmission is difficult, but it is not guaranteed correction of arbitrary corruption.

Checksums protect blocks of data

A checksum is a value calculated from a block of data and sent or stored with it so that the calculation can be repeated later.

The sender computes the value using an agreed algorithm. The receiver recomputes it from the received data and compares it with the supplied value. A mismatch detects an error and can trigger retransmission. A match means only that the data passes that particular check: different data blocks can produce the same checksum. A checksum generally does not locate or repair the error.

For a deliberately simple example, add the data-byte values and take the remainder on division by 256. For bytes 200, 80 and 5, the sum is 285, so the checksum is $285\bmod256=29$. If the final byte arrives as 6, the recalculated checksum is 30, which does not match 29. If instead the first byte increases to 201 and the second decreases to 79, the sum remains 285, so the error is missed. This is a limitation of this simple sum algorithm, not a claim that all checksum algorithms have the same strength. The exact algorithm must be stated when calculating a checksum.

Checksums are useful for transferred blocks and stored files because they summarise a large amount of data in a smaller check value. They add processing and some extra stored/transmitted data. An ordinary checksum is an accidental-error check; it does not by itself establish who sent the data or protect against an attacker who can replace both data and checksum.

Check digits detect identifier mistakes

A check digit is calculated from the other digits of an identifier and appended to help detect entry or transcription mistakes.

An identifier such as a stock code is not an arithmetic quantity. Its check digit adds a consistency constraint. When a user enters the identifier, the system recomputes or validates the constraint; a failed check can prompt re-entry. It does not prove that the identifier exists or belongs to the intended item, and it normally does not reveal the correct digit.

Consider this original scheme: multiply the four payload digits, left to right, by 3, 1, 3 and 1. Append a digit that makes the weighted sum plus that digit a multiple of 10. For payload 5724, the weighted sum is $5\times3+7\times1+2\times3+4\times1=32$. The next multiple of 10 is 40, so append 8 to make 57248. Validation repeats the weighted sum and checks $32+8=40$.

If 57248 is entered as 57348, the total becomes 43, so the error is detected. Swapping the first two payload digits to give 75248 makes the total 44, also failing. This example does not imply every transposition is detected: swapping the first and third payload digits, which have equal weights, preserves the sum. Different real schemes use different weights and rules. Apply the stated algorithm rather than assuming every check digit uses this one.