16. Adders: the full adder, the carry chain and lookahead

Lecture 15 opens the part of the course about datapaths: the blocks that do the same operation on every bit of a word. The first and most important is the adder. The lecture starts from a single bit, the full adder, whose two outputs turn out to be two famous logic functions. Chaining full adders gives the ripple-carry adder, and its delay is set by the carry rippling from the bottom bit to the top. The lecture then builds the full adder from transistors and uses two of its properties to make the carry chain fast. One is self-duality, which makes every pull-up network a mirror of its pull-down; the other is the late arrival of the carry. After a short look at how a datapath is laid out, it turns to parallel adders, which spend hardware to compute the carries without waiting for the ripple. Each one starts from the same rewriting of the carry into generate and propagate: carry bypass, carry select and, the way adders are really built, carry lookahead, ending at a radix-4 lookahead tree. The next lecture continues with radix-2 trees (Chapter 17).

After this chapter you can:

1. write a full adder’s two outputs as the majority and the odd parity of its inputs, and check them against the truth table;
2. find the critical path of a ripple-carry adder and count its stages;
3. turn an adder into a subtractor;
4. say what a self-dual function is and why it makes a gate’s pull-up and pull-down identical;
5. draw the mirror adder’s carry and sum stages, place $c_{in}$ correctly, and compute their logical efforts;
6. remove the carry chain’s inverters by alternating polarity, and compute what it saves and when;
7. lay out a datapath as a bit stack with a uniform bit pitch;
8. define generate and propagate, and say why the sum needs $p = a\oplus b$b;
9. trace the critical paths of carry-bypass, carry-select and lookahead adders and compare them;
10. unroll the carry recursion into group generate and propagate, combine two groups, and build a radix-4 lookahead tree.

Boxes and equations marked board were written in the lecture. Parts marked added are explanations, arguments or examples this guide adds; every number in them is recomputed in the page’s test.

Before you start. Three things from earlier chapters run through this one. Complementary static CMOS (Chapter 7, §4): a gate’s NFET pull-down network conducts when the output should be 0, and its PFET pull-up is the dual network, series and parallel exchanged. The course’s delay model (Chapter 8, §1): a stage’s delay is its gain $g\cdot h$ in units of $\tau_{inv}$τinv​, where $g$ is its logical effort and $h$ its load over its input capacitance; drain capacitance is ignored. Binary numbers (Chapter 15, §11): bit 0 is the least significant, and two’s complement negates by inverting every bit and adding 1. One note on the recording: Lecture 15 was taped in two takes. At 21:44 the board is suddenly clean, because the second half was re-recorded; nothing is lost between them.

Symbols

Symbol	Meaning	Unit	First appears
$a$a, $b$b; $a_i$ai​, $b_i$	the two operand bits; bit $i$ of each operand (bit 0 the least significant, drawn at the right)	—	§1, §2
$c_{in}$cin​, $c_{out}$	a full adder’s carry in and carry out	—	§1
$s$s, $s_i$	a full adder’s sum bit; bit $i$ of the sum	—	§1, §2
$\bar x$xˉ, $\overline{c_{out}}$	the complement of $x$ (the board’s overbar)	—	§1
$\oplus$	exclusive OR (XOR)	—	§1
$c_i$	the carry into bit $i$i: $c_0 = c_{in}$cin​, and bit $i$‘s carry out is $c_{i+1}$	—	§2, §12
$N$	the number of bits in the adder	—	§2
$t_c$tc​, $t_{sum}$	the delay of one carry stage and of one sum stage added	$\tau_{inv}$	§2
SUB	the subtract control bit added	—	§3
$g$ (no bit index)	logical effort, Chapter 7’s: an input’s capacitance over that of an inverter of the same drive. Written with a word subscript where it could be confused with a generate: $g_{c_{in}}$gcin​​, $g_a$	—	§5
$h$	electrical effort: a stage’s load over its input capacitance	—	§5
$\tau_{inv}$	the fan-out-of-one (FO1) inverter delay, the unit of the gains	ps	§5
units	gate width in multiples of the reference inverter’s NFET (inverter: NFET 1, PFET 2, input 3)	—	§5
$x$	the size of an inverter in the carry chain, in multiples of the reference inverter added	—	§7
$s_{in}$	the input capacitance the next bit’s sum stage puts on the carry wire added	units	§7
$g_i$gi​, $p_i$	generate $a_ib_i$ and propagate $a_i\oplus b_i$ of bit $i$ (always with a bit index, or as "$g = ab$" in §9)	—	§9
$M$	the number of bits in a group (bypass) or bin (select) added	—	§10
$P$	a group’s propagate: the AND of its bits’ $p_i$	—	§10
$t_{mux}$tmux​, $t_{PG}$	the delay of a 2:1 multiplexer and of a PG cell added	$\tau_{inv}$	§10
$G$G, $P$P; $G_{3:0}$G3:0​, $P_{3:0}$	group generate and group propagate (the board’s braces); the subscript names the bits, high index first added	—	§12
LA	a lookahead unit (radix 4: it takes four bits or four groups)	—	§13
$t_{LA}$	the delay through one lookahead unit added	$\tau_{inv}$	§13
$L$	the number of levels in a lookahead tree added	—	§13

1. The full adder: majority and odd parity

You need

Binary addition by hand added. Add column by column, starting at the least significant bit (the right). In each column add the two bits and the carry that came in from the right. A column that adds to 0 or 1 writes it and carries 0; one that adds to 2 (binary 10) writes 0 and carries 1; one that adds to 3 (binary 11) writes 1 and carries 1.

XOR added. $x\oplus y = 1$ when exactly one of $x$x, $y$ is 1. It is associative, so $a\oplus b\oplus c$ needs no brackets: it is 1 when an odd number of $a$a, $b$b, $c$ are 1.

The question. Every adder, however fast, is built from one-bit pieces. What does the piece for one column of a hand addition compute, and what logic functions are its outputs?

The block is the full adder (FA) board (00:51). It takes three bits, the two operand bits $a$ and $b$ and the carry $c_{in}$ coming from the column to its right, and gives two: the sum bit $s$ and the carry $c_{out}$ into the column to its left. The board draws it the way hand addition runs: $a$ and $b$ from above, $c_{in}$ from the right, $c_{out}$ out to the left and $s$ out below. Keep that orientation: in every chain in this chapter, bit 0 is at the right and the carry flows right to left.

The full adder, redrawn from the board (Lecture15 @ 03:52). Left: the block, with the carry entering from the right and leaving to the left, as in hand addition. Right: its truth table. Read each row as a count: $c_{out}$ and $s$ are the number of ones among $a$a, $b$b, $c_{in}$cin​, written in binary.

The board (Lecture15 @ 03:52)

Lecture15 @ 03:52The full adder, its truth table, the majority function and the odd parity function.

Fair copy of the board above (Lecture15 @ 03:52), mark for mark in its own layout. All black: one pen wrote the whole board. The bottom of the table’s vertical rule, behind the lecturer’s hand here, is copied from 03:23. The table’s rows are levelled; on the board they drift down to the right.

From the truth table to two functions (board, 01:16–03:56)

1. The table. Eight rows, one for each combination of $a$a, $b$b, $c_{in}$ (01:16–02:11). Read one in words: row 011 is $0 + 1 + 1 = 2$2, binary 10, so $c_{out} = 1$ and $s = 0$0.
2. The carry is the majority. $c_{out}$ is 1 in rows 011, 101, 110 and 111: exactly the rows where at least two of the three inputs are 1. As a sum of products, one product for each pair of inputs that are both 1 (02:12–03:06) board: $c_{out} = ab + bc_{in} + ac_{in}$acin​. The board names it the majority function: the output agrees with the majority of the inputs.
3. The sum is the odd parity. $s$ is 1 in rows 001, 010, 100 and 111: one or three ones, an odd number. That is $s = a\oplus b\oplus c_{in}$ (03:06–03:56) board, the odd parity function.
4. Why the block adds added. In every row, $2c_{out} + s = a + b + c_{in}$cin​: the two outputs are the count of ones written in binary, $c_{out}$ the twos digit and $s$ the ones digit. That is what a column of hand addition needs.

The last column below is the count, which the two outputs encode:

$a\ b\ c_{in}$	$c_{out}$	$s$	$a + b + c_{in}$
000	0	0	0
001	0	1	1
010	0	1	1
011	1	0	2
100	0	1	1
101	1	0	2
110	1	0	2
111	1	1	3

The full adderboard

$$c_{out} = ab + bc_{in} + ac_{in}\ \ \text{(majority)},\qquad s = a\oplus b\oplus c_{in}\ \ \text{(odd parity)}$$

Holds when: one bit position; a, b and c_in are single bits

Memorize or derive. Memorize both: they are the most-used formulas of the chapter, and their names (majority, odd parity) carry them. $2c_{out} + s = a + b + c_{in}$ is the one-line derivation if you forget: count the ones and write the count in binary.

A worked example (the board’s rows). Row 011: $ab = 0$0, $bc_{in} = 1$1, $ac_{in} = 0$0, so $c_{out} = 1$1; $0\oplus1\oplus1 = 0$0, so $s = 0$0; and $2 \times 1 + 0 = 2 = 0 + 1 + 1$1. Row 111: all three products are 1, so $c_{out} = 1$1; $1\oplus1\oplus1 = 1$1; and $2 + 1 = 3$3.

Traps.

• Reading $s$ as an OR. $a + b + c_{in}$ in Boolean algebra is the OR, which is 1 on row 011; the sum bit there is 0. The sum is the parity, not the OR.
• Dropping a product term. $c_{out} = ab + bc_{in}$ misses row 101 ($a = c_{in} = 1$a=1, $b = 0$0), where the carry is 1. Each of the three pairs needs its term.

Check yourself Which rows of the full adder's truth table have c_out = 1 and s = 0?

Rows 011, 101 and 110: exactly two of the three inputs are 1, so the count is 2, binary 10.

Check yourself Show from the table that c_out does not change when you exchange a and c_in. What property of the formula guarantees it, and does s have it too?

Exchanging $a$ and $c_{in}$ maps row 001 to 100 and 011 to 110 (rows 000, 010, 101 and 111 map to themselves); in each pair $c_{out}$ is the same (0 and 0; 1 and 1). The formula $ab + bc_{in} + ac_{in}$ is symmetric in its three inputs: exchanging any two permutes its terms. So is $a\oplus b\oplus c_{in}$cin​, so $s$ has it too. A full adder does not care which input is the carry, which §5 and §6 exploit.

2. The ripple-carry adder and its critical path

You need

The full adder (§1). Three bits in, two out: $c_{out} = ab + bc_{in} + ac_{in}$ (1 when at least two inputs are 1) and $s = a\oplus b\oplus c_{in}$ (1 when an odd number are). The carry enters from the right and leaves to the left.

The full adder and its truth table (§1; Lecture15 @ 03:52, redrawn). Original figure ↑

Synchronous timing (Chapter 13). Logic between flip-flops must settle within one clock period, for every input: the period is set by the slowest path through the logic.

The question. Chain $N$ full adders and you have an $N$-bit adder. How long does it take, and which path through it sets that time?

Ripple carry (board, 04:36–08:30)

1. Hand addition. Add 1111 and 0001 (04:41). The right column is $1 + 1 = 2$2: write 0, carry 1. The next is $1 + 0 + 1 = 2$2: write 0, carry 1. And so on: “one and one is zero, carry the one”, four times. The result is 0000 with a carry out of 1, which is $15 + 1 = 16$16.
2. The circuit. One full adder per column, right to left (05:09–06:28) board. Bit 0’s carry-in is $c_{in} = 0$0; bit $i$ takes $a_i$ and $b_i$ from above and gives $s_i$ below; each carry-out goes into the next bit’s carry-in, and the last carry-out is the adder’s $c_{out}$cout​. The carry ripples from bit to bit, so this is the ripple-carry adder board.
3. The delay depends on the operands. In 1111 + 0000 no column makes a carry: every bit’s sum is ready as soon as its own $a_i$ai​, $b_i$ arrive (07:10). In 1111 + 0001 the carry made at bit 0 must pass through every bit before the top sum is right.
4. The clock must wait for the worst. “In a synchronous design, I have to wait for the longest answer” (07:38). So we time the adder by its worst-case path, the critical path board: a carry made at bit 0 that ripples through every carry circuit to the top.
5. What to optimize. On that path the carry circuit appears once per bit, and a sum circuit only once, at the end. For an 8-bit adder the critical path includes “eight copies of the carry chain” (15:53), the lecturer says, and the sum appears on it once. So the carry logic is what matters; a slow sum circuit costs only once.

The board’s two additions added (values from Lecture15 @ 09:32). Left: 1111 + 0001 makes a carry in every column; the result is 0000 with a carry out of 1. Right: 1111 + 0000 makes no carry at all. The same adder finishes sooner for the right-hand pair, but the clock cannot know which pair is coming.

