2.13 Parity: Even/Odd Parity Bits for Error Detection

Generate an even or odd parity bit for a given data word, check received data for single-bit errors, and explain why parity cannot detect every possible error pattern.

Parity is the simplest widely used scheme for detecting transmission or storage errors in binary data: a single extra bit, the parity bit, is appended to a data word so that the total count of 1-bits in the combined word (data plus parity) satisfies a chosen rule — either always even (even parity) or always odd (odd parity). If a single bit gets flipped in transit, the count of 1s changes parity, and a receiver checking that count can detect that something went wrong, even though it cannot generally tell which bit was corrupted or fix it.

Even parity vs odd parity

Even parity sets the parity bit so that the total number of 1-bits across the data plus the parity bit is even. Odd parity sets the parity bit so that total is odd instead. Both schemes accomplish the same fundamental error-detection goal; the choice between them is a system design convention, not a difference in detection capability — a system must simply agree in advance which convention the transmitter and receiver both use.

Generating the parity bit is done in practice with the XOR operation: the parity bit equals the XOR of all the data bits for odd parity's complement, or its inverse for even parity (equivalently, count the 1s directly and choose the parity bit to make the total meet the desired evenness/oddness) — XOR is a natural fit because XOR-ing a set of bits together yields 1 exactly when an odd number of those bits are 1.

Parity checking at the receiver

On the receiving end, the same total-1s count is recomputed across the received data plus its received parity bit. If the result matches the agreed convention (even, or odd), the data is presumed correct; if it does not match, the receiver knows at least one bit was corrupted somewhere in transit, even though it does not know where. To generate the parity bit for a given data word, count the number of 1-bits and select the parity value accordingly, so the resulting total meets whichever convention (even or odd) the system has chosen.

Detection limitations

Parity has a well-defined and important limitation: it can detect many single-bit errors, but it cannot uniquely locate the corrupted bit and may fail to detect an even number of bit errors. If exactly one bit flips, the total 1-count's evenness/oddness necessarily changes, so a single-bit error is always detected. But if exactly two bits flip (or any even number of bits), each flip changes the parity, and two flips cancel each other out — the total count's evenness/oddness returns to what it was before, so the receiver sees a passing parity check on genuinely corrupted data.

Because of this, simple parity is only suitable for situations where errors are expected to be rare and predominantly single-bit, and it provides detection only, never correction — a receiver that detects a parity failure knows only that an error occurred, not which bit is wrong, and typically must request retransmission rather than repair the data itself. More powerful error-detecting and error-correcting codes (beyond the scope of this introductory topic) are used where stronger guarantees are required.

Parity bit rule

XOR of a set of bits equals 1 exactly when an odd number of those bits are 1 — which is exactly the condition that needs correcting to reach an even total for even parity. Both transmitter and receiver must agree in advance on even vs odd parity; mixing conventions makes every check meaningless.

Even parity: choose parity bit P so that
  (count of 1s in data) + P  is EVEN

Odd parity: choose parity bit P so that
  (count of 1s in data) + P  is ODD

Generation via XOR:
  P (for even parity) = XOR of all data bits

Code Examples

Counting the 1-bits in the data word 1011001 gives four 1s, which is already an even count. To keep the total count of 1s (across data and parity bit together) even, the parity bit must be 0 — adding a 1 would make the total five (odd), which would violate the even-parity rule.

Data 1011001 has four 1-bits (even), so the even-parity bit is 0.

Flipping exactly one bit changes the total 1-count's evenness, so the receiver's parity check correctly flags the single-bit error. But flipping exactly two bits (as in the third line) changes the count twice, returning it to even — the parity check passes even though the data is corrupted, illustrating parity's fundamental blind spot for even numbers of bit errors.

A single flipped bit is always caught; two flipped bits can silently pass the parity check.

Data: 1011001

Count the 1s: 1,0,1,1,0,0,1 -> four 1-bits (positions with value 1: 4 of them)

For EVEN parity, total 1s (data + parity bit) must be even.
Current count = 4 (already even) -> parity bit P = 0

