FD1. Adders, shifters and PLAs: the exam way

This is the exam way of FD1: each part as you would write it on the paper, with what to recognize, the lines to write, the trap to watch and the answer. Every part keeps the anchor it has on FD1, so the switch at the top of the page takes you to the same part’s full solution. The methods are three cards of the playbook: parallel-prefix adders for FN17-8, logarithmic shifters for FN12-6, and PLAs for FN12-10a and FN19-6, whose replica clocks also use the clock-generation card. FD1’s seven harder variations stay on FD1 only, at the end of each family: adders, shifters and PLAs. Work them there, against the budgets their titles give.

The clock. The past finals gave 180 minutes. FN12 had 200 points, 0.9 min a point, so its 15-point shifter has about 14 minutes and its 9-point PLA about 8; FN17 and FN19 had 250, 0.72 min a point, so FN17-8’s 15 points have about 11 minutes and FN19-6’s 10 and 8 points about 7 and 6. (The past midterms gave 75 minutes for 150 points, 0.5 min a point: a final part has more time, and more steps.)

Three conventions run through every line below. The adder’s carry-in is position 0, entered as the pair $(c_{in}, 0)$ , and the bits are 1 to 8; a span $i{:}j$ is positions $j$ to $i$ , high index first. Delays in $\tau_{inv}$ are Chapter 17’s example values, $t_{PG} = 2$ , $t_e = 4$ (one radix-2 element), $t_{sum} = 4$ , with fan-out ignored. A PLA’s literal lines run $\bar x_i$ , ground, $x_i$ ; a device whose gate sits on a line pulls its row low when that line is 1. Input rows are written $x_0x_1x_2$ .

FN17-8: an 8-bit parallel-prefix 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$ , $g = ab$ , a radix-two lookahead element with the equations: $P = p_1p_0$ , $G = g_1 + p_1g_0$ , and sum generator with the equation: $s = p\oplus c$ . Draw the critical path through your network. (15 points)

A grid of nine rows: (c_in, 0) at the bottom, then g_1, p_1 up to g_8, p_8, each a horizontal wire to the right ending in C_1 to C_8. Four levels of small boxes with circles, drawn as columns. Level 1 has eight boxes labelled 1:0 to 8:7, each fed diagonally from the row below. Level 2 has seven boxes, 2:0, 3:0, 4:1, 5:2, 6:3, 7:4, 8:5, fed from two rows below. Level 3 has five, 4:0, 5:0, 6:0, 7:0, 8:1, fed from four rows below. Level 4 has one box, 8:0, fed by a long diagonal from the carry-in row. — FN17-8 prints no figure. This is the network its adder is built on: the 8-bit Kogge–Stone network (Chapter 17 §3; Lecture16 @ 10:41, redrawn). Row $k$ ends in $C_k = G_{k:0}$ ; 21 elements in 4 levels. Turned a quarter turn anticlockwise, its rows are the key’s bit columns, bit 8 at the left.

The adder and its critical path (15 points)

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?

Recognize. Parallel-prefix adders: three rows of blocks, “radix-two” means a tree of two-input merges, “critical path” means the deepest chain. About 11 minutes, all of it drawing: lay out the nine columns first, then the levels.

On the paper.

Positions: $(c_{in}, 0)$ at 0, bits 1–8; bit 8 at the left
Bottom: 8 PG blocks, $g_k = a_kb_k$ , $p_k = a_k\oplus b_k$
Network: Kogge–Stone; level $m$ merges a row with the one $2^{m-1}$ below
Levels: 1:0 … 8:7 (8); 2:0, 3:0, 4:1 … 8:5 (7); 4:0 … 7:0, 8:1 (5); 8:0 (1): 21 elements
Element: $(G_{hi}, P_{hi})\circ(G_{lo}, P_{lo}) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})$ , higher span on the left
Carries: $C_k = G_{k:0}$ ; $c_{out} = G_{8:0}$
Top: $s_1 = p_1\oplus c_{in}$ ; $s_k = p_k\oplus G_{k-1:0}$ , the carry from the column to its right
Depths: $C_7$ 3 levels ( $\lceil\log_2 8\rceil$ ), $C_8$ 4 ( $\lceil\log_2 9\rceil$ )
Path to $s_8$ : PG $_7$ → 7:6 → 7:4 → 7:0 → XOR: $t_{PG} + 3t_e + t_{sum}$
Path to $c_{out}$ : PG $_8$ → 8:7 → 8:5 → 8:1 → 8:0: $t_{PG} + 4t_e$
e.g. $2 + 12 + 4 = 18$ and $2 + 16 = 18\,\tau_{inv}$ (fan-out ignored): mark both
Check $1 + 1$ , $c_{in} = 0$ : $C_1 = 1$ , $s_1 = 0$ , $s_2 = 1$ → 2 ✓