A 4-bit ripple-carry adder, redrawn from the board (Lecture15 @ 09:32). Each carry-out feeds the next bit’s carry-in, from bit 0 at the right to bit 3 at the left. The thick line is the critical path: a carry made at bit 0, rippling through every carry to the top sum $s_3$s3​.

The board (Lecture15 @ 09:32)

Lecture15 @ 09:32Ripple carry: the column sum, the two example additions, the four-bit chain with its critical path, and (in the overbars) the start of subtraction.

Fair copy of the board above (Lecture15 @ 09:32), mark for mark in its own layout. Orange is the pale pen, which drew the ripple-carry adder and its examples: the column sum, the two small sums and the chain with its labels. Black is the violet pen: the full-adder notes from 03:52 and, over the orange, the marks added afterwards: the ring round the worst case, the critical path into $s_3$s3​, and the subtraction ($\bar b_i$bˉi​ and $c_{in} = 1$ for $a + (-b)$(−b)). The left edge of bit 0’s box, the carry into bit 1 and its label, behind the lecturer’s hand here, are copied from 08:47. The table and the parity function of 03:52 are erased by now.

Counting the critical path

Let $t_c$ be the delay of one carry circuit (from its carry-in to its carry-out) and $t_{sum}$ that of one sum circuit added. Follow the carry made at bit 0.

• The carry into bit $N-1$1, $c_{N-1}$cN−1​, comes out of $N - 1$ carry circuits (bits 0 to $N-2$2).
• If the sum circuit needs only $a$a, $b$ and the carry into its bit, as $s = a\oplus b\oplus c_{in}$ does, the top sum $s_{N-1}$ follows one sum delay later: $(N-1)\,t_c + t_{sum}$tsum​.
• The carry-out $c_{out}$ needs one more carry circuit: $N\,t_c$Ntc​.
• The lecture’s circuit (§5) computes its sum from its own bit’s carry-out, so the top bit’s carry circuit also lies on the path to $s_{N-1}$sN−1​: $N\,t_c + t_{sum}$tsum​. That is the lecturer’s count for 8 bits, eight carry stages and one sum, and the eight-stage drawing below.

The critical path of an 8-bit ripple-carry adder, redrawn from the board (Lecture15 @ 18:06): eight carry stages and one sum stage. Every bit adds a carry stage to the path; the sum stage is paid once.

From §9 on, every adder forms its sums as $s_i = p_i\oplus c_i$ from the carry into its bit, so the comparisons there use the first count.

Ripple-carry delayadded

$$\begin{gathered} t_{ripple} \approx (N-1)\,t_c + t_{sum}\ \ \text{to } s_{N-1}\\ N\,t_c\ \ \text{to } c_{out} \end{gathered}$$

Holds when: the worst-case operands (a carry made at bit 0 rippling to the top); every bit's carry circuit has the same delay t_c; the sum circuit needs only a, b and the carry into its bit (for a sum stage that waits for its own carry-out, as the mirror adder's does, add one t_c)

Memorize or derive. Derive: trace the carry from bit 0 and count the circuits it passes. The one thing to remember is that the delay is linear in $N$N: double the width, double the time.

A worked example. First the board’s two additions: 1111 + 0001 gives carries $c_1, c_2, c_3, c_4 = 1, 1, 1, 1$1,1,1,1, sum 0000 and $c_{out} = 1$ (16); 1111 + 0000 gives no carries and sum 1111 (15). Now some delays added: take, for example, $t_c = t_{sum} = 4\,\tau_{inv}$ (§7 finds 4 for the lecture’s carry stage with its inverter removed and a light sum stage; with an inverter it is about 5). An 8-bit adder’s top sum arrives after $7 \times 4 + 4 = 32\,\tau_{inv}$ and its $c_{out}$ after $8 \times 4 = 32\,\tau_{inv}$32τinv​; with the lecture’s circuit, whose sum waits for its own carry stage, the top sum takes $8 \times 4 + 4 = 36\,\tau_{inv}$36τinv​. A 32-bit adder’s top sum takes $128\,\tau_{inv}$128τinv​: four times the width, four times the delay.

Traps.

• Timing the adder by a typical input. Most additions finish early, but the clock has to cover 1111 + 0001.
• Optimizing the sum first. The sum circuit is on the path once; the carry circuit $N$ times.

Check yourself Which 4-bit operand pairs (with c_in = 0) make a carry ripple from bit 0 all the way to c_out?

Bit 0 must generate a carry, $a_0 = b_0 = 1$1, and each of bits 1 to 3 must pass it on, which needs exactly one of $a_i$ai​, $b_i$ to be 1. For example 1111 + 0001, or 0101 + 1011.

Check yourself With the example delays, an 8-bit ripple adder's carry stage gets faster, from 5 to 4 τ_inv. How much sooner does c_out arrive? If instead the sum stage got 1 τ_inv faster, how much sooner would c_out arrive?

Step 1: $c_{out}$ passes eight carry stages, so it goes from $8 \times 5 = 40$ to $8 \times 4 = 32\,\tau_{inv}$32τinv​: $8\,\tau_{inv}$ sooner. Step 2: no sum stage lies on the path to $c_{out}$cout​, so a faster sum stage changes it by nothing. (The top sum would gain $1\,\tau_{inv}$1τinv​; the carry stage’s speed-up gains it seven, one per carry stage before it.)

3. Subtraction with the same adder

You need

Two’s complement (Chapter 15, §11). An $n$-bit word with its top bit as the sign. To negate a number, invert every bit and add 1: $-b = \bar b + 1$1. A carry out of the top bit is dropped.

XOR as a controlled inverter added. $b\oplus 0 = b$ and $b\oplus 1 = \bar b$bˉ: an XOR passes $b$ when its other input is 0 and inverts it when it is 1.

The ripple-carry adder (§2): full adders chained right to left, bit 0’s carry-in $c_{in}$ free.

The 4-bit ripple-carry adder (§2; Lecture15 @ 09:32, redrawn). Original figure ↑

The question. Can the same adder subtract, without a second circuit?

a − b on an adder (board, 08:30–09:30)

1. Rewrite the subtraction. $a - b = a + (-b)$ board.
2. Negate $b$ in two’s complement. Invert every bit of $b$ (the board’s overbars on $b_0 \dots b_3$b0​…b3​) and add 1 board.
3. Use the free carry-in for the “+1”. Bit 0’s carry-in is otherwise 0; set it to 1 (the board’s “$c_{in} = 0$cin​= / $= 1$1”). Nothing else in the adder changes.
4. One control bit (09:30, spoken). A bit SUB added does both: XOR it into every $b_i$bi​, and wire it to $c_{in}$cin​. SUB = 0 adds; SUB = 1 subtracts.

An adder–subtractor added, as described in the lecture (09:30). One control bit SUB feeds an XOR on every $b_i$ and bit 0’s carry-in. SUB = 0: the XORs pass $b$ and $c_{in} = 0$0, so the circuit adds. SUB = 1: the XORs invert $b$ and $c_{in} = 1$1, so it computes $a + \bar b + 1 = a - b$b.

Subtraction on an adderboard

$$a - b = a + \bar b + 1$$

Holds when: two's-complement numbers of the adder's width; the carry out of the top bit is dropped

Memorize or derive. Derive: negation in two’s complement is invert-and-add-one, and the adder’s carry-in supplies the one.

A worked example added (4 bits). $5 - 3$3: $5 = 0101$ and $\bar 3 = 1100$1100, so $0101 + 1100 + 1 = 0010 = 2$2, with a carry out of 1, dropped. $3 - 5$5: $0011 + 1010 + 1 = 1110$1110, which in two’s complement is $-2$−2, with a carry out of 0.

Trap. Inverting $b$ but leaving $c_{in} = 0$ computes $a + \bar b = a - b - 1$1: $5 - 3$ comes out as 0001.

Check yourself What does the 4-bit subtractor output for 0 − 1, and how do you read the result?

Step 1: $\bar 1 = 1110$1110, so the adder computes $0000 + 1110 + 1 = 1111$1111. Step 2: read it in two’s complement: the top bit is 1, so it is negative; inverting and adding 1 gives $0000 + 1 = 0001$0001, so $1111 = -1$−1. Correct.

Check yourself With SUB = 1, what does the 4-bit circuit give for 4 − 4, and why is its carry-out 1?

Step 1: $\bar 4 = 1011$1011, so the adder computes $0100 + 1011 + 1 = 10000$10000: sum 0000, carry-out 1. Step 2: inverting and adding 1 adds $16 - b$b, so the adder computes $a + 16 - b$b, which reaches 16, and carries out, exactly when $a \ge b$ as unsigned numbers. Here $4 \ge 4$4, so the carry-out is 1. (In 5 − 3 it was 1 too; in 3 − 5 it was 0.)

4. Self-duality: why the pull-up equals the pull-down

You need

Complementary static CMOS (Chapter 7, §4). The NFET pull-down network conducts on the rows where the output is 0, so the gate computes the complement of the pull-down’s condition. The PFET pull-up is the dual network: the same inputs, with every series connection made parallel and every parallel one series. A PFET conducts on a 0. Exactly one network conducts for every input, so the gate is static.

The two outputs (§1): $c_{out} = ab + bc_{in} + ac_{in}$acin​, the majority, and $s = a\oplus b\oplus c_{in}$cin​, the odd parity.

The question. To build the full adder in static CMOS we need a pull-down and a pull-up for each output. What special property do these two functions have, and what does it buy in the circuit?

Self-duality (board, 10:04–12:16)

1. The definition (10:51) board. Complement all three inputs, and the output complements: $\bar s(a, b, c_{in}) = s(\bar a, \bar b, \bar c_{in})$ and $\overline{c_{out}}(a, b, c_{in}) = c_{out}(\bar a, \bar b, \bar c_{in})$cout​(aˉ,bˉ,cˉin​). A function with this property is self-dual board. Check one row: $s(0, 1, 1) = 0$0, and $s(1, 0, 0) = 1 = \bar 0$0ˉ.
2. Why it holds added. Complementing all three inputs turns a count of $k$ ones into $3 - k$k. “At least two of three” becomes “at most one”, the complement of the majority; an odd count becomes an even one, the complement of the parity.
3. What it buys (11:35–12:06). A pull-up of PFETs conducts when its inputs are low; so a pull-up network built with the same series–parallel structure as the pull-down, on the same inputs, conducts exactly when the pull-down would conduct on the complemented inputs. For the gate to work, the pull-up must conduct when the output is 1, which is when the pull-down is off. For a self-dual function those two conditions coincide, so the pull-up can have the same structure as the pull-down. “If the logic function in question is self dual, then the pull-up and pull-down networks will be exactly the same. And that’s going to make the layout very convenient.”
4. The majority’s networks added. Its pull-down conducts for $ab + c_{in}(a + b)$b): $c_{in}$ in series with ($a$a parallel $b$b), and beside that branch $a$ in series with $b$b. Chapter 7’s rule would build the pull-up as the dual: swap series and parallel everywhere, giving ($c_{in}$cin​ parallel $a$–$b$b) in series with ($a$a parallel $b$b). That works, but self-duality offers a second pull-up: the pull-down’s own structure in PFETs, which by step 3 conducts exactly when the output should be 1. The two pull-ups conduct for the same inputs; only the second is a mirror image of the pull-down, and that is the one the lecture uses. The pull-down and its mirror are drawn below.

The majority’s pull-down and the mirror pull-up added. Left: the pull-down, conducting for $ab + c_{in}(a + b)$b). Right: the same structure in PFETs, conducting for $\bar a\bar b + \bar c_{in}(\bar a + \bar b)$bˉ), the majority of the complemented inputs, which by self-duality is 1 exactly when $c_{out} = 0$0. The two networks are the same up to the order of devices in a branch, which is why the lecture’s circuit (§5) has a pull-up that mirrors its pull-down.

The board (Lecture15 @ 11:45)

Lecture15 @ 11:45Self-duality: complementing every input complements both outputs.

Fair copy of the board above (Lecture15 @ 11:45), mark for mark in its own layout. Orange is the pale pen’s column sum, the one part of 09:32’s ripple-carry layer still on the board; everything else is the violet pen, in black. The two small sums, the ripple chain with its critical path, “ripple carry adder” and “critical path” are erased by now. The two equations are levelled; on the board they drift down to the right.

The sum written with the carry

The board also rewrites the sum in a form the circuit will use (12:41, written at 18:06) board:

$$s = abc_{in} + \overline{c_{out}}\,(a + b + c_{in}).$$

Why it is right, case by case:

