Error Detection and Correction: Parity and Two-Dimensional Parity

The Idea of Error Detection

The sender appends error-detection and -correction bits (EDC) to the data $D$ it wants to protect and sends both. The receiver gets possibly altered values $D'$ and $EDC'$ and uses them to decide whether the data is in error. Error-detection techniques cannot catch every error: some error patterns always happen to slip past. In general, a longer EDC lowers the probability of an undetected error but adds overhead.

Parity Check

The simplest form of error detection is a single parity bit. Suppose the information to send is 0111000110101011. With even parity, the sender simply appends one more bit, 1, so that the total number of 1s is even.

With even parity, the receiver only needs to count whether the number of 1s it received is even. If it finds an odd number of 1s, an odd number of bit errors has occurred. However, if an even number of bit errors occurs, the errors cannot be detected.

Odd parity works the other way round: the parity bit makes the total number of 1s odd. In the example above, the odd parity bit would be 0. Errors in real channels often occur in bursts that affect several adjacent bits at once, so a single parity bit misses errors fairly often.

Two-Dimensional Parity

Two-dimensional parity can not only detect a single-bit error but also find the erroneous bit from its row and column indexes and correct it.

The data is arranged in rows and columns, a parity bit is computed for each row and each column, and the bottom-right bit checks those parity bits. Here is an example with even parity:

If the bit at row 2, column 2 changes from 1 to 0 in transit, the checks of row 2 and column 2 both fail. Their intersection is the bad bit, and the receiver corrects it by flipping it:

Two-dimensional parity detects any two bit errors but cannot correct them: if both errors are in one row, only two columns fail and the row cannot be determined. If four errors sit at the corners of a rectangle, the 1s change in pairs in every row and column, and the errors go completely undetected. The ability of a receiver to correct errors directly, without retransmission, is called forward error correction (FEC); it is especially useful where retransmission is expensive, such as satellite links and real-time audio and video.