FD1. Final practice: adders, shifters and PLAs

This page practises the final’s datapath and control questions: how a fast adder is assembled from small blocks and where its slowest path runs, how a shifter moves a word by any amount in a few rows of multiplexers, and how a PLA turns a truth table into two planes of NOR gates, including the dynamic PLA and the self-timed clocks that keep its planes from racing. Every past-final part on these topics is here, re-solved from the papers; the keys’ answers are not copied, and where a key slips the page says so. The parts come in three families: parallel-prefix adders (FN17-8), logarithmic shifters (FN12-6) and PLAs (FN12-10a, FN19-6a–b). Each family opens with a How to approach section that gives the model and the moves once, and ends with harder added variations: longer chains, setups no past paper uses, and heavier arithmetic, as the real Fall 2026 midterm was.

Every part is worked the same way: what it asks, the idea, why this formula, the solution in steps (each gives its reason first), a check by another route, the answer, and what to remember. Try each part first; open the Hint if you are stuck. The answer key’s verdict is folded at the end of each past-paper part (FN19 has no key; its parts are compared with the unofficial proposed solutions instead).

Before you start. Everything here is taught in Chapter 16, Chapter 17 and Chapter 18, and each section below restates what it uses:

• generate and propagate, the PG cell and the sum (Chapter 16 §9); group terms and the radix-2 element with the carry-in entered as $(c_{in}, 0)$ (§12, §13); subtraction with the same adder (§3);
• the element’s order, carries as prefixes, Kogge–Stone, Brent–Kung and the whole prefix adder (Chapter 17 §1–§6); shifts and the logarithmic shifter (§7–§8);
• PLAs as NOR–NOR planes, reading one back, the dynamic PLA and its replica clocks (Chapter 18 §1–§4, §7–§9).

Conventions on this page.

• Positions. As on the Lecture 16 boards and FN17-8, the carry-in is position 0, entered as the pair $(c_{in}, 0)$(cin​,0), and the bits are 1 to $N$N, bit 1 the least significant. A span $i{:}j$ ($i \ge j$i≥j) is the group of positions $j$ to $i$i, written high index first; the boards and the key write it low index first (“0–8” is the span 8:0).
• Delays. Where a time is needed, the page uses Chapter 17’s example values: the PG cell $t_{PG} = 2\,\tau_{inv}$2τinv​, one radix-2 element $t_e = 4\,\tau_{inv}$4τinv​, the sum XOR $t_{sum} = 4\,\tau_{inv}$4τinv​, for example. Fan-out is ignored, as in the lecture’s level counts.
• Pages are the papers’ printed page labels.

Symbols

Symbol	Meaning	Unit	First appears
$a_k$ak​, $b_k$	bit $k$ of the two operands, $k = 1 \dots N$ (bit 1 the least significant)	—	approach 1
$N$	the number of bits	—	approach 1
$g_k$gk​, $p_k$	bit $k$‘s generate $a_kb_k$ and propagate $a_k\oplus b_k$	—	approach 1
$c_{in}$cin​, $c_{out}$	the adder’s carry-in and carry-out	—	approach 1
$i{:}j$	a span: positions $j$ to $i$i, high index first	—	approach 1
$G_{i:j}$Gi:j​, $P_{i:j}$	a span’s group generate and group propagate	—	approach 1
$\circ$	the radix-2 element: $(G_{hi}, P_{hi})\circ(G_{lo}, P_{lo}) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})$	—	approach 1
$C_k$	the carry out of bit $k$k, $G_{k:0}$Gk:0​; $C_0 = c_{in}$	—	approach 1
$s_k$	bit $k$ of the sum	—	approach 1
$t_{PG}$tPG​, $t_e$te​, $t_{sum}$	the delays of the PG cell, one element and the sum XOR	$\tau_{inv}$	approach 1
$\tau_{inv}$	the fan-out-of-one inverter delay (Chapter 7)	ps	approach 1
$L$L, $L'$	the depth in elements of $C_{N-1}$ (the top sum’s carry) and of $C_N$ ($c_{out}$cout​)	—	approach 1
$s'_k$	bit $k$ of the miswired adder’s sum, $p_k\oplus C_k$	—	Variation 1
$t_x$	the delay of the XOR that inverts $b$ for a subtraction	$\tau_{inv}$	Variation 2
$A_i$Ai​, $Y_i$	bit $i$ of a shifter’s input and output word, $i = 0 \dots N-1$ ($A_{N-1}$AN−1​ the MSB, the sign bit)	—	approach 2
$S_k$Sk​, $s$	the shift amount’s bit $k$ (row $k$‘s select) and the amount, $s = \sum_k 2^kS_k$	—	approach 2
$w_i$	bit $i$ of the word entering a row of the shifter ($w^{(k)}$w(k) after row $k$k)	—	approach 2
$a$a, $b$b, $c$c, $y$	FN12-6’s mux: data inputs, control and output, $y = ac + b\bar c$	—	FN12-6
$rot$rot, $arith$arith, $fill$	Variation 4’s mode lines and the common pad bit $A_7\cdot arith$	—	Variation 4
$x_i$xi​, $\bar x_i$	a PLA’s input $i$ and its complement, each on its own literal line	—	approach 3
$P_k$	a PLA’s AND-plane row $k$ (a product term); FN12-10a’s key writes p0–p2	—	approach 3
$f_k$fk​, $y_k$	a PLA’s outputs (FN12-10a’s with inverters, FN19-6’s without)	—	approach 3
$\phi$ϕ, $\phi_{AND}$ϕAND​, $\phi_{OR}$	the input clock (clk); the AND plane’s and the OR plane’s clocks (low: precharge, high: evaluate)	—	approach 3
$t_{pre}$tpre​, $t_{eval}$	the slowest AND row’s (the replica’s) precharge and evaluate times	ps	approach 3
$t_{inv}$tinv​, $t_{NAND}$	the generators’ inverter and NAND delays	ps	FN19-6b
$t_{OR}$	the OR plane’s evaluate time	ps	Variation 7

How to approach a parallel-prefix adder question

Recognize it by the words: “parallel adder”, “prefix”, “lookahead element”, “radix-two”, “Kogge–Stone”, “Brent–Kung”, “PG generator”, “sum generator”, “critical path”. The paper gives the three blocks’ equations and asks for the block diagram that joins them, and for the slowest path through it. Nothing is computed; the marks are for the wiring and the path.

The model. A sum bit needs the carry into it, and the carry into bit $k$ depends on every bit below it. The ripple adder computes those carries one after another, so the last one waits for $N$ stages. A prefix adder computes each carry as a group term of all the positions below it, $C_k = G_{k:0}$Gk:0​, and builds those groups in a tree of small identical blocks, so the last carry waits only about $\log_2 N$ blocks (Chapter 17 §2). The adder has three rows:

• PG generators at the bottom: each bit makes $g_k = a_kb_k$ (it makes a carry by itself) and $p_k = a_k\oplus b_k$ (it passes an incoming carry on) (Chapter 16 §9).
• The network in the middle: radix-2 elements, each merging two adjacent spans, the higher one on the left (Chapter 17 §1). The carry-in enters at position 0 as $(c_{in}, 0)$(cin​,0): a “group” that generates exactly when $c_{in} = 1$ and never propagates, because nothing lies below it.
• Sum generators at the top: $s_k = p_k\oplus C_{k-1}$Ck−1​, each bit’s own propagate XOR the carry into it, which is the carry out of the bit below.

The whole prefix adder at 4 bits (Chapter 17 §6, added), drawn as FN17-8’s paper draws its adder, the highest bit at the left: each sum takes its carry from the column to its right, the bit below. Original figure ↗

The three blocksboard

$$\begin{gathered} g_k = a_kb_k,\qquad p_k = a_k\oplus b_k\\ (G_{hi}, P_{hi})\circ(G_{lo}, P_{lo}) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})\\ s_k = p_k\oplus C_{k-1} \end{gathered}$$

Holds when: any prefix adder; the propagate must be the XOR (not a + b) because the sum reuses it; the element's inputs must be adjacent spans, the higher one first

Carries as prefixesadded

$$\begin{gathered} C_k = G_{k:0},\qquad c_{out} = C_N = G_{N:0}\\ s_1 = p_1\oplus c_{in},\qquad s_k = p_k\oplus G_{k-1:0} \end{gathered}$$

Holds when: the carry-in entered as (c_in, 0) at position 0, bits 1 … N; C₀ = c_in

The critical pathadded

$$t_{s_N} \approx t_{PG} + L\,t_e + t_{sum},\qquad t_{c_{out}} \approx t_{PG} + L'\,t_e$$

Holds when: L is the depth in elements of C_(N−1), L′ that of C_N; one delay per element, fan-out and wire ignored

Why these, and their conditions. The three blocks are the paper’s own equations; memorize them (FN17-8 prints them, but the next paper may not). The carries: derive in two lines. The carry out of bit $k$ is “a carry made somewhere in positions 0 to $k$ and passed by everything above it”, which is the group generate $G_{k:0}$Gk:0​; the sum of bit $k$ needs the carry into bit $k$k, which is the carry out of bit $k-1$1. The element is associative, so any bracketing of the same positions in the same order gives the same $G$G; it is not commutative, so the higher span always goes on the left (Chapter 17 §1). The critical path: derive by tracing an output back to the inputs. The top sum needs $C_{N-1}$CN−1​, not $C_N$CN​; $c_{out}$ needs $C_N$CN​, which may be a level deeper.

The moves.

1. Number the positions: $(c_{in}, 0)$ at 0, bits 1 to $N$N. Draw them as the paper does (FN17-8’s key puts bit 8 at the left).
2. Bottom row: one PG generator per bit.
3. The network: Kogge–Stone unless the paper names another. In level $m$m, every row whose span does not yet reach 0 merges with the row $2^{m-1}$ below it; a row stops once it reaches 0. For 8 bits: 8, 7, 5 and 1 elements, 21 in all, in 4 levels (Chapter 17 §3).
4. Top row: $s_1$ from $p_1$ and $c_{in}$cin​; $s_k$ from $p_k$ (straight up from its own PG generator) and the 0-to-$(k-1)$ output of the bit below it (with bit 8 at the left, the column to its right); $c_{out}$ from the 0-to-$N$ output.
5. Critical path: find the depths $L$ of $C_{N-1}$ and $L'$ of $C_N$CN​; draw PG → $L$ elements → top sum, and PG → $L'$ elements → $c_{out}$cout​; say which is longer and why.
6. Check with one addition through the drawing, for example $1 + 1$1: $C_1$ must come out 1, $s_1$ 0 and $s_2$ 1.

Decide on the way: which network (Kogge–Stone for speed and regular fan-out, Brent–Kung for fewer elements; Chapter 17 §5); whether “critical path” means the top sum or $c_{out}$ (mark both and say when each wins); which side the carry-in enters (the side of the least significant bit).

Traps. Wiring each sum to its own column’s carry, $s_k = p_k\oplus C_k$Ck​: one position too high, and the answer key of FN17-8 does it. Swapping an element’s inputs (the lower span on the left). Feeding the sums from the network’s $P$ outputs instead of each bit’s own $p_k$pk​. Forgetting the carry-in, or giving it a propagate of 1. Calling Brent–Kung “faster”: it is smaller, never faster.

FN17-8: an 8-bit parallel-prefix adder and its critical path (15 points)

You need

The PG cell and the sum (Chapter 16 §9). One bit with operands $a$a, $b$ makes $g = ab$ (it generates a carry whatever comes in) and $p = a\oplus b$ (it passes an incoming carry on). Its carry out is $g + p\,c_{in}$ and its sum is $s = p\oplus c_{in}$cin​.

The PG cell, and the carry and sum from $g$ and $p$ (Chapter 16 §9, added). Original figure ↗

Groups and the element (Chapter 16 §12, Chapter 17 §1). A run of bits acts like one big bit with a group generate $G$ and propagate $P$P. Two adjacent groups merge in one radix-2 element, $(G_{hi}, P_{hi})\circ(G_{lo}, P_{lo}) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})$Phi​Glo​, Phi​Plo​), the higher group on the left. The carry-in is the group $(c_{in}, 0)$ at position 0.

The radix-2 element as the board draws it (Chapter 17 §1; Lecture16 @ 03:32, redrawn): the higher group enters from the left. Original figure ↗

Carries are prefixes (Chapter 17 §2). The carry out of bit $k$ is $C_k = G_{k:0}$Gk:0​, so $s_k = p_k\oplus C_{k-1}$ and $c_{out} = C_8$C8​. No network of two-input elements can make $C_k$ in fewer than $\lceil\log_2(k + 1)\rceil$ levels.

The question (FN17-8, p18, in the paper’s words). Draw the block schematic diagram of an 8-bit parallel adder composed of an interconnection of three logic building blocks: a PG generator with the equations: $p = a\oplus b$b, $g = ab$ab, a radix-two lookahead element with the equations: $P = p_1p_0$p1​p0​, $G = g_1 + p_1g_0$p1​g0​, and sum generator with the equation: $s = p\oplus c$c. Draw the critical path through your network. (15 points)

FN17-8 prints no figure. This is the network its adder is built on: the 8-bit Kogge–Stone network of Lecture 16 (Chapter 17 §3; Lecture16 @ 10:41, redrawn). Each row is a position, the carry-in $(c_{in}, 0)$ at the bottom; each element takes its higher input along its row and its lower input on a diagonal from a lower row; row $k$ ends in $C_k = G_{k:0}$Gk:0​. 21 elements in 4 levels, drawn as the four columns of boxes.

Reading the question. The paper’s lookahead element is written for two bits, $G = g_1 + p_1g_0$p1​g0​, $P = p_1p_0$p1​p0​; in a tree its inputs are groups, so read $g_1, p_1$ as the higher span’s $(G, P)$ and $g_0, p_0$ as the lower span’s. The sum generator’s $c$ is the carry into the bit. “Your network” leaves the choice of network open: the lecture’s two are Kogge–Stone and Brent–Kung.

The adder and its critical path (15 points)

FN17-8, p18. Draw the block schematic diagram of an 8-bit parallel adder composed of an interconnection of three logic building blocks: a PG generator with the equations: $p = a\oplus b$b, $g = ab$ab, a radix-two lookahead element with the equations: $P = p_1p_0$p1​p0​, $G = g_1 + p_1g_0$p1​g0​, and sum generator with the equation: $s = p\oplus c$c. Draw the critical path through your network. (15 points)

The 8-bit Kogge–Stone network (Chapter 17 §3): row $k$ ends in $C_k$Ck​. Original figure ↑

Hint

Which carry does sum bit $k$ need: the one into the bit or the one out of it? Which span’s group generate is that, and which bit’s line carries it?

What it asks. A drawing, not a number: the three kinds of block wired into a working 8-bit adder, and the slowest path from an input to an output marked on it. The unknowns are the network between the PG generators and the sum generators, and where each sum takes its carry. The words that decide the method are “radix-two lookahead element”, which says the carries are built in a tree of two-input group merges, and “critical path through your network”, which asks for the deepest chain of blocks.