• No input or one input is 1. Then $c_{out} = 0$0, so $\overline{c_{out}} = 1$1, and the second term is $a + b + c_{in}$cin​: 1 when exactly one input is 1, 0 when none is. The product $abc_{in}$ is 0. So $s$ is 1 for one input, 0 for none. Correct.
• Exactly two are 1. $c_{out} = 1$ kills the second term, and $abc_{in} = 0$0. So $s = 0$0. Correct.
• All three are 1. $abc_{in} = 1$1. So $s = 1$1. Correct.

The point: a three-input XOR in static CMOS is large, but this form needs only AND and OR of the inputs and of $\overline{c_{out}}$cout​​, which the carry gate already makes. The table checks both properties on every row:

$a\ b\ c_{in}$	$s$	$s(\bar a, \bar b, \bar c_{in})$	$c_{out}$	$c_{out}(\bar a, \bar b, \bar c_{in})$	$abc_{in} + \overline{c_{out}}(a + b + c_{in})$
000	0	1	0	1	0
001	1	0	0	1	1
010	1	0	0	1	1
011	0	1	1	0	0
100	1	0	0	1	1
101	0	1	1	0	0
110	0	1	1	0	0
111	1	0	1	0	1

Self-duality and the sum identityboard

$$\bar f(a, b, c) = f(\bar a, \bar b, \bar c),\qquad s = abc_{in} + \overline{c_{out}}\,(a + b + c_{in})$$

Holds when: any self-dual function f; the identity holds for the full adder's s and c_out on every input

Memorize or derive. Memorize the definition of self-dual, and that both full-adder outputs have it. Derive the sum identity from the three cases above when you need it: it is the form that FN12-10b’s domino full adder and MT24-5a’s dynamic one use.

A worked example (the identity on two rows). Row 110: $c_{out} = 1$1, so $\overline{c_{out}}(a + b + c_{in}) = 0$0, and $abc_{in} = 0$0: $s = 0$0, as $1 + 1 + 0 = 2$ (binary 10) says. Row 100: $\overline{c_{out}} = 1$ and $a + b + c_{in} = 1$1, so $s = 1$1.

Traps.

• “The two outputs are duals of each other.” The lecturer says it loosely (10:38), but the property is that each output is its own dual.
• Every gate’s pull-up mirrors its pull-down. No: a NAND’s pull-down is series and its pull-up parallel. Only a self-dual function can have identical networks.
• The mirror is the dual. It is not: the dual of the majority’s pull-down is ($c_{in}$cin​ parallel $a$–$b$b) in series with ($a$a parallel $b$b), a different arrangement of the same five devices. The two conduct for the same inputs, which is why either serves; the mirror is chosen because it matches the pull-down in the layout.

Check yourself Is a two-input XOR self-dual?

No. Complementing both inputs leaves an XOR unchanged, $\bar a\oplus\bar b = a\oplus b$b, but self-duality needs it to complement. An XOR of an odd number of inputs is self-dual; an even number is not.

Check yourself Is the complement of the majority, c̄_out, also self-dual? What does the answer say about the gate that produces c̄_out?

Step 1: complement both sides of $\overline{c_{out}}(a,b,c_{in}) = c_{out}(\bar a,\bar b,\bar c_{in})$cout​(aˉ,bˉ,cˉin​): $c_{out}(a,b,c_{in}) = \overline{c_{out}}(\bar a,\bar b,\bar c_{in})$cout​​(aˉ,bˉ,cˉin​), which is the definition of self-duality for $\overline{c_{out}}$cout​​. Step 2: the gate that computes $\overline{c_{out}}$ (a static CMOS gate always computes a complement) can therefore have identical pull-up and pull-down. That is the carry stage of §5.

5. The mirror adder at transistor level

You need

Sizing stacks and logical effort (Chapter 7, §8). The reference inverter has an NFET of 1 unit and a PFET of 2 units (the PFET is half as strong per width), so its input is 3 units. To give a gate the same drive, every conducting path must be as strong as one inverter device, so a device in a series stack of $n$ is $n$ times as wide. An input’s logical effort is its gate width over the inverter’s 3 units: a two-input NAND (NFETs 2, PFETs 2) has $g = 4/3$4/3.

Self-duality (§4). Both full-adder outputs are self-dual, so each gate can have a pull-up with the same structure as its pull-down. The majority’s pull-down is $c_{in}$ over ($a$a parallel $b$b), beside $a$–$b$ in series.

The majority’s pull-down and the identical pull-up built from it (§4). Original figure ↑

The sum identity (§4): $s = abc_{in} + \overline{c_{out}}(a + b + c_{in})$cin​).

The question. What does the lecture’s full adder look like in transistors, and what does it cost to drive its inputs?

The lecture draws a static CMOS full adder device by device (12:16–15:17) but gives it no name. This guide calls it the mirror adder added, because every pull-up in it is the mirror image of its pull-down, and that is the name it goes by in textbooks.

The two stages (board, 13:20–15:11)

1. The carry stage. The pull-down: an NFET $c_{in}$ over NFETs $a$ and $b$ in parallel, and beside that branch NFETs $b$ and $a$ in series (13:20–14:10) board. It conducts when $c_{in}(a + b) + ab$ab, the majority, so the gate’s output is $\overline{c_{out}}$cout​​. The pull-up is the same structure in PFETs, which self-duality allows. An inverter after it gives $c_{out}$cout​.
2. The sum stage. The pull-down: an NFET $\overline{c_{out}}$ over NFETs $a$a, $b$b, $c_{in}$ in parallel, and beside it NFETs $a$a, $b$b, $c_{in}$ in series (14:10–15:11) board. It conducts when $\overline{c_{out}}(a + b + c_{in}) + abc_{in}$abcin​, which by §4’s identity is $s$s, so the output is $\bar s$sˉ. Again the pull-up is the same structure in PFETs, and an inverter gives $s$s.
3. Count the devices added. Carry stage: 5 NFETs and 5 PFETs, 10. Sum stage: 7 and 7, 14. Two inverters, 4. In all, 28 transistors.

The mirror adder’s carry stage, redrawn from the board (Lecture15 @ 21:39). The pull-down conducts for $ab + c_{in}(a + b)$b), so the output is $\overline{c_{out}}$cout​​; the pull-up has the same structure in PFETs. The two $c_{in}$ devices sit next to the output node (§6 explains why), and an inverter restores $c_{out}$cout​.

The mirror adder’s sum stage, redrawn from the board (Lecture15 @ 21:39). Its pull-down conducts for $\overline{c_{out}}(a + b + c_{in}) + abc_{in}$abcin​, which is $s$ (§4), so the output is $\bar s$sˉ; an inverter gives $s$s. The $\overline{c_{out}}$ input comes from the carry stage.

The board (Lecture15 @ 18:06)

Lecture15 @ 18:06The transistor-level full adder: carry stage, sum stage, the alternative stack (top), the eight-bit chain (bottom) and the sum identity (left).

Fair copy of the board above (Lecture15 @ 18:06), mark for mark in its own layout. Black is the violet pen: the notes from 03:52–11:45 with the sum identity $s = abc_{in} + \overline{c_{out}}\,(a + b + c_{in})$ added, the carry stage (output $\overline{c_{out}}$cout​​, then an inverter to $c_{out}$cout​), the sum stage (output $\bar s$sˉ, then an inverter to $s$s), the alternative carry stack at the top, struck through, and the eight-stage carry chain. Teal is the cyan pen, added over the finished circuit: the rings on the $c_{in}$ input and on the two $c_{in}$ devices next to the output, the rings on the top stack’s $c_{in}$ devices next to the rails, the ring on the carry inverter, and the line along the chain’s carries. The $a$–$b$ column of the carry stage lies over the lecturer’s face, which washes out its labels; they match 21:39, where the column is unchanged. The lone $b$ left of $c_{in}$ is what is left of 09:32’s column sum. The devices are drawn with the course’s symbols; the board draws squiggle channels.

Sizing the stages and their logical efforts

Now size each stage, by Chapter 7’s stack rule, to drive like the reference inverter added.

The carry stage sized for the reference inverter’s drive added. Every path through each network passes two devices, so every NFET is 2 and every PFET 4. The $c_{in}$ wire drives one NFET and one PFET, 6 units; the $a$ wire (and likewise $b$b) drives two of each, 12 units.

