By the end of this chapter you should be able to:
- Derive the half-adder and full-adder equations from their truth tables and justify why \(S = A \oplus B \oplus C_{in}\) cannot be simplified further.
- Build a full adder from two half adders and an OR gate, and explain why the two-level carry expression is preferred when the adder is to be cascaded.
- Compute the worst-case propagation delay of an \(n\)-bit ripple-carry adder from stated gate delays, and hence its maximum operating frequency.
- Define the carry generate and carry propagate functions and use them to write the carry recurrence.
- Expand the recurrence into the four look-ahead carry equations, state the resulting delay and gate count, and explain why a 16-bit look-ahead adder is built in blocks.
- Design a controlled adder–subtractor using exclusive-OR gates and the 2's-complement rule of Chapter 3.
- Detect signed overflow with \(V = C_n \oplus C_{n-1}\) and distinguish it from an unsigned carry-out.
Everything so far has been about expressing a required behaviour and then reducing it to the fewest gates. This part of the course changes the question. The blocks in Chapters 16 to 20 are the ones a datapath is actually assembled from, and for each of them the interesting design decision is no longer how few gates but how few gate delays. The adder is the clearest case. A four-bit adder can be built from twenty-four gates and it will give the right answer; the trouble is that it will take eighty nanoseconds to do so, and nothing in Chapter 8 tells you why, or what to do about it.
The reason is the carry. Bit 3 of a sum cannot be computed until the carry out of bit 2 is known, which needs the carry out of bit 1, which needs the carry out of bit 0. That chain is the only place in a combinational circuit where the number of gate levels grows with the width of the operands, and it is what sets the clock rate of a simple processor. This chapter builds the adder from its truth table, measures the damage the carry chain does, and then removes it by computing every carry directly from the operands — the carry-look-ahead idea, which is the single most important trick in arithmetic hardware. It closes by turning the same adder into a subtractor with four exclusive-OR gates and the two's-complement rule from Chapter 3, and by detecting the overflow that rule makes possible.
1 The Half Adder
Chapter 3 set out the four one-bit additions: \(0+0=0\), \(0+1=1\), \(1+0=1\) and \(1+1=10\). The last of these is the only awkward one, because a two-bit answer will not fit in a one-bit output. It forces any adder to have two outputs — a sum bit of the same weight as the operands, and a carry bit of twice that weight. Writing that out as a truth table gives the whole specification of the circuit:
| \(A\) | \(B\) | \(A+B\) in binary | Carry \(C\) | Sum \(S\) |
|---|---|---|---|---|
| 0 | 0 | 00 | 0 | 0 |
| 0 | 1 | 01 | 0 | 1 |
| 1 | 0 | 01 | 0 | 1 |
| 1 | 1 | 10 | 1 | 0 |
Both columns are recognisable. The sum column is 0, 1, 1, 0 — the exclusive-OR of Chapter 5 — and the carry column is 0, 0, 0, 1, which is AND:
Two gates. The XOR contributes the addition proper and the AND detects the one case that overflows a single bit.
This circuit is called a half adder, and the name is a warning rather than a description of size: it adds two bits and nothing else. In a multi-bit addition every column except the least significant has three bits to add — the two operand bits and the carry arriving from the column to its right — and a half adder has nowhere to put that third input. Even at bit 0 designers usually fit a full adder, so that the carry input can be driven for subtraction as Section 6 needs.
Fix the cost now, because everything later is measured against it. In NAND-only form, following the conversion of Chapter 10, an exclusive-OR costs four NAND gates and the AND costs two, so a half adder is six NAND gates — one and a half 7400 packages.
2 The Full Adder
A full adder accepts the third bit. Its inputs are the two operand bits \(A\) and \(B\) and the carry \(C_{in}\) coming from the next lower column; its outputs are the sum \(S\) and the carry \(C_{out}\) passed on to the next higher column. Because the three inputs are simply added, the truth table is a list of the values of \(A + B + C_{in}\), written in two bits:
| \(m\) | \(A\) | \(B\) | \(C_{in}\) | Sum of inputs | \(C_{out}\) | \(S\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 2 | 0 | 1 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 2 | 1 | 0 |
| 4 | 1 | 0 | 0 | 1 | 0 | 1 |
| 5 | 1 | 0 | 1 | 2 | 1 | 0 |
| 6 | 1 | 1 | 0 | 2 | 1 | 0 |
| 7 | 1 | 1 | 1 | 3 | 1 | 1 |
So \(S = \Sigma m(1,2,4,7)\) and \(C_{out} = \Sigma m(3,5,6,7)\). Plot the sum on a three-variable K-map and nothing happens: minterms 1, 2, 4 and 7 have codes 001, 010, 100 and 111, and no two of them differ in a single bit, so there is not one adjacent pair on the whole map. The canonical form is already minimal, and the only reduction available is the algebraic one that recognises the parity pattern:
The sum bit is 1 whenever an odd number of the three inputs is 1. That is the definition of odd parity, and it is why exclusive-OR trees reappear in Chapter 17 as parity generators — a parity circuit and the sum output of an adder are the same function.
The carry map is more obliging. Minterms 3, 5, 6 and 7 give three overlapping pairs — \((3,7)\), \((5,7)\) and \((6,7)\) — and no larger group, so all three are prime implicants, all three are essential, and
A carry is produced whenever at least two of the three inputs are 1 — the majority function of three variables.
There is a second, equally valid form of the carry. Since \(AC_{in} + BC_{in} = (A+B)C_{in}\), and since the case \(A = B = 1\) is already covered by the \(AB\) term, the OR may be replaced by an exclusive-OR without changing the function:
This second form is what makes a full adder out of two half adders. The first half adder produces \(S_1 = A \oplus B\) and \(C_1 = AB\); the second adds \(C_{in}\) to \(S_1\), producing the final sum \(S = S_1 \oplus C_{in}\) and a second carry \(C_2 = S_1 C_{in}\); and an OR gate merges the two carries, since the two half adders can never both produce a carry at once. Figure 16.1 shows the result.
The two carry expressions are logically identical but they are not electrically identical, and which one you build matters. In the two-half-adder circuit of Figure 16.1 the path from \(A\) or \(B\) to \(C_{out}\) runs XOR \(\to\) AND \(\to\) OR, three levels; in the two-level form \(AB + AC_{in} + BC_{in}\) every input reaches \(C_{out}\) through one AND and one OR, two levels. The path that matters in a cascade is the one from \(C_{in}\) to \(C_{out}\), and that is two levels in both. The analysis in the next section therefore uses the two-level carry and a pair of exclusive-ORs for the sum, which is what a 7483 or 74LS283 actually contains.
Counting gates for the two-level version: two exclusive-ORs for the sum, three two-input ANDs and one three-input OR for the carry — six gates per bit, and the figure of six gates per full adder is used throughout this chapter and the next.
3 The Ripple-Carry Adder and Its Delay
An \(n\)-bit parallel adder is \(n\) full adders side by side, the carry output of each wired to the carry input of the next. All \(2n\) operand bits are applied at once, which is why it is called parallel; the carries are not parallel at all but appear one after another from right to left, which is why it is called ripple-carry. Figure 16.2 shows the four-bit version, the circuit inside a 74LS283.
To put a number on the delay we need a gate model, stated once and used consistently for the rest of the chapter.
Take \(\Delta = 10\ \text{ns}\) for any basic gate — AND, OR, NAND, NOR or inverter — which is close to the 74LS figure of 9.5 ns quoted in Chapter 12. An exclusive-OR is two levels of basic gates internally, so take it as \(2\Delta = 20\ \text{ns}\). Counting levels this way is what makes a hand analysis portable: change \(\Delta\) and every result below scales. All the figures quoted are worst-case, not the average \(t_{pd}\) of a data sheet.
Now follow the carry. Every full adder produces \(C_{out}\) from all three of its inputs through one AND level and one OR level, so once its inputs are stable the carry appears \(2\Delta\) later. At bit 0 all three inputs — \(A_0\), \(B_0\) and \(C_0\) — are applied at \(t = 0\), so
The sum bits are cheaper but they wait on the same carries. \(S_i = (A_i \oplus B_i) \oplus C_i\); the first exclusive-OR is ready at \(2\Delta\), which for every bit above the least significant is earlier than \(C_i\) arrives, so the second exclusive-OR starts as soon as the carry lands and \(t(S_i) = 2i\Delta + 2\Delta\). The last sum bit is therefore ready at \(t(S_{n-1}) = 2n\Delta\), at exactly the same moment as the final carry-out. The worst case for the whole adder is
Linear in the word length. Doubling the width doubles the time, which is the defining weakness of the circuit.
With \(\Delta = 10\ \text{ns}\):
Figure 16.2 marks the intermediate carries: \(C_1\) at 20 ns, \(C_2\) at 40 ns, \(C_3\) at 60 ns and \(C_4\) at 80 ns. If the adder feeds a register clocked on the same edge that presents the operands, the clock period cannot be shorter than this, so the four-bit unit is limited to
A 32-bit ripple adder would need 640 ns and run below 1.6 MHz. That is the reason no machine with a word longer than about eight bits has ever used plain ripple carry in its main adder.
The worst case is not a rare pathological input. Take \(A = \) 0001 and \(B = \) 1111: bit 0 generates a carry, and every bit above it has \(A_i \neq B_i\), so each one passes the incoming carry on without being able to decide anything itself. The carry travels the full width and the answer 10000 is not correct until 80 ns have passed.
Note also that the adder is wrong during that 80 ns, not merely late: \(S_3\) changes several times as successive carries arrive, exactly the multiple-transition behaviour Chapter 11 called a dynamic hazard. Nothing downstream may sample the sum until the worst case has elapsed.
4 Carry Generate and Carry Propagate
The delay comes entirely from the recurrence \(C_{i+1} = f(A_i, B_i, C_i)\): each carry is defined in terms of the one below it, so the hardware must evaluate them in order. To escape, factor the carry equation so that the dependence on \(C_i\) sits in one term:
The two coefficients depend only on the operand bits at position \(i\), and each has a plain physical meaning. Define
Bit \(i\) generates a carry when both its operand bits are 1, in which case a carry leaves that position whatever arrives at it. Bit \(i\) propagates a carry when exactly one of its operand bits is 1, in which case a carry leaves the position if and only if one entered it.
With these the carry recurrence becomes
and the sum is \(S_i = P_i \oplus C_i\), so \(P_i\) is used twice and costs nothing extra. Both \(G_i\) and \(P_i\) are available \(2\Delta\) after the operands are applied — \(\Delta\) for the AND, \(2\Delta\) for the exclusive-OR — and, crucially, they are available for every bit position at that same instant, because none of them involves a carry.
For carry purposes \(P_i = A_i + B_i\) would serve equally well, since the two definitions differ only when \(A_i = B_i = 1\), and there \(G_i = 1\) forces \(C_{i+1} = 1\) anyway. The exclusive-OR is preferred because the sum bit needs it in any case.
\(G_i\) and \(P_i\) depend only on \(A_i\) and \(B_i\), so the whole adder can compute them in parallel in two gate delays. Everything that remains — the entire serial part of the problem — is contained in the single recurrence \(C_{i+1} = G_i + P_i C_i\), which is now short enough to unroll by hand.
The same two functions can be defined for a whole block of bits rather than one. A four-bit block generates a carry if any bit in it generates one that the bits above it propagate, and propagates a carry only if every one of its bits does:
These group functions let a second layer of look-ahead treat a whole four-bit slice exactly as the first layer treats a single bit. Section 5 uses them to build the 16-bit adder.
5 Carry-Look-Ahead
Unrolling \(C_{i+1} = G_i + P_i C_i\) removes the recursion. Substituting each carry into the next, for four bits:
Each equation reads as a sentence: a carry leaves bit \(i\) if bit \(i\) generates one, or if some lower bit generates one and every bit between propagates it, or if the carry into the adder is 1 and every bit propagates it.
Every one of these is a sum of products of \(P\)s, \(G\)s and \(C_0\) — two gate levels, no carries on the right-hand side. Figure 16.3 draws the network for \(C_3\); the other three have the same shape with fewer or more terms.
The timing follows immediately. \(P\) and \(G\) are ready at \(2\Delta\); one AND level and one OR level bring every carry out together at \(4\Delta\); and each sum bit is one more exclusive-OR beyond its carry:
Independent of \(i\). The 60 ns is the delay of a four-bit look-ahead adder, and it would still be 60 ns if the block were eight bits wide.
Against 80 ns for the four-bit ripple adder that is a speed-up of only 1.33, which is a fair warning that look-ahead is not worth the trouble at four bits alone. Its value appears when the blocks are stacked, because the ripple figure keeps growing and the look-ahead figure does not.
The cost is gates and, worse, fan-in. Building all \(n\) carries of an \(n\)-bit block this way needs \(1+2+\dots+n = n(n+1)/2\) AND gates and \(n\) OR gates, and the widest of them has \(n+1\) inputs:
| Block width \(n\) | AND gates | OR gates | Largest fan-in | Verdict |
|---|---|---|---|---|
| 4 | 10 | 4 | 5 | routine |
| 8 | 36 | 8 | 9 | possible, rarely done |
| 16 | 136 | 16 | 17 | not buildable in practice |
A 17-input gate does not exist in any standard family, and Chapter 12 gives the reason: fan-in costs delay, because each extra input adds capacitance and, in TTL, another series transistor. That is why four bits is the near-universal block size and why the 74182 look-ahead carry generator is a four-bit part. Wider adders are built by stacking blocks.
(a) Plain ripple carry. From Worked Example 16.1, \(2 \times 16 \times \Delta = 32\Delta = 320\ \text{ns}\).
(b) Four 4-bit look-ahead blocks, carry rippled between them. Inside a block the path from the block's carry-in to its carry-out is the single AND–OR pair of the \(C_4\) equation, so it costs \(2\Delta\) once \(P\) and \(G\) are ready. Block 0 delivers \(C_4\) at \(4\Delta\); each further block adds \(2\Delta\), giving \(C_8\) at \(6\Delta\), \(C_{12}\) at \(8\Delta\) and \(C_{16}\) at \(10\Delta\). The internal carries of the last block appear \(2\Delta\) after \(C_{12}\), at \(10\Delta\), and its sum bits one exclusive-OR later:
(c) Four 4-bit blocks with a second level of look-ahead. Each block also emits its group functions \(P_G\) and \(G_G\); \(P_G\) is a four-input AND of the \(P\)s, ready at \(3\Delta\), and \(G_G\) is an AND–OR network ready at \(4\Delta\). A 74182 then applies the same four equations one level up and produces \(C_4, C_8, C_{12}\) and \(C_{16}\) together at \(4\Delta + 2\Delta = 6\Delta\). The last block's internal carries follow at \(8\Delta\) and its sums at:
| 16-bit organisation | Gate delays | Time | Speed-up | \(f_{max}\) |
|---|---|---|---|---|
| Ripple carry | 32 | 320 ns | 1.00 | 3.13 MHz |
| 4 \(\times\) 4-bit CLA, carries rippled | 12 | 120 ns | 2.67 | 8.33 MHz |
| 4 \(\times\) 4-bit CLA + 74182 | 10 | 100 ns | 3.20 | 10.0 MHz |
Most of the benefit — 2.67 of the 3.2 — comes from simply using look-ahead blocks at all. The second-level generator buys the last 20 ns, and on a 64-bit adder, where four second-level blocks would themselves be rippled, its contribution is much larger.
The gate count moves the other way, though not by much at four bits: the ripple adder is \(4 \times 6 = 24\) gates, and the look-ahead adder is four exclusive-ORs for \(P\), four ANDs for \(G\), ten ANDs and four ORs in the carry network and four exclusive-ORs for the sums — 26 gates. Blocking is what keeps that cost linear in the word length while the delay stays nearly constant.
6 The Adder–Subtractor
Chapter 3 established that in 2's-complement arithmetic subtraction is not a separate operation. To form \(A - B\), take the 2's complement of \(B\) — complement every bit and add one — and then add:
Both of the things that need doing are already available in the adder. The \(+1\) is just \(C_0 = 1\), an input that is otherwise tied low; and complementing \(B\) under the control of a single line is exactly what an exclusive-OR gate does. From the truth table of Chapter 5,
An exclusive-OR with one input used as a control is a controlled inverter: it passes the other input unchanged or inverted, according to the control. This is the second of the three standard uses of XOR in this course, the others being parity (Chapter 17) and equality detection (also Chapter 17).
So take one mode line \(M\), feed each \(B_i\) through an exclusive-OR whose other input is \(M\), and connect \(M\) to \(C_0\) as well. Figure 16.4 shows the four-bit circuit: four exclusive-OR gates added to the adder of Figure 16.2 and one wire.
With \(M = 0\) each gate passes \(B_i\) and \(C_0 = 0\), so the circuit computes \(A + B\). With \(M = 1\) each gate delivers \(B_i'\) and \(C_0 = 1\), so it computes \(A + \overline{B} + 1 = A - B\). One control line, four gates, no separate subtractor and no borrow logic anywhere.
\(11 - 6\). \(A = \) 1011, \(B = \) 0110, \(M = 1\). The exclusive-ORs deliver \(\overline{B} = \) 1001 and \(C_0 = 1\):
Discard \(C_4 = 1\); the answer is 0101 \(= 5\), which is correct.
\(6 - 11\). \(A = \) 0110, \(B = \) 1011, \(M = 1\), so \(\overline{B} = \) 0100:
Here \(C_4 = 0\) and the result is 1011, which read as a 2's-complement number is \(-5\). Again correct.
The two examples show what \(C_4\) means during a subtraction, and it is the opposite of what a beginner expects. Treating the operands as unsigned, \(C_4 = 1\) means no borrow was needed — that is, \(A \geq B\) — and \(C_4 = 0\) means a borrow was needed and the result printed as an unsigned number is wrong by \(2^4\). The carry-out of a 2's-complement subtractor is the complement of the borrow, which is why processors that expose a borrow flag invert \(C_n\) before storing it.
Two practical points. The exclusive-ORs sit in front of the adder and add \(2\Delta\), so the four-bit adder–subtractor takes 100 ns rather than 80 ns; quoting only the adder's figure undershoots. And the same arrangement extends into an arithmetic logic unit — replace each exclusive-OR by a function-select network and the block performs a chosen operation from a table of them, which is the subject of Chapter 20.
7 Overflow Detection
The circuit of Figure 16.4 does not know whether the patterns applied to it are meant to be unsigned or 2's-complement signed numbers; it adds \(n\)-bit patterns and produces an \(n\)-bit pattern plus a carry. Whether the answer is usable depends on the interpretation, and the two interpretations fail in different ways — which is why every ALU carries two flags.
- For unsigned operands the answer is wrong when it will not fit in \(n\) bits, which is precisely when \(C_n = 1\). The carry-out is the unsigned overflow flag.
- For signed operands the range is \(-2^{n-1}\) to \(2^{n-1}-1\), and \(C_n\) says nothing useful: adding \(-1\) to \(-1\) produces \(C_4 = 1\) with a perfectly correct answer, while adding \(+7\) to \(+3\) produces \(C_4 = 0\) with a badly wrong one.
Chapter 3 gave the rule in words: signed overflow occurs when two operands of the same sign produce a result of the opposite sign, and can never occur when the operands have opposite signs. Turning that into a gate needs one observation about the most significant column. That column adds \(A_{n-1}\), \(B_{n-1}\) and \(C_{n-1}\), and produces \(S_{n-1}\) and \(C_n\). If \(C_{n-1}\) and \(C_n\) are equal, the sign column has behaved consistently and the sign bit of the result is the sign the arithmetic demands. If they differ, a carry has been absorbed into or emitted from the sign position without a matching one on the other side, and the sign bit has been corrupted:
One exclusive-OR gate on two signals the adder already produces internally. That is the entire cost of signed overflow detection, and it is why the flag is universal.
The equivalent form written directly in terms of the sign bits is
which says the same thing: two negatives giving a positive, or two positives giving a negative. Checking all 256 four-bit additions confirms that the two expressions agree with each other and with the arithmetic definition on every one of them. The first form is cheaper by three gates, but the second is the one to use if the internal carries are not brought out of the package.
| Operation | \(A\) | \(B\) | \(S\) | \(C_3\) | \(C_4\) | \(V\) | Signed reading | Unsigned reading |
|---|---|---|---|---|---|---|---|---|
| \(+7 + 3\) | 0111 | 0011 | 1010 | 1 | 0 | 1 | \(-6\): wrong | \(10\): correct |
| \(+5 + 4\) | 0101 | 0100 | 1001 | 1 | 0 | 1 | \(-7\): wrong | \(9\): correct |
| \(-8 + (-1)\) | 1000 | 1111 | 0111 | 0 | 1 | 1 | \(+7\): wrong | \(23\): wrong |
| \(-1 + (-1)\) | 1111 | 1111 | 1110 | 1 | 1 | 0 | \(-2\): correct | \(30\): wrong |
Row 1: \(7 + 3 = 10\), which is outside the signed range \(-8 \ldots +7\), and indeed \(C_4 \neq C_3\) so \(V = 1\) — yet \(C_4 = 0\), so an unsigned machine sees no problem and is right not to. Row 4 is the mirror image: \(C_4 = 1\) flags an unsigned overflow, but \(C_4 = C_3\) so \(V = 0\) and the signed answer \(-2\) is perfectly correct. The two flags are independent, and reading one as the other is the most common single mistake in this part of the subject.
Overflow during subtraction is caught by the same gate, because the circuit really is performing an addition — of \(A\) and \(\overline{B}+1\) — and the sign rule applies to whatever two numbers are actually added. No mode-dependent logic is needed, which is one more reason 2's complement is the representation every machine uses.
8 Summary and Key Results
| Block | Defining equations | Cost and delay |
|---|---|---|
| Half adder | \(S = A \oplus B\), \(C = AB\) | 2 gates; no carry input, so usable only at bit 0 |
| Full adder | \(S = A \oplus B \oplus C_{in}\), \(C_{out} = AB + AC_{in} + BC_{in}\) | 6 gates; \(C_{in} \to C_{out}\) is 2 gate levels |
| Full adder from two half adders | \(C_{out} = AB + (A \oplus B)C_{in}\) | Same function; \(A,B \to C_{out}\) becomes 3 levels |
| Ripple-carry adder, \(n\) bits | \(C_{i+1} = G_i + P_iC_i\) evaluated in order | \(6n\) gates, \(2n\Delta\); 80 ns at 4 bits, 320 ns at 16 |
| Generate and propagate | \(G_i = A_iB_i\), \(P_i = A_i \oplus B_i\) | Both ready at \(2\Delta\) for every bit at once |
| 4-bit carry-look-ahead | \(C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0\) | 26 gates, all carries at \(4\Delta\), sums at \(6\Delta\) = 60 ns |
| 16-bit look-ahead in blocks | Group \(P_G = P_3P_2P_1P_0\), \(G_G = G_3 + P_3G_2 + \ldots\) | 120 ns rippled between blocks, 100 ns with a 74182 |
| Adder–subtractor | \(B_i \oplus M\) into the adder, \(C_0 = M\) | \(n\) extra XOR gates and \(2\Delta\) extra delay |
| Overflow flag | \(V = C_n \oplus C_{n-1}\) | One gate; independent of the unsigned carry-out |
9 Common Mistakes
A half adder has two inputs, and every column of a multi-bit addition except the least significant has three bits to add. Wiring half adders in a row produces a circuit that discards each carry as it is formed, so it computes the bitwise exclusive-OR of the two operands and not their sum — and it gives the right answer whenever no carry happens to occur, which is exactly what makes the fault hard to find on the bench. If a stage has a carry arriving at it, it needs a full adder.
The carry path through a full adder is one AND level and one OR level, not one gate, so an \(n\)-bit ripple adder costs \(2n\Delta\) and not \(n\Delta\). The same slip in reverse is to add up the average \(t_{pd}\) from the front of a data sheet: Chapter 12 showed that \(t_{PLH}\) and \(t_{PHL}\) differ, and a worst-case timing analysis must use the larger figure at every stage of the critical path. Both errors make a design look comfortably fast on paper and fail at the clock rate you chose because of it.
\(C_n\) is the unsigned overflow indicator and \(V = C_n \oplus C_{n-1}\) is the signed one, and Worked Example 16.4 shows additions where each is 1 while the other is 0. A related slip belongs to subtraction: on a 2's-complement adder–subtractor \(C_n = 1\) means no borrow was required, so the carry-out must be inverted before it is reported as a borrow.
10 Chapter Review
1. Show that \(AB + AC_{in} + BC_{in}\) and \(AB + (A \oplus B)C_{in}\) are the same function, and explain why the two circuits nevertheless behave differently in a ripple-carry adder.
Expand the second: \(AB + (AB' + A'B)C_{in} = AB + AB'C_{in} + A'BC_{in}\). Compare with the first, \(AB + AC_{in} + BC_{in} = AB + (A B + AB')C_{in} + (AB + A'B)C_{in} = AB + ABC_{in} + AB'C_{in} + A'BC_{in}\); the extra term \(ABC_{in}\) is absorbed by \(AB\) under \(X + XY = X\), so the two expressions are equal on all eight input combinations. They differ in structure: the first is two levels from every input, so \(A, B \to C_{out}\) costs \(2\Delta\); the second contains an exclusive-OR in the path, so \(A, B \to C_{out}\) costs \(2\Delta + 2\Delta = 4\Delta\). In a cascade the critical path is \(C_{in} \to C_{out}\), which is \(2\Delta\) in both, so the difference only shows at bit 0 — but a designer who builds every stage from two half adders and then quotes \(2n\Delta\) has understated the first stage.
2. An 8-bit ripple-carry adder is built in 74LS, for which we take \(\Delta = 10\ \text{ns}\) and an exclusive-OR as \(2\Delta\). Find the worst-case delay, the maximum clock rate, and the input pattern that produces the worst case.
Each stage adds \(2\Delta\) to the carry, so \(t(C_8) = 2 \times 8 \times 10 = 160\ \text{ns}\). The last sum bit, \(S_7 = P_7 \oplus C_7\), is ready at \(2 \times 7 \times 10 + 20 = 160\ \text{ns}\) as well, so the adder settles at 160 ns and \(f_{max} = 1/160\ \text{ns} = 6.25\ \text{MHz}\). The worst case needs bit 0 to generate a carry and every higher bit to propagate it, so \(A_0 = B_0 = 1\) and \(A_i \neq B_i\) for \(i \geq 1\): for instance \(A = \)
00000001with \(B = \)11111111, or \(A = \)10101011with \(B = \)01010101. Note that halving the width to four bits would double the clock rate to 12.5 MHz — the delay is linear in \(n\).3. Write the look-ahead expression for \(C_3\), state how many gates it needs and at what time it is valid, and compare that with the time \(C_3\) becomes valid in a ripple-carry adder.
\(C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0\), which is one 2-input AND, one 3-input AND, one 4-input AND and one 4-input OR — four gates, drawn in Figure 16.3. \(P\) and \(G\) are ready at \(2\Delta\), the AND level finishes at \(3\Delta\) and the OR at \(4\Delta\), so \(C_3\) is valid 40 ns after the operands. In the ripple adder \(C_3\) is the third carry in the chain and is valid at \(2 \times 3 \times \Delta = 60\ \text{ns}\). The gap widens with position: \(C_1\) is 20 ns either way, but by \(C_4\) it is 40 ns against 80 ns, and in an eight-bit block it would be 40 ns against 160 ns.
4. A 4-bit adder\u2013subtractor is given \\(A = \\)
1101and \\(B = \\)0101with \\(M = 1\\), and then \\(A = \\)1010with the same \\(B\\) and \\(M\\). Trace the carries in each case and state \\(C_4\\) and \\(V\\).Read as signed numbers the two operations are \\(-3-5\\) and \\(-6-5\\). In both, the exclusive-ORs deliver \\(\\overline{B} = \\)
1010and \\(C_0 = M = 1\\).
First case,1101+1010+ 1: column 0 gives \\(1+0+1 = 10\\), so \\(S_0 = 0\\), \\(C_1 = 1\\); column 1 gives \\(0+1+1 = 10\\), so \\(S_1 = 0\\), \\(C_2 = 1\\); column 2 gives \\(1+0+1 = 10\\), so \\(S_2 = 0\\), \\(C_3 = 1\\); column 3 gives \\(1+1+1 = 11\\), so \\(S_3 = 1\\), \\(C_4 = 1\\). The result1000is \\(-8\\), which is correct and just inside the range, and \\(V = C_4 \\oplus C_3 = 1 \\oplus 1 = 0\\) confirms it.
Second case,1010+1010+ 1: the carries are \\(C_1 = 0\\), \\(C_2 = 1\\), \\(C_3 = 0\\), \\(C_4 = 1\\) and the result is0101. That reads as \\(+5\\), whereas \\(-6-5 = -11\\) which will not fit in four bits, and \\(V = 1 \\oplus 0 = 1\\) catches it. Note that \\(C_4 = 1\\) in both cases and is therefore useless as a signed indicator \\(-\\) it only says that no unsigned borrow was needed.5. Why does a 16-bit adder use four 4-bit look-ahead blocks rather than one 16-bit look-ahead block, given that the single block would be faster?
Because the single block cannot be built. Extending the look-ahead equations to sixteen bits needs \(16 \times 17/2 = 136\) AND gates and sixteen OR gates, and the equation for \(C_{16}\) has seventeen product terms of which the largest is a seventeen-input AND. No standard logic family offers gates of that fan-in, and Chapter 12 explains why: each additional input adds input capacitance and, in TTL, another emitter in series, so the delay of a wide gate is no longer the \(\Delta\) the analysis assumed. Splitting into four-bit blocks keeps the widest gate at five inputs, keeps the gate count linear in the word length, and costs only 100 ns against the 320 ns of ripple carry — a 3.2-fold speed-up for an entirely buildable circuit.