Parity Bit Tutorial: Single-Bit Error Detection

TL;DR: A parity bit is one extra bit appended to a binary word so that the total number of 1s is even (even parity) or odd (odd parity). A chain of XOR gates generates the bit on the sender side; the same chain on the receiver side flags any single-bit flip — though it silently misses errors that flip an even number of bits.

A parity bit is the simplest non-trivial error-detection mechanism in digital communications. It costs one bit of overhead per word, requires only XOR gates, and detects every single-bit error and every odd-multiplicity error. Its limits are equally simple: it cannot tell which bit flipped, and it cannot detect any even-multiplicity error. For every serial protocol of the 1970s and 80s — UART, RS-232, parallel printer interfaces — parity was the universal first line of defense.

What Exactly Is a Parity Bit?

Take a $k$-bit data word. Count its 1s. Append a single bit $P$ chosen so that the count of 1s in the resulting $(k+1)$-bit codeword satisfies a fixed rule:

• Even parity: total number of 1s is even.
• Odd parity: total number of 1s is odd.

For an 8-bit data byte $D_7 D_6 D_5 D_4 D_3 D_2 D_1 D_0$, the even-parity bit is:

$P_{even} = D_7 \oplus D_6 \oplus D_5 \oplus D_4 \oplus D_3 \oplus D_2 \oplus D_1 \oplus D_0$

XOR is the perfect operator here — it returns 1 if and only if its inputs have an odd number of 1s, which is exactly the condition we want for $P_{even}$. For odd parity, invert the result: $P_{odd} = \overline{P_{even}}$. The choice between even and odd is conventional; what matters is that sender and receiver agree.

If the XOR gate’s role as a difference detector feels familiar, that’s because the same algebraic property — output equals 1 when input weight is odd — drives both single-bit comparison and parity computation. The difference is just the number of inputs in the chain.

Truth Table for a 4-Bit Even-Parity Generator

The output is 1 in exactly the rows with an odd number of 1s among $D_3 \dots D_0$.

Building the Generator

For an $n$-bit word, you need an $n$-input XOR. Two-input XOR gates compose either as a flat tree:

     XOR
    /   \
   XOR   XOR
   / \   / \
  D3 D2 D1 D0

or as a linear chain:

D3 ─┐
    XOR ─┐
D2 ─┘    XOR ─┐
         /    XOR ── P
D1 ─────┘    /
D0 ─────────┘

The flat tree has $\log_2 n$ gate delays on the critical path; the chain has $n - 1$. For wide words you want the tree. For an 8-bit byte at any reasonable serial baud rate the difference is irrelevant — four gate delays versus seven, both well under one nanosecond. Use whichever is more convenient to draw.

The Checker

On the receive side you have the data bits $D_7 \dots D_0$ and the received parity bit $P$. Recompute parity over just the data, then compare:

$\text{Error} = P \oplus (D_7 \oplus D_6 \oplus \dots \oplus D_0)$

If Error is 1, something flipped. If 0, either no error occurred or an even-multiplicity error did. Implementation-wise the checker is identical to the generator with one extra XOR for the comparison — or, equivalently, just one big XOR of all $n+1$ received bits. If even parity was used, that single combined XOR should be 0 on a clean word.

The checker is the same circuit you’d use for equality comparison with an XNOR operating on the local recomputation versus the received bit, just collapsed into one XOR tree.

Worked Example

Send the byte $D = 10110100$ with even parity.

Count of 1s: 4 (even). So $P = 0$. Transmit 9 bits: $D_7 \dots D_0 P = 101101000$.

Clean reception: receiver reads $101101000$. XOR of all 9 bits = 0. No error flagged. Strip $P$, deliver $10110100$.

Single-bit error: during transmission, $D_3$ flips from 0 to 1. Receiver reads $101111000$. XOR of all 9 bits = 1. Error flagged; receiver discards the byte and (in a typical UART) signals a framing error to the host.

Double-bit error (silent failure): $D_3$ flips from 0 to 1 and $D_5$ flips from 1 to 0. Receiver reads $100111000$. XOR of all 9 bits = 0. No error flagged. Receiver delivers $10011100$, a corrupted byte that looks valid. This is the unfixable weakness of plain parity.

Where Parity Lives

UART and RS-232. Most asynchronous serial frames have a configurable parity option — 8N1 (8 data bits, no parity, 1 stop bit), 8E1 (even parity), 8O1 (odd parity), 7E1 (legacy 7-bit ASCII with even parity). The parity bit is generated by the transmitter’s UART hardware as the final shift step before the stop bit, and checked by the receiver’s UART before raising the receive-data-ready interrupt.

Memory. Early IBM PCs used a 9-bit DIMM — eight data bits plus one parity bit per byte — to detect (but not correct) DRAM errors. Modern systems have moved to ECC with Hamming-style codes that correct single-bit flips, but the chain of XORs in the parity tree is still there inside the ECC encoder.

Storage tape and floppy. Many tape and floppy formats included a parity track for the same reason. A scratched tape might lose individual bits; parity flagged the loss without trying to recover.

Buses. Some embedded buses (ISA’s parity lines, certain industrial fieldbus variants) carry per-byte or per-word parity. The check is so cheap that it’s free to include.

To see this in action with a real circuit, the 8-bit serial transmitter/receiver template gives you a working serial channel built from shift registers. Add one XOR gate per bit on the transmit side as a generator chain, send the result alongside the data, and compare against a recomputed value on the receive side. Flip a switch to inject errors and watch the checker fire.

Limits, Quantified

A parity bit detects:

• All single-bit errors.
• All errors of odd multiplicity (3, 5, 7, … flips).

A parity bit does not detect:

• Any error of even multiplicity (2, 4, 6, … flips).
• Burst errors longer than 1 bit are caught only if they happen to be odd-weight.

The probability of catching a random burst depends on the bit-error rate. If individual bits flip independently with probability $p$ and $p$ is small (say $10^{-6}$ per bit), the probability of a double-bit error per 8-bit byte is roughly $\binom{8}{2} p^2 \approx 28 p^2$, which is vastly smaller than the probability of a single-bit error $\approx 8p$. So in low-error environments, parity catches the overwhelming majority of real errors. In high-noise environments — a long copper run with EMI, deep-space links, faulty memory — parity becomes inadequate quickly and you graduate to Hamming, CRC, or Reed-Solomon.

Parity vs Hamming: A Quick Comparison

Parity is the right tool when retransmission is cheap and errors are rare. Hamming codes become worthwhile the moment retransmission isn’t possible — RAM, satellite links, optical media.

Common Pitfalls

• Mismatched even/odd convention. Both ends must agree. UART configuration strings exist exactly to negotiate this.
• Parity computed over the wrong bit set. Some protocols include start/stop bits in the parity; most don’t. Read the spec.
• Treating parity as integrity protection. Parity is detection, not authentication. Anyone can recompute the parity bit for a malicious payload.
• Assuming parity means error-free. A clean parity check means no odd-multiplicity error was detected. It does not mean the data is correct.

What’s Next

The next post in this series, Hamming Code Error Correction Explained (with Math), walks through the next step up — three parity bits arranged so that any single-bit flip is not just detected but located and corrected. After that, Gray Code Explained: Why Rotary Encoders Use It shows another use of XOR-based encoding for glitch-free transitions in mechanical sensors and asynchronous FIFOs.

To experiment with parity right now, open the 8-bit serial transmitter/receiver template, add XOR gates as a parity generator on the transmit side and an identical chain plus a comparator on the receive side, and verify the checker fires for every single-bit fault you inject.