Parity generators - checkers: Question bank — Hardware deep dive

The five symbols this page uses — defined here, self-contained

You do not need the parent note open to follow along. Everything rests on five pieces of notation, all defined right here.

Definition The vocabulary, from zero

A bit is a single one-or-zero value — think of a light that is either ON (1) or OFF (0).
$d_{0}, d_{1}, \dots, d_{n - 1}$ are the data bits — the actual $n$ bits of your message. The little number (the subscript) is just a name tag: $d_{0}$ is "bit number 0", $d_{3}$ is "bit number 3". They are not multiplied by anything.
$\oplus$ is the XOR ("exclusive-or") operator. $a \oplus b = 1$ when exactly one of $a, b$ is 1, and $0$ otherwise. Read $a \oplus b \oplus c$ as "combine all these with XOR." Its magic: the result is 1 exactly when an odd number of the inputs are 1.
XNOR is XOR with its output flipped — written $\overline{a \oplus b}$ . The bar on top means "invert": turn 1 into 0 and 0 into 1.
$P$ is the parity bit — one extra bit the sender appends so the total count of 1s follows a chosen rule (even total, or odd total).
$E$ is the error signal the receiver computes — a single bit that is meant to be one value when the word is clean and the other value when a flip happened.

Here is the ground truth of XOR — the entire engine of parity in one small table.

Formula XOR truth table (the whole engine)

$a$	$b$	$a \oplus b$	number of 1s in ${a, b}$
0	0	0	0 — even
0	1	1	1 — odd
1	0	1	1 — odd
1	1	0	2 — even

Notice the pattern: $a \oplus b = 1$ exactly on the odd rows. XOR is literally an "is the count odd?" detector. Chain more inputs and it keeps answering that same question for the whole group.

The figure below shows the gate tree that turns four data bits into a parity bit, and shows the checker being the same tree with one extra input.

And this table shows every error case the traps below refer to, side by side, so you can see why some are caught and some slip through.

The three loaded facts, restated so this page stands alone:

XOR of a set of bits equals 1 exactly when an odd number of them are 1 — that is the whole engine.
Even-parity generator $= P = d_{0} \oplus d_{1} \oplus \dots \oplus d_{n - 1}$ ; odd-parity generator is its complement (XNOR).
The checker XORs everything including $P$ to get the error signal $E = d_{0} \oplus \dots \oplus d_{n - 1} \oplus P$ .

True or false — justify

A single flipped bit is always caught by an even-parity checker.

True — one flip changes the count of 1s by

\pm 1

, so an even count becomes odd, breaking the rule and forcing

E = 1

. Parity is guaranteed against any odd number of flips.

Even parity means the parity bit

P

is always 0.

False —

P

is whatever makes the total count even. If the data already has an odd number of 1s,

P = 1

. "Even" describes the total, not the parity bit's value.

The parity checker needs a completely different circuit from the generator.

False — both are the same XOR tree. The checker is just an

(n + 1)

-input version that also feeds

P

in; its output is the error flag. Same gates, one extra input.

For odd parity, a correct received word gives

E = 0

False — a correct odd-parity word has an odd count of 1s, so XORing everything gives

E = 1

. In odd parity,

E = 0

signals an error (the reverse of even parity).

Adding a parity bit lets the receiver repair corrupted data.

False — parity only tells you that something broke, never which bit. Locating and fixing the fault needs more redundancy, e.g. Hamming Codes.

XOR and XNOR give the same parity-generator output for the same data.

False — they are complements. For data

101

the XOR is

0

(even-parity

P

) while the XNOR is

1

(odd-parity

P

). They agree only in that one is always the flip of the other.

If the data has an even number of 1s, the even-parity bit is 0.

True — the total is already even, so no extra 1 is needed. Formally

X = d_{0} \oplus \dots \oplus d_{n - 1} = 0

and

P = X = 0

A parity system that misses double-bit errors is broken and should never be used.

False — it is working as designed. Parity is a deliberately cheap net that catches all odd-count errors; missing even-count errors is a known, accepted trade-off for its tiny hardware cost.

Spot the error

"For even parity, set

P = \overline{d_{0} \oplus d_{1} \oplus \dots}

(XNOR of all data bits)."