Widths and logical efforts (Chapter 7's sizing)

1. Carry stage widths. Every path from the output to ground passes two NFETs ($c_{in}$cin​ then $a$ or $b$b; or $b$ then $a$a), so every NFET is $2 \times 1 = 2$2. Every path in the pull-up passes two PFETs, so every PFET is $2 \times 2 = 4$4.
2. Carry stage, $c_{in}$ input. It drives one NFET (2) and one PFET (4): 6 units. Logical effort $g_{c_{in}} = 6/3 = 2$2.
3. Carry stage, $a$ input (and $b$b). It drives two NFETs and two PFETs, one in each branch: $2\cdot2 + 2\cdot4 = 12$ units, so $g_a = g_b = 12/3 = 4$4.
4. Sum stage widths. The series branch $a$–$b$–$c_{in}$ is three high, so those NFETs are 3 and PFETs 6. In the other branch every path passes two devices ($\overline{c_{out}}$cout​​ and one of the parallel three), so those are 2 and 4.
5. Sum stage inputs. $\overline{c_{out}}$ drives one 2 and one 4: 6 units, $g = 2$2. The $a$ input drives a 3 and a 2 (NFETs) and a 6 and a 4 (PFETs): 15 units, $g = (3 + 2 + 6 + 4)/3 = 5$5. So do $b$ and $c_{in}$cin​.

The mirror carry stage's logical effortsadded

$$g_{c_{in}} = \frac{2 + 4}{3} = 2,\qquad g_a = g_b = \frac{2\cdot2 + 2\cdot4}{3} = 4$$

Holds when: every device sized for the reference inverter's drive (NFET 1, PFET 2) by the stack rule; drain capacitance ignored

Memorize or derive. Derive: size by the stack rule, add up the input’s gate widths, divide by 3. It takes a minute and needs nothing memorized.

The worked example’s lesson. The $c_{in}$ input costs half as much to drive as $a$ or $b$b. That is just right, because $c_{in}$ is the input on the critical path (§2): each carry stage drives the next one’s $c_{in}$cin​, so its light load makes the chain fast. The sum stage is heavier ($g = 5$g= on $a$a, $b$ and $c_{in}$cin​), but it is on the critical path only once, at the top bit.

Traps.

• Sizing the sum stage’s three-high branch like the rest. It is three high, so 3 and 6, not 2 and 4.
• Treating the inverter after $\overline{c_{out}}$ as free. The next bit needs $c_{in}$ in true polarity, so with this circuit every bit pays an inverter on the critical path. §7 removes it.

Check yourself Which devices in the carry stage are driven by c_in, and where in their stacks are they?

One NFET and one PFET, each the device next to the output node: the NFET $c_{in}$ sits directly under the output, above the parallel $a$a, $b$b; the PFET $c_{in}$ sits directly above the output, below the parallel $a$a, $b$b.

Check yourself A two-input NAND sized for the reference inverter's drive has g = 4/3. How many times more input capacitance does the carry stage's a input present than a NAND input of the same drive, and why?

Step 1: the NAND input drives one 2-unit NFET and one 2-unit PFET, 4 units; the carry stage’s $a$ drives two NFETs of 2 and two PFETs of 4, 12 units. Step 2: $12/4 = 3$ times. The reason is that $a$ appears in both branches of each network, and in each it sits in a two-high stack, so it drives two doubled devices per network instead of one.

6. The carry input goes next to the output

You need

Pin swapping (Chapter 7, §5). The order of devices in a series stack does not change the logic, but it changes the delay: for a single input switching, the device closest to the output switches with less delay. So a late-arriving signal goes to the device next to the output.

Why a device low in the stack is slow (Chapter 8, §10). Before a device lower in a stack can pull the output down, it must first discharge the internal node between it and the devices above. If those upper devices are already on, that node was charged high and must be emptied first; the penalty grows roughly as the square of the stack height. If instead the lower devices are the ones already on, the internal node is already at the rail and the top device switches like an inverter.

The carry stage (§5): $c_{in}$ over ($a$a parallel $b$b), beside $a$–$b$ in series, in both networks.

The mirror adder’s carry stage (§5; Lecture15 @ 21:39, redrawn), with its $c_{in}$ devices next to the output. Original figure ↑

The question. In the carry stage, $c_{in}$ and the pair ($a$a parallel $b$b) are in series. Either order gives the same logic. Which order should we draw, and why does it matter more here than in most gates?

The order of the stack (board, 16:25–17:40)

1. The other way to draw it (16:25–16:58) board. Put $c_{in}$ next to the rails ($V_{DD}$VDD​ above, ground below) and the parallel pair next to the output. The logic is unchanged: series devices conduct in either order. “This is not a good choice … even though logically it’s absolutely correct” (16:58–17:11).
2. Which input arrives last (17:14–17:40). In a ripple adder all the $a_i$ and $b_i$ are set at the start of the cycle. The carry $c_{in}$ of a high bit arrives only after the carry has rippled up to it, so $c_{in}$ is the latest-arriving input of every carry stage.
3. So $c_{in}$ goes next to the output. By the time it arrives, the $a$a, $b$ devices below it have settled, and if they conduct, the internal node between them and the $c_{in}$ device is already at the rail. The $c_{in}$ device then switches like an inverter’s. With the order reversed, the late $c_{in}$ device would be at the bottom and would have to discharge the internal node first.
4. Every bit pays it. The choice is repeated in every carry stage, and every carry stage is on the critical path (“absolutely part of the critical path”, 17:57): eight times over in an 8-bit adder.

Two orders for the same branch of the carry stage, redrawn from the board (Lecture15 @ 18:06). Left (✓): the late $c_{in}$ drives the devices next to the output, as in the lecture’s circuit. Right (✗): the board’s alternative, logically identical, with $c_{in}$ next to the rails, where its device must first discharge the internal node.

The rule. No new formula: this is Chapter 7’s pin-swapping rule applied to the input whose lateness is built into the architecture. Memorize it: the late input goes next to the output.

Why no number. The course’s delay model gives every device in a stack the same strength; Chapter 8 §10 gives only the trend for the bottom device ($\sim n^2$∼n2), not a value. So the chapter does not put a figure on the penalty. What it can say is how often it is paid: once per bit, all along the critical path.

A worked trace added (no number). Take $a = 1$1, $b = 0$0, with $c_{in}$ rising last, so $\overline{c_{out}}$ must fall. In the ✓ order the pull-down is output, NFET $c_{in}$cin​, the $a\parallel b$ pair, ground: the $a$ device is already on, so the node between the pair and the $c_{in}$ device is already at ground, and the $c_{in}$ device discharges the output like an inverter’s NFET. In the ✗ order it is output, the pair, NFET $c_{in}$cin​, ground: the $a$ device connects the internal node to the high output, so the node has charged to about $V_{DD} - V_T$VT​, and when $c_{in}$ rises its device must first empty that node before the output can fall. Same logic, a slower edge, in every bit.

Trap. Applying the rule to $a$ or $b$b. They arrive early, at the start of the cycle, so their place in the stack matters little. The rule is about the late input.

Check yourself In the sum stage, which input arrives last, and where does the lecture's circuit put it?

Step 1: the sum stage takes $a$a, $b$b, $c_{in}$ and $\overline{c_{out}}$cout​​. $\overline{c_{out}}$ comes from this bit’s carry stage, which itself waits for $c_{in}$cin​, so $\overline{c_{out}}$ is the last to arrive. Step 2: in the lecture’s sum stage the $\overline{c_{out}}$ NFET is directly under the output and its PFET directly above it: next to the output, as the rule wants.

Check yourself Now the pull-up in the ✗ order: a = 0, b = 1, and c_in falls last, so c̄_out must rise. Which internal node holds the wrong charge, and which device must fix it before the output can rise?

Step 1: in the ✗ order the pull-up is $V_{DD}$VDD​, PFET $c_{in}$cin​, the $a\parallel b$ pair, output. With $a = 0$ the $a$ PFET is on and connects the node between the pair and the $c_{in}$ device to the output, which is low; so the node has been pulled down (to within about a threshold of ground). Step 2: when $c_{in}$ falls, the $c_{in}$ PFET, the one by the rail, must first charge that node before the output can rise. In the ✓ order that node sits between $V_{DD}$‘s pair and the $c_{in}$ device and is already held at $V_{DD}$ by the on $a$ PFET.

7. Removing the carry chain’s inverters

You need

Self-duality (§4). Complementing every input complements the output: $c_{out}(\bar a, \bar b, \bar c) = \overline{c_{out}(a, b, c)}$cout​(a,b,c)​, and the same for $s$s.

Gains (Chapter 8, §1). A stage’s delay is $g\cdot h\,\tau_{inv}$hτinv​: its logical effort $g$ times its electrical effort $h$h, the load it drives over its own input capacitance. An inverter has $g = 1$1. A path’s delay is the sum of its stages’ gains.

The carry stage’s numbers (§5). Sized for the reference inverter’s drive (NFET 1, PFET 2), its $c_{in}$ input is 6 units with $g_{c_{in}} = 2$2. The sum stage’s $\overline{c_{out}}$ input is also 6 units; its $c_{in}$ input is 15.

The carry stage sized for inverter drive (§5): $c_{in}$ presents 6 units, $g_{c_{in}} = 2$2. Original figure ↑

The question. Every bit’s carry passes the carry stage and an inverter, and both are on the critical path. Can the inverter go?

Alternating polarity (board, 18:11–21:10)

1. Take the inverters out (18:11) board. The board crosses out both output inverters, the carry’s and the sum’s (both are ringed and struck out by 21:39). Bit 0, fed $a_0$a0​, $b_0$ and $c_{in}$cin​, now produces $\overline{c_{out}}$ (and $\bar s_0$sˉ0​).
2. Feed the next bit inverted inputs (19:17–20:20) board. Bit 1 receives the inverted carry. Give it inverted operands too, $\bar a_1$ and $\bar b_1$bˉ1​. Then all three of its inputs are complemented, and by self-duality its carry stage computes $\overline{c_{out}}(\bar a_1, \bar b_1, \bar c_1) = c_{out}(a_1, b_1, c_1)$cout​(a1​,b1​,c1​): the true carry. Its sum stage likewise gives the true $s_1$s1​.
3. Alternate. Bit 2 receives a true carry, so it takes true $a_2$a2​, $b_2$ and gives an inverted carry and $\bar s_2$sˉ2​, like bit 0. Bit 3 is like bit 1, and so on: even bits take true operands and produce inverted outputs, odd bits take inverted operands and produce true outputs.
4. Where the inverters went (20:20–21:10). To the operands of the odd bits, which are ready at the start of the cycle and are inverted in parallel with everything else, and to the even bits’ sums, which leave the adder. Neither is on the carry chain. “I don’t pay any penalty in having to invert the A and the B’s … So this is a win” (21:00).

The inverterless carry chain, redrawn from the board (Lecture15 @ 21:39; the board draws three bits and part of a fourth, and bit 3 completes the pattern). Even bits take true operands and pass on an inverted carry; odd bits take inverted operands and, by self-duality, pass on the true carry. The only inverters left are on the even bits’ sums, off the carry path.

The board (Lecture15 @ 21:39)

Lecture15 @ 21:39The last board of the first take: both output inverters crossed out, and the inverterless chain with its alternating inputs.

Fair copy of the board above (Lecture15 @ 21:39), mark for mark in its own layout: the last board before the lecture’s re-taped second part. Black is the violet pen: the transistor-level full adder of 18:06, unchanged, and the title; the rest of the left column is erased (a stub of the “Datapath / dataflow” underline and the lone $b$ of 09:32’s column sum remain). Teal is the cyan pen: the rings of 18:06, the strokes through both output inverters (the carry and the sum stage drop them), and the inverterless chain with “parallel adder”. Two slips are copied as written and marked †: bit 2’s inputs "$a_2b_7$" are $a_2b_2$a2​b2​, and its sum "$\bar s_3$" is $\bar s_2$sˉ2​. The lower corner of the leftmost box, under the lecturer’s hand here, is copied from 21:00. The chain’s three left bits sit a little further apart than on the board, so the carry labels fit between the boxes.

What the win is worth

The lecture says “win” without a number. Chapter 8’s gains give one added. Use §5’s sizes: the carry stage’s $c_{in}$ input is 6 units with $g_{c_{in}} = 2$2, and its own sum stage’s $\overline{c_{out}}$ input is 6 units. Leave out, for now, the next bit’s sum stage, which also reads the carry through its $c_{in}$ input; its load $s_{in}$ is the condition at the end.

Per bit, with and without the inverter (τ_inv)

1. Without the inverter. Each carry node drives the next carry stage’s $c_{in}$ (6) and its own sum stage’s $\overline{c_{out}}$ (6): $h = 12/6 = 2$2, so the stage takes $g\cdot h = 2 \times 2 = 4\,\tau_{inv}$ per bit.
2. With an inverter of size $x$ (input $3x$ units). The carry stage drives the inverter and its own sum stage: $2 \times (3x + 6)/6 = x + 2$2. The inverter drives the next $c_{in}$cin​: $1 \times 6/(3x) = 2/x$2/x. Per bit, $t(x) = x + 2 + 2/x$2/x.
3. The best inverter. The terms $x$ and $2/x$ balance where $x = 2/x$2/x, at $x = \sqrt2$2​: $t = 2 + 2\sqrt2 = 4.83\,\tau_{inv}$4.83τinv​. A unit inverter ($x = 1$x=1) gives $5\,\tau_{inv}$5τinv​.
4. Eight bits. Inverterless: $8 \times 4 = 32\,\tau_{inv}$32τinv​. With the best inverters $38.6\,\tau_{inv}$ (38.63); with unit inverters $40\,\tau_{inv}$40τinv​. Removing the inverters saves $6.6\,\tau_{inv}$ against the best, 17%.

The carry chain’s delay per bit added, computed from Chapter 8’s gains with §5’s sizes, the next sum stage’s $c_{in}$ load left out: with an inverter of size $x$ after each carry stage, $x + 2 + 2/x$ (curve; least, $2 + 2\sqrt2 = 4.83$4.83, at $x = \sqrt2$2​), and without it, 4 (line). No inverter size reaches the line.

Check (a bound). By the inequality of arithmetic and geometric means, $x + 2/x \ge 2\sqrt{x\cdot 2/x} = 2\sqrt2$ for every $x > 0$0, so $t(x) \ge 2 + 2\sqrt2 > 4$4: no inverter, however sized, beats the inverterless chain here. The plot shows the same: the curve never touches the line.

The carry chain per bit, with and without invertersadded

$$\begin{gathered} t_{\text{no inv}} = 4\,\tau_{inv}\\ t(x) = \Big(x + 2 + \frac{2}{x}\Big)\tau_{inv} \ \ge\ (2 + 2\sqrt2)\,\tau_{inv}\ \text{ at } x = \sqrt2 \end{gathered}$$

Holds when: §5's sizing (carry stage c_in input 6 units, g = 2; the sum stage's c̄_out input 6 units); every bit loaded alike; the next bit's sum stage's c_in load left out (see below); drain capacitance ignored

Memorize or derive. Derive: two gains per bit, each $g\cdot h$ with the loads read off the circuit. The lesson to memorize is the lecture’s: an inverter on the carry chain is paid $N$ times.

What breaks it: the sum stage’s load. The next bit’s sum stage reads the carry too, through its $c_{in}$ input; call that load $s_{in}$ units. Without inverters it sits on the carry node: $2(12 + s_{in})/6 = 4 + s_{in}/3$sin​/3. With an inverter it sits on the inverter’s output: $x + 2 + (6 + s_{in})/(3x)$sin​)/(3x), least $2 + 2\sqrt{(6 + s_{in})/3}$2(6+sin​)/3​. The two are equal at $s_{in} = 6$ (both $6\,\tau_{inv}$6τinv​, with $x = 2$2), and the inverterless chain wins exactly when $s_{in} < 6$6: when the sum stage loads the carry less than the next carry stage does. A sum stage sized for full drive, as in §5, puts $s_{in} = 15$ units on it ($g = 5$g=5), and then the inverter wins: $9\,\tau_{inv}$ against $2 + 2\sqrt7 = 7.29\,\tau_{inv}$ at $x = \sqrt7 = 2.65$2.65. So the lecture’s win comes with a design rule added: build the sum stage small. It is off the critical path except at the top bit, so it can afford to be slow, and a small sum stage keeps the carry wire light. FN19-3’s $C_{load}$Cload​, “the loading of the sum circuit at each bit”, is this load: in its inverterless chain the own sum stage’s $\overline{c_{out}}$ input and the next one’s $c_{in}$ input both sit on the carry node, lumped.

Traps.

• Inverting the carry but not the next bit’s operands. The next stage would then compute the majority of mixed polarities, $c_{out}(a_1, b_1, \bar c_1)$cout​(a1​,b1​,cˉ1​), which is wrong.
• Forgetting the even bits’ sums. They come out inverted and still need an inverter, off the carry path but there.

Check yourself In the inverterless chain, which bits take inverted a and b?

The odd bits: 1, 3, 5, …. Bit 0 takes true operands, because it receives the true $c_{in}$cin​; each bit after it receives a carry of the opposite polarity to its neighbour’s.

Check yourself FN19-3's carry chain (solved in F2, §4) has, in every stage, the carry input's device in series with one conducting device on each side, the other two inputs tied to 1 and 0. Which part of the mirror carry stage is that, and why is the stage's logical effort 2?