The idea. Every carry is a prefix: the carry out of bit $k$ is the group generate of positions 0 to $k$k, with the carry-in as position 0. So the network’s job is to make the eight spans 1:0, 2:0, …, 8:0, and a tree makes them in $\lceil\log_2 9\rceil = 4$ levels instead of 8. The sums then need only one XOR each, but each must take the carry into its bit, the span that stops one position below it. The critical path is the longest chain PG → elements → output; its length is set by the depth of the carry the output needs.

Why this formula. The adder rests on $C_k = G_{k:0}$ and $s_k = p_k\oplus C_{k-1}$Ck−1​.

• Where it comes from. A carry leaves bit $k$ if some position $j \le k$ generates (position 0 “generates” when $c_{in} = 1$1) and every bit from $j + 1$ to $k$ propagates. That is exactly the group generate of the span $k{:}0$k:0, which the element builds by merging adjacent spans (Chapter 17 §2). The sum of bit $k$ is its own $p_k$ XOR the carry coming into it, and the carry into bit $k$ is the carry out of bit $k - 1$1: $C_{k-1}$Ck−1​.
• Why the carry-in is $(c_{in}, 0)$(cin​,0). A group’s carry out is $G + P\cdot(\text{carry in from below})$(carry in from below). Below position 0 there is nothing, so its $P$ must be 0, and its $G$ is $c_{in}$ itself. Merging any span with it gives $(G + P\,c_{in},\ 0)$Pcin​, 0): Chapter 16’s group carry.
• Conditions. The element’s inputs must be adjacent spans, the higher one on the left: the element is associative but not commutative (Chapter 17 §1). The propagate must be the XOR, because the sum reuses it.
• The critical-path formula. Each block on a path adds its delay, so the top sum is ready at $t_{PG} + L\,t_e + t_{sum}$ with $L$ the depth of $C_7$C7​, and $c_{out}$ at $t_{PG} + L'\,t_e$ with $L'$ the depth of $C_8$C8​.
• The tempting alternative. Taking each sum’s carry from its own column, $s_k = p_k\oplus C_k$Ck​. It looks tidy (the column ends right under its sum block) and it is wrong: it adds the carry out of the bit back into the bit.

FN17-8

1. Positions. Because each carry is a group that reaches down to the carry-in, the network covers nine positions: $(c_{in}, 0)$ at position 0 and bits 1 to 8 above it. Following the paper’s key, draw bit 8 at the left and the carry-in entering at the right, so each bit is a vertical line, a column. Turned a quarter turn anticlockwise, the docked network is this grid: its row $k$ becomes the key’s column $k$k, and its levels, left to right, become the key’s rows of elements, bottom to top.
2. Bottom row: eight PG generators. Because the network and the sums both need each bit’s $g$ and $p$p, bit $k$‘s generator takes $a_k$ak​, $b_k$ and gives $g_k = a_kb_k$ and $p_k = a_k\oplus b_k$bk​.
3. Middle: the network. Because Kogge–Stone reaches every carry at the depth bound, use it. Level 1 merges each row with the row below: 1:0, 2:1, 3:2, 4:3, 5:4, 6:5, 7:6, 8:7 (8 elements). Level 2 merges with the row two below: 2:0, 3:0, 4:1, 5:2, 6:3, 7:4, 8:5 (7). Level 3, four below: 4:0, 5:0, 6:0, 7:0, 8:1 (5). Level 4, eight below: 8:0 (1). That is $8 + 7 + 5 + 1 = 21$ elements in 4 levels; each element’s left input comes along its own row and its lower input on a diagonal from the lower row.
4. Top row: eight sum generators. Because $s_k$ needs the carry into bit $k$k: $s_1 = p_1\oplus c_{in}$cin​, with $c_{in}$ wired straight up from the input; $s_2 = p_2\oplus G_{1:0}$G1:0​; …; $s_8 = p_8\oplus G_{7:0}$G7:0​. Each sum takes its $p_k$ on a wire straight up from its own PG generator, past the network, and its carry, in the key’s layout, from the top of the column one to its right (the bit below; in the docked network, the end of row $k - 1$1). The 0-to-8 output, $G_{8:0}$G8:0​, is $c_{out}$cout​; it feeds no sum.
5. The depths. Because each level doubles a span’s reach, $C_1$ is ready after 1 level, $C_2$ and $C_3$ after 2, $C_4$ to $C_7$ after 3 and $C_8$ after 4: each at its bound $\lceil\log_2(k + 1)\rceil$1)⌉. So $L = 3$ for the top sum’s carry $C_7$C7​, and $L' = 4$ for $C_8$C8​.
6. The critical path. Because the top sum waits for $C_7$C7​, one path runs $a_7, b_7$ → PG$_7$ → 7:6 → 7:4 → 7:0 → the $s_8$ XOR: $t_{PG} + 3t_e + t_{sum}$tsum​, $2 + 12 + 4 = 18\,\tau_{inv}$ with the example delays. The other runs $a_8, b_8$ → PG$_8$ → 8:7 → 8:5 → 8:1 → 8:0 → $c_{out}$cout​: $t_{PG} + 4t_e = 2 + 16 = 18\,\tau_{inv}$18τinv​. Mark both: the sum path is the critical one when the XOR is slower than an element ($t_{sum} > t_e$tsum​>te​), the carry-out path otherwise; with the example values they tie.

The FN17-8 answer drawn whole (new figure; the spans come from the drawing’s own taps and the adder is checked on all $2^{17}$ additions). Each sum $s_k$ takes $p_k$ from its own PG block and its carry $G_{k-1:0}$ from the column one to its right; $s_1$ takes $c_{in}$cin​. Thick: the path to the top sum, PG$_7$ → 7:6 → 7:4 → 7:0 → $s_8$s8​. Thick dashed: the path to $c_{out}$cout​, PG$_8$ → 8:7 → 8:5 → 8:1 → 8:0. Grey numbers: the levels.

The cone of $C_8 = c_{out}$ (Chapter 17 §3, added): eight elements in a balanced tree, four deep. Every bit’s PG generator is four elements from $c_{out}$cout​, so each is on a path of the same length. Original figure ↗

Check. By one addition through the drawing, $1 + 1$ with $c_{in} = 0$0: bit 1 has $(g_1, p_1) = (1, 0)$ and every other bit $(0, 0)$(0,0). The element 1:0 gives $G_{1:0} = 1 + 0\cdot0 = 1$1, so $C_1 = 1$1; every span above it meets a killing bit, so $C_2 = \dots = C_8 = 0$0. The sums: $s_1 = p_1\oplus c_{in} = 0$0, $s_2 = p_2\oplus C_1 = 1$1, the rest 0: $s = 00000010 = 2$2, as it must be. And $0 + 0$ with $c_{in} = 1$1, which tests the $c_{in}$ wire into $s_1$ that $1 + 1$ never uses: every bit kills, so $C_1 = \dots = C_8 = 0$0, $s_1 = p_1\oplus c_{in} = 1$ and the rest are 0: $s = 1$1. The model prefixAdd runs the same drawing on all $2^{17} = 131{,}072$ additions of two 8-bit words and a carry-in and gets every one right. By the bound: no two-input network can make $C_7$ (8 positions) in fewer than 3 levels or $C_8$ (9 positions) in fewer than 4, so this path cannot be shortened by a better network, only by faster blocks.

Answer: Eight PG generators ($g_k = a_kb_k$gk​=ak​bk​, $p_k = a_k\oplus b_k$bk​) feed a Kogge–Stone network of 21 radix-2 elements in 4 levels over positions 0 ($c_{in}$cin​, 0) to 8, which makes $C_k = G_{k:0}$Gk:0​; eight sum generators make $s_1 = p_1\oplus c_{in}$ and $s_k = p_k\oplus G_{k-1:0}$Gk−1:0​, and $c_{out} = G_{8:0}$G8:0​. Critical path: PG → three elements → $s_8$ ($t_{PG} + 3t_e + t_{sum}$tPG​+tsum​), or PG → four elements → $c_{out}$ ($t_{PG} + 4t_e$tPG​+4te​); 18 $\tau_{inv}$ each with the example delays. (With the board’s Brent–Kung network, 13 elements, $C_7$ is 4 levels deep and PG → four elements → $s_8$s8​, 22 $\tau_{inv}$τinv​, is the critical path.)

The adder of the answer, with both critical paths. Original figure ↑

Remember. Three rows, and one rule for the top row: each sum takes the carry from the bit below, $s_k = p_k\oplus C_{k-1}$Ck−1​, and $c_{out}$ is the full span’s output, $G_{N:0}$GN:0​. The critical path is PG, then the depth of the carry the output needs, then the XOR; the top sum needs $C_{N-1}$CN−1​, one carry short of $c_{out}$cout​.

The level at which each carry is ready (Chapter 17 §5, computed): Kogge–Stone (solid) puts $C_7$ at 3, Brent–Kung (hatched) at 4. Original figure ↗

The key’s drawing (FN17-8, solutions p18)

FN17-8’s key (solutions p18, the key’s handwriting). Its network and PG blocks are right; every sum block takes its own column’s carry, one position too high (see the key’s verdict).

The answer key differs

The key draws correct PG blocks and a correct Kogge–Stone network (21 elements over $(c_{in}, 0)$ and 8 bits, 4 levels), but wires every sum block one position too high: each $s_k$ takes its own column’s 0–$k$ output, which it labels $C_k$Ck​, the carry out of bit $k$k, instead of the column below’s 0–$(k-1)$1); and $s_1$ takes the $(c_{in}, 0)$ element’s 0–1 output instead of $c_{in}$cin​, its output even labelled “C₁”. That computes $s_k = p_k\oplus C_k$Ck​. With $a_1 = b_1 = 1$ and $c_{in} = 0$ it gives $s_1 = 0\oplus1 = 1$1, so $1 + 1 = 1$1. Run on all 131,072 additions by prefixAdd(…, 'own'), the key’s wiring is wrong on 117,950 (90.0 %); only $c_{out}$ is always right (Variation 1 finds exactly which additions survive). The fix moves each sum’s carry wire one column to the right and feeds $s_1$ from $c_{in}$cin​. Its miswiring also changes the critical path: $s_8$ would wait for $C_8$C8​, four levels, $22\,\tau_{inv}$ with the example delays.

The key’s slip in one picture (new figure): (a) the right wiring, each $s_k$ from the column one to its right; (b) the key’s, each $s_k$ from its own column (its $C_1$C1​, †). For $1 + 1$ with $c_{in} = 0$ the carries are $C_0, C_1, C_2 = 0, 1, 0$0,1,0: (a) gives $s_2s_1 = 10$10, (b) gives 01. The key’s wiring is wrong on 117,950 of the $2^{17}$ additions (Variation 1).

Harder variations: parallel-prefix adders

You need

The prefix adder (Chapter 17 §6). PG generators make $g_k = a_kb_k$ak​bk​, $p_k = a_k\oplus b_k$bk​; a network of radix-2 elements, $(G_{hi}, P_{hi})\circ(G_{lo}, P_{lo}) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})$Phi​Glo​, Phi​Plo​), makes every carry $C_k = G_{k:0}$ with $(c_{in}, 0)$ at position 0; the sums are $s_k = p_k\oplus C_{k-1}$ and $c_{out} = C_N$CN​. The top sum is ready at $t_{PG} + L\,t_e + t_{sum}$tsum​, $L$ the depth of $C_{N-1}$CN−1​; $c_{out}$ at $t_{PG} + L'\,t_e$L′te​.

The whole prefix adder at 4 bits (Chapter 17 §6, added). Original figure ↗

The two networks (Chapter 17 §3–§5). Kogge–Stone: in level $m$ each unfinished row merges with the row $2^{m-1}$ below; every carry at the bound $\lceil\log_2(k + 1)\rceil$1)⌉. Brent–Kung: power-of-two spans from position 0 first, then the others filled in from them; fewer elements, more levels for some carries.

The board’s Brent–Kung network (Chapter 17 §4; Lecture16 @ 17:54, redrawn): 13 elements, 4 levels. Original figure ↗

These three variations added are harder than FN17-8 in the ways the real midterm was: Variation 1 is a debugging chain on the key’s own miswiring, an unfamiliar question form; Variation 2 runs a subtraction through all 21 elements by hand, heavy bookkeeping against the clock; Variation 3 scales the adder to 16 bits and finds that the slowest sum need not be the top one. The budgets assume the practice finals’ pace, about 1.8 minutes a point. No key exists, so there is no key verdict.

Variation 1: debugging the miswired adder (about 20 minutes)

Variation 1: debugging the miswired adder

added The question. An 8-bit Kogge–Stone adder is built as FN17-8’s key draws it: correct PG generators and a correct network, but each sum generator fed from its own column, $s'_k = p_k\oplus C_k$Ck​. (a) Give the smallest addition it gets wrong, and what it outputs. (b) Write $s'_k$ in terms of the right sum $s_k$ and two carries. (c) For exactly which inputs is the whole output right? (d) Count them, out of all $2^{17}$ additions with a carry-in, and give the share. (e) Is $c_{out}$ ever wrong? A tester applies 100 random additions; how likely is it that every one passes?

The network (Chapter 17 §3): row $k$ ends in $C_k$Ck​; the miswired adder feeds $s_k$ from row $k$ instead of row $k - 1$1. Original figure ↑

Hint

The right sum and the miswired one use the same $p_k$pk​. What do they differ by, and when is that difference zero for every bit at once?

What it asks. A diagnosis of a known fault, in five steps: a failing case, the fault’s algebra, the exact set of inputs that hide it, their number, and what that means for testing. What is unfamiliar is the direction: instead of building the adder, the question asks what a specific wrong one does.

The idea. The miswired sum uses the carry out of its bit where it should use the carry into it. XOR is its own inverse, so the error in bit $k$ is the XOR of those two carries: the output is right in bit $k$ exactly when the carry does not change across bit $k$k. All eight bits are right only when no carry changes anywhere, so every carry equals $c_{in}$cin​, and that is a condition on each bit separately, which makes the count a simple power.

Why this formula. $s'_k = p_k\oplus C_k = (p_k\oplus C_{k-1})\oplus(C_{k-1}\oplus C_k) = s_k\oplus C_{k-1}\oplus C_k$Ck​.

• Where it comes from. XOR is associative and $C_{k-1}\oplus C_{k-1} = 0$0, so inserting it changes nothing; the first bracket is the right sum (Chapter 17 §6).
• Conditions. Only the sum wiring differs; the PG generators and the network are right, so every $C_k$ is the true carry.
• When a carry does not change across bit $k$k. $C_k = g_k + p_kC_{k-1}$pk​Ck−1​. If $C_{k-1} = 0$ the carry stays 0 unless the bit generates ($a_k = b_k = 1$ak​=1); if $C_{k-1} = 1$ it stays 1 unless the bit kills ($a_k = b_k = 0$ak​=0).
• The tempting alternative. Counting the cases where the sum happens to be right by testing a few numbers. The exhaustive count follows from the algebra in two lines and is exact.

Variation 1

