Parity generators - checkers: Exercises — Hardware deep dive

Ten problems climbing from "can you spot a parity bit?" to "design and reason about a multi-word scheme." Every problem has a full worked solution hidden in a collapsible callout — cover it, solve, then reveal. Prerequisite tools: XOR and XNOR gates and the parent Parity Generators / Checkers.

Before we begin, three shared conventions we lean on the whole way down.

Figure s01 below draws exactly this: four bits ( $d_{3} \dots d_{0}$ ) light up yellow for a $1$ and blue for a $0$ ; the pink box on the right is the running XOR answer $X$ . Three yellow squares (three 1s) means an odd count, so the XOR box reads $1$ .

Level 1 — Recognition

Can you read a parity word and count correctly?

Exercise 1.1 (L1)

A 4-bit data word $1101$ is sent with an even-parity bit appended. What is the full 5-bit transmitted word?

Recall Solution 1.1

WHAT we do: count the 1s in the data, then choose $P$ to make the total even. Step 1: Data $1101$ has three 1s (count $= 3$ , which is odd). Step 2: Even parity wants an even total. We have odd → we must add one more 1, so $P = 1$ . Step 3: Transmitted word $= 11011 = 11011$ . Total 1s $= 4$ (even). ✓ Answer: $11011$ .

Exercise 1.2 (L1)

Same data $1101$ , but now using odd parity. What is $P$ ?

Recall Solution 1.2

WHY different: odd parity wants the total count of 1s to be odd. Data already has three 1s (odd). Adding a 1 would make it even — bad. So $P = 0$ keeps the total at $3$ (odd). ✓ Answer: $P = 0$ , word $= 11010$ .

Level 2 — Application

Turn the XOR formula into a mechanical procedure.

Exercise 2.1 (L2)

Using the even-parity generator $P = d_{3} \oplus d_{2} \oplus d_{1} \oplus d_{0}$ , compute $P$ for data $0110$ .

Recall Solution 2.1

WHAT we do: XOR the bits one pair at a time. $P = 0 \oplus 1 \oplus 1 \oplus 0$ Step by step: $0 \oplus 1 = 1$ ; then $1 \oplus 1 = 0$ ; then $0 \oplus 0 = 0$ . WHY we may go strictly left to right: XOR is associative, meaning $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ — the way we bracket the operations never changes the result. So we are free to collapse the chain one pair at a time from the left; any other grouping (or even a different order, since XOR is also commutative) lands on the same $P$ . That is precisely why a hardware XOR tree and a left-to-right hand calculation agree. Answer: $P = 0$ . Check: data has two 1s, so total already even — no extra 1 needed. ✓

Exercise 2.2 (L2)

An odd-parity generator handles data $1011$ . Give $P$ using the XNOR rule $P = \overline{d_{3} \oplus d_{2} \oplus d_{1} \oplus d_{0}}$ .

Recall Solution 2.2