The 8-bit prefix adder, bit 8 at the left: PG blocks along the bottom, the 21-element Kogge–Stone network with (c_in, 0) entering at the right, XOR sum blocks along the top each taking p_k from its own PG block and its carry from the column one to its right; a thick path PG 7, 7:6, 7:4, 7:0 into s_8 and a thick dashed path PG 8, 8:7, 8:5, 8:1, 8:0 to c_out. — What to draw (FD1’s adder): each sum takes its carry from the column one to its right; both critical paths marked. Original figure ↗

Watch out. Each sum takes the carry into its bit, $C_{k-1}$ , not its own column’s $C_k$ . The key wires every sum one position too high: $1 + 1$ comes out 1. The board’s Brent–Kung is smaller (13 elements), not faster: its $C_7$ is 4 levels deep, so $s_8$ comes at 22 $\tau_{inv}$ .

Answer: Eight PG generators feed a Kogge–Stone network of 21 radix-2 elements in 4 levels over $(c_{in}, 0)$ and bits 1–8, making $C_k = G_{k:0}$ ; eight sum generators make $s_1 = p_1\oplus c_{in}$ and $s_k = p_k\oplus G_{k-1:0}$ , and $c_{out} = G_{8:0}$ . Critical path: PG → three elements → $s_8$ ( $t_{PG} + 3t_e + t_{sum}$ ), or PG → four elements → $c_{out}$ ( $t_{PG} + 4t_e$ ); 18 $\tau_{inv}$ each with the example delays.

Full solution

FN12-6: an 8-bit arithmetic right shifter from 2:1 muxes (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)

A rectangle labelled MUX with inputs a and b entering from the top, a control c entering from the left, and an output y leaving at the bottom; beside it the equation y = ac + b c-bar. — FN12-6’s building block (Final 2012, p7, redrawn): a 2:1 multiplexer with $y = ac + b\bar c$ , so $y = a$ when $c = 1$ and $y = b$ when $c = 0$ .

The shifter (15 points)

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

Recognize. Logarithmic shifters: a mux block with its equation, “shift amount”, “three-bit control signal”, “arithmetic right”. About 14 minutes: the drawing is 24 boxes, so draw one row whole and repeat it.

On the paper.

$y = ac + b\bar c$ : $a$ passes when $c = 1$
$s = 4S_2 + 2S_1 + S_0$ : three rows, shifting by 1, 2, 4
Row $k$ , mux $i$ : $c = S_k$ , $a = w_{i+2^k}$ (diagonal from the left), $b = w_i$ (straight down)
Row $S_0$ : mux 7’s $a$ = $A_7$
Row $S_1$ : muxes 7, 6 take $A_7$
Row $S_2$ : muxes 7–4 take $A_7$
All pads straight from the input $A_7$ : an arithmetic right shift never changes the MSB
$3\times8 = 24$ muxes; $1 + 2 + 4 = 7$ pads
Check: $A = 1001\,0111$ ( $-105$ ), $S = 110$
$S_0 = 0$ : $1001\,0111$ ; $S_1 = 1$ : $1110\,0101$ ; $S_2 = 1$ : $1111\,1110 = -2$
$\lfloor -105/64\rfloor = \lfloor -1.64\rfloor = -2$ ✓

Three rows of eight muxes under S_0, S_1, S_2: each b input from straight above, each a input on a diagonal from 1, 2 or 4 columns to the left; a rail at the far left carries A_7 to the seven pad inputs; outputs Y_7 to Y_0. — What to draw (FD1’s shifter): three rows, the diagonals 1, 2 and 4 columns long, and the seven pads on the $A_7$ rail. Original figure ↗

Watch out. Pad with $A_7$ , not 0: with 0 pads the same word comes out $0000\,0010 = 2$ , a logical shift. Put the shifted bit on $a$ , the input that passes on a 1; swapped, $S = 000$ shifts by 7.

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

Full solution

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

FN12-10, p14. In this problem, we consider some of the combinational logic circuit styles we studied in the course.