1. (a) The smallest failure. Because the error appears where a carry changes across a bit, look for the smallest addition in which one does. With $c_{in} = 1$ it happens at once: in $0 + 0$ bit 1 kills, so $C_1 = 0$ while $C_0 = 1$1, and the miswired adder gives $s'_1 = p_1\oplus C_1 = 0\oplus0 = 0$ and every other bit 0: it outputs 0 for $0 + 0 + 1$1. With $c_{in} = 0$ a carry can change only where a bit generates, so the smallest case is $a = b = 1$1: $C_1 = 1$ while $C_0 = 0$0, $s'_1 = 0\oplus1 = 1$ and $s'_2 = p_2\oplus C_2 = 0\oplus0 = 0$0: it outputs $00000001 = 1$ for $1 + 1$1.
2. (b) The error term. Because $s'_k$ and $s_k$ share $p_k$pk​, $s'_k = s_k\oplus C_{k-1}\oplus C_k$Ck​: bit $k$ is wrong exactly when the carry into it differs from the carry out of it.
3. (c) When all eight bits are right. Because each bit needs $C_{k-1} = C_k$Ck​, the whole word is right only when $C_0 = C_1 = \dots = C_8$C8​: every carry equals $c_{in}$cin​. With $c_{in} = 0$ that means no bit generates (each $(a_k, b_k) \ne (1, 1)$(1,1)); with $c_{in} = 1$1, no bit kills (each $(a_k, b_k) \ne (0, 0)$(0,0)).
4. (d) The count. Because the condition is on each bit alone, each bit has 3 allowed pairs out of 4: $3^8 = 6561$ cases with $c_{in} = 0$ and $3^8$ with $c_{in} = 1$1, $2\times3^8 = 13{,}122$ right. Wrong: $131{,}072 - 13{,}122 = 117{,}950$117,950. The share right is $2\times3^8/2^{17} = (3/4)^8 = 10.0\,\%$10.0%.
5. (e) The carry-out, and a test. Because $c_{out} = C_8$ comes straight from the network, which is right, $c_{out}$ is never wrong; only the sum bits are. A random addition passes with probability $(3/4)^8 \approx 0.100$0.100, so all 100 pass with probability $0.100^{100}$0.100100, about $10^{-100}$10−100: the first test or two will catch it.

The right wiring (a) against the key’s (b) on $1 + 1$ (FN17-8’s KeyNote). Original figure ↑

Check. By the model: countWrong on the key’s wiring finds 117,950 wrong additions, and running all $2^{17}$ cases confirms that the output is right exactly when every carry equals $c_{in}$cin​, and that $c_{out}$ always agrees. At 4 bits the same formula gives $2^9 - 2\times3^4 = 512 - 162 = 350$ wrong, the count Chapter 17 §6 gives for its 4-bit adder.

Answer: (a) $0 + 0$ with $c_{in} = 1$ gives 0 instead of 1; with $c_{in} = 0$0, the smallest is $1 + 1$1, which gives 1 instead of 2. (b) $s'_k = s_k\oplus C_{k-1}\oplus C_k$Ck​. (c) Right only when every carry equals $c_{in}$cin​: no bit with $a_k = b_k = 1$ if $c_{in} = 0$0, no bit with $a_k = b_k = 0$ if $c_{in} = 1$1. (d) $2\times3^8 = 13{,}122$ right, 117,950 wrong; $(3/4)^8 = 10.0\,\%$ right. (e) $c_{out}$ is always right; 100 random tests all pass with probability about $10^{-100}$10−100.

Remember. An off-by-one carry corrupts a sum bit exactly where the carry changes: the error is $C_{k-1}\oplus C_k$Ck​. A wiring fault that only shows when a carry moves survives the additions with no carries at all, such as $0 + 0$ with $c_{in} = 0$ or any two numbers with no common 1 bits.

Variation 2: a subtraction through all 21 elements (about 25 minutes)

Variation 2: a subtraction through all 21 elements

added The question. FN17-8’s Kogge–Stone adder is made a subtractor as in Chapter 16 §3: each $b_k$ passes through an XOR with the subtract line, which inverts it, and $c_{in} = 1$1. (a) For $a = 108$ and $b = 56$56, write $a$ and $\bar b$ in binary and the nine leaf pairs $(g_k, p_k)$(gk​,pk​), $(c_{in}, 0)$ included. (b) Evaluate all 21 elements, level by level. (c) Read off the carries and the result; what does $c_{out}$ say? (d) What would FN17-8’s key wiring output for the same subtraction? (e) Repeat (c) for $56 - 108$ and interpret the result. (f) With the XOR taking $t_x = 2\,\tau_{inv}$ (for example), when is $s_8$ ready?

The adder–subtractor (Chapter 16 §3, added; a ripple adder there, bits numbered from 0): an XOR on each $b$ inverts it when SUB is 1, and SUB is also the carry-in, so $a - b = a + \bar b + 1$1. Original figure ↗

Hint

Which pairs $(g_k, p_k)$ can a bit have, and what does the element do with a killing $(0, 0)$ on its left?

What it asks. A full hand evaluation of the network, as an exam might ask to “show the values on your diagram”: 9 leaves, 21 elements, 8 sums, then an interpretation. The arithmetic is light per element but long, and one slip propagates; that is the time pressure.

The idea. Two’s complement turns subtraction into addition: $-b = \bar b + 1$1, so $a - b = a + \bar b + 1$1, and the $+1$ is the carry-in (Chapter 16 §3). Then everything is FN17-8’s adder. Each element needs only three facts: a high span that generates gives $(1, 0)$(1,0); one that kills, $(0, 0)$(0,0), gives $(0, 0)$(0,0); one that propagates, $(0, 1)$(0,1), passes the low span through unchanged.

Why this formula. $(G_{hi}, P_{hi})\circ(G_{lo}, P_{lo}) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})$Phi​Glo​, Phi​Plo​), read as three cases.

• Where it comes from. The element’s equations (Chapter 17 §1). With $(G_{hi}, P_{hi}) = (1, 0)$ the output is $(1, 0)$(1,0); with $(0, 0)$ it is $(0, 0)$(0,0); with $(0, 1)$ it is $(G_{lo}, P_{lo})$(Glo​,Plo​). $(1, 1)$ never occurs.
• Conditions. The higher span on the left; spans adjacent. The carry-in pair is $(1, 0)$ here, a generating position 0.
• What $c_{out}$ means. $a + \bar b + 1 = a - b + 2^8$28, so the carry out of bit 8 is 1 exactly when $a - b \ge 0$0: no borrow.

Variation 2

1. (a) The leaves. Because bit 1 is the least significant: $a = 108 = 01101100$01101100, $b = 56 = 00111000$00111000, $\bar b = 11000111 = 199$199. Bits 1 to 8 (from the right): $a$ gives 0, 0, 1, 1, 0, 1, 1, 0 and $\bar b$ gives 1, 1, 1, 0, 0, 0, 1, 1. So $(g, p)$ = bit 1 $(0, 1)$(0,1), bit 2 $(0, 1)$(0,1), bit 3 $(1, 0)$(1,0), bit 4 $(0, 1)$(0,1), bit 5 $(0, 0)$(0,0), bit 6 $(0, 1)$(0,1), bit 7 $(1, 0)$(1,0), bit 8 $(0, 1)$(0,1), and position 0 is $(c_{in}, 0) = (1, 0)$(1,0).
2. (b) Level 1 (each row with the row below). Because level 1 joins each row to the one below, each element sees two single positions: 1:0 = $(0,1)\circ(1,0) = (1, 0)$(1,0); 2:1 = $(0,1)\circ(0,1) = (0, 1)$(0,1); 3:2 = $(1, 0)$ (bit 3 generates); 4:3 = $(0,1)\circ(1,0) = (1, 0)$(1,0); 5:4 = $(0, 0)$ (bit 5 kills); 6:5 = $(0,1)\circ(0,0) = (0, 0)$(0,0); 7:6 = $(1, 0)$(1,0); 8:7 = $(0,1)\circ(1,0) = (1, 0)$(1,0).
3. (b) Level 2 (two rows below). Because level 2 joins each row to the span two rows below, its inputs are level 1’s outputs (or the carry-in and 1:0, passed along their rows): 2:0 = 2:1 ∘ $(c_{in}, 0)$ = $(0,1)\circ(1,0) = (1, 0)$(1,0); 3:0 = 3:2 ∘ 1:0 = $(1, 0)$(1,0); 4:1 = 4:3 ∘ 2:1 = $(1, 0)$(1,0); 5:2 = 5:4 ∘ 3:2 = $(0, 0)$(0,0); 6:3 = 6:5 ∘ 4:3 = $(0, 0)$(0,0); 7:4 = 7:6 ∘ 5:4 = $(1, 0)$(1,0); 8:5 = 8:7 ∘ 6:5 = $(1, 0)$(1,0).
4. (b) Levels 3 and 4 (four, then eight rows below). Because each level doubles the reach, level 3 finishes rows 4 to 7 and level 4 finishes row 8: 4:0 = 4:1 ∘ $(c_{in}, 0)$ = $(1, 0)$(1,0); 5:0 = 5:2 ∘ 1:0 = $(0, 0)$(0,0); 6:0 = 6:3 ∘ 2:0 = $(0, 0)$(0,0); 7:0 = 7:4 ∘ 3:0 = $(1, 0)$(1,0); 8:1 = 8:5 ∘ 4:1 = $(1, 0)$(1,0). Then 8:0 = 8:1 ∘ $(c_{in}, 0)$ = $(1, 0)$(1,0).
5. (c) Carries and sums. Because $C_k$ is the $G$ of the span $k{:}0$k:0: $C_0 \dots C_8$ = 1, 1, 1, 1, 1, 0, 0, 1, 1. The sums $s_k = p_k\oplus C_{k-1}$Ck−1​, bits 1 to 8: $1\oplus1 = 0$0, $1\oplus1 = 0$0, $0\oplus1 = 1$1, $1\oplus1 = 0$0, $0\oplus1 = 1$1, $1\oplus0 = 1$1, $0\oplus0 = 0$0, $1\oplus1 = 0$0. Read from bit 8 down: $s = 00110100 = 52$52, and $c_{out} = C_8 = 1$1: no borrow, $108 - 56 = 52 \ge 0$0.
6. (d) The key’s wiring. Because it XORs each $p_k$ with $C_k$ instead: bits 1 to 8 give $1\oplus1$1, $1\oplus1$1, $0\oplus1$1, $1\oplus1$1, $0\oplus0$0, $1\oplus0$0, $0\oplus1$1, $1\oplus1$ = 0, 0, 1, 0, 0, 1, 1, 0, so $01100100 = 100$100. The carry changes across bits 5 and 7, and exactly those bits are wrong (Variation 1).
7. (e) The other way round. Because only the inverted operand changes, the same network runs again: $56 - 108$108: $\bar b = \overline{01101100} = 10010011 = 147$147, and the same network gives carries 1, 1, 1, 0, 0, 1, 1, 0, 0, $s = 11001100 = 204$ and $c_{out} = 0$0. A carry-out of 0 is a borrow: the result is negative, $204 - 256 = -52$ in two’s complement.
8. (f) The time. Because the XOR on $b$ sits in front of the PG generators and the path is otherwise FN17-8’s: $t_x + t_{PG} + 3t_e + t_{sum} = 2 + 2 + 12 + 4 = 20\,\tau_{inv}$20τinv​.

Variation 2 through the network (computed in checks.test.ts and in the figure’s generator): $108 - 56 = 108 + 199 + 1$1, each node labelled $G, P$G,P. The carries at the top, $C_8 \dots C_0$ = 1, 1, 0, 0, 1, 1, 1, 1, 1, give $s_8 \dots s_1 = 0011\,0100 = 52$ with $c_{out} = 1$ dropped.

Check. By the integers: $108 + 199 + 1 = 308 = 256 + 52$52, so the sum is 52 with a carry out of 1; and $56 + 147 + 1 = 204 < 256$256, so no carry out. By a ripple of the carries, bit by bit: $C_0 = 1$1; bits 1 and 2 propagate it (1, 1); bit 3 generates (1); bit 4 propagates (1); bit 5 kills (0); bit 6 propagates the 0 (0); bit 7 generates (1); bit 8 propagates (1). The same nine carries as the tree.

Answer: (a) $(c_{in}, 0) = (1, 0)$(1,0); bits 1–8: $(0,1)$(0,1), $(0,1)$(0,1), $(1,0)$(1,0), $(0,1)$(0,1), $(0,0)$(0,0), $(0,1)$(0,1), $(1,0)$(1,0), $(0,1)$(0,1). (b) Level 1: 1:0 $(1,0)$(1,0), 2:1 $(0,1)$(0,1), 3:2 $(1,0)$(1,0), 4:3 $(1,0)$(1,0), 5:4 $(0,0)$(0,0), 6:5 $(0,0)$(0,0), 7:6 $(1,0)$(1,0), 8:7 $(1,0)$(1,0); level 2: 2:0, 3:0, 4:1 $(1,0)$(1,0), 5:2, 6:3 $(0,0)$(0,0), 7:4, 8:5 $(1,0)$(1,0); level 3: 4:0 $(1,0)$(1,0), 5:0, 6:0 $(0,0)$(0,0), 7:0, 8:1 $(1,0)$(1,0); level 4: 8:0 $(1,0)$(1,0). (c) Carries 1, 1, 1, 1, 1, 0, 0, 1, 1; $s = 52$52, $c_{out} = 1$ (no borrow). (d) 100. (e) $s = 204$204, $c_{out} = 0$0: a borrow, $-52$−52. (f) $20\,\tau_{inv}$20τinv​.

Remember. A subtractor is the adder with $\bar b$ and $c_{in} = 1$1, and $c_{out} = 1$ means “no borrow”. To evaluate a network fast, classify each span as generate $(1, 0)$(1,0), kill $(0, 0)$ or propagate $(0, 1)$(0,1): a generate or kill on the left decides the element alone; a propagate passes the right input through.

Variation 3: sixteen bits, and the sum that comes last (about 20 minutes)

Variation 3: sixteen bits, and the sum that comes last

added The question. A 16-bit prefix adder with a carry-in (positions 0 to 16). (a) How many elements and levels does Kogge–Stone need? (b) The strict Brent–Kung pattern over the same 17 positions has 27 elements and 6 levels, with carry depths 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5 for $C_1$ to $C_{16}$C16​. Which carries are deepest, and why is $C_{15}$ shallow? (c) With the example delays, when is each adder’s top sum $s_{16}$ ready, and its $c_{out}$cout​? (d) Which sum is the last to be ready in each adder, and when? (e) Name the critical path of the Brent–Kung adder, block by block.

Levels and elements against the number of positions (Chapter 17 §5, computed): Brent–Kung’s levels grow twice as fast. Original figure ↗

Hint

In Brent–Kung, which carries does the up-sweep make directly, and which must wait for the down-sweep?

What it asks. The same adder at twice the width, in both networks, and a comparison that goes beyond $c_{out}$cout​: which output really finishes last. The unfamiliar step is (d): FN17-8’s rule of thumb, “the top sum or $c_{out}$cout​”, fails for Brent–Kung.