Wrong gate. Even parity uses plain XOR; XNOR gives odd parity. The XNOR would flip the total to odd, breaking the even convention. Remember: "Even is plain XOR; Odd wears an N-coat."

"The receiver got

E = 1

in an even-parity system, so the data is definitely fine."

Backwards reading. In even parity,

E = 0

means fine and

E = 1

means error.

E = 1

says at least one (odd number of) bit flipped — the data is not trustworthy.

"To check the word, XOR only the data bits and ignore

P

The checker must include

P

. XORing data alone just re-computes the generator value; it can't compare against the received

P

. Including

P

is exactly what makes

E

reflect whether the rule still holds.

"A double flip changes the count of 1s by 2, so parity flips twice and

E = 1

The verdict is wrong even though the count-change is right. Two flips change parity twice, which returns it to the original even/odd state, so

E

ends up unchanged — the error is silently missed.

"XOR is left-to-right only, so

a \oplus b \oplus c

must be grouped as

(a \oplus b) \oplus c

Grouping doesn't matter — XOR is associative, so

(a \oplus b) \oplus c = a \oplus (b \oplus c)

. Any bracketing (or a balanced tree of gates) gives the same parity result.

"Even-parity generator for

n

data bits needs

n

XOR gates."

It needs

n - 1

two-input XOR gates to combine

n

bits (each gate merges two lines into one). A common trap is counting one gate per input instead of one per combination.

Why questions

Why is XOR — and not AND or OR — the natural gate for parity?

Because XOR's output is 1 exactly when an odd number of its inputs are 1, which is literally the parity question. AND asks "all 1s?" and OR asks "any 1s?" — neither counts oddness, so neither computes parity.

Why does chaining XORs still compute the parity of the whole group?

XOR is associative and commutative, so a chain acts as one big "is the total count odd?" test regardless of order or grouping. Each additional 1 among the inputs toggles the running result.

Why does a single bit flip always flip the error signal

E

A flip changes the count of 1s by exactly

\pm 1

, which changes the parity of that count. Since

E

is the parity of the whole received word, its value flips with it.

Why does odd parity use the complement of the even formula?

Even parity forces the total count even; odd parity wants the opposite outcome for the same data, and the opposite of an XOR result is its XNOR. Inverting the even generator's output is exactly the requirement flip.

Why is a parity circuit purely combinational, with no memory?

The parity bit depends only on the current data bits, not on any past inputs. With no feedback or stored state needed, it belongs to Combinational Circuits — see also XOR and XNOR gates.

Why can't parity tell you which bit flipped?

A single parity bit carries only one bit of information: "count is right / count is wrong." That is enough to detect a fault but far too little to pinpoint one of

n

positions — locating needs multiple, cleverly placed parity bits (Hamming Codes).

Why do stronger schemes like Checksums and CRC exist if parity is so cheap?

Parity misses all even-count errors and many burst errors. Checksums and CRC add more redundancy to catch far more error patterns, trading a little extra hardware and bits for much stronger detection.

Edge cases

What parity bit does an all-zero data word get, in even parity?

P = 0

. There are zero 1s, and zero is an even count, so no extra 1 is needed — the XOR of all-zeros is 0.

What parity bit does an all-zero data word get, in odd parity?

P = 1

. Zero 1s is even, so odd parity must add one 1 to reach an odd total; the XNOR of all-zeros is 1.

What happens if the parity bit

P

itself is the bit that gets corrupted?

It is still caught —

P

is part of the counted word, so flipping it changes the total count by

\pm 1

just like any data bit, forcing

E

to signal an error. Parity protects itself.

If exactly THREE bits flip in an even-parity word, is the error detected?

Yes — three is an odd number of flips, so the parity toggles an odd number of times and ends up wrong (

E = 1

). Parity catches any odd count of errors, not just single flips.

Can a parity checker ever raise a false alarm on an untouched, correctly generated word?

No — if no bit flips, the received word still satisfies the parity rule, so

E

takes its "good" value. False alarms only arise from actual corruption, never from clean transmission.

Connections

XOR and XNOR gates — every trap here rests on XOR meaning "odd count?".
Combinational Circuits — why parity has no memory.
Error Detection and Correction — the detect-only role of parity.
Hamming Codes — the "which bit?" upgrade parity can't do.
Checksums and CRC — stronger successors that patch parity's blind spots.