Transmitted word: 1011001 0   (data + parity bit)

Correct even-parity word:   1011001 0   (4 ones + parity 0 = 4, even)

Single-bit error (bit flipped):  1001001 0   (3 ones + parity 0 = 3, odd -> DETECTED)

Double-bit error (two bits flipped): 1001101 0   (4 ones + parity 0 = 4, even -> NOT detected!)

Parity check outcomes

Parity reliably catches an odd number of bit errors but can silently miss an even number of simultaneous bit errors.

Original data + parity  ->  count of 1s matches convention (even/odd)

1 bit flips   -> count changes parity  -> MISMATCH -> error DETECTED
2 bits flip   -> count returns to original parity -> MATCH -> error MISSED
3 bits flip   -> count changes parity again -> MISMATCH -> error DETECTED

Important Rules

Even parity: total 1-bit count of (data + parity bit) must be even.

Odd parity: total 1-bit count of (data + parity bit) must be odd.

To generate the parity bit, count the data's 1-bits and choose the parity value to satisfy the chosen convention.

Parity reliably detects any odd number of bit errors, but can miss any even number of simultaneous bit errors, and never identifies which specific bit is wrong.

Where this shows up

Parity bits have historically been used in serial communication protocols (such as RS-232), in ECC/parity RAM modules found in servers to catch single-bit memory corruption, and in simple data storage formats; modern high-reliability systems typically layer on stronger error-correcting codes (like Hamming codes or CRC checks) precisely because parity alone cannot correct errors or reliably catch even-numbered bit-flip patterns.

Assuming a passing parity check guarantees the data is completely error-free.

Understand that parity only guarantees detection of an odd number of bit errors — a passing check is consistent with either 'no errors' or 'an even number of simultaneous errors', so it is not an absolute correctness guarantee.

Parity can detect many single-bit errors, but it cannot uniquely locate the corrupted bit and may fail to detect an even number of bit errors. Treating a passing parity check as a proof of correctness overlooks this specific, well-known blind spot.

[tricky] Can a simple parity check ever fail to detect a data corruption? A. No, parity always detects every possible error B. Yes — if an even number of bits (e.g., exactly two) are flipped, the total 1-bit count returns to its original evenness/oddness, so the parity check passes despite the corrupted data C. No, but only because modern hardware never corrupts more than one bit D. Yes, but only for odd parity, never for even parity

B. Yes — if an even number of bits (e.g., exactly two) are flipped, the total 1-bit count returns to its original evenness/oddness, so the parity check passes despite the corrupted data — Parity can detect many single-bit errors, but it cannot uniquely locate the corrupted bit and may fail to detect an even number of bit errors. Two (or any even number of) simultaneous bit flips cancel out in terms of parity, so the check passes even though the data was corrupted — this limitation applies equally to even and odd parity conventions.

[interview] Why can a parity check detect that an error occurred but not identify which bit is wrong? A. Because parity only encodes a single aggregate count (evenness/oddness of 1-bits) across the whole word, which carries no information about the position of any individual bit B. Because parity bits are always transmitted separately from the data on a different wire C. Because parity checks only work on the first bit of a data word D. Because parity is a form of encryption, not error detection

A. Because parity only encodes a single aggregate count (evenness/oddness of 1-bits) across the whole word, which carries no information about the position of any individual bit — A parity bit is a single summary value (whether the total 1-count is even or odd) computed over the whole data word — it collapses all positional information into one bit, so a mismatch reveals only that an error exists somewhere, with no information left to pinpoint which specific bit changed.

For the data word 1101010, compute the odd-parity bit, then show that flipping any single bit of the transmitted (data+parity) word is detected by recomputing the parity check.

1101010 has four 1-bits (even). For odd parity, the total count must be odd, so the parity bit must be 1 (4+1=5, odd). Transmitted word: 1101010 1. Flipping any single bit changes the total count by exactly one, making it even again, which fails the odd-parity check and is correctly detected as an error.

Count the 1-bits in 1101010 first, then choose the parity bit so the total count is odd.