The idea. Kogge–Stone puts every carry at its bound, so its deepest carries are the highest ones, and the top sum and $c_{out}$ are the last outputs. Brent–Kung’s up-sweep builds the power-of-two spans from position 0 directly: 1:0, 3:0, 7:0 and 15:0, at levels 1 to 4. The other carries are filled in afterwards, each one element after a carry it builds on, and those fill-ins can be deeper than the top ones. The critical path ends at the sum whose carry is deepest, wherever it sits.

Why this formula. $t_{s_k} \approx t_{PG} + d(C_{k-1})\,t_e + t_{sum}$tsum​, the depth of the carry each sum needs, maximized over $k$k.

• Where it comes from. The critical-path formula of FN17-8, applied to every sum instead of only the top one. FN17-8’s version assumes the deepest carry below $C_N$ is $C_{N-1}$CN−1​, which holds for Kogge–Stone and fails for Brent–Kung.
• Kogge–Stone counts. Level $m$ has $(N + 1) - 2^{m-1}$ elements over $N + 1$ positions (Chapter 17 §3); levels $\lceil\log_2(N + 1)\rceil$1)⌉.
• Conditions. One delay per element, fan-out ignored (Brent–Kung’s heavily loaded nodes would make it slower still).

Variation 3

1. (a) Kogge–Stone. Because level $m$ merges rows $2^{m-1}$ apart and 17 positions need 5 doublings ($2^4 = 16 < 17$24=17): $16 + 15 + 13 + 9 + 1 = 54$ elements, 5 levels. $C_1$ to $C_{16}$ are at their bounds: 1, 2, 2, 3, 3, 3, 3, then 4 for $C_8$ to $C_{15}$C15​, and 5 for $C_{16}$C16​.
2. (b) Brent–Kung’s deep and shallow carries. Because the up-sweep pairs and doubles from position 0, it makes $C_1$C1​, $C_3$C3​, $C_7$C7​, $C_{15}$ (spans 1:0, 3:0, 7:0, 15:0) at levels 1, 2, 3, 4, the bound. The down-sweep then makes 11:0 from 11:8 and 7:0 (level 4), 13:0 from 13:12 and 11:0 (level 5), and 14:0 from bit 14 and 13:0 (level 6). So $C_{14}$ is the deepest carry, at 6; $C_{10}$C10​, $C_{12}$C12​, $C_{13}$ and $C_{16}$ are at 5. Half the elements of Kogge–Stone (27 against 54) cost one more level.
3. (c) Top sum and carry-out. Because $s_{16}$ needs $C_{15}$C15​: Kogge–Stone $t_{PG} + 4t_e + t_{sum} = 2 + 16 + 4 = 22\,\tau_{inv}$22τinv​, Brent–Kung the same 22, since $C_{15}$ is an up-sweep carry at level 4. $c_{out} = C_{16}$ is at level 5 in both: $2 + 20 = 22\,\tau_{inv}$22τinv​.
4. (d) The last sum. Because each $s_k$ waits for $C_{k-1}$Ck−1​: in Kogge–Stone the deepest carry below $C_{16}$ is at level 4, so $s_9$ to $s_{16}$ all finish at $22\,\tau_{inv}$22τinv​. In Brent–Kung, $s_{15}$ needs $C_{14}$ at level 6: $2 + 24 + 4 = 30\,\tau_{inv}$30τinv​, eight later than its top sum.
5. (e) Brent–Kung’s critical path. Because $C_{14}$ is built on the longest chain of the network, the up-sweep to 7:0 and then three fill-ins: $a_1, b_1$ → PG$_1$ → 1:0 → 3:0 → 7:0 → 11:0 → 13:0 → 14:0 → the $s_{15}$ XOR. Each element on it takes the previous one as its lower input (3:0 = 3:2 ∘ 1:0, 7:0 = 7:4 ∘ 3:0, 11:0 = 11:8 ∘ 7:0, 13:0 = 13:12 ∘ 11:0, 14:0 = bit 14 ∘ 13:0). Block by block: PG, six elements, XOR.

Carry depths for 16 bits (computed from the two networks over 17 positions; solid Kogge–Stone, hatched Brent–Kung). Brent–Kung’s $C_{14}$ is the deepest carry (6 levels), while $C_{15}$C15​, made by the up-sweep, is ready after 4.

Check. By the bound: $C_{14}$ spans 15 positions, so any two-input network needs at least $\lceil\log_2 15\rceil = 4$ levels; Brent–Kung’s 6 is two over, which matches Chapter 17 §5’s $2\log_2 N - 2$ Brent–Kung levels against Kogge–Stone’s $\log_2 N$log2​N: they differ by $\log_2 N - 2 = 2$ at $N = 16$16. The model prefixAdd runs both networks on 3000 random 16-bit additions each and gets every one right, so the depths belong to working adders; analyse gives 54 and 27 elements, 5 and 6 levels.

Answer: (a) 54 elements, 5 levels. (b) $C_{14}$ is deepest (6 levels); $C_{15}$ is made by the up-sweep at level 4, the bound. (c) $s_{16}$ at $22\,\tau_{inv}$ and $c_{out}$ at $22\,\tau_{inv}$ in both. (d) Kogge–Stone: $s_9$ to $s_{16}$ at 22; Brent–Kung: $s_{15}$ at $30\,\tau_{inv}$30τinv​. (e) PG$_1$ → 1:0 → 3:0 → 7:0 → 11:0 → 13:0 → 14:0 → the $s_{15}$ XOR: PG, six elements, the sum XOR.

Remember. The critical path ends at the sum whose carry is deepest. In Kogge–Stone that is the top sum (or $c_{out}$cout​); in Brent–Kung it can be a sum in the middle, because the up-sweep’s power-of-two carries arrive early and the filled-in ones late.

How to approach a logarithmic shifter question

Recognize it by the words “shifter”, “shift amount”, “arithmetic right”, “logical”, “rotate”, a multiplexer block with its equation (FN12-6 prints $y = ac + b\bar c$bcˉ), and “a three-bit control signal”. The paper asks for a block-level schematic; the marks are for the rows, the wiring of each mux’s two inputs, and what fills the vacated end.

The model. A right shift by $s$ places makes output bit $i$ equal to input bit $i + s$s; the top $s$ outputs have no input bit to copy and must be filled: with 0 for a logical shift, with copies of the sign bit for an arithmetic one, with the bits that fell off the bottom for a rotate (Chapter 17 §7). Any amount from 0 to $N - 1$ is a sum of distinct powers of 2, so a shift by $s$ is a shift by 1 or not, then by 2 or not, then by 4 or not, each controlled by one bit of $s$ written in binary. Each conditional shift is one row of 2:1 multiplexers (Chapter 17 §8).

The board’s 8-bit logarithmic logical right shifter (Chapter 17 §8; Lecture16 @ 31:19, redrawn): row $S_k$ shifts by $2^k$2k; the inputs with no bit to their left take a 0 pad. Original figure ↗

The logarithmic right shifterboard

$$\begin{gathered} Y_i = A_{i+s},\qquad s = \textstyle\sum_k 2^kS_k\\ \text{row } k,\ \text{mux } i:\quad 1\text{-input} = w_{i+2^k},\quad 0\text{-input} = w_i\\ \log_2 N \text{ rows of } N \text{ muxes},\qquad 1 + 2 + \dots + \tfrac{N}{2} = N - 1 \text{ pads}\\ \text{stack height} = \log_2 N + 1 \end{gathered}$$

Holds when: N a power of 2; row k (select S_k) shifts by 2^k; the mux's selected-when-1 input takes the shifted bit; pads 0 (logical), A_(N−1) (arithmetic) or the wrapped bit (rotate)

Why these, and their conditions. $w$ is the word entering the row. The shift amounts of the rows add, because shifting by $2^j$ and then by $2^k$ is shifting by $2^j + 2^k$2k; derive the structure from that. The pad count is $\sum_k 2^k = N - 1$1: row $k$ has $2^k$ muxes whose shifted input would come from beyond the MSB. For an arithmetic shift every pad is $A_{N-1}$AN−1​, taken straight from the input: an arithmetic right shift never changes the MSB, so every row’s MSB is still $A_{N-1}$AN−1​. The stack height counts the driver plus one pass device per row, if the muxes are pass transistors (Chapter 17 §8); derive it, and break it with inverters every two or three rows, inverting the pads of the rows that carry inverted data.

The moves.

1. Read the mux equation: which input passes when the control is 1. In FN12-6, $y = ac + b\bar c$bcˉ: $a$ passes when $c = 1$1.
2. One row per select bit, $S_0$ shifting by 1, $S_1$ by 2, $S_2$ by 4 (any order works; keep the paper’s).
3. In row $k$k, mux $i$i: the control is $S_k$Sk​; the selected-when-1 input takes the bit $2^k$ to the left (index $i + 2^k$2k) of the row above; the other takes the bit straight above.
4. The pads: every 1-input whose index $i + 2^k$ passes $N - 1$1: tie it to 0, $A_{N-1}$ or the wrapped bit, as the shift kind demands.
5. Count the muxes and pads, and check one word through the rows, for example a negative number shifted by an amount with two 1 bits.

Decide on the way: the shift kind (the pads); whether the paper wants transistor detail (pass muxes, stack height, inverters) or only blocks; which input of the paper’s mux is the selected-when-1 one.

Traps. Swapping the mux inputs (then $S = 000$ shifts by 7). Padding an arithmetic shift with 0. Taking a pad from the row’s own output on the wrong side. Inserting inverters but leaving the next rows’ pads uninverted. Using a one-hot select (eight lines) where the paper says “a three-bit control signal”: that is the barrel shifter.

FN12-6: an 8-bit arithmetic right shifter from 2:1 muxes (15 points)

You need

Shifts (Chapter 17 §7). A right shift by $s$ moves every bit $s$ places toward the LSB. A logical shift fills the vacated top bits with 0; an arithmetic shift fills them with copies of the MSB (sign extension), so that a two’s-complement number is divided by $2^s$2s, rounding down: $x \gg_{\text{arith}} s = \lfloor x/2^s\rfloor$⌊x/2s⌋.

The kinds of shift (Chapter 17 §7; Lecture16 @ 22:11, redrawn): the arithmetic right shift copies the MSB into itself. Original figure ↗

The 2:1 multiplexer (Chapter 17 §8). A select picks one of two inputs. Built from pass transistors it is two NFETs (or two transmission gates) joined at the output, so a signal passing through several in a row sees them in series with its driver: the stack height.

Two’s complement (Chapter 15 §11). The MSB of an 8-bit word weighs $-128$−128: $1001\,0111 = -128 + 23 = -105$−105.

The question (FN12-6, p7, in the paper’s words). Draw the (block-level) schematic of an 8-bit arithmetic right shifter using the basic multiplexer building block shown below. The shift amount should be determined by a three-bit control signal. (15 points)

FN12-6’s building block (Final 2012, p7, redrawn): a 2:1 multiplexer with data inputs $a$ and $b$b, control $c$ and output $y = ac + b\bar c$bcˉ, so $y = a$ when $c = 1$ and $y = b$ when $c = 0$0.

The exam’s own figure (FN12-6, p7)

FN12-6, p7 (source figure).

Reading the question. “Arithmetic right” fixes the fill: copies of the sign bit $A_7$A7​. “A three-bit control signal” fixes the select: the shift amount in binary, $S_2S_1S_0$S2​S1​S0​, which is the logarithmic shifter, not the barrel shifter (whose eight selects are one-hot).

The shifter (15 points)

FN12-6, p7. Draw the (block-level) schematic of an 8-bit arithmetic right shifter using the basic multiplexer building block shown below. The shift amount should be determined by a three-bit control signal. (15 points)

FN12-6’s mux (p7): $a$ passes when $c = 1$1. Original figure ↑

Hint

Any shift amount from 0 to 7 is a sum of which three fixed shifts, and what must enter a row at the top when a bit is shifted in from beyond $A_7$A7​?

What it asks. A block diagram: an 8-bit word $A_7 \dots A_0$ in, the word shifted right arithmetically by $s = 0 \dots 7$ out, built only from the paper’s 2:1 mux, with $s$ given as three bits. The unknowns are how many muxes, how they are arranged and wired, and what feeds the inputs that have no bit to take. The decisive words are “three-bit control”, which says each control bit must act on its own, and “arithmetic”, which says what fills the top.

The idea. Write the amount in binary, $s = 4S_2 + 2S_1 + S_0$S0​. A shift by $s$ is then a shift by 1 if $S_0 = 1$1, followed by a shift by 2 if $S_1 = 1$1, followed by a shift by 4 if $S_2 = 1$1. Each of those is a row of eight muxes all controlled by one select bit: each mux passes either the bit straight above (no shift) or the bit $2^k$ places to the left (shift). Three rows, eight muxes each. The muxes near the top have no bit $2^k$ to their left; for an arithmetic shift they take the sign bit $A_7$A7​, so that the vacated places fill with copies of the sign.

Why this formula. Row $k$k, mux $i$i: $y = a\,S_k + b\,\bar S_k$ with $a = w_{i+2^k}$ (or $A_7$ if $i + 2^k > 7$7) and $b = w_i$wi​, where $w$ is the word entering the row.

• Where it comes from. The paper’s equation, $y = ac + b\bar c$bcˉ, passes $a$ when $c = 1$1. With $c = S_k$Sk​, the row shifts when its select bit is 1, so $a$ must be the shifted bit and $b$ the unshifted one. Shifts compose by adding, so three rows give every amount $4S_2 + 2S_1 + S_0$ (Chapter 17 §8).
• Why every pad is $A_7$A7​. The vacated bits of an arithmetic right shift are copies of the MSB. After any row the MSB is still $A_7$ (the row copied it into place 7 or left it there), so the pads of every row can come straight from the input $A_7$A7​; that also avoids a wire from one row’s output back to its own pad.
• Conditions. The rows are independent and in any order; the paper’s $c$ must be driven by one bit of the amount per row.
• The tempting alternatives. Padding with 0 (a logical shift: $-105$ by 6 would give 2, not $-2$−2). Swapping $a$ and $b$ (then $S = 000$ shifts by 7). One row of 8:1 multiplexers per bit (eight-input selection that the paper’s 2:1 block does not offer).

The same construction at 4 bits (Chapter 17 §8, added): every input past the MSB is wired to the sign bit $A_3$A3​, straight from the input. FN12-6 is the 8-bit version: three rows, and seven pads tied to $A_7$A7​. Original figure ↗

FN12-6

