AlgoPlusAlgoPlus
Learn/Networking
Lesson

Parity & Checksum

A parity bit keeps the count of 1s even; doing it per row and column locates a single flipped bit.

8 min read Watch it move Build it

A checksum is any small value computed from data and sent alongside it, so the receiver can recompute it and verify nothing changed in transit. The simplest checksum of all is a single parity bit — and building it up into two dimensions turns pure error *detection* into error *correction*.

One parity bit: detect a single flip

Under even parity, you append one extra bit chosen so the group holds an even number of 1s. The receiver counts the 1s: if the total is odd, at least one bit flipped in transit. It's cheap and it always catches a single-bit error — but it has a blind spot: if *two* bits flip, the count stays even and the error slips through. A single parity bit also can't tell you *which* bit is wrong.

Detection is not correction
One parity bit only raises a flag — it can't locate the bad bit, and an even number of flips fools it entirely. To *fix* an error you need more structure.

2D parity: locate the bad bit

Arrange the data as a grid and compute a parity bit for every row and every column (this is 2D parity, also called a longitudinal redundancy check or LRC). Now a single flipped bit breaks the parity of exactly one row *and* one column. Where that failing row and failing column cross is the corrupted bit — so you not only detect it, you can flip it back and correct it.

data + row parity        a single flip at (row 2, col 3)
  1 0 1 1 | 1              1 0 1 1 | 1   ok
  0 1 1 0 | 0      -->      0 1 0 0 | 0   row 2 FAILS
  1 1 0 1 | 1              1 1 0 1 | 1   ok
  --------- col parity
  0 0 0 0                  0 0 1 0
                              ^ col 3 FAILS
  intersection (row 2, col 3) = the corrupted bit
Why the intersection works
A single flip changes the 1-count of just one row and just one column. Their failing checks act like an X-marks-the-spot coordinate, naming the exact bit to correct.
Still fooled by some multi-bit errors
If bits flip at the four corners of a rectangle, every affected row and column ends up with an even count again — 2D parity sees nothing wrong. It corrects one error well, but isn't bulletproof against patterned multi-bit corruption.
OperationTimeSpace
1D parity · no location; even flips slip bydetect 1-bit+1 bit
2D parity · correct single errorsdetect & locate 1-bit+1 bit per row & col
Check yourself
With 2D parity, how is a single corrupted bit located?