A static PLA. Three horizontal rows, each starting at the left at a PFET whose gate is grounded. Nine vertical lines labelled at the bottom x0 bar, ground, x0, x1 bar, ground, x1, x2 bar, ground, x2. NFETs connect the rows to the ground lines: the first row has devices with gates on x0 bar and x1 bar; the second row one device with its gate on x2; the third row devices on x0 bar, x1 bar and x2 bar. On the right two vertical columns, each with a grounded-gate PFET at the top: the left column has NFETs gated by the first and second rows, the right column NFETs gated by the second and third rows, connecting to horizontal ground lines. Each column ends in an inverter, giving f0 and f1. — FN12-10a’s circuit (Final 2012, p14, redrawn). Dashed lines are ground lines. The row names $P_0$ , $P_1$ , $P_2$ are the key’s (its p0, p1, p2); the paper prints none.

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)

Hint

A row with a device on

\bar x_0

is pulled low when

\bar x_0 = 1

. When is that row high?

Recognize. PLAs, reading one: rows of devices on literal lines, columns at the right, inverters under them. About 8 minutes: rows, columns, simplify, one trace.

On the paper.

Row = NOR of its device lines = AND of their complements
$P_0$ : devices on $\bar x_0$ , $\bar x_1$ → $x_0x_1$
$P_1$ : on $x_2$ → $\bar x_2$
$P_2$ : on $\bar x_0$ , $\bar x_1$ , $\bar x_2$ → $x_0x_1x_2$
Columns + inverters: each output is the OR of its column’s rows
$f_0 = P_0 + P_1 = x_0x_1 + \bar x_2$
$f_1 = P_1 + P_2 = \bar x_2 + x_0x_1x_2$
Since $\bar a + ab = \bar a + b$ ( $a = x_2$ ): $f_1 = \bar x_2 + x_0x_1 = f_0$
Trace $x_0x_1x_2 = 101$ : $\bar x_1 = 1$ pulls $P_0$ , $P_2$ low; $x_2 = 1$ pulls $P_1$ low
No row high → both columns high → $f_0 = f_1 = 0$ ; formula $0 + 0$ ✓
$f_0 = f_1 = 1$ on $x_0x_1x_2 =$ 000, 010, 100, 110, 111

FN12-10a's PLA with each row's product at its right end, x0 x1, x2 bar, x0 x1 x2, the two sums under the columns, and the input 101 traced: the lines at 1 thick, the devices they turn on marked with arrows. — What to write on the figure (FD1’s reading): each row’s product at its right, each column’s sum below, and one input traced. Original figure ↗

Watch out. A device on a line puts the complement of that line’s literal in the product: a device on $\bar x_0$ means the row needs $x_0 = 1$ . Simplify $f_1$ before you stop; it is the same function as $f_0$ .

Answer: $P_0 = x_0x_1$ , $P_1 = \bar x_2$ , $P_2 = x_0x_1x_2$ ; $f_0 = x_0x_1 + \bar x_2$ ; $f_1 = \bar x_2 + x_0x_1x_2 = x_0x_1 + \bar x_2$ , the same function as $f_0$ .

Full solution

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

FN19-6, p13. Consider the following dynamic PLA structure.

A dynamic PLA. At the top left an NFET gated by phi AND connects ground to a horizontal line that feeds three vertical ground lines. Four horizontal rows start at PFETs gated by phi AND. Literal lines: x0 bar (from an inverter on x0), x0, x1 bar, x1, x2 bar, x2. Row 1 has NFETs on x0 bar and x1 bar; row 2 one NFET on x2; row 3 NFETs on x0 bar, x1 bar and x2 bar; row 4 NFETs on x0 and x1 bar. On the right two columns y0 and y1, each with a PFET gated by phi OR at the top; y0 has NFETs gated by rows 1 and 2, y1 by rows 2, 3 and 4, to horizontal ground lines that join a vertical line with an NFET foot gated by phi OR to ground. No output inverters. — FN19-6’s dynamic PLA (Final 2019, p13, redrawn; dashed lines are virtual-ground lines). $\phi_{AND}$ clocks the rows, $\phi_{OR}$ the columns. The columns are the outputs $y_0$ , $y_1$ : there are no output inverters.

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$ , $x_1$ , and $x_2$ )? (10 points)

Hint

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

Recognize. PLAs, reading one: the long preamble is a condition (the clocks are right), so read it as a static PLA. About 7 minutes; look for output inverters before you write anything.