1. The select. Because the amount is three bits, write $s = 4S_2 + 2S_1 + S_0$S0​: $S_0$ controls a shift by 1, $S_1$ by 2, $S_2$ by 4.
2. Row $S_0$ (by 1). Because each output bit $i$ must become $A_{i+1}$ when $S_0 = 1$ and stay $A_i$ when $S_0 = 0$0: eight muxes, each with $c = S_0$S0​, $a = A_{i+1}$Ai+1​, $b = A_i$Ai​. Mux 7’s $a$ would be $A_8$A8​, which does not exist: tie it to $A_7$A7​. Call the row’s outputs $w^{(1)}_7 \dots w^{(1)}_0$w7(1)​…w0(1)​.
3. Row $S_1$ (by 2). Because the same logic applies two places at a time: mux $i$ has $c = S_1$S1​, $a = w^{(1)}_{i+2}$wi+2(1)​, $b = w^{(1)}_i$wi(1)​. Muxes 7 and 6 would need $w^{(1)}_9$ and $w^{(1)}_8$w8(1)​: tie both $a$ inputs to $A_7$A7​.
4. Row $S_2$ (by 4). Because the last select bit shifts four places at a time, mux $i$ has $c = S_2$S2​, $a = w^{(2)}_{i+4}$wi+4(2)​, $b = w^{(2)}_i$wi(2)​; muxes 7, 6, 5 and 4 take $A_7$A7​. The row’s outputs are $Y_7 \dots Y_0$Y7​…Y0​.
5. Count. Because there is one row per select bit and one mux per output bit: $3 \times 8 = 24$ muxes, and $1 + 2 + 4 = 7$ pad inputs, all wired to $A_7$A7​.
6. One word through it. Because a negative number with two select bits set exercises the pads of two rows: $A = 1001\,0111$ ($-105$−105), $S_2S_1S_0 = 110$ (shift by 6). Row $S_0$ = 0 passes it: $1001\,0111$10010111. Row $S_1$ = 1 shifts by 2 and pads with $A_7 = 1$1: $1110\,0101$11100101. Row $S_2$ = 1 shifts by 4 and pads with 1: $1111\,1110 = -2$−2.

The FN12-6 answer drawn (new figure; the drawn wiring is checked on all 256 words and 8 amounts): 24 of the paper’s muxes, $a$ selected when the row’s select is 1. Row $S_k$‘s mux $i$ takes $b$ from straight above and $a$ from $2^k$ columns to the left; the 7 pads past bit 7 hang on the $A_7$ rail at the left. At the right, Step 6’s word $1001\,0111$ shifted by $S = 110$ row by row.

Check. By value: $\lfloor -105/64\rfloor = \lfloor -1.64\rfloor = -2$−2, which is $1111\,1110$11111110, the output of step 6. With 0 pads the same circuit would give $0000\,0010 = 2$2, which is $151 \gg 6$ for the unsigned reading: the pads alone make it arithmetic. The model logShifter(…, true) runs the drawn shifter on all $256 \times 8$ words and amounts and matches $\lfloor x/2^s\rfloor$ every time.

Answer: A logarithmic shifter: three rows of eight muxes (24 in all). Row $k$ ($k = 0, 1, 2$k=0,1,2) is controlled by $S_k$ and shifts by $2^k$2k: mux $i$ has $c = S_k$Sk​, $a$ = the row input’s bit $i + 2^k$2k, $b$ = its bit $i$i. The seven $a$ inputs with $i + 2^k > 7$ (mux 7 in row $S_0$S0​; 7, 6 in row $S_1$S1​; 7, 6, 5, 4 in row $S_2$S2​) are tied to $A_7$A7​, the sign bit.

Remember. Shift amount in binary → one row per bit, row $k$ shifting by $2^k$2k; the mux input that passes on a 1 takes the shifted bit; the pads say which kind of shift it is: 0, the sign bit $A_{N-1}$AN−1​, or the wrapped bit.

If the muxes are pass transistors (Chapter 17 §8, added): a bit passes three in series after its driver, a stack of 4; an inverter after row $S_1$ breaks it into 3 and 2 (the rows after it then carry inverted data, and their pads must be $\bar A_7$Aˉ7​). Original figure ↗

The key’s drawing (FN12-6, p7)

FN12-6’s key (p7, the key’s handwriting), built from the paper’s 2:1 mux block.

The answer key agrees

It draws the same logarithmic shifter: three rows of eight muxes under $S_0$S0​, $S_1$S1​, $S_2$S2​, each $b$ input from straight above and each $a$ input from 1, 2 or 4 places to the left, and the seven pads on wires labelled $A_7$A7​. Only legibility differs: row $S_2$ labels three of its four pad wires $A_7$A7​; the fourth is drawn like the others, and the value is unaffected.

Harder variations: logarithmic shifters

You need

The logarithmic right shifter (Chapter 17 §8). $\log_2 N$ rows of $N$ 2:1 muxes; row $k$k, controlled by $S_k$Sk​, passes either the bit straight above or the bit $2^k$ to the left, so the rows together shift by $\sum_k 2^kS_k$∑k​2kSk​. The $N - 1$ inputs that would reach past the MSB are pads: 0 (logical), $A_{N-1}$ (arithmetic), or the bit that fell off the bottom (rotate).

The board’s 8-bit logarithmic shifter (Chapter 17 §8; Lecture16 @ 31:19, redrawn). Original figure ↗

Stack height (Chapter 17 §8). With pass-transistor muxes, a path is its driver plus one pass device per row it crosses, $\log_2 N + 1$ in all; an inverter after a row starts a new stack, inverts the data, and so inverts what the following rows’ pads must carry.

The barrel shifter (Chapter 17 §9). One NFET for every (output, shift amount) pair, $N^2$ devices, with one-hot selects.

These two variations added go beyond FN12-6 in the ways the real midterm did: Variation 4 adds a mode the paper never asks for (rotate) and asks for the extra hardware and its cost in stack height; Variation 5 scales to 32 bits and makes the reader place buffers and work out each row’s pad polarity, a chain of five dependent parts. Budgets assume about 1.8 minutes a point. No key exists.

Variation 4: one shifter, three kinds of shift (about 25 minutes)

Variation 4: one shifter, three kinds of shift

added The question. FN12-6’s 8-bit right shifter, built from the paper’s 2:1 mux, must now do a logical, an arithmetic or a rotating right shift, chosen by two mode lines: $rot$ (1 for rotate) and $arith$ (1 for arithmetic, used only when $rot = 0$0). (a) What must each pad input carry in each mode? (b) Add the fewest blocks: what goes on each pad, and how many 2:1 muxes in all? (c) Shift $A = 1001\,0110$ by $S = 011$ in all three modes, row by row. (d) Check each result by value. (e) With pass-transistor muxes and the fill made by one static gate, what is the worst stack height now, and on which path?

FN12-6’s mux (p7): $y = ac + b\bar c$bcˉ. Original figure ↑

Hint

In a rotate, which bit of the row’s input does mux $i$‘s shifted input need when $i + 2^k$ runs past 7?

What it asks. A small design extension and its cost: the pad logic for three modes, the block count, one word worked in three modes, and the effect on the stack. The unfamiliar part is the rotate: its pads come from the bottom of the same row, not from a fixed bit.

The idea. Only the pads differ between the three shifts; the 24 row muxes stay. A logical shift pads 0, an arithmetic one $A_7$A7​, and a rotate pads each row with the bits that row pushes out at the bottom: in row $k$ the mux at $i$ needs $w_{i+2^k-8}$wi+2k−8​, the input bit $(i + 2^k) \bmod 8$8. So each pad is a choice between “the wrapped bit” and “a fill bit”, and the fill bit is $arith\cdot A_7$A7​, the same for every pad. A choice between two signals is exactly the paper’s mux.

Why this formula. Pad of row $k$k, mux $i$ ($i + 2^k > 7$i+7): $y = w_{i+2^k-8}\cdot rot + fill\cdot\overline{rot}$rot, with $fill = A_7\cdot arith$arith.

• Where it comes from. A rotate right by $s$ makes $Y_i = A_{(i+s) \bmod 8}$A(i+s)mod8​; rotations compose like shifts, so each row can rotate by $2^k$ or not, wrapping the $2^k$ bits it pushes out (Chapter 17 §7). The fill is FN12-6’s $A_7$ when $arith = 1$ and 0 otherwise.
• The fill from the paper’s block. $y = ac + b\bar c$ with $a = A_7$A7​, $c = arith$arith, $b = 0$ gives $A_7\cdot arith$arith: one more mux. Made instead as one static AND gate, it restores the level, which matters for (e).
• Conditions. $arith$ is ignored when $rot = 1$1. Each bit wraps at most once in a whole rotation, because the total amount is below 8.

Variation 4

1. (a) The pads by mode. Because only the vacated places differ: logical 0, arithmetic $A_7$A7​, rotate the wrapped bit $w_{i+2^k-8}$ of the same row’s input (row $S_0$ mux 7 takes $w_0$w0​; row $S_1$ muxes 7, 6 take $w_1$w1​, $w_0$w0​; row $S_2$ muxes 7 to 4 take $w_3$ to $w_0$w0​).
2. (b) The added blocks. Because each of the 7 pads chooses between its wrapped bit and the common fill, put one paper mux on each pad: $c = rot$rot, $a = w_{i+2^k-8}$wi+2k−8​, $b = fill$fill; and one more mux makes $fill = A_7\cdot arith$ ($a = A_7$a=A7​, $b = 0$0, $c = arith$arith). In all $24 + 7 + 1 = 32$ muxes.
3. (c) Logical, $A = 1001\,0110$10010110, $S = 011$ (by 3). Because $S_0 = S_1 = 1$ and $S_2 = 0$0, rows $S_0$ and $S_1$ shift, row $S_2$ passes, and the pads are 0. Row $S_0$ (by 1, pad 0): $0100\,1011$01001011. Row $S_1$ (by 2, pads 0): $0001\,0010$00010010. Row $S_2$ = 0: $0001\,0010$00010010.
4. (c) Arithmetic (pads $A_7 = 1$1). Because only the pads change with the mode, the rows are the same with 1s entering at the top. Row $S_0$S0​: $1100\,1011$11001011. Row $S_1$S1​: $1111\,0010$11110010. Row $S_2$ = 0: $1111\,0010$11110010.
5. (c) Rotate (pads wrapped). Because each row’s pads take the bits that row pushes out at the bottom: row $S_0$S0​: the 0 leaving bit 0 enters bit 7: $0100\,1011$01001011. Row $S_1$S1​: the 1, 1 leaving bits 1 and 0 enter bits 7 and 6: $1101\,0010$11010010. Row $S_2$ = 0: $1101\,0010$11010010.
6. (e) The stack. Because a pad path now has the pad mux in it: a wrapped bit passes its driver, the pad mux and the three rows (one pass device per row, whether it shifts or not): 5. The fill path is the same length if the fill comes from a static gate (gate, pad mux, three rows); made by the paper’s pass mux instead, it would be 6. FN12-6’s shifter had 4.

Variation 4’s row $S_1$ (new figure; checked in all three modes on 256 words): each pad of the row is a pad mux with $c = rot$rot, choosing the wrapped bit ($w_1$w1​ for mux 7, $w_0$ for mux 6) or the common $fill = A_7\cdot arith$ from one AND gate.

Check. (d) By value, $A = 150$ unsigned, $-106$ signed. Logical: $150 \gg 3 = \lfloor 18.75\rfloor = 18 = 0001\,0010$00010010. Arithmetic: $\lfloor -106/8\rfloor = \lfloor -13.25\rfloor = -14 = 1111\,0010$11110010. Rotate: the three bits that fall off, 110, re-enter at the top: $110\,10010 = 1101\,0010 = 210$210. A simulation of the drawn circuit (row muxes, pad muxes and fill) matches the three shifts on all $256 \times 8$ words and amounts in each mode, and its worst path is 5 devices.

Answer: (a) Logical 0; arithmetic $A_7$A7​; rotate the bit the same row pushes out at the bottom, $w_{i+2^k-8}$wi+2k−8​. (b) One mux per pad ($c = rot$c=rot, $a$ = the wrapped bit, $b = fill$fill) and one for $fill = A_7\cdot arith$arith: 32 muxes. (c) Logical $0001\,0010$00010010, arithmetic $1111\,0010$11110010, rotate $1101\,0010$11010010. (d) 18, $-14$−14, 210. (e) 5 (driver, pad mux, three rows), against 4 for FN12-6’s shifter; 6 if the fill is a pass mux too.

Remember. The rows of a logarithmic shifter never change; the kind of shift lives entirely in the pads. Extra logic on the pads lengthens exactly the paths that use them, so make the shared fill with a restoring gate.

Variation 5: thirty-two bits, buffered (about 25 minutes)

Variation 5: thirty-two bits, buffered

added The question. A 32-bit arithmetic right logarithmic shifter, its muxes made of pass transistors. (a) How many rows, muxes and pads, and how many select bits? (b) What is a path’s stack height with no buffers? (c) Place the fewest inverters (one after every mux of a row) that keep every stack at 3 or less; which rows? Does the output come out true or inverted? (d) What must the pads of each row carry? (e) Compare the device count with a 32-bit barrel shifter’s.

Stack height in the logarithmic shifter (Chapter 17 §8, added): an inverter after a row starts a new stack and inverts the data. Original figure ↗

Hint

An inverter after a row restarts the count at 1. How many pass devices can follow a driver before the stack passes 3?

What it asks. The same structure at four times the width, then the transistor-level fixes FN12-6 leaves out: buffering, the polarity of the data after the buffers, and what that does to the sign-bit pads. The chain matters: (d) depends on (c).

The idea. 32 bits need 5 select bits, so 5 rows; a path crosses all 5, so with its driver the stack is 6. Each inverter starts a new stack, so at most two rows can follow a driver: inverters after rows $S_1$ and $S_3$ give stacks of 3, 3 and 2. Each inverter also flips the data, so rows $S_2$ and $S_3$ carry inverted bits; a pad in those rows stands for an inverted bit too, so it must be $\bar A_{31}$Aˉ31​. After the second inverter the data is true again.

Why this formula. Stack height $= 1 + (\text{rows since the last driver})$(rows since the last driver); rows $\log_2 32 = 5$5; pads $1 + 2 + 4 + 8 + 16 = 31$31.

• Where it comes from. The board’s count, “my stack height here is at least four” for 8 bits (Chapter 17 §8): the driver and one pass device per row. An inverter after a row is a new driver.
• Pads after an inversion. A row passes what it is given; if its data are inverted, a pad that must stand for the sign bit must also be inverted, as the lecture says of the 8-bit case: “I would need to also invert these zeros” (Lecture16 @ 32:12).
• Conditions. Each inverter sits after every mux of its row; the pads come from the input $A_{31}$ (or its complement).

Variation 5