Step 1: with $a = 1$ and $b = 0$ the stage is held in propagate. The $a$–$b$ series branch could never conduct (one of its devices is always off), so FN19-3 leaves it out; what remains is the $c_{in}$ branch, $c_{in}$ in series with the one conducting device of the ($a$a parallel $b$b) pair on each side. Each stage inverts its carry, as this section’s chain does. Step 2: every device is in a two-high stack, so each is twice the inverter’s width; the $c_{in}$ input drives one doubled NFET and one doubled PFET, twice an inverter’s input for the same drive: $g = 2$2.

FN19-3 itself, with its delay, energy and best width, is solved in F2, §4.

8. Datapath layout: the bit stack

You need

Layout image (Chapter 9, §8). Each metal layer has a preferred routing direction, alternating up the stack: if M1 runs horizontally, M2 runs vertically, M3 horizontally, and so on. A route that must turn changes layer instead of blocking the layer it is on.

Design rules (Chapter 9, §6). Every layer has a minimum width and a minimum spacing. A routing track is one wire’s width plus one spacing: the pitch at which parallel wires can be packed.

The question. A datapath does the same thing to every bit of a word. How does that shape its layout?

The bit stack (board, 23:24–27:40)

1. The same circuit in every bit (23:24–24:42). Datapaths are “highly structured”, so their layouts are built as a bit stack board: each block (an adder, a shifter, a logic unit LU) is cut into identical bit slices, and the blocks are stacked so that bit $i$ of every block lies in the same column.
2. Data one way, control the other (24:42–25:15) board. The data run up and down through every block, on the vertical layers M2 and M4. The control signals, which tell a whole block what to do and so are shared by all its bits, come in from the side on the horizontal layers M1, M3 and M5. That is layout image at the scale of the whole datapath.
3. One bit pitch for every block (25:15–27:40) board. The width of a slice, the bit pitch, must be the same in every block. If a shifter’s slices were narrower than the adder’s, the data wires would have to jog sideways between them (the board’s crossed-wire sketch), which costs area and wiring.
4. Choose the pitch first. The pitch is set early, from the number of routing tracks a slice needs, each a minimum width plus a minimum spacing (“# of routing tracks”, “minimum width”, to which the board soon adds “spacings”). A more complex block then grows taller, not wider.

A datapath as a bit stack, redrawn from the board (Lecture15 @ 27:07). Every block is cut into slices of one bit pitch, bit 7 at the left; data run vertically on M2 and M4, control horizontally on M1, M3 and M5. A more complex block is taller, not wider. Right (✗): blocks of different pitch force the data wires to jog between them.

The board (Lecture15 @ 27:07)

Lecture15 @ 27:07The bit stack: blocks sliced by bit, data vertical, control horizontal, and one bit pitch for all.

Fair copy of the board above (Lecture15 @ 27:07), mark for mark in its own layout. Black is the cream pen: the titles and the bit stack with its data and control notes. Teal is the cyan pen, which added the pitch notes over it: the arrow beside the adder, the ring round “bit pitch”, “# of routing tracks”, “minimum width” and the sketch of two rows with different pitches joined by bent wires. Two board slips are copied as written and marked †: the 5 among the bit numbers is written like an 8, and “minimum” is written “aimimum”. The stroke after “width” is the start of the “/” of “width/spacings”, which the lecturer is writing here.

The ripple-carry adder in a bit stack

The adder's slices (board, 27:58–30:55)

1. Two cells per bit (27:58) board. Each bit’s slice holds a carry cell C over a sum cell S; the eight slices sit side by side.
2. Shared rails and wells (28:57–29:44) board. Horizontal M1 rails run along the rows: $V_{DD}$ above the carry cells, ground between the carry and sum cells, $V_{DD}$ below the sum cells. The PFETs sit next to $V_{DD}$ and the NFETs next to ground, so the rows read P, N (carry), N, P (sum), and the next block below shares the bottom n-well and $V_{DD}$ rail.
3. A power grid (29:44) board. Vertical M2 straps over the slices alternate between vdd! and gnd! (the global net names), tying the rails into a grid.
4. Cells that wire themselves (29:57–30:55). With forethought, each carry cell’s carry-out lands where the next cell’s carry-in is, so the cells abut and the carry chain connects with very little extra metal: “they just connect together like a set of Lincoln Logs” (30:24).

The ripple-carry adder as a bit stack, redrawn from the board (Lecture15 @ 30:26). Each bit is a carry cell C over a sum cell S. M1 rails run along the rows ($V_{DD}$VDD​, ground, $V_{DD}$VDD​), with the PFET rows (P) beside $V_{DD}$ and the NFET rows (N) beside ground; the dashed P row is the next block’s, sharing the n-well. M2 straps alternate vdd! and gnd! to form a grid.

The board (Lecture15 @ 30:26)

Lecture15 @ 30:26The ripple-carry adder in a bit stack: carry and sum cells, M1 rails, M2 straps.

Fair copy of the board above (Lecture15 @ 30:26), mark for mark in its own layout, on the coordinates of the 27:07 copy. Black is the cream pen (the titles and the bit stack); teal is the cyan pen (the pitch notes of 27:07, then the carry and sum cells with their M1 rails, “spacings” and the hatched tracks at the right); magenta is the violet pen, which added the M2 straps and, in the eighth column, the ringed device rows: P, N for the carry cell and N, P for the sum cell, then the next block’s P row sharing the bottom rail. Two board slips are copied as written and marked †: the 5 among the bit numbers is written like an 8, and “minimum” is written “aimimum”. The strap labels are wider in type than the columns they sit in, so the vdd! labels are set one row above the gnd! labels.

Bit pitchadded

$$\begin{gathered} \text{bit pitch} \gtrsim (\text{number of tracks})\\ \times\ (\text{minimum width} + \text{minimum spacing}) \end{gathered}$$

Holds when: a slice's width set by the routing tracks it needs on its vertical layer; a track is one minimum width plus one minimum spacing

Memorize or derive. Derive it from the meaning of a track. The facts to remember are qualitative: one pitch for all blocks, set first; data vertical, control horizontal; complexity goes into height.

A worked example added (illustrative values; the course gives no metal pitch). For example, with 8 M2 tracks per bit at a track pitch of 0.2 µm, the bit pitch is at least $8 \times 0.2 = 1.6$ µm, and a 32-bit datapath is at least $32 \times 1.6 = 51.2$ µm wide, in every block.

Trap. Choosing each block’s pitch for its own density. The blocks then do not line up, and every boundary between them needs jogs.

Check yourself In the same stack, a shifter needs 10 M2 tracks per bit and the adder 8. What bit pitch must the stack use, and where does the adder's spare room go?

Step 1: the pitch must fit the block that needs the most tracks, the shifter: 10 tracks, for example $10 \times 0.2 = 2.0$ µm, and the 32-bit stack is then 64 µm wide. Step 2: the adder keeps that same pitch; its two spare tracks per bit stay free for routing, and any extra logic it has goes into its height.

Check yourself A 64-bit stack's densest block needs 12 tracks per bit, at 0.2 µm a track. How wide is the stack, and how much narrower would it be if that block were redesigned to need 10?

Step 1: the pitch is set by the densest block: $12 \times 0.2 = 2.4$ µm, so the stack is $64 \times 2.4 = 153.6$ µm wide, in every block. Step 2: at 10 tracks the pitch is 2.0 µm and the stack 128 µm: 25.6 µm narrower, for the whole datapath, because every block shares the pitch.

9. Parallel adders start from generate and propagate

You need

The full adder (§1): $c_{out} = ab + bc_{in} + ac_{in}$ (majority), $s = a\oplus b\oplus c_{in}$ (odd parity).

The ripple’s critical path (§2). In an $N$-bit ripple-carry adder the worst case is a carry made at bit 0 rippling through every bit’s carry circuit: the delay grows linearly with $N$N.

The 8-bit ripple’s critical path (§2; Lecture15 @ 18:06, redrawn): every bit adds a carry stage. Original figure ↑

The question. To beat the ripple, the carries must be computed without waiting for each other. What do all the faster adders start from?

From the carry to g and p (21:10–34:50)

1. Why parallel adders (21:10–21:44, and again after the seam, 22:30–22:58). They compute the carries in parallel, paying in hardware, power and area. For small adders the ripple is hard to beat: “for like 8-bit adders or so, a ripple carry adder is probably gonna be the fastest implementation” (22:58); beyond that, parallel architectures win. The lecture shows two “historical” ones first, carry bypass and carry select (34:25), then carry lookahead, “the way these adders are really done”.
2. Rewrite the carry (32:17–32:52) board. Factor $c_{in}$ out of two terms of the majority: $c_{out} = ab + c_{in}(a + b)$b). Name the pieces: $g = ab$ab, the generate, and $p = a + b$b, the propagate. Then $c_{out} = g + p\,c_{in}$pcin​.
3. What the names mean (32:52–33:24). If $g = 1$ (both bits 1), the bit makes a carry whatever $c_{in}$ is: it generates one. If $g = 0$ and $p = 1$1, the bit passes $c_{in}$ through: it propagates it. If both are 0, $c_{out} = 0$0: the bit kills the carry.
4. Two choices of propagate (33:24–33:54) board. $p = a + b$ or $p = a\oplus b$b. They differ only at $a = b = 1$1, and there $g = 1$ already makes $c_{out} = 1$1. So the carry comes out right with either.
5. Only $a\oplus b$ gives the sum (34:00–34:22). With $p = a\oplus b$b, the sum is $s = a\oplus b\oplus c_{in} = p\oplus c_{in}$cin​: one more XOR. With $p = a + b$ it fails at $a = b = 1$1, $c_{in} = 0$0: the true sum is 0, but $(a + b)\oplus c_{in} = 1$1. “That’s a very important idea that students often get confused about” (34:22). From here on, $p = a\oplus b$b.

$a\ b$	$g = ab$	$a + b$	$a\oplus b$
00	0	0	0
01	0	1	1
10	0	1	1
11	1	1	0

The PG cell and the carry and sum from it added (equations from Lecture15 @ 33:43 and 34:50). Left: one AND and one XOR turn $a$a, $b$ into $g$ and $p$p. Right: $c_{out} = g + p\,c_{in}$ and $s = p\oplus c_{in}$cin​. Every parallel adder keeps the left half for each bit and replaces the right half’s carry by something faster.

The board (Lecture15 @ 33:43)

Lecture15 @ 33:43Generate and propagate: c_out = g + p c_in, with p = a + b or a ⊕ b.

Fair copy of the board above (Lecture15 @ 33:43), mark for mark in its own layout. One pen wrote the whole board, so the copy is all black. Nothing on the board is hidden: the lecturer’s hand is below "$p = a\oplus b$", and both lines for $p$ are whole. Faint remnants of the wiped bit-stack board are left out.

Generate and propagateboard

$$g = ab,\quad p = a\oplus b,\qquad c_{out} = g + p\,c_{in},\qquad s = p\oplus c_{in}$$

Holds when: the carry holds with p = a + b or p = a ⊕ b; the sum s = p ⊕ c_in needs p = a ⊕ b (the condition is spoken, 34:00–34:22)

Memorize or derive. Memorize all four, with the condition: the carry works for either propagate, the sum only for $a\oplus b$b. The derivation is one line: factor $c_{in}$ out of the majority.

A worked example added. $a = b = c_{in} = 1$1: $g = 1$1, $p = 0$0; $c_{out} = 1 + 0\cdot1 = 1$ and $s = 0\oplus1 = 1$1, so the bit writes 11, which is $1 + 1 + 1 = 3$3. With $p = a + b = 1$ instead, the sum would come out $1\oplus1 = 0$0, wrong.

Trap. Computing $p = a + b$ because an OR is cheaper than an XOR, and then using it for the sum (or, §10, for a bypass).

Check yourself For which inputs do a + b and a ⊕ b differ?

Only for $a = b = 1$1, where the OR is 1 and the XOR is 0.

Check yourself A bit has g = 0 and p = 1, and its c_in rises from 0 to 1. What do c_out and s do?

Step 1: $c_{out} = g + p\,c_{in} = c_{in}$cin​, so it follows, 0 to 1: the bit propagates. Step 2: $s = p\oplus c_{in} = 1\oplus c_{in}$cin​, so it falls, 1 to 0.

10. Carry bypass

You need

Propagate (§9). A bit with $p_i = a_i\oplus b_i = 1$ passes its carry-in straight to its carry-out ($g_i$gi​ is then 0). A group of bits that all have $p_i = 1$ passes its carry-in through all of them.

The PG cell, and the carry and sum from $g$ and $p$ (§9). Original figure ↑

A 2:1 multiplexer (mux; Chapter 10, §7 builds them). Two data inputs and a select: the output copies one input or the other, chosen by the select.

The ripple’s critical path (§2): a carry made at bit 0, rippling through every bit; $(N-1)\,t_c + t_{sum}$ to the top sum.