On the paper.

Clocks right → each row and column settles to its NOR, as in a static PLA
$P_0$ : $\bar x_0$ , $\bar x_1$ → $x_0x_1$ ; $P_1$ : $x_2$ → $\bar x_2$
$P_2$ : $\bar x_0$ , $\bar x_1$ , $\bar x_2$ → $x_0x_1x_2$ ; $P_3$ : $x_0$ , $\bar x_1$ → $\bar x_0x_1$
No output inverters: $y = \overline{\text{OR of the column's rows}}$
$y_0 = \overline{P_0 + P_1} = \overline{x_0x_1}\cdot x_2 = x_2(\bar x_0 + \bar x_1)$
$y_1 = \overline{P_1 + P_2 + P_3}$ : needs $x_2 = 1$ ; then $\overline{x_0x_1 + \bar x_0x_1} = \bar x_1$
$y_1 = \bar x_1x_2$
Trace $x_0x_1x_2 = 111$ : $P_0$ , $P_2$ stay high → both columns fall → $y_0 = y_1 = 0$ ✓
Trace $x_0x_1x_2 = 001$ : every row pulled low → both stay precharged → $y_0 = y_1 = 1$ ✓

Watch out. This paper draws no output inverters: $y_0 = P_0 + P_1$ , the FN12-10a habit, is the complement of the right answer on every one of the 8 input rows. A device on $x_0$ (row $P_3$ ) means $\bar x_0$ in the product.

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

Full solution

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)

Two circuits. Upper: phi goes straight to one input of a NAND gate, and also through an inverter, a box labelled replica AND row and a second inverter to the NAND's other input; the NAND's output is phi AND. Lower: phi AND goes through a box labelled replica AND row and an inverter to phi OR. — 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}$ .

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?

Recognize. PLAs, clocking a dynamic one, with the clock-generation card’s replica delay: “replica AND row, two instance of which” means one design used twice. About 6 minutes: a transistor sketch and two edge equations.

On the paper.

Upper box (clocked by $\bar\phi$ ): its precharge sets how long $\phi_{AND}$ stays low
Lower box (clocked by $\phi_{AND}$ ): its evaluate sets $\phi_{OR}\!\uparrow$
Copy a real row: precharge PFET and NFET foot, both on the box’s clock input $u$
Slowest precharge = most capacitance: 3 NFETs, the most on any row ( $P_2$ )
Slowest evaluate = one device on: gates $V_{DD}$ , 0, 0
Load like the most loaded row: 2 OR-plane gates ( $P_1$ feeds $y_0$ and $y_1$ ) + the full row wire
Same layout, same array: it tracks the real rows at every corner
$\phi_{AND}$ low $= 2t_{inv} + t_{pre}$ ; $\phi_{OR}\!\uparrow = \phi_{AND}\!\uparrow + t_{eval} + t_{inv}$
e.g. Chapter 18’s example: $t_{inv} = 20$ , $t_{NAND} = 30$ , $t_{pre} = 150$ , $t_{eval} = 200$ ps
$\phi_{AND}$ low 30–220 ps: $190 > 150$ ✓
$\phi_{OR}\!\uparrow$ at $220 + 200 + 20 = 440$ ps, after the slowest row ends at 420 ✓

One dynamic row at transistor level: a PFET gated u from V_DD to the row node R; three NFETs in parallel from R to an internal node, gates V_DD, 0 and 0; an NFET foot gated u to ground; a capacitor C_row at R; beside it the two boxes R, inputs phi bar and phi AND. — What to draw (FD1’s replica row): three devices, one on, the foot and the precharge PFET on $u$ , and $C_{row}$ . Original figure ↗

Watch out. All devices on is the fastest evaluate: $\phi_{OR}$ would rise before the slowest real row has fallen. The lecture’s two different dummy rows work, but the paper asks for one design used twice. A typical row’s load is not enough: copy the worst.

Answer: One replica row, used in both boxes: a copy of a real AND row (precharge PFET and foot on its clock input) with three NFETs, the widest product, one gated by $V_{DD}$ and two by ground, loaded like the heaviest real row (two OR-plane gates, as $P_1$ , plus the full row wire). One device on gives the slowest evaluate, which times $\phi_{OR}\!\uparrow$ ; a full row gives at least the slowest precharge, which times $\phi_{AND}$ ‘s low pulse.

Full solution