1. (a) Size. Because each row handles one select bit and shifts by $2^k$2k: $\log_2 32 = 5$ rows ($S_4 \dots S_0$S4​…S0​, shifts 1, 2, 4, 8, 16) of 32 muxes: 160 muxes. Pads: row $k$ has $2^k$2k, so $1 + 2 + 4 + 8 + 16 = 31$31.
2. (b) Unbuffered. Because a bit crosses one pass device in each of the 5 rows after its driver: $5 + 1 = 6$6, far past 3.
3. (c) Buffers. Because each driver can be followed by at most two pass devices, five rows need two inverter rows (one inverter after $S_2$ would leave 4 and 3), and any two that leave no more than two pass rows per stack work. Three placements do: after $S_0$ and $S_2$ (stacks 2, 3, 3), after $S_1$ and $S_2$ (3, 2, 3), and after $S_1$ and $S_3$ (3, 3, 2). Take the last: driver + $S_0$ + $S_1$ = 3, inverter + $S_2$ + $S_3$ = 3, inverter + $S_4$ = 2. Two inversions cancel, so the output is true in all three.
4. (d) The pads. Because rows $S_0$ and $S_1$ see true data, their 3 pads are $A_{31}$A31​; rows $S_2$ and $S_3$ see the data inverted by the first inverter, so their $4 + 8 = 12$ pads are $\bar A_{31}$Aˉ31​; row $S_4$S4​, after the second inverter, sees true data again: its 16 pads are $A_{31}$A31​. For the other placements the inverted-pad rows are $S_1$ and $S_2$ (inverters after $S_0$ and $S_2$S2​) or $S_2$ alone (after $S_1$ and $S_2$S2​).
5. (e) Against the barrel shifter. Because the barrel shifter joins every output to every shift amount by one NFET: $32 \times 32 = 1024$ NFETs, plus a 5-to-32 decoder for one-hot selects. The log shifter’s 160 pass-NFET muxes use $2 \times 160 = 320$ NFETs plus the 64 inverters of two rows. The mux NFETs alone are 3.2 times fewer; with the inverters, 448 devices, under half; but more series stages.

Variation 5’s 32-bit shifter in bands (new figure; stacks from logStackHeights(5, [1, 3])): inverter rows after $S_1$ and $S_3$ cap every series stack at 3 (a driver and two pass devices). Between the two inverter rows the data is complemented, so rows $S_2$ and $S_3$ pad with $\bar A_{31}$Aˉ31​; the output is true again.

Check. By the extreme case: $A = 1000 \dots 0$ ($-2^{31}$−231) shifted by 31 must give $-1$−1, all ones. With $S = 11111$ every row shifts and pads; the simulation with inverted pads in rows $S_2$S2​, $S_3$ gives $-1$−1, and on 4000 random words and amounts it matches the arithmetic shift every time. With $A_{31}$ on every pad instead, $-1$ shifted by 4 does not come out $-1$−1: the wrong polarity in row $S_2$ puts zeros into a negative number.

Answer: (a) 5 rows, 160 muxes, 31 pads, 5 select bits. (b) 6. (c) Two inverter rows, after $S_1$ and $S_3$ (stacks 3, 3, 2), after $S_0$ and $S_2$ (2, 3, 3) or after $S_1$ and $S_2$ (3, 2, 3); output true. (d) For $S_1$S1​, $S_3$S3​: rows $S_0$S0​, $S_1$S1​, $S_4$ take $A_{31}$ (19 pads), rows $S_2$S2​, $S_3$ take $\bar A_{31}$ (12 pads); for $S_0$S0​, $S_2$S2​: rows $S_1$S1​, $S_2$ take $\bar A_{31}$Aˉ31​; for $S_1$S1​, $S_2$S2​: row $S_2$ alone. (e) Barrel 1024 NFETs; log shifter 320 NFETs in its muxes, about 3.2 times fewer.

Remember. Buffering a pass-transistor shifter is a parity bookkeeping job: count the inverters above each row, and invert that row’s pads when the count is odd. Place buffers every two rows to keep stacks at 3.

How to approach a PLA question

Recognize it by the picture: a grid of vertical literal lines ($x_i$xi​ and $\bar x_i$xˉi​, often with ground lines between them), horizontal rows with a pull-up at one end, small NFETs at some crossings, and a second grid of columns at the right; or by the words “PLA”, “AND plane”, “OR plane”, “product terms”, "$\phi_{AND}$", "$\phi_{OR}$", “replica”. The papers ask three things: read the functions off a drawn PLA (FN12-10a, FN19-6a), build one, or clock a dynamic one (FN19-6b).

The model. A PLA builds any sum of products from NOR gates only (Chapter 18 §1). Each row of the AND plane is a NOR of the literal lines its devices sit on: a device whose gate is on line $\ell$ pulls the row low when $\ell = 1$1, so the row is high only when every one of its lines is 0. By De Morgan that NOR is the AND of the complements, a product term. Each column of the OR plane is a NOR of the rows it has devices on, so with an inverter after it, it is their OR. In a static PLA the gates are pseudo-NMOS: a PFET load with its gate grounded (Chapter 18 §2). In a dynamic PLA each plane is precharged high while its clock is low and evaluates while it is high, and the OR plane must wait for the AND plane (Chapter 18 §7).

The lecture’s static PLA (Chapter 18 §3; Lecture17 @ 14:52, redrawn). FN12-10a prints it without row $P_3$P3​; FN19-6 prints it whole, dynamic, without the output inverters. Original figure ↗

Reading a NOR–NOR PLAadded

$$\begin{gathered} \text{row} = \overline{\ell_1 + \ell_2 + \dots} = \bar\ell_1\,\bar\ell_2\cdots\\ \text{column} = \overline{\text{row}_a + \text{row}_b + \dots}\\ \text{output} = \begin{cases}\text{row}_a + \text{row}_b + \dots & \text{with an inverter}\\ \overline{\text{row}_a + \text{row}_b + \dots} & \text{without}\end{cases} \end{gathered}$$

Holds when: every row and column is a NOR (pseudo-NMOS or dynamic, after evaluation); a device's gate on line ℓ pulls its row low when ℓ = 1

The dynamic PLA's clocksboard

$$t_{\phi_{AND}\ \mathrm{low}} \ge t_{pre},\qquad t(\phi_{OR}\!\uparrow) \ge t(\phi_{AND}\!\uparrow) + t_{eval}$$

Holds when: each plane precharges while its clock is low and evaluates while it is high; t_pre and t_eval are the slowest AND row's (the lecture states them in words, 40:06–41:53)

Why these, and their conditions. A device on line $x_i$ means the row needs $\bar x_i$xˉi​, and a device on $\bar x_i$ means it needs $x_i$xi​: the flip is the whole trick of reading, and it comes from the NOR (derive: NOR of lines = AND of their complements). The output inverter decides between the OR of the rows and its complement; FN19-6 draws none. The clock requirements come from the race: during precharge every row is high, so if the OR plane evaluated while a row was still falling, that row’s device would discharge its column for good (Chapter 18 §7); memorize them in words. A replica row tracks the real rows at every process, voltage and temperature corner because it is one (Chapter 18 §8–§9).

The moves.

1. Label the lines at the bottom of each vertical: true, complement and ground. Note which way each device’s gate faces.
2. Each row: list its devices’ lines, flip each literal, AND them.
3. Each column: the rows with devices in it; OR them, and complement if there is no output inverter.
4. Simplify (absorption $a + ab = a$a; $\bar a + ab = \bar a + b$b), then check two input rows by tracing them through the grid, not through the formula.
5. For a dynamic PLA: state the clock order (the AND plane evaluates first), and build the clocks from replica rows: the slowest precharge (the most capacitance on the row) for $\phi_{AND}$‘s low pulse, the slowest evaluate (one device on) for $\phi_{OR}$‘s rising edge.

Decide on the way: output inverters or not; which literal a device’s gate is on (the lines alternate $\bar x_i$xˉi​, ground, $x_i$xi​); whether “simplify” is wanted (FN12-10a’s key leaves $f_1$ unsimplified, and it equals $f_0$f0​).

Traps. Reading a device on $x_i$ as the literal $x_i$ (it is $\bar x_i$xˉi​). Forgetting that a dynamic column without an inverter gives the complement. A replica that copies a typical row instead of the slowest. Evaluating the replica for $\phi_{OR}$ with all devices on (the fastest evaluate, not the slowest).

FN12-10a: reading a static PLA (9 points)

You need

A row is a NOR (Chapter 18 §2). Each AND-plane row has a pseudo-NMOS pull-up, a PFET with its gate grounded, always on but weak, and an NFET to ground wherever the row needs a literal. Any NFET that is on pulls the row low; with all off, the PFET holds it high. So the row is the NOR of the lines its NFETs’ gates sit on.

One programmed crossing (Chapter 18 §3, added): the device’s gate sits on the literal line, its terminals on the row and the ground line beside it. Original figure ↗

NOR–NOR is AND–OR (Chapter 18 §1). By De Morgan, $\overline{\bar a + \bar b} = ab$ab: a row with devices on $\bar a$ and $\bar b$ is the product $ab$ab. A column is the NOR of its rows; an inverter after it gives their OR.

The question (FN12-10, p14, in the paper’s words). In this problem, we consider some of the combinational logic circuit styles we studied in the course. (a) In the following circuit, find f0 and f1 (Boolean equations) as a function of x0, x1, and x2. (9 points)

FN12-10a’s circuit (Final 2012, p14, redrawn). Dashed lines are ground lines; one $V_{DD}$ rail per plane stands for the paper’s pull-up bars. The paper prints the circuit unlabelled: the row names $P_0$P0​, $P_1$P1​, $P_2$ used below are the key’s (its p0, p1, p2).

The exam’s own figure (FN12-10, p14)

FN12-10a, p14 (source figure). The handwritten “PLA” and the row names p0, p1, p2 are the key’s.

Reading the figure. Under the rows, the vertical lines repeat in threes, labelled at the bottom: $\bar x_i$xˉi​, a ground line, $x_i$xi​. Each NFET’s gate is the short bar on a literal line; its two terminals join the row and the ground line next to it. At the right, each column’s NFETs are gated by the rows and join the column to the horizontal ground lines. Both columns end in inverters.

Part (a): f0 and f1 (9 points)

FN12-10a, p14. In the following circuit, find f0 and f1 (Boolean equations) as a function of x0, x1, and x2. (9 points)

FN12-10a’s PLA (p14). Original figure ↑

Hint

A row with a device on $\bar x_0$ is pulled low when $\bar x_0 = 1$1. When is that row high?

What it asks. Two Boolean functions read off a transistor drawing: what $f_0$ and $f_1$ are for each input combination, as equations. The unknowns are the three product terms the rows make and which of them each output collects. The word that decides the method is “circuit”: the answer comes from the devices, so every device’s gate line and every inverter matters.

The idea. Each row is a pseudo-NMOS NOR of the lines its devices sit on, which is the AND of the complements of those lines: a product term. Each column is a NOR of the rows that have devices in it, and the inverter under it turns that into an OR. So the PLA is a sum of products: read the rows, read which rows each column uses, write the sums, and simplify.

Why this formula. Row $= \overline{\ell_1 + \ell_2 + \dots} = \bar\ell_1\bar\ell_2\cdots$ℓˉ1​ℓˉ2​⋯; output $=$ OR of its column’s rows (inverter present).

• Where it comes from. A pseudo-NMOS row is low if any of its NFETs is on, high otherwise (Chapter 18 §2): a NOR. De Morgan’s law turns the NOR of the lines into the AND of their complements (Chapter 18 §1). The column is the same gate turned on its side, and the inverter undoes its final NOT.
• Conditions. The pull-ups are weak enough that one on NFET wins (the pseudo-NMOS ratio, which the paper assumes); the inputs and their complements are both available on the lines. Both hold in the figure.
• The tempting alternative. Reading a device’s line as the literal itself: a device on $\bar x_0$ means the row needs $x_0 = 1$1, not $\bar x_0$xˉ0​.

FN12-10a

1. Row $P_0$ (the key’s p0). Because its devices’ gates are on $\bar x_0$ and $\bar x_1$xˉ1​, it is high only when both lines are 0: $P_0 = \overline{\bar x_0 + \bar x_1} = x_0x_1$x0​x1​.
2. Row $P_1$P1​. Because its one device’s gate is on $x_2$ (its left terminal on the ground line between $\bar x_2$ and $x_2$x2​, its right one on the row): $P_1 = \bar x_2$xˉ2​.
3. Row $P_2$P2​. Because it has devices on $\bar x_0$xˉ0​, $\bar x_1$ and $\bar x_2$xˉ2​: $P_2 = \overline{\bar x_0 + \bar x_1 + \bar x_2} = x_0x_1x_2$x0​x1​x2​.
4. The columns. Because the left column has devices gated by $P_0$ and $P_1$ and an inverter after it, $f_0 = P_0 + P_1 = x_0x_1 + \bar x_2$xˉ2​. The right column has devices gated by $P_1$ and $P_2$P2​: $f_1 = P_1 + P_2 = \bar x_2 + x_0x_1x_2$x0​x1​x2​.
5. Simplify $f_1$f1​. Because $\bar x_2 + x_2\cdot(x_0x_1) = \bar x_2 + x_0x_1$ (if $x_2 = 0$ the first term is already 1; if $x_2 = 1$ the second term is $x_0x_1$x0​x1​): $f_1 = x_0x_1 + \bar x_2 = f_0$f0​. Row $P_2$ adds nothing that $P_0$ and $P_1$ do not already cover.

FN12-10a read (new figure): each row’s product at its right, each column’s sum below. The input $x_0x_1x_2 = 101$ traced: the lines at 1 ($x_0$x0​, $\bar x_1$xˉ1​, $x_2$x2​) are thick, and every device they turn on (arrows) pulls its row low, so all three rows are 0 and $f_0 = f_1 = 0$0, as $x_0x_1 + \bar x_2$ gives for 101.

Check. By two input rows traced through the grid. $x_0x_1x_2 = 111$111: every complement line is 0, so $P_0$ and $P_2$ stay high; the line $x_2$ is 1, so $P_1$ is pulled low. Both columns see a high row, fall, and invert to 1: $f_0 = f_1 = 1$1, and the formula gives $1\cdot1 + 0 = 1$1. $x_0x_1x_2 = 101$101: the line $\bar x_1$ is 1, which pulls down $P_0$ and $P_2$P2​, and $x_2 = 1$ pulls down $P_1$P1​. No row is high, both columns stay high, and the outputs are 0; the formula gives $0 + 0 = 0$0. The model evaluatePla runs all eight input rows: $f_0 = f_1 = 1$ on 000, 010, 100, 110 and 111.

Answer: $P_0 = x_0x_1$x0​x1​, $P_1 = \bar x_2$xˉ2​, $P_2 = x_0x_1x_2$x0​x1​x2​; $f_0 = x_0x_1 + \bar x_2$xˉ2​; $f_1 = \bar x_2 + x_0x_1x_2 = x_0x_1 + \bar x_2$xˉ2​, the same function as $f_0$f0​.

Remember. A device on a line means the complement of that line’s literal is in the product. Read rows, then columns, then look for the inverters; finish by simplifying, because a PLA programmed by hand need not be minimal.

A PLA to read for practice (Chapter 18 §4, added), with no output inverter: there the column gives the complement of the OR. Original figure ↗

The answer key agrees

It labels the rows p0, p1, p2 and writes $p_0 = \overline{\bar x_0 + \bar x_1} = x_0x_1$x0​x1​, $p_1 = \bar x_2$xˉ2​, $p_2 = x_0x_1x_2$x0​x1​x2​, $f_0 = x_0x_1 + \bar x_2$xˉ2​, $f_1 = \bar x_2 + x_0x_1x_2$x0​x1​x2​. All right; it leaves $f_1$ unsimplified, and it equals $f_0$ on all eight rows.