Step 1 — inner XOR (this is our named quantity $X$ , the XOR of all data bits): $X = 1 \oplus 0 \oplus 1 \oplus 1$ . Left to right: $1 \oplus 0 = 1$ ; $1 \oplus 1 = 0$ ; $0 \oplus 1 = 1$ . So $X = 1$ . Step 2 — invert (that's the "N" in XNOR): $P = \overline{X} = \overline{1} = 0$ . WHY invert? $X = 1$ says data already has an odd count of 1s. Odd parity wants odd total, so we add nothing: $P = 0$ . ✓ Answer: $P = 0$ , word $= 10110$ (three 1s, odd). ✓

Exercise 2.3 (L2)

A parity checker in an even-parity system receives $11010$ (four data bits $d_{3} d_{2} d_{1} d_{0}$ then $P$ ). Compute the error flag $E = d_{3} \oplus d_{2} \oplus d_{1} \oplus d_{0} \oplus P$ and state the verdict.

Recall Solution 2.3

WHAT the checker does: XOR everything including $P$ . $E = 1 \oplus 1 \oplus 0 \oplus 1 \oplus 0$ $1 \oplus 1 = 0$ ; $0 \oplus 0 = 0$ ; $0 \oplus 1 = 1$ ; $1 \oplus 0 = 1$ . So $E = 1$ . Verdict: in an even-parity system $E = 0$ means OK, $E = 1$ means ERROR. Here $E = 1$ → error detected. (Sanity: the received word has three 1s — odd — but even parity demands an even count. Broken. ✓) Answer: $E = 1$ , error flagged.

Level 3 — Analysis

Reason about what parity catches and misses.

Exercise 3.1 (L3)

Even-parity system. The sender starts from the 4-bit data $1010$ , appends the correct even-parity bit, and transmits the valid 5-bit word. During transit, the bits at positions $d_{2}$ and $d_{0}$ both flip. Does the checker catch this double error? Compute $E$ before and after the flips.

Recall Solution 3.1

Step 1 — build the valid word the sender actually transmits. Data $= 1010$ (bits $d_{3} d_{2} d_{1} d_{0} = 1010$ ), which has two 1s. Even parity of two 1s needs $P = X = 1 \oplus 0 \oplus 1 \oplus 0 = 0$ . So the transmitted word is $d_{3} d_{2} d_{1} d_{0} P = 10100 = 10100$ . Confirm it is valid by running the checker on it: $E_{sent} = 1 \oplus 0 \oplus 1 \oplus 0 \oplus 0 = 0. ✓ (valid even word gives E = 0)$ Step 2 — apply the two stated flips. Flip $d_{2}$ ( $0 \to 1$ ) and flip $d_{0}$ ( $1 \to 0$ ). The word becomes $d_{3} d_{2} d_{1} d_{0} P = 11100 = 11100$ . Now run the checker on the received word: $E_{recv} = 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0.$ $1 \oplus 1 = 0$ , $0 \oplus 1 = 1$ , $1 \oplus 0 = 1$ , $1 \oplus 0 = 1$ → $E_{recv} = 1$ ? Let us redo carefully, one pair at a time: $1 \oplus 1 = 0$ ; $0 \oplus 1 = 1$ ; $1 \oplus 0 = 1$ ; $1 \oplus 0 = 1$ . So $E_{recv} = 1$ .

Careful recount (this is the crux of the exercise). The received word $11100$ has three 1s — that is odd, so $E = 1$ . But we flipped two bits; shouldn't parity be restored? It is restored only when the two flips change the count of 1s by an even net amount. Here $d_{2} : 0 \to 1$ adds a 1 and $d_{0} : 1 \to 0$ removes a 1 — net change $= + 1 - 1 = 0$ , an even change. So the count of 1s should be unchanged at two, not three. Re-examine the flipped word: starting from $10100$ (bits $1, 0, 1, 0, 0$ ), setting $d_{2} \to 1$ gives $1, 1, 1, 0, 0$ and setting $d_{0} \to 0$ leaves $d_{0}$ at $0$ (it was already $0$ !).

The trap this exposes. In $10100$ the bit $d_{0}$ is already $0$ , so "flip $d_{0}$ " turns it into a $1$ , not a $0$ : $d_{0} : 0 \to 1$ . Reapplying correctly: $d_{2} : 0 \to 1$ and $d_{0} : 0 \to 1$ give $d_{3} d_{2} d_{1} d_{0} P = 11110 = 11110$ . $E_{recv} = 1 \oplus 1 \oplus 1 \oplus 1 \oplus 0 = 0.$ $1 \oplus 1 = 0$ ; $0 \oplus 1 = 1$ ; $1 \oplus 1 = 0$ ; $0 \oplus 0 = 0$ → $E_{recv} = 0$ . Step 3 — verdict. $E_{recv} = 0$ says "OK", yet two bits are wrong. The double error is NOT caught. WHY: here both flips were $0 \to 1$ , each adding a 1, so the count of 1s changed by $+ 2$ (from two 1s to four 1s) — an even change. Even changes preserve parity, so $E$ returns to its "good" value $0$ . Parity detects only an odd number of errors; any even number of flips is invisible.

Exercise 3.2 (L3)

For a 4-data-bit even-parity code (5-bit words total), how many of the $2^{5} = 32$ possible 5-bit patterns are valid even-parity words? What fraction is that, and what does it mean for undetected-error probability?

Recall Solution 3.2

Step 1: A valid word is any 4-bit data value with its forced parity bit. There are $2^{4} = 16$ data values, each giving exactly one valid 5-bit word. So 16 valid words. Step 2: Fraction $= 16/32 = 1/2$ . Exactly half of all 5-bit patterns have even parity. WHY: for each of the 16 data patterns the parity bit is determined, so we never double-count and never skip — precisely half the space is "legal." Meaning: if an error lands you on any other legal codeword, it's invisible. Since legal words are spread out at "distance 2" (you need $\geq 2$ flips to move between them), single flips always land on an illegal word (caught), but some double flips land on a legal one (missed). Answer: 16 valid words, fraction $= 1/2$ .

Level 4 — Synthesis

Build and combine parity structures.

Exercise 4.1 (L4)

You must generate even parity for 8 data bits but you only own 2-input XOR gates. Design the tree: how many gates, and what is the minimum number of gate-delays (levels) from data to $P$ ?

Recall Solution 4.1

WHAT we need: XOR of $d_{0} \dots d_{7}$ built from 2-input pieces. Gate count: XORing $n$ bits with 2-input gates always costs $n - 1$ gates (each gate reduces the count of live values by one; start with 8, end with 1). So $8 - 1 = 7$ gates. Delay (levels): pair them in a balanced tree, not a chain. Level 1: 4 gates → four partial results. Level 2: 2 gates → two results. Level 3: 1 gate → final $P$ . So $⌈ lo g_{2} 8 ⌉ = 3$ levels. WHY a tree, not a chain: a straight chain of 7 gates has 7 levels of delay; the balanced tree cuts that to 3 while using the same 7 gates. Same hardware, faster answer. Answer: 7 two-input XOR gates, 3 levels of delay.

Figure s02 draws this balanced tree: the eight blue input dots ( $d_{0} \dots d_{7}$ ) feed four yellow XOR gates on level 1, whose outputs feed two pink gates on level 2, which feed one final gate producing $P$ . Count the gate boxes (7) and the horizontal rows of gates (3 levels) directly off the picture.

Exercise 4.2 (L4)

A memory stores 4-bit words with even parity. You want to compute the parity bit and also have the raw XOR chain reusable as a checker later. Show that the generator and checker are the same circuit, using data $0011$ end-to-end.

Recall Solution 4.2

Generate: $X = 0 \oplus 0 \oplus 1 \oplus 1 = 0$ , so $P = 0$ . Stored word $= 00110$ . Check (read back a clean word $00110$ ): feed all 5 bits into the same style of XOR tree, now with one extra input for $P$ : $E = 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 = 0.$ $E = 0$ → OK. ✓ The identity: the checker is literally an $(n + 1)$ -input parity computation. Notice $E = X \oplus P$ . Since we chose $P = X$ during generation, $E = X \oplus X = 0$ for any clean word — the algebra guarantees a valid word always checks clean. Answer: same XOR tree; generator uses $n$ inputs, checker uses $n + 1$ , and $E = X \oplus P = 0$ whenever untouched.

Level 5 — Mastery

Push to the edges: degenerate inputs, layered parity, limits.

Exercise 5.1 (L5)

Degenerate cases. For even parity, what is $P$ when (a) the data is all zeros ( $0000$ )? (b) the data is a single bit ( $n = 1$ , value $1$ )? (c) $n = 0$ (no data bits at all)?

Recall Solution 5.1

(a) $0000$ : count of 1s $= 0$ , which is even. $P = 0 \oplus 0 \oplus 0 \oplus 0 = 0$ . So $P = 0$ . The all-zero word $00000$ is a valid even word — parity's "resting state." ✓ (b) $n = 1$ , data $= 1$ : $X$ = XOR of one bit = the bit itself = $1$ . So $P = 1$ ; word $= 11$ (two 1s, even). A single-bit-plus-parity code just duplicates the bit for even parity. (c) $n = 0$ : XOR of no bits is the identity element $0$ (the "empty" parity). So $P = 0$ . Gate-count convention for the empty tree (clearing up " $n - 1$ "): the formula " $n - 1$ two-input XOR gates" describes a tree that combines $n$ values. When $n = 0$ or $n = 1$ there is nothing to combine, so you build zero gates — you never build a negative number of gates. The clean way to say it is: the number of 2-input gates is $max (n - 1, 0)$ , i.e. $0$ gates for $n = 0$ and for $n = 1$ . For $n = 0$ the output is the conventional empty-XOR value $0$ ; for $n = 1$ the output is just the lone bit wired straight through. So " $n - 1$ " is shorthand valid for $n \geq 1$ combining steps, floored at zero for the degenerate ends. Answer: (a) $P = 0$ ; (b) $P = 1$ ; (c) $P = 0$ .

Exercise 5.2 (L5)

2-D parity (a taste of Hamming Codes). Arrange 4 data bits in a $2 \times 2$ grid, add an even-parity bit per row ( $R_{0}, R_{1}$ ), per column ( $C_{0}, C_{1}$ ), and one corner bit $Q$ that is the parity of the whole grid (equivalently the parity of the parities). For data

$d_{0} d_{2} d_{1} d_{3} = 1101$ compute $R_{0}, R_{1}, C_{0}, C_{1}$ and the corner $Q$ , then show that a single bit flip can be located (not just detected).

Recall Solution 5.2

Row parities (even, XOR across each row): $R_{0} = d_{0} \oplus d_{1} = 1 \oplus 0 = 1$ . $R_{1} = d_{2} \oplus d_{3} = 1 \oplus 1 = 0$ . Column parities (XOR down each column): $C_{0} = d_{0} \oplus d_{2} = 1 \oplus 1 = 0$ . $C_{1} = d_{1} \oplus d_{3} = 0 \oplus 1 = 1$ . Corner parity $Q$ — the parity of the entire grid. It can be read three equivalent ways, and they must agree: $Q = d_{0} \oplus d_{1} \oplus d_{2} \oplus d_{3} = 1 \oplus 0 \oplus 1 \oplus 1 = 1$ , and also $Q = R_{0} \oplus R_{1} = 1 \oplus 0 = 1$ , and also $Q = C_{0} \oplus C_{1} = 0 \oplus 1 = 1$ . All three give $Q = 1$ . ✓ WHY $Q$ matters: it guards the parity bits themselves. If noise flips one of the row/column parity bits (not a data bit), the corner check $R_{0} \oplus R_{1}$ vs $C_{0} \oplus C_{1}$ vs $Q$ stops agreeing, telling you the fault is in the parity layer, not the data.

Now locate a single data flip. Suppose noise flips $d_{3}$ ( $1 \to 0$ ) in transit; the receiver holds the corrupted grid $1100$ but still has the original parity bits $R_{0} = 1, R_{1} = 0, C_{0} = 0, C_{1} = 1, Q = 1$ that were transmitted alongside. The receiver recomputes each row and column parity from the bits it received and compares to the parity bits it was sent:

Recomputed $R_{0}^{'} = d_{0} \oplus d_{1} = 1 \oplus 0 = 1$ . Sent $R_{0} = 1$ . Match → row 0 is clean.
Recomputed $R_{1}^{'} = d_{2} \oplus d_{3} = 1 \oplus 0 = 1$ . Sent $R_{1} = 0$ . Mismatch → row 1 fails.
Recomputed $C_{0}^{'} = d_{0} \oplus d_{2} = 1 \oplus 1 = 0$ . Sent $C_{0} = 0$ . Match → column 0 is clean.
Recomputed $C_{1}^{'} = d_{1} \oplus d_{3} = 0 \oplus 0 = 0$ . Sent $C_{1} = 1$ . Mismatch → column 1 fails.

Read off the address. Exactly one row failed (row 1) and exactly one column failed (column 1). Their intersection is the single grid cell that belongs to both the failing row and the failing column: row 1 ∩ column 1 $= d_{3}$ . That crossing cell is the flipped bit. Correct it: invert $d_{3}$ back from $0$ to $1$ , restoring the original grid. Re-checking now gives every row and column parity matching again, and the corner $Q$ agrees — confirming a single data flip (not a parity-bit flip) and that it is fully repaired. WHY this beats 1-D parity: a single parity flag told us only that an error existed. Two independent coordinates — which row broke and which column broke — form an $(x, y)$ address, and the unique cell at their crossing pins the exact bit. The corner $Q$ is the extra sanity check that the parity bits themselves were not the thing that got hit. This "intersection locates the error" idea is exactly the seed that grows into Hamming Codes. Answer: $R_{0} = 1, R_{1} = 0, C_{0} = 0, C_{1} = 1, Q = 1$ ; after flipping $d_{3}$ , row 1 and column 1 are the only failures and their intersection is cell $d_{3}$ , correctly locating (and thus allowing correction of) the flipped bit.

Figure s03 shows the $2 \times 2$ grid after $d_{3}$ has flipped: row 1 and column 1 are marked FAIL, and their dashed intersection box points at $d_{3}$ as the located error.

Exercise 5.3 (L5)

Limiting behaviour. As the number of data bits $n \to \infty$ under a fixed independent per-bit flip probability $p$ , argue qualitatively what happens to the chance that simple parity misses an error. Reason with words and pictures only — no formulas.

Recall Solution 5.3

Setup: parity misses exactly when an even, nonzero number of bits flip. Reasoning (in words): with more bits the expected number of flips grows — a longer word simply offers more places for noise to strike. Once a word typically suffers several flips, whether that total is odd or even becomes essentially a coin toss: half the time even (missed), half the time odd (caught). So as the word gets very long, the chance of an undetected error creeps up toward roughly one-half. Picture it: imagine tossing a fair coin once per flipped bit and asking "is the number of heads even?" — with many tosses that answer is near 50/50, and parity is blind to exactly the "even" half. Conclusion: single-bit parity is a short-word, low-noise tool. For long messages it degrades toward near-useless (miss chance near one-half), which is exactly why real systems move to Checksums and CRC and multi-bit Hamming Codes. Answer: the miss probability rises toward about one-half as $n \to \infty$ ; parity does not scale to long messages.

Connections

XOR and XNOR gates — every exercise is chained XOR/XNOR under the hood.
Parity Generators / Checkers — the parent concept these problems drill.
Combinational Circuits — all these circuits are memoryless.
Hamming Codes — the 2-D "locate-by-intersection" idea (Ex 5.2) generalises here.
Error Detection and Correction & Checksums and CRC — where you go when parity's limits (Ex 5.3) bite.
Adders & Multiplexers — other XOR-heavy combinational blocks worth comparing.

Active Recall

Recall Quick self-quiz

Even-parity $P$ for $1101$ ? ::: $P = 1$ (three 1s → add one → total four). Checker $E$ for received $11010$ (even system)? ::: $E = 1$ → error. Gates and delay levels to XOR 8 bits with 2-input gates? ::: 7 gates, 3 levels. How does 2-D parity locate a bad bit? ::: The failing row and failing column intersect at it. What extra bit guards the row/column parities themselves? ::: The corner parity $Q$ = parity of the whole grid. As $n \to \infty$ , the miss probability of simple parity tends to? ::: About one-half.