Stage delays added, all in $\tau_{inv}$τinv​: $t_c$ is one carry stage’s delay (carry-in to carry-out), $t_{sum}$ one sum stage’s, $t_{mux}$ one 2:1 mux’s and $t_{PG}$ one PG cell’s.

The question. If a whole group of bits propagates, its carry-out is simply its carry-in. Can a wire around the group skip the ripple?

The bypass adder (board, 35:16–38:50)

1. One group (35:16–36:29) board. Take a 4-bit group of the ripple adder. If $p_0$ to $p_3$ are all 1, the carry-in will reach the group’s end anyway, through four carry circuits. A mux at the group’s end chooses between the rippled carry-out and the group’s carry-in, carried around the group on a bypass wire; its select is $P = p_3p_2p_1p_0$ board. When $P = 1$ the carry skips the group in one mux delay.
2. Sixteen bits (36:29–37:21). Four groups, each with its bypass mux; the last group’s mux gives $c_{out}$cout​.
3. The critical path (37:21–38:24). A carry that bypasses everything is fast. The slow case starts and ends with a ripple: a carry generated at bit 0 cannot bypass group 0 (with $g_0 = 1$1, $p_0 = 0$0, so $P = 0$0). It ripples through group 0’s four bits and passes group 0’s mux; groups 1 and 2 propagate fully, so it bypasses each in one mux delay; then it ripples through group 3 to the top sum $s_{15}$s15​.
4. The lecturer’s count (38:24): “two ripples through four, and then two mux delays”, against sixteen carry stages. The careful count added adds two details: the path also passes group 0’s mux (the board draws one there), and in group 3 the carry into bit 15 needs only three carry circuits ($c_{12}$c12​ to $c_{15}$c15​), then the sum. With the PG cells first (the select needs the $p_i$pi​, and the carry cells use $g$g, $p$p), the path is $t_{PG} + 4t_c + 3t_{mux} + 3t_c + t_{sum}$tsum​.
5. “Historical” (34:25). Bypass adders are rarely used now, but finding their critical path is the reasoning every faster adder needs.

A 16-bit carry-bypass adder, redrawn from the board (Lecture15 @ 38:48). Each 4-bit group has a mux that passes the group’s carry-in straight on when every bit propagates ($P = p_3p_2p_1p_0 = 1$P=1); the last one gives $c_{out}$cout​. The bypass wires, which the board runs under the groups, are drawn as arcs over them; the board’s own violet arcs mark the critical path. The thick line is the critical path: generated at bit 0, rippling through group 0, through its mux, bypassing groups 1 and 2, and rippling through group 3 to $s_{15}$s15​.

The board (Lecture15 @ 38:48)

Lecture15 @ 38:48Carry bypass: four groups, each with a mux selected by the AND of its propagates; the violet arcs mark the critical path.

Fair copy of the board above (Lecture15 @ 38:48), mark for mark in its own layout. Black is the cyan pen, which drew the adder: four groups of four full adders with a mux at the end of each group, fed by the group’s rippled carry and by its carry-in on the wire under the group. Magenta is the violet pen’s critical path: rippling through the first group, then along two arcs from mux to mux over the second and third groups, then rippling through the last group to the top sum. The board’s tiny FA labels inside the boxes are left out. The title’s first letter is written like a K (†): read “Carry”. The left end, dimmed behind the lecturer here, is read from 38:25.

Carry-bypass delayadded

$$\begin{aligned} t_{bypass} \approx{}& t_{PG} + M\,t_c + \Big(\frac{N}{M} - 1\Big)t_{mux}\\ &+ (M - 1)\,t_c + t_{sum} \end{aligned}$$

Holds when: N bits in groups of M; the worst case generates at bit 0 and ends at the top sum; a carry entering a fully propagating group waits only for its mux; the PG cells come first (the select needs the p_i); p = a ⊕ b

Memorize or derive. Derive it by tracing: ripple out of the first group, one mux per group after that up to the last, ripple into the top bit, one sum.

A worked example added. Take, for example, $t_c = t_{sum} = t_{mux} = 4\,\tau_{inv}$ and $t_{PG} = 2\,\tau_{inv}$2τinv​. Sixteen bits in groups of 4: $2 + 16 + 12 + 12 + 4 = 46\,\tau_{inv}$46τinv​, against the ripple’s $15 \times 4 + 4 = 64\,\tau_{inv}$64τinv​. The lecturer’s round count, $8t_c + 2t_{mux}$2tmux​, gives $40\,\tau_{inv}$40τinv​.

The carry-out added. The same carry, generated at bit 0, reaches $c_{out}$ through all four muxes, with no ripple at the end: $t_{PG} + 4t_c + 4t_{mux} = 2 + 16 + 16 = 34\,\tau_{inv}$34τinv​, sooner than $s_{15}$s15​. The top sum, not the carry-out, sets the clock.

Why the select must use $p = a\oplus b$ added. The lecture allows “A or B, or A XOR B” (35:30); for a bypass, only XOR works. Take $a = 1111$1111, $b = 1000$1000, $c_{in} = 0$0. The true sum is 23, binary 10111, so the group’s carry-out is 1 (bit 3 generates it). With OR-propagate every bit has $a_i + b_i = 1$1, so $P = 1$1, and the mux passes the carry-in, 0: wrong. With XOR-propagate, $p_3 = 1\oplus1 = 0$0, so $P = 0$0, and the mux takes the rippled carry, 1: right. A group with $P = 1$ under XOR has no generating bit, so its carry-out really is its carry-in.

Traps.

• Counting only the skipped groups’ muxes. The path also passes the first group’s mux: three muxes for four groups.
• Taking the bypass path as the critical one. A carry that bypasses every group is the fast case; the slow one starts and ends with a ripple.

Check yourself Which input pattern makes group 1 (bits 4–7) bypass its carry?

$P_1 = p_7p_6p_5p_4 = 1$1: in each of bits 4 to 7 exactly one of $a_i$ai​, $b_i$ is 1 ($a_i\oplus b_i = 1$ai​⊕1).

Check yourself With the example delays, how long does a 64-bit bypass adder in groups of 4 take, and how does that compare with a 64-bit ripple adder?

Step 1: $N/M - 1 = 15$ muxes, so $t = 2 + 16 + 15 \times 4 + 12 + 4 = 94\,\tau_{inv}$94τinv​. Step 2: the ripple takes $63 \times 4 + 4 = 256\,\tau_{inv}$256τinv​. The bypass is still linear in $N$ (one mux per group), but with a slope of $t_{mux}$ per four bits instead of $t_c$ per bit.

11. Carry select

You need

PG and the sum (§9): $g_i = a_ib_i$ai​bi​, $p_i = a_i\oplus b_i$bi​, and the sum $s_i = p_i\oplus c_i$ci​, where $c_i$ is the carry into bit $i$i.

The PG cell, and the carry and sum from $g$ and $p$ (§9). Original figure ↑

A 2:1 multiplexer (Chapter 10, §7): the select picks one of two inputs.

Critical-path reasoning (§10). Follow the slowest signal through the blocks, counting each block it must wait for once; blocks that work at the same time count once together.

Stage delays added, all in $\tau_{inv}$τinv​: $t_c$ is one carry stage’s delay (carry-in to carry-out), $t_{sum}$ one sum stage’s, $t_{mux}$ one 2:1 mux’s and $t_{PG}$ one PG cell’s.

The question. Instead of waiting to learn a group’s carry-in, compute the group’s carries for both possible carry-ins in advance, and choose when the real one arrives. How fast is that?

The select adder (board, 39:24–43:26)

1. One bin of four (39:24–40:30) board. Bits 3–0: a PG generator, then two carry chains fed the same $g$g, $p$p: the “0 carry” chain assumes a carry-in of 0, the “1 carry” chain a carry-in of 1.
2. Select (40:30–41:29) board. A mux on the real $c_{in}$ picks one chain’s carries. This is speculation: half the work is thrown away, “hence the name select”.
3. The sums (41:29–41:49). The sum generator needs only the $p_i$ and the chosen carries (“I don’t need the G’s”), because $p = a\oplus b$ gives $s_i = p_i\oplus c_i$ (§9).
4. Sixteen bits (41:49–42:42) board. Bins 7–4, 11–8 and 15–12 repeat the bin. Each bin’s carry-out, from its mux, is the select of the next bin’s mux; the last mux gives $c_{out}$cout​.
5. The critical path (42:42–43:26). All the bins’ chains run at the same time, right after PG. Then the muxes work in series: bin 0’s mux on $c_{in}$cin​, then bin 1’s on bin 0’s carry-out, and so on. So: PG, one 4-bit chain, four muxes, and the top bin’s sum.

A 16-bit carry-select adder, redrawn from the board (Lecture15 @ 43:39). In every 4-bit bin, two carry chains compute the carries for a carry-in of 0 and of 1, at the same time; a mux, selected by the previous bin’s carry-out, picks one set, and the sum box forms $s_i = p_i\oplus c_i$ci​. The thick line is the critical path: PG, one chain, the four muxes in series, and the top bin’s sum.

The board (Lecture15 @ 43:39)

Lecture15 @ 43:39Carry select: two speculative chains per bin, a mux on the real carry, and the critical path.

Fair copy of the board above (Lecture15 @ 43:39), mark for mark in its own layout. Black is the violet pen: the bins, their blocks (boxes in bin 3–0, D shapes in the others), the muxes and the select chain, and the pale title. Teal is the cyan pen: the title’s underline and the critical path, added last, from bin 3–0’s P/G down into its mux, along the select chain and down through bin 15–12. Two slips are copied as written and marked †: the 1 of “1 carry” is drawn with a hook and reads like a 2 (the quoted input “1” and the speech at 40:14 settle it as 1), and the carry-out at bin 3–0’s mux is written “Cay” for $c_{out}$cout​. Bin 7–4’s upper blocks, washed out by the lecturer’s raised hand here, are copied from 42:40, as is the select wire under the cyan path.

Carry-select delayadded

$$t_{select} \approx t_{PG} + M\,t_c + \frac{N}{M}\,t_{mux} + t_{sum}$$

Holds when: N bits in bins of M; all bins' chains run at once after the PG cells; the muxes work in series, one per bin; p = a ⊕ b for the sums

Memorize or derive. Derive by tracing: one chain (they all run at once), then every mux (they run in series), then one sum.

A worked example added (the same example delays as §10: $t_c = t_{sum} = t_{mux} = 4$4, $t_{PG} = 2\,\tau_{inv}$2τinv​). Sixteen bits in bins of 4: $2 + 16 + 16 + 4 = 38\,\tau_{inv}$38τinv​, against bypass 46 and ripple 64. At 64 bits: $86\,\tau_{inv}$86τinv​, and now the chain of 16 muxes is 64 of those 86. The mux chain is linear in $N$N; a tree (§13) avoids it.

Trap. Counting bin 0’s mux as free because $c_{in}$ is known early. The mux still has to wait for bin 0’s chains to finish before it can pass their carries on.

Check yourself How much hardware does carry select add to a ripple adder, per bin, and what does it buy at 16 bits with the example delays?

Step 1: per bin, a second carry chain and a mux (and the PG cells, if the ripple’s full adders did not have them). Step 2: at 16 bits the delay falls from $64$ to $38\,\tau_{inv}$38τinv​, for roughly twice the carry hardware.

Check yourself At 64 bits the bin size M is free. With the example delays, which M makes t_PG + M t_c + (N/M) t_mux + t_sum smallest, and what is the delay?

Step 1: bigger bins lengthen the one chain on the path ($Mt_c$Mtc​) but shorten the mux chain ($(N/M)t_{mux}$(N/M)tmux​); the sum of the two is least where they are equal, $Mt_c = (N/M)t_{mux}$(N/M)tmux​, so $M = \sqrt{Nt_{mux}/t_c} = \sqrt{64} = 8$8. Step 2: $2 + 32 + 32 + 4 = 70\,\tau_{inv}$70τinv​, against 86 with bins of 4 (and 86 again with bins of 16).

12. Carry lookahead: unrolling the carry

You need

Generate, propagate and the carry (§9). For bit $i$i: $g_i = a_ib_i$ (the bit makes a carry), $p_i = a_i\oplus b_i$ (the bit passes its carry-in on), and the bit’s carry-out is $g_i + p_i$ times its carry-in. The sum is $p_i$ XOR the carry into the bit.

The PG cell and the carry and sum from $g$ and $p$ (§9). Original figure ↑

Carry numbering (this section and §13). $c_i$ is the carry into bit $i$i: $c_0 = c_{in}$cin​, bit 0’s carry-out is $c_1$c1​, and bit $i$‘s carry-out is $c_{i+1}$ci+1​. So $s_i = p_i\oplus c_i$ci​, and a 4-bit group’s carry-out is $c_4$c4​.