FN19-6: a dynamic PLA and its replica clocks (18 points)

You need

Precharge and evaluate (Chapter 18 §7). In a dynamic PLA each row’s pull-up is a PFET gated by $\phi_{AND}$ϕAND​, with an NFET foot gated by $\phi_{AND}$ under its devices; each column’s by $\phi_{OR}$ϕOR​. Clock low: the PFET charges the node high, the foot is off. Clock high: the node falls if any of its devices is on, and otherwise floats high. Once evaluated, every row and column holds the NOR of its inputs, as in a static PLA.

One row of a dynamic PLA feeding one column (Chapter 18 §7; Lecture17 @ 43:07, redrawn). Original figure ↗

The race and the two clocks (Chapter 18 §7). During precharge every row is high. If the OR plane evaluated while a row whose product is false was still falling, that row would discharge its column for good. So $\phi_{OR}$ may rise only after the slowest row has evaluated, and $\phi_{AND}$‘s low pulse must be long enough for the slowest row to precharge.

The two clocks (Chapter 18 §8; Lecture17 @ 43:07, redrawn): $\phi_{AND}$ low for a replica precharge, $\phi_{OR}$ rising a replica evaluate after $\phi_{AND}$ rises. Original figure ↗

The question (FN19-6, p13, in the paper’s words). Consider the following dynamic PLA structure.

FN19-6’s dynamic PLA (Final 2019, p13, redrawn; dashed lines are virtual-ground lines). $\phi_{AND}$ drives the rows’ PFETs and the AND plane’s foot (top left); $\phi_{OR}$ drives the columns’ PFETs and the OR plane’s foot (right). The columns are the outputs $y_0$y0​, $y_1$y1​: there are no output inverters.

The exam’s own figure (FN19-6, p13)

FN19-6, p13 (source figure).

Reading the figure. The literal lines are made at the bottom: each input $x_i$ runs up as the true line, and an inverter beside it makes $\bar x_i$xˉi​; the vertical lines between them are virtual-ground lines, joined at the top and grounded through the $\phi_{AND}$ foot. It is the lecture’s four-row example (Chapter 18 §3) made dynamic, and FN12-10a’s PLA with a fourth row.

Part (a): the logic function (10 points)

FN19-6a, p13. We discussed in class how it is necessary to derive the clocks $\phi_{AND}$ and $\phi_{OR}$ in such a manner that the OR plane does not being (sic) to evaluate until after the AND plane has evaluated. Furthermore, both $\phi_{AND}$ and $\phi_{OR}$ must allow for adequate precharge time. If the clocks satisfy this relationship, what is the logic function of this PLA (i. e, what are $y_0$ and $y_1$ as a function of $x_0$x0​, $x_1$x1​, and $x_2$x2​)? (10 points)

FN19-6’s PLA (p13). Original figure ↑

Hint

Once both planes have evaluated, what does each row hold, and what does a column with no inverter after it give?

What it asks. The steady logic function of the PLA, after both planes have evaluated in the right order: $y_0$ and $y_1$ as equations in $x_0$x0​, $x_1$x1​, $x_2$x2​. The question’s long preamble is a condition, not a task: “if the clocks satisfy this relationship” means the race is avoided, so the dynamic PLA computes exactly what a static PLA with the same devices would. The words that decide the answer are in the figure: no inverters after the columns.

The idea. After evaluation every row is the NOR of its device lines, a product, and every column the NOR of its rows. Without output inverters the outputs are the complements of the sums of products. So read the four products as for FN12-10a, form each column’s NOR, and simplify with De Morgan.

Why this formula. $y = \overline{P_a + P_b + \dots}$ for the rows $P$ in each column.

• Where it comes from. A dynamic node precharged high falls during evaluate if any of its devices is on, and stays high otherwise: once settled it is a NOR, like a pseudo-NMOS node (Chapter 18 §4, last line). With the clock order of the question, every row has its final value before the columns evaluate.
• Conditions. The clocks meet the two requirements (given); the inputs are stable during evaluate.
• The tempting alternative. Copying FN12-10a’s habit and writing $y_0 = P_0 + P_1$P1​: that ignores that this paper draws no inverters. The OR form would be the complement of the right answer on every row.

FN19-6a

1. The rows. Because each row is the NOR of its device lines (call them $P_0$ to $P_3$ from the top): $P_0$ has devices on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​: $x_0x_1$x0​x1​. $P_1$ has one on $x_2$x2​: $\bar x_2$xˉ2​. $P_2$ on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​, $\bar x_2$xˉ2​: $x_0x_1x_2$x0​x1​x2​. $P_3$ on $x_0$ and $\bar x_1$xˉ1​: $\bar x_0x_1$xˉ0​x1​.
2. $y_0$y0​. Because its column has devices gated by $P_0$ and $P_1$ and no inverter: $y_0 = \overline{x_0x_1 + \bar x_2} = \overline{x_0x_1}\cdot x_2 = x_2(\bar x_0 + \bar x_1)$xˉ1​).
3. $y_1$y1​. Because its column has devices gated by $P_1$P1​, $P_2$ and $P_3$P3​: $y_1 = \overline{\bar x_2 + x_0x_1x_2 + \bar x_0x_1}$xˉ2​+x0​x1​x2​+xˉ0​x1​​. The first term forces $x_2 = 1$ for $y_1$ to be 1; with $x_2 = 1$ the rest is $\overline{x_0x_1 + \bar x_0x_1} = \overline{x_1}$x1​​. So $y_1 = \bar x_1x_2$xˉ1​x2​.
4. A cross-check with FN12-10a. Because $y_0$‘s column uses the same two rows as FN12-10a’s $f_0$f0​, but without the inverter, $y_0 = \bar f_0$fˉ​0​: the two papers’ PLAs give complementary first outputs.

Check. By the truth table, traced through the grid for two rows. $x_0x_1x_2 = 001$001: $\bar x_0 = \bar x_1 = 1$ pull down $P_0$P0​, $P_2$P2​, and $P_3$ (via $\bar x_1$xˉ1​); $x_2 = 1$ pulls down $P_1$P1​. No row high: both columns stay precharged, $y_0 = y_1 = 1$1; the formulas give $1\cdot1 = 1$ and $1\cdot1 = 1$1. $x_0x_1x_2 = 111$111: $P_0$ and $P_2$ stay high, so both columns fall: $y_0 = y_1 = 0$0; the formulas give $1\cdot0 = 0$ and $0\cdot1 = 0$0. The model evaluatePla over all eight rows: $y_0 = 1$ on 001, 011, 101 and $y_1 = 1$ on 001, 101.

Answer: $y_0 = \overline{x_0x_1 + \bar x_2} = x_2(\bar x_0 + \bar x_1)$xˉ1​); $y_1 = \overline{\bar x_2 + x_0x_1x_2 + \bar x_0x_1} = \bar x_1x_2$xˉ1​x2​.

Remember. A dynamic PLA, once its clocks are right, computes what the static one computes. Look for the output inverters before writing the answer: without them each output is the complement of its column’s sum of products.

The answer key agrees

FN19 has no official key. The unofficial proposed solution reads the same four rows and, noting that there are no output inverters, gives $y_0 = \overline{P_1 + P_2}$ (its row names start at 1) $= x_2(\bar x_0 + \bar x_1)$ and $y_1 = \bar x_1x_2$xˉ1​x2​.

Part (b): a replica AND row for both clocks (8 points)

FN19-6b, p14. Design a replica AND row, two instance (sic) of which can be used in the circuits below to generate $\phi_{AND}$ and $\phi_{OR}$ to meet the timing constraints described in (a). (8 points)

FN19-6b’s clock generators (Final 2019, p14, redrawn; each box $R$ is the paper’s “replica AND row”). Upper: $\phi_{AND}$ is the NAND of $\phi$ and the inverted output of a replica row clocked by $\bar\phi$ϕˉ​. Lower: $\phi_{OR}$ is the inverted output of a replica row clocked by $\phi_{AND}$ϕAND​.

The exam’s own figure (FN19-6b, p14)

FN19-6b, p14 (source figure).

Hint

In each generator, which edge does the replica row’s delay set, and what makes a real row’s precharge or evaluate the slowest?

What it asks. A transistor-level design of one dynamic row, a “replica”, to be dropped into both boxes of the paper’s figure, so that $\phi_{AND}$‘s low pulse is long enough for the AND plane to precharge and $\phi_{OR}$ rises only after the AND plane has evaluated. The decisive words are “a replica AND row, two instance of which”: one design, used twice.

The idea. A replica is a copy of the circuit whose delay must be waited for, built and placed the same way, so that it slows down and speeds up with the real rows at every corner of process, voltage and temperature (Chapter 18 §8). In the upper generator the replica’s precharge sets how long $\phi_{AND}$ stays low; in the lower one its precharge sets when $\phi_{OR}$ falls and its evaluate sets when $\phi_{OR}$ rises. So the one row must precharge at least as slowly as the slowest real row and evaluate at least as slowly as the slowest real row.

Why this formula. The generators’ edges (Chapter 18 §9): $t_{\phi_{AND}\ \mathrm{low}} = 2t_{inv} + t_{pre}$ and $\phi_{OR}\!\uparrow = \phi_{AND}\!\uparrow + t_{eval} + t_{inv}$tinv​, where $t_{pre}$ and $t_{eval}$ are the replica’s.

• Where they come from. Upper: $\phi$ rises, the NAND falls ($\phi_{AND}\!\downarrow$ϕAND​↓); $\bar\phi$ falls one inverter later and the replica precharges; when it is high the second inverter drops the NAND’s other input and $\phi_{AND}$ rises. Lower: $\phi_{AND}$ rises, the replica evaluates, and when it has fallen the inverter raises $\phi_{OR}$ϕOR​.
• What makes a row slow. Precharge: the most capacitance on the row node, which is the most devices (the maximum literal count, 3 here: row $P_2$P2​) with their internal node charged too. Evaluate: the fewest devices on, one, discharging the row alone (Chapter 18 §9).
• Conditions. The replica is laid out like a real row, sits in the same array, and drives the load of the most heavily loaded real row (the full row wire and as many OR-plane gates as any row drives), or its delays are not the worst real row’s.
• The tempting alternative. Two different rows, all devices on for $\phi_{AND}$ and one on for $\phi_{OR}$ϕOR​, as the lecture builds them. That works, but the paper asks for one design used twice (Chapter 18 §9).

The lecture’s two dummy rows (Chapter 18 §9; Lecture17 @ 49:25, redrawn): all on for the slowest precharge, one on for the slowest evaluate. The one-row design below keeps the right-hand row’s pattern. Original figure ↗

FN19-6b

1. Start from a real row. Because the replica must track the real rows, copy one: a precharge PFET from $V_{DD}$ to the row node and an NFET foot to ground, both gated by the replica’s clock input (the signal entering the box: $\bar\phi$ in the upper generator, $\phi_{AND}$ in the lower), laid out in the same array.
2. Give it the maximum literal count. Because the slowest precharge belongs to the row with the most devices, give it three NFETs in parallel between the row node and the foot, as many as the widest product ($P_2$P2​, $x_0x_1x_2$x0​x1​x2​). Their drains load the row node like the heaviest real row.
3. Turn exactly one device on. Because the slowest evaluate is a row discharging through a single device: tie one NFET’s gate to $V_{DD}$ and the other two to ground. In the lower generator the row then evaluates as slowly as any real row can, so $\phi_{OR}$ rises only after every row has settled. In the upper generator it still precharges the node between the devices and the foot, through the one on device, so its precharge is at least as slow as the heaviest real row’s.
4. Load it like the most heavily loaded real row. Because a row’s delay depends on what it drives, and the replica must be at least as slow as every real row: two OR-plane gates here ($P_1$P1​ feeds both $y_0$ and $y_1$y1​; $P_0$P0​, $P_2$ and $P_3$ feed one each), on dummy columns, plus the full row wire, before the generator’s inverter. The replica then has the most drains (3) and the most gate load (2), so it is the slowest of the real rows on both counts.
5. Place both instances. Because the two boxes need the same behaviour: the same design in both, as dummy rows inside the PLA’s array. The upper one makes $\phi_{AND}$‘s low pulse $2t_{inv} + t_{pre}$tpre​, longer than any row’s precharge; the lower one makes $\phi_{OR}$ fall a replica precharge and an inverter ($t_{pre} + t_{inv}$tpre​+tinv​) after $\phi_{AND}$ falls and rise $t_{eval} + t_{inv}$ after it rises, after the slowest row’s evaluate.

The FN19-6b answer (new figure): one replica AND row, used in both boxes. It copies a real row with the most devices (three), turns exactly one on (gates $V_{DD}$VDD​, 0, 0) so it discharges as slowly as the slowest real row, and carries $C_{row}$Crow​, the heaviest real row’s wire and OR-plane gate load. Its clock input $u$ is $\bar\phi$ in the upper generator and $\phi_{AND}$ in the lower.

The two clocks with example delays (Chapter 18 §9, computed): $\phi_{AND}$ low 30–220 ps, $\phi_{OR}$ low 200–440 ps. Original figure ↗

Check. By the two requirements with Chapter 18’s example delays ($t_{inv} = 20$tinv​=20, $t_{NAND} = 30$30, $t_{pre} = 150$150, $t_{eval} = 200$ ps, for example): $\phi_{AND}$ is low from 30 to 220 ps, 190 ps, more than the 150 ps precharge (requirement 1, with $2t_{inv}$ to spare); $\phi_{OR}$ rises at $220 + 200 + 20 = 440$ ps, after the slowest row finishes at 420 ps (requirement 2, with $t_{inv}$ to spare). One condition is new with the single design: in the upper generator the replica must evaluate again, through its one device, while $\phi$ is low, so $\phi$‘s low phase must cover $2t_{inv} + t_{eval} = 240$ ps; at the example’s 640 ps period with a 50 % duty, the low phase is 320 ps.

Answer: One replica row, used in both boxes: a copy of a real AND row (precharge PFET and foot on the replica’s clock input), with the maximum literal count of NFETs, three, of which one has its gate tied to $V_{DD}$ and two to ground, and its output loaded like the most heavily loaded real row’s (two OR-plane gates, as $P_1$ has, plus the full row wire). It evaluates through one device (the slowest evaluate, which times $\phi_{OR}\!\uparrow$ϕOR​↑) and precharges a full row with its internal node (at least the slowest precharge, which times $\phi_{AND}$‘s low pulse).

Remember. A replica copies the worst real case for the edge it times: most capacitance for precharge, one device on for evaluate. One row with all devices present and one on serves both.

The answer key agrees

FN19 has no official key. The unofficial proposed solution designs the same kind of row: a precharge PFET on the replica’s clock, the capacitance of the worst-loaded real row (wire, diffusion and OR-plane gates), and one active device plus the foot as the evaluate path, used in both generators. It adds sizing margins for variation, which the paper does not ask for.

Harder variations: PLAs

You need

Reading and building a PLA (Chapter 18 §1–§5). Each row is a NOR of the literal lines its devices sit on, a product of the complements: a true literal $x_i$ in a product puts a device on the $\bar x_i$ line. Each column is the NOR of its rows; with an inverter it is their OR. Fewer rows means a smaller PLA: Espresso finds a small shared cover, and rows can be shared between outputs when one product is an implicant of both.

The lecture’s static PLA (Chapter 18 §3; Lecture17 @ 14:52, redrawn). Original figure ↗

The dynamic PLA’s clocks (Chapter 18 §9). With clk rising at 0: $\phi_{AND}$ falls at $t_{NAND}$ and rises at $t_{inv} + t_{pre} + t_{inv} + t_{NAND}$tNAND​; $\phi_{OR}$ falls $t_{pre} + t_{inv}$ after $\phi_{AND}$ falls and rises $t_{eval} + t_{inv}$ after $\phi_{AND}$ rises; the outputs are valid an OR-plane evaluate later, and the period must add the output latch’s setup.

These two variations added are harder than FN12-10a and FN19-6 in the ways the real midterm was: Variation 6 runs the other way, from a function to a programmed PLA, its minimum size, its device count and what the race does to it, a six-part chain; Variation 7 puts the replica clocks at a slow corner, against a fixed delay, with heavier arithmetic. Budgets assume about 1.8 minutes a point. No key exists.

Variation 6: a full adder as a PLA (about 25 minutes)

Variation 6: a full adder as a PLA

added The question. Build a full adder as a NOR–NOR PLA with output inverters: inputs $x_0 = a$a, $x_1 = b$b, $x_2 = c_{in}$cin​; outputs $c_{out}$ and $s$s. (a) Write each output as a sum of products. (b) What is the fewest rows the AND plane can have, if rows may be shared between the outputs? Justify. (c) Program the rows: on which literal lines do the devices go? (d) Count the devices of the static (pseudo-NMOS) version, output inverters included (not the input inverters that make $\bar x_i$xˉi​, as in Chapter 18 §2). (e) The PLA is made dynamic, and by mistake both planes get the same clock. Which entries of the two truth tables come out wrong? (f) With two proper clocks, how many NFETs does the replica row need?

FN12-10a’s PLA (p14), the style to build in: rows with pull-ups, devices on the literal lines, columns with inverters. Original figure ↑

Hint

Which pairs of the parity function’s 1s differ in one bit, and could a product cover two of them?

What it asks. The reverse of FN12-10a: from two functions to a programmed PLA, with a proof that it is as small as it can be, its cost in devices, and the failure the dynamic version suffers without its two clocks. What is unfamiliar is the minimality argument and the race count on a PLA no paper draws.

The idea. The carry is 1 when at least two inputs are 1; three products of two literals cover it. The sum is the parity of three bits: 1 on 001, 010, 100, 111. Any two of those differ in two bits, so no product of fewer than three literals fits inside the parity function: it needs four rows. Rows could be shared between the outputs only where a product is an implicant of both, and only 111 is; sharing it saves nothing, because the carry’s other three 1s still need three rows. So seven rows is the minimum.

Why this formula. Row devices: a true literal $x_i$ in the product puts a device on $\bar x_i$xˉi​, a complemented $\bar x_i$ on $x_i$xi​. Device count (static): one NFET per programmed crossing, one PFET load per row and per column, two devices per output inverter (Chapter 18 §2).

• Where it comes from. The row is the NOR of its device lines, which is the AND of their complements (Chapter 18 §1).
• The race with one clock. At the start of evaluate every row is still high from precharge, so every column with any device discharges, whatever the inputs; a column cannot rise again before the next precharge (Chapter 18 §7). With an output inverter every output then reads 1 in the worst case.
• Conditions. The worst case of the race: the columns discharge faster than the false rows fall.

Variation 6

1. (a) Sums of products. Because the carry is the majority and the sum the parity: $c_{out} = ab + ac_{in} + bc_{in}$bcin​; $s = a\bar b\bar c_{in} + \bar ab\bar c_{in} + \bar a\bar bc_{in} + abc_{in}$abcin​.
2. (b) The fewest rows. Because the parity’s four 1s (100, 010, 001, 111) are pairwise two bits apart, each needs its own product: 4 rows. The carry’s 1s are 011, 101, 110, 111; its three two-literal products are prime and each is the only one covering one of 011, 101, 110, so they are all needed: 3 rows. Only 111 is an implicant of both outputs; letting the carry use the parity’s 111 row would still leave 011, 101 and 110, pairwise two bits apart, needing three more rows. So 7, and the exhaustive search of the model minimumCover agrees.
3. (c) Programming. Because a true literal puts its device on the complement line: $ab$ on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​; $ac_{in}$ on $\bar x_0$xˉ0​, $\bar x_2$xˉ2​; $bc_{in}$ on $\bar x_1$xˉ1​, $\bar x_2$xˉ2​; $a\bar b\bar c_{in}$ on $\bar x_0$xˉ0​, $x_1$x1​, $x_2$x2​; $\bar ab\bar c_{in}$ on $x_0$x0​, $\bar x_1$xˉ1​, $x_2$x2​; $\bar a\bar bc_{in}$ on $x_0$x0​, $x_1$x1​, $\bar x_2$xˉ2​; $abc_{in}$ on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​, $\bar x_2$xˉ2​. The $c_{out}$ column has devices on the first three rows, the $s$ column on the last four; each column ends in an inverter.
4. (d) Devices. Because each programmed crossing is one NFET: AND plane $3\times2 + 4\times3 = 18$18, OR plane $3 + 4 = 7$7, loads $7 + 2 = 9$ PFETs, inverters $2\times2 = 4$4: 38 devices.
5. (e) One clock on both planes. Because every row is high when evaluation starts, both columns discharge on every input, and after the inverters both outputs read 1. They are wrong wherever the right value is 0: $c_{out}$ on 000, 001, 010, 100 and $s$ on 000, 011, 101, 110, 8 of the 16 entries. The 1s are right by luck.
6. (f) The replica. Because the widest product has three literals, the replica row has three NFETs (one on, in FN19-6b’s single design).

Variation 6’s full adder in FN12-10a’s style (new figure; checked on all eight input rows): three rows for $c_{out}$cout​, four for $s$s, each true literal’s device on the complement line.

Check. By the model: plaFromTable builds the seven-row PLA, plaTables gives $c_{out}$ and $s$ on all eight rows, staticPlaDevices counts 18, 7, 9 and 38, and sharedClockColumns gives 1 on both outputs for every input. By one row traced by hand: $abc_{in} = 110$ has $\bar x_0 = \bar x_1 = 0$0, so the row $ab$ (devices on $\bar x_0$xˉ0​, $\bar x_1$xˉ1​) stays high and the $c_{out}$ column falls: $c_{out} = 1$1. For $s$s: $x_2 = 0$ but $x_0 = x_1 = 1$1, so the rows $a\bar b\bar c_{in}$ (device on $x_1$x1​), $\bar ab\bar c_{in}$ (on $x_0$x0​) and $\bar a\bar bc_{in}$ (on $x_0$x0​, $x_1$x1​) are pulled low, and $abc_{in}$ is pulled low by $\bar x_2 = 1$1: $s = 0$0, and $1 + 1 + 0 = 10_2$102​.

Answer: (a) $c_{out} = ab + ac_{in} + bc_{in}$bcin​, $s = a\bar b\bar c_{in} + \bar ab\bar c_{in} + \bar a\bar bc_{in} + abc_{in}$abcin​. (b) 7 rows: the parity’s four minterms are isolated, the carry’s three primes are all essential, and the one shareable product, $abc_{in}$abcin​, saves no row. (c) As in step 3. (d) 38 devices. (e) Every output reads 1: wrong on the 8 entries where the right value is 0. (f) Three NFETs.

Remember. Parity is a PLA’s worst case: no two of its 1s are adjacent, so every minterm costs a row. To prove a cover minimal, show that each product is forced, not that you could not find a smaller one.

Variation 7: the replica clocks at a slow corner (about 25 minutes)

Variation 7: the replica clocks at a slow corner

added The question. FN19-6’s PLA is clocked by FN19-6b’s generators with the single replica row. At the typical corner, $t_{inv} = 20$20, $t_{NAND} = 30$30, the replica’s precharge $t_{pre} = 150$ and evaluate $t_{eval} = 200$200, the OR plane’s evaluate 150 and the output latch’s setup 50 ps (for example). (a) Find the four clock edges, the outputs’ valid time and the shortest period at the typical corner. (b) At a slow corner the gates (inverters, NAND, latch) are 10 % slower and every row and column 30 % slower. Recompute (a). (c) Do the two requirements still hold, and with what margins? (d) A designer replaced the lower replica by a fixed inverter chain tuned to the typical $t_{eval} + t_{inv}$tinv​; it slows like the gates. What happens at the slow corner? (e) What must clk’s high and low phases cover at the slow corner, and by how much must the period grow?

FN19-6b’s generators (p14). Original figure ↑

Hint

Which edges move with the rows, and which only with the gates? A replica moves with the rows; a fixed chain does not.

What it asks. The generators’ timing worked twice, then the point of a replica made quantitative: at a corner where rows slow more than gates, the replica keeps both requirements and a fixed delay does not. Heavy arithmetic, one chain.

The idea. Each edge is a sum of gate delays and replica delays. The replica’s terms scale with the real rows, so the requirement margins, which are made of gate delays only, stay positive at every corner. A fixed chain’s delay scales with the gates, so when the rows slow more, the OR plane starts before the slowest row has finished.

Why this formula. With clk rising at 0 (Chapter 18 §9): $\phi_{AND}\!\downarrow = t_{NAND}$tNAND​; $\phi_{AND}\!\uparrow = 2t_{inv} + t_{pre} + t_{NAND}$tNAND​; $\phi_{OR}\!\downarrow = \phi_{AND}\!\downarrow + t_{pre} + t_{inv}$tinv​; $\phi_{OR}\!\uparrow = \phi_{AND}\!\uparrow + t_{eval} + t_{inv}$tinv​; valid $= \phi_{OR}\!\uparrow + t_{OR}$+tOR​; period $\ge$ valid + setup.

• Where it comes from. Tracing each generator edge by edge (FN19-6b’s steps).
• The margins. Requirement 1: $t_{\phi_{AND}\ \mathrm{low}} - t_{pre} = 2t_{inv}$2tinv​. Requirement 2: $\phi_{OR}\!\uparrow - (\phi_{AND}\!\uparrow + t_{eval}) = t_{inv}$tinv​. Both are gate delays only, positive at every corner.
• Conditions. The replica’s $t_{pre}$ and $t_{eval}$ are the slowest real row’s at every corner (it is a real row); the delays are rounded to whole ps.

Variation 7

1. (a) Typical. $\phi_{AND}\!\downarrow = 30$30; $\phi_{AND}\!\uparrow = 20 + 150 + 20 + 30 = 220$ (low 190); $\phi_{OR}\!\downarrow = 30 + 150 + 20 = 200$200; $\phi_{OR}\!\uparrow = 220 + 200 + 20 = 440$ (low 240); valid at $440 + 150 = 590$590; period $\ge 590 + 50 = 640$ ps.
2. (b) The slow corner’s delays. Because gates are 10 % slower and rows 30 %: $t_{inv} = 22$22, $t_{NAND} = 33$33, setup 55; $t_{pre} = 195$195, $t_{eval} = 260$260, the OR plane 195 ps.
3. (b) The slow corner’s edges. $\phi_{AND}\!\downarrow = 33$33; $\phi_{AND}\!\uparrow = 22 + 195 + 22 + 33 = 272$ (low 239); $\phi_{OR}\!\downarrow = 33 + 195 + 22 = 250$250; $\phi_{OR}\!\uparrow = 272 + 260 + 22 = 554$ (low 304); valid at $554 + 195 = 749$749; period $\ge 749 + 55 = 804$ ps.
4. (c) The requirements. Because the margins are gate delays: requirement 1, $239 - 195 = 44$ ps ($2t_{inv}$2tinv​); requirement 2, the slowest row finishes at $272 + 260 = 532$ and $\phi_{OR}$ rises at 554, 22 ps later ($t_{inv}$tinv​). Both hold.
5. (d) A fixed chain. Because it was tuned to $200 + 20 = 220$ ps and slows like a gate, it gives 242 ps at the slow corner, while the slowest row needs 260: $\phi_{OR}$ rises 18 ps before the slowest row has evaluated. For those 18 ps a falling row is still high while the OR plane evaluates, and its column can discharge for good: a wrong 0 on $y_0$ or $y_1$ (no inverters), the race of Chapter 18 §7.
6. (e) clk’s phases. Because clk’s high phase must outlast $\phi_{AND}$‘s low pulse (239 ps), and its low phase must let the upper replica evaluate again through its one device, $2t_{inv} + t_{eval} = 44 + 260 = 304$ ps: at the 804 ps period with a 50 % duty both phases are 402 ps, enough. The period grows from 640 to 804 ps, 25.6 %, so the clock must slow down at that corner; the replicas stretch the clocks but cannot shorten the logic.

Variation 7’s clocks (computed with the example delays): (a) typical, (b) the slow corner with gates 10 % and rows 30 % slower; times in ps, $T$ the minimum period. Dashed: $\phi_{OR}'$ from a fixed delay tuned at nominal, which rises at $272 + 242 = 514$ ps, 18 ps before the slowest row finishes at $272 + 260 = 532$532; the replica’s $\phi_{OR}$ rises at 554.

The typical corner’s clocks (Chapter 18 §9, computed): (a)‘s numbers. Original figure ↗

Check. By the closed form for $\phi_{OR}$‘s low time, $t_{\phi_{AND}\ \mathrm{low}} + t_{eval} - t_{pre}$tpre​: typical $190 + 200 - 150 = 240$240, slow $239 + 260 - 195 = 304$304, as in steps 1 and 3. The model plaClockEdges gives the same eight numbers at each corner. Scaling sense: every term grew by 10 % or 30 %, so the period’s growth, 25.6 %, must lie between them, and it does, nearer 30 % because the rows dominate the path.

Answer: (a) $\phi_{AND}$ low 30–220 ps, $\phi_{OR}$ low 200–440 ps, valid 590 ps, period $\ge 640$ ps. (b) $\phi_{AND}$ low 33–272 ps (239), $\phi_{OR}$ low 250–554 ps (304), valid 749 ps, period $\ge 804$ ps. (c) Yes: margins 44 ps ($2t_{inv}$2tinv​) and 22 ps ($t_{inv}$tinv​). (d) The fixed chain gives 242 ps against the 260 ps the slowest row needs: requirement 2 fails by 18 ps, and a column can discharge to a wrong 0. (e) High phase $\ge 239$ ps, low phase $\ge 304$ ps; the period grows 25.6 %, to 804 ps.

Remember. A replica’s margins are made of gate delays, so they survive every corner; a fixed delay’s margin is a difference between a gate chain and a row, and it changes sign when the rows slow more than the gates.