The question. Each carry depends on the one before it, which is why it ripples. Can we write every carry directly from the $g$‘s, $p$‘s and $c_{in}$cin​, so that all of them are computed at once?

Unrolling (board, 44:10–47:59)

1. The recursion (44:10–44:52) board. In the new numbering, bit $i$‘s carry-out is $c_{i+1} = g_i + p_ic_i$pi​ci​. Each carry needs the one below it: that is the ripple.

2. Substitute (44:58–46:49) board, “⇒ unroll”. Put each carry into the next:

   $$\begin{aligned} c_1 &= g_0 + p_0c_{in}\\ c_2 &= g_1 + p_1c_1 = g_1 + p_1(g_0 + p_0c_{in})\\ &= g_1 + p_1g_0 + p_1p_0c_{in}\\ c_3 &= g_2 + p_2c_2 = g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_{in}\\ c_4 &= g_3 + p_3c_3\\ &= g_3 + p_3g_2 + p_3p_2g_1 + p_3p_2p_1g_0 + p_3p_2p_1p_0c_{in} \end{aligned}$$

   Every carry is now a sum of products of the $g$‘s, $p$‘s and $c_{in}$cin​: two levels of logic, with no carry waiting for another. Four bits at a time is called radix 4 board.

3. Read each line in words. $c_4$ is 1 if bit 3 generates; or bit 2 generates and bit 3 propagates; or bit 1 generates and bits 3 and 2 propagate; or bit 0 generates and bits 3 to 1 propagate; or $c_{in}$ is 1 and all four bits propagate. Each term is “a carry made here, passed by everything above”.

4. Group generate and propagate (47:15–47:59) board. Each line has the shape $G + P\,c_{in}$Pcin​. The board braces them for $c_2$c2​: $G = g_1 + p_1g_0$ and $P = p_1p_0$p1​p0​; for $c_3$c3​: $G = g_2 + p_2g_1 + p_2p_1g_0$ and $P = p_2p_1p_0$p2​p1​p0​. The group generate $G$ says the group makes a carry by itself; the group propagate $P$ says it passes $c_{in}$ through. They are $g$ and $p$ again, one level up.

The board (Lecture15 @ 48:01)

Lecture15 @ 48:01The unrolled carries c₁ to c₄, radix 4, with the braces for group generate G and group propagate P.

Fair copy of the board above (Lecture15 @ 48:01), mark for mark in its own layout. All black: one blue pen wrote the board (the title and its underline are left from 33:43). $c_4$c4​’s lines lie over the lecturer’s striped shirt here, which washes them out; their terms are read on 47:09, where they are clear, and the G bracket over the second line and the start of the P bracket under the last, new at 48:01, on a frame at 48:15. Two slips are copied as written and marked †: "$p_2p_1s_0$" for $p_2p_1g_0$ and "$p_3s_2$" for $p_3g_2$p3​g2​. The fourth term’s $p_3$ is written over a first attempt. The lines are levelled; on the board they drift down to the right.

Groups of four, and groups of groups

For the four bits added (the bit range in the subscript, high index first):

$$\begin{gathered} G_{3:0} = g_3 + p_3g_2 + p_3p_2g_1 + p_3p_2p_1g_0,\qquad P_{3:0} = p_3p_2p_1p_0,\\ c_4 = G_{3:0} + P_{3:0}\,c_{in}. \end{gathered}$$

The smallest case is two bits added: $c_2 = G_{1:0} + P_{1:0}c_{in}$ with $G_{1:0} = g_1 + p_1g_0$ and $P_{1:0} = p_1p_0$p1​p0​. Read the formula with “bit 1” and “bit 0” replaced by “the upper group” and “the lower group”: the pair generates if the upper part generates, or the lower part generates and the upper part propagates; it propagates if both parts do. That is the radix-2 element:

$$G = G_{hi} + P_{hi}G_{lo},\qquad P = P_{hi}P_{lo}.$$

It combines any two adjacent groups, of any size, into one. Two 2-bit groups give the 4-bit group: $G_{3:2} + P_{3:2}G_{1:0} = (g_3 + p_3g_2) + p_3p_2(g_1 + p_1g_0)$p1​g0​), which is $G_{3:0}$ term by term, and $P_{3:2}P_{1:0} = P_{3:0}$P3:0​. And the carry-in can join as a group of its own below bit 0, with $(G, P) = (c_{in}, 0)$(cin​,0): it “generates” exactly when $c_{in} = 1$ and passes nothing through. Combining bit 0 with it gives $(g_0 + p_0c_{in},\ 0) = (c_1, 0)$(c1​,0): the carry into bit 1. So the carry into any bit is the group generate of everything below it, the carry-in included. Chapter 17’s radix-2 trees, and FN17-8’s adder, are networks of this one element.

The radix-2 element added. Main: it combines an upper group $(G_{hi}, P_{hi})$ and the adjacent lower group $(G_{lo}, P_{lo})$ into one group. Middle: applied to two bits, it gives the two-bit group terms of the board’s $c_2$c2​. Right: with the carry-in entered as the group $(c_{in}, 0)$(cin​,0), it gives the carry $c_1 = g_0 + p_0c_{in}$ and a propagate of 0 (the box’s equations are written inside it).

Lookaheadboard

$$\begin{gathered} c_{i+1} = g_i + p_ic_i,\qquad c_4 = G_{3:0} + P_{3:0}\,c_{in}\\ (G, P) = (G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo}) \end{gathered}$$

Holds when: c_i is the carry into bit i (c₀ = c_in); g_i = a_i b_i, p_i = a_i ⊕ b_i; G and P are what the board's braces mark, P the coefficient of c_in (the radix-2 element is added)

Memorize or derive. Memorize the recursion $c_{i+1} = g_i + p_ic_i$ and the radix-2 element. Derive $c_2$ to $c_4$ by substitution (three lines), and $G_{3:0}$G3:0​, $P_{3:0}$ by reading off the coefficient of $c_{in}$cin​.

A worked example

An added example added: $a = 1011$ (11), $b = 0110$ (6), $c_{in} = 0$0.

bit $i$	3	2	1	0
$a_i$	1	0	1	1
$b_i$	0	1	1	0
$g_i = a_ib_i$	0	0	1	0
$p_i = a_i\oplus b_i$	1	1	0	1
$c_i$ (into bit $i$i)	1	1	0	0
$s_i = p_i\oplus c_i$	0	0	0	1

1011 + 0110 by lookahead

1. PG. Because every carry formula needs only $g$ and $p$p: $g_3g_2g_1g_0 = 0010$ and $p_3p_2p_1p_0 = 1101$1101.
2. The carries, each from its unrolled formula. $c_1 = g_0 + p_0c_{in} = 0 + 1\cdot0 = 0$0. $c_2 = g_1 + \dots = 1$1, since $g_1 = 1$1. $c_3 = g_2 + p_2g_1 + \dots = 0 + 1\cdot1 = 1$1. $c_4 = g_3 + p_3g_2 + p_3p_2g_1 + \dots = 0 + 0 + 1\cdot1\cdot1 = 1$1. None waited for another.
3. The sums. $s_i = p_i\oplus c_i$ci​: 1, 0, 0, 0 from bit 0 up, so $s = 0001$0001, and $c_{out} = c_4 = 1$1. The answer is binary 10001, which is 17, and $11 + 6 = 17$17.
4. The group terms. $G_{3:0} = 1$ (the group makes its own carry, at bit 1, and bits 2 and 3 pass it) and $P_{3:0} = 0$ (bit 1 does not propagate). So $c_4 = 1 + 0\cdot c_{in} = 1$ whatever $c_{in}$ is.

A second case, all-propagate: $a = 1011$1011, $b = 0100$0100, $c_{in} = 1$1. Then $g = 0000$ and $p = 1111$1111, so $G_{3:0} = 0$ and $P_{3:0} = 1$1: the group passes $c_{in}$ straight through. Every carry is 1, $s = 0000$ and $c_{out} = 1$1: binary 10000, which is 16, and $11 + 4 + 1 = 16$16.

Check. The ripple of §2 gives the same carries bit by bit: in the first example bit 0 adds $1 + 0 + 0$ (no carry), bit 1 adds $1 + 1 + 0$ (carry), bit 2 adds $0 + 1 + 1$ (carry), bit 3 adds $1 + 0 + 1$ (carry): $c_1, c_2, c_3, c_4 = 0, 1, 1, 1$0,1,1,1, as in the table. (The page’s test compares the two on all 512 inputs of a 4-bit adder.)

Traps.

• Off by one in the carries. $c_i$ is the carry into bit $i$i, so $s_i = p_i\oplus c_i$ and $c_4$ is the 4-bit group’s carry-out. Wiring $s_i$ from $c_{i+1}$ shifts every sum one place. Past papers number bits differently (FN17-8 counts its bits from 1, with the carry-in at position 0), so settle the numbering before wiring a sum.
• Putting $c_{in}$ inside $P$P. $P$ is the coefficient of $c_{in}$cin​, $p_1p_0$p1​p0​, as the board’s brace marks it (the brace stops at $c_{in}$cin​), so that the carry is $G + P\,c_{in}$Pcin​. Fold $c_{in}$ into $P$ and the group no longer combines with its neighbour by $P = P_{hi}P_{lo}$Phi​Plo​.

Check yourself Write c₃ fully unrolled.

$c_3 = g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_{in}$p2​p1​p0​cin​: a carry made at bit 2, or at bit 1 and passed by bit 2, or at bit 0 and passed by bits 1 and 2, or the carry-in passed by all three.

Check yourself An 8-bit group is two 4-bit groups. Write G_7:0 and P_7:0 with the radix-2 element, say in words when the 8-bit group generates, and evaluate it for (G_7:4, P_7:4) = (0, 1) and (G_3:0, P_3:0) = (1, 0).

Step 1: $G_{7:0} = G_{7:4} + P_{7:4}G_{3:0}$ and $P_{7:0} = P_{7:4}P_{3:0}$P7:4​P3:0​: the byte generates if its upper half generates, or its lower half generates and every bit of the upper half propagates. Step 2: $G_{7:0} = 0 + 1\cdot1 = 1$ and $P_{7:0} = 1\cdot0 = 0$0: the carry made in the lower half passes through the upper half, so the byte’s carry-out is 1 whatever its carry-in.

Check yourself Start from the carry-in as the group (c_in, 0) and apply the radix-2 element twice, first with bit 0 and then with bit 1. What do you get, and what does the order of the combinations do to the delay?

Step 1: $(g_0, p_0)$ with $(c_{in}, 0)$ gives $(g_0 + p_0c_{in},\ 0) = (c_1, 0)$(c1​,0); then $(g_1, p_1)$ with $(c_1, 0)$ gives $(g_1 + p_1c_1,\ 0) = (c_2, 0)$(c2​,0), the board’s $c_2$c2​. Step 2: combined one bit at a time like this, the elements form a chain, one after another: the ripple again. A tree (§13, Chapter 17) combines the same pairs in a different order, so that each carry passes far fewer elements.

13. The radix-4 lookahead unit and the tree adder

You need

Group generate and propagate (§12). Four bits’ carries can be computed at once from their $g_i$gi​, $p_i$ and the carry-in: $c_1 = g_0 + p_0c_{in}$ up to $c_4 = G_{3:0} + P_{3:0}c_{in}$P3:0​cin​, with $G_{3:0} = g_3 + p_3g_2 + p_3p_2g_1 + p_3p_2p_1g_0$ (the group makes a carry) and $P_{3:0} = p_3p_2p_1p_0$ (the group passes $c_{in}$cin​). The same formulas work with groups in place of bits.

The radix-2 element (§12): two adjacent groups make one. Original figure ↑

The PG cell and the sum (§9): each bit makes $g_i = a_ib_i$ and $p_i = a_i\oplus b_i$bi​, and, once its carry $c_i$ is known, $s_i = p_i\oplus c_i$ci​.

The PG cell, and the carry and sum from $g$ and $p$ (§9). Original figure ↑

Stage delays added, all in $\tau_{inv}$τinv​: $t_c$ is one carry stage’s delay (carry-in to carry-out), $t_{sum}$ one sum stage’s, $t_{mux}$ one 2:1 mux’s and $t_{PG}$ one PG cell’s; $t_{LA}$ is the delay through one lookahead unit.

The question. Lookahead computes four carries at once. How do we build a 16-bit or 64-bit adder from it without rippling again?

From one unit to a tree (board, 48:52–54:50)

1. The radix-4 lookahead unit (48:52–50:44) board. One block, “LA (radix-4)”, holds §12’s logic. Below it sit four cells, one per bit. Each cell takes $a_i$ai​, $b_i$ and sends $p_i$pi​, $g_i$ up to the LA; the LA sends each cell its carry $c_i$ back down; the cell gives $s_i$si​. For four bits the critical path is: PG in the cells, the LA, the sum in the cells.
2. Sixteen bits, rippled (50:44–51:38) board. Four units in a row, each unit’s $c_{out}$ into the next unit’s carry-in. It works, but each unit must wait for the one before: the carry ripples again, four bits at a step. “Not great”.
3. A second level (51:38–53:15) board. Each first-level unit can also give its group’s $G$ and $P$P, which do not depend on its carry-in. Put one more LA unit, the same logic, over the four: it takes the four groups’ $(G, P)$ and $c_{in}$ and returns the group carries $c_4$c4​, $c_8$c8​, $c_{12}$ and $c_{out}$cout​, all at once, exactly as the first level returns bit carries.
4. The critical path (53:23–54:07). $a$a, $b$ into the cells (PG); up to the first level ($G$G, $P$P); up to the second level (group carries); back down to the first level, which now has its carry-in and makes the bit carries; down to the cells (sums). This is a tree, radix 4: a tree adder.
5. Counting the LA delays added. Rippled units put $N/4$ LA delays on the path. A tree of $L$ levels puts $2L - 1$1: up through $L$ levels, then back down through $L - 1$ (the top level’s carries go straight out). Sixteen bits: rippled 4, tree 3. Sixty-four bits: rippled 16, tree 5. The tree’s count grows with $\log_4 N$log4​N.
6. What comes next (54:07–54:50). Radix-2 trees, Brent–Kung and Kogge–Stone, built from §12’s two-group element: the next lecture (Chapter 17).

A radix-4 lookahead unit over its four cells, redrawn from the board (Lecture15 @ 51:37, as first drawn at 50:17). Each cell sends its $p_i$pi​, $g_i$ up (labelled on bit 0); the LA returns the carries $c_0$ to $c_3$ (and $c_{out}$cout​) all at once; each cell then forms $s_i = p_i\oplus c_i$ci​. The carry labels are added.

Sixteen bits from four lookahead units in a row, redrawn from the board (Lecture15 @ 51:37). Each unit waits for the carry-out of the one before it: the thick line is the rippled path through $c_4$c4​, $c_8$c8​, $c_{12}$ to $c_{out}$ (labels added), one LA delay per four bits.

The board (Lecture15 @ 51:37)

Lecture15 @ 51:37Four radix-4 lookahead units rippled: the right one with its four cells.

Fair copy of the board above (Lecture15 @ 51:37), mark for mark in its own layout. All black: one blue pen wrote the board (the title and its underline are left from 33:43). The three blocks at the left are the rippled lookahead units, still unlabelled; the lecturer’s arm crosses them here, and every stroke matches 53:45, where he stands clear. Only the right cell is labelled on the board (“p a b g”).

A 16-bit radix-4 lookahead tree, redrawn from the board (Lecture15 @ 53:45; the labels $c_4$c4​, $c_8$c8​, $c_{12}$ are added, and the top unit is drawn wide, with straight wires, where the board draws it narrow with curves). The first-level units send their groups’ $G$G, $P$ up; the second-level unit returns the group carries; each first-level unit then makes its bit carries. The thick line is a critical path: PG, up two levels, down one, and the sum: three LA delays.

The board (Lecture15 @ 54:50)

Lecture15 @ 54:50The radix-4 tree: a second-level LA over four first-level units, and 'radix-2' for next time.

Fair copy of the board above (Lecture15 @ 54:50), mark for mark in its own layout: the 51:37 board grown into a tree. All black: one blue pen (it looks violet towards the left edge, where the light shifts its hue). The title, the ripple arrows between the blocks, and the radix-4 unit’s own $c_{in}$ and $c_{out}$ are erased by now; the unit keeps a stub of its $c_{out}$ wire. The lecturer stands in front of the middle, and his shirt washes out the strokes there: the curves above the third block and the right unit’s left cell are copied from 53:45, where they are clear. The board writes each pair “PG”; they are set as $P$ and $G$G.

Lookahead adders: the LA delays on the pathadded

$$\begin{gathered} t_{tree} \approx t_{PG} + (2L - 1)\,t_{LA} + t_{sum}\\ t_{LA\,rippled} \approx t_{PG} + \frac{N}{4}\,t_{LA} + t_{sum} \end{gathered}$$

Holds when: radix-4 units; L = ⌈log₄ N⌉ levels (the top level only partly filled when N is not a power of 4, as at 8 bits); one t_PG to start and one t_sum to finish

Memorize or derive. Derive both by tracing the board’s path: up $L$ levels for the group terms, down $L - 1$ for the carries. What to memorize is the shape: rippled units are linear in $N$N, a tree is logarithmic.

Comparing the five adders

An added comparison added, with the same example stage delays as §10 and §11 ($t_c = t_{sum} = t_{mux} = 4$tc​=4, $t_{PG} = 2$2) and, for example, $t_{LA} = 10\,\tau_{inv}$ (a radix-4 unit is a two-level gate with up to five-input terms, so slower than one carry stage). These are illustrations of the path counts, not the course’s numbers.

Adder	Critical path	8 bits	16 bits	64 bits
ripple	$(N-1)t_c + t_{sum}$	32	64	256
bypass (groups of 4)	$t_{PG} + 4t_c + (N/4 - 1)t_{mux} + 3t_c + t_{sum}$	38	46	94
select (bins of 4)	$t_{PG} + 4t_c + (N/4)t_{mux} + t_{sum}$	30	38	86
LA units rippled	$t_{PG} + (N/4)t_{LA} + t_{sum}$	26	46	166
radix-4 tree	$t_{PG} + (2L - 1)t_{LA} + t_{sum}$	36	36	56

The five adders’ critical paths added, computed from the path counts with example stage delays $t_c = t_{sum} = t_{mux} = 4$4, $t_{PG} = 2$ and $t_{LA} = 10\,\tau_{inv}$10τinv​. RCA: ripple carry; CBA: carry bypass; CSA: carry select (not the carry-save adder of multipliers); LA×4, LA×16: lookahead units rippled. Left, 16 bits; right, 64 bits. The tree pulls away as $N$ grows; the others are linear in $N$N.

What the numbers say. At 16 bits the tree is fastest ($2 + 30 + 4 = 36\,\tau_{inv}$2+36τinv​), with select close behind (38). At 64 bits the tree takes 56 against 86 for select and 256 for ripple: logarithmic against linear. At 8 bits all five are within a few stage delays of each other (26 to 38), and which one wins depends on the stage delays assumed. That is where the lecturer places the ripple’s limit, “8-bit adders or so”; the example numbers neither confirm nor contradict that rule of thumb.

Check. Count the LA units on the tree’s thick path: the rightmost first-level unit, the second-level unit, the leftmost first-level unit. Three, which is $2L - 1$ with $L = 2$2.

Traps.

• Counting the tree’s levels once. The carries come back down through the first level: $2L - 1$ LA delays, not $L$L.
• Using the second level’s carries as bit carries. They are group carries ($c_4$c4​, $c_8$c8​, $c_{12}$c12​); the first-level units still turn them into the carries of each bit.

Check yourself How many radix-4 lookahead units does a 64-bit tree need, and how many levels?

16 units over the bits, 4 over those, 1 at the top: 21 units in 3 levels.

Check yourself With the example delays, at what width does the radix-4 tree first beat the ripple adder: 4, 8 or 16 bits?

Step 1: at 4 bits the tree is one unit: $2 + 10 + 4 = 16$16, and the ripple $3 \times 4 + 4 = 16$16: a tie. Step 2: at 8 bits the tree needs two levels, $2 + 30 + 4 = 36$36, against the ripple’s 32: slower. At 16 bits the tree still has two levels, 36, against 64: it wins from 16 bits.

On the exam

Adders carry little direct weight in the past finals. One part is new to this chapter, FN17-8 (15 points), which it shares with Chapter 17; the others are already solved elsewhere in the guide, and this chapter supplies the adder background they lean on.

Part	Points	What it asks	Sections
FN17-8	15	an 8-bit parallel adder built from PG generators, radix-2 lookahead elements and sum generators, and its critical path	§9, §12 (the radix-2 element and the $(c_{in}, 0)$ entry), §13; the prefix network in Chapter 17
FN19-3a–d	39	a static ripple-carry chain: delay, energy, best width	§7 (it is this chain, held in propagate), §5
FN12-10b	9	a full adder in NP domino, $Z = ABC + \bar Y(A + B + C)$	§4 (the sum identity), §1
MT24-5a	15	the Sum and Carry of a dynamic full adder	§1, §4
MT23-2b, HW4-3b	16, —	carry and XOR in pass-transistor and CPL logic	§1

FN17-8 is solved, with its own figure and key, on the datapath practice page (FD1). What this chapter prepares: the three kinds of block are §9’s PG cell, §12’s radix-2 element and §9’s sum $s_i = p_i\oplus c_i$ci​; the carry into each bit is the group generate of everything below it, with the carry-in entered as $(c_{in}, 0)$ (§12); and the critical path runs up the network and out through a sum (§13). Chapter 17 adds the radix-2 network itself. At the finals’ pace of 0.7–0.9 minutes a point, it is a 10–14 minute part.

Memorize.

• $c_{out} = ab + bc_{in} + ac_{in}$ (majority) and $s = a\oplus b\oplus c_{in}$ (odd parity).
• Self-dual: $\bar f(a, b, c) = f(\bar a, \bar b, \bar c)$f(aˉ,bˉ,cˉ); both outputs have it, so each gate’s pull-up can mirror its pull-down. $s = abc_{in} + \overline{c_{out}}(a + b + c_{in})$cin​).
• The late input, $c_{in}$cin​, goes next to the output.
• $g = ab$ab, $p = a\oplus b$ (not $a + b$b, for the sum or a bypass); $c_{out} = g + p\,c_{in}$pcin​; $s = p\oplus c_{in}$cin​.
• $c_{i+1} = g_i + p_ic_i$pi​ci​, with $c_i$ the carry into bit $i$i; two groups combine as $(G_{hi} + P_{hi}G_{lo},\ P_{hi}P_{lo})$Phi​Glo​, Phi​Plo​).
• Each architecture’s critical path in words: ripple (every carry), bypass (ripple, muxes, ripple), select (one chain, every mux), tree (up, down, sum).

Derive (with the path).

• The unrolled carries. Substitute $c_{i+1} = g_i + p_ic_i$ into itself three times; read $G$ and $P$ as the terms without and with $c_{in}$cin​.
• The radix-2 element. The two-bit case $c_2 = g_1 + p_1g_0 + p_1p_0c_{in}$p1​p0​cin​, with groups in place of bits.
• The carry chain per bit. Gains $g\cdot h$ from the loads: without inverters $2 \times 12/6 = 4$4; with an inverter of size $x$x, $x + 2 + 2/x \ge 2 + 2\sqrt2$22​; the next sum stage’s load decides.
• The critical-path counts of ripple, bypass, select, rippled lookahead and the tree, by tracing.

Method card. The playbook’s adder-architecture card: recognize a block diagram of PG, lookahead and sum blocks, or “draw the critical path”; moves PG, then carries as $G + Pc$Pc, then sums $p\oplus c$c, marking the path up and down the tree; traps, the carry index and $p = a\oplus b$b.

The lecture’s boards

The boards of Lecture 15 used in this chapter (25 frames)

Lecture15 @ 00:33 Lecture 15: datapath/dataflow, adders

Lecture15 @ 03:23 the full adder and its truth table

Lecture15 @ 03:52 majority and odd parity

Lecture15 @ 06:25 the ripple chain being drawn

Lecture15 @ 09:32 ripple carry, its critical path, a − b

Lecture15 @ 11:45 self-dual

Lecture15 @ 16:06 the transistor-level full adder

Lecture15 @ 18:06 c_in next to the output; the 8-bit chain; the sum identity

Lecture15 @ 20:15 the inverterless chain being drawn

Lecture15 @ 21:39 inverters crossed out; the inverterless chain

Lecture15 @ 22:39 the second take: a clean board

Lecture15 @ 25:22 the bit stack

Lecture15 @ 27:07 bit pitch and routing tracks

Lecture15 @ 30:26 the ripple-carry adder in a bit stack

Lecture15 @ 33:43 generate and propagate

Lecture15 @ 34:50 p = a + b or a ⊕ b

Lecture15 @ 38:48 carry bypass and its critical path

Lecture15 @ 42:40 carry select before the critical path

Lecture15 @ 43:39 carry select and its critical path

Lecture15 @ 47:09 the unrolled carries, c₄ uncovered

Lecture15 @ 48:01 group generate and propagate; radix-4

Lecture15 @ 50:17 one radix-4 LA unit with one cell

Lecture15 @ 51:37 four LA units rippled

Lecture15 @ 53:45 the radix-4 tree

Lecture15 @ 54:50 tree (radix-4); radix-2 next