By the end of this chapter you should be able to:
- Derive the three outputs of a one-bit comparator and show that they form a one-hot code.
- Build the equality and magnitude equations of a four-bit comparator from the digit-by-digit comparison procedure, and verify them.
- Explain the purpose of the 7485's three cascading inputs, state how they must be tied on the least significant package, and compute the delay of a cascaded comparator.
- Design parity generators and checkers as exclusive-OR trees, and compute the tree depth and propagation delay for any word length.
- Implement the parity-checked link of Chapter 4 at gate level and state precisely which errors it detects and which it does not.
- Construct an \(n \times n\) array multiplier from AND gates and adder rows, and derive both its gate count and its worst-case delay.
Chapter 16 spent its length on one function because the adder is the block whose delay sets the speed of everything else. This chapter takes three functions that are individually simpler but turn up just as often: deciding which of two numbers is larger, counting whether a group of bits contains an odd or an even number of ones, and multiplying. A comparator sits at the end of every address-decode path and inside every sorting and limit-check circuit; a parity tree guards every memory array and serial link; and a multiplier is the largest single block in any signal-processing datapath.
All three are built from gates you already have, and all three are worth studying for the same reason: each one shows a different relationship between how many gates a circuit needs and how long it takes. The comparator's delay does not depend on its width at all. The parity tree's grows as \(\log_2 n\) while its gate count grows as \(n\). The array multiplier's gate count grows as \(n^2\) while its delay grows only as \(n\). Getting those three scalings straight is more useful than memorising any of the circuits.
1 Comparing Two Bits
A magnitude comparator answers the question \"which of these two numbers is larger?\" with three mutually exclusive outputs — greater, equal and less. It could be done by subtraction: build the adder–subtractor of Chapter 16, compute \(A - B\), and read the sign and zero flags. That works, and every processor does it that way because the subtractor is there anyway. A dedicated comparator is cheaper and, as we shall see, considerably faster, because it does not have to wait for a carry to travel the width of the word.
Start with one bit. The truth table has four rows and three output columns:
| \(A\) | \(B\) | \(G\ (A > B)\) | \(E\ (A = B)\) | \(L\ (A < B)\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Each column is a single minterm or a pair, so no minimisation is needed:
The equality output is the exclusive-NOR of the two bits. This is the third standard use of the exclusive-OR family in the course, after parity and the controlled inverter of Chapter 16: XNOR is an equality detector, and a bank of them is how every comparator, every address decoder and every cache tag check begins.
Two properties of the three outputs are worth noticing, because both are used later. First, exactly one of them is 1 for any input pair — they are a one-hot code, and \(G + E + L = 1\) identically. Second, because of that, any one of the three can be recovered from the other two: \(L = (G + E)'\). A comparator therefore needs to build only two of its three outputs and can derive the third with a NOR gate, which is what a designer short of gates does. The 7485 nevertheless generates all three independently, because the cascading scheme of Section 3 needs each one available without the extra inversion delay.
2 The Four-Bit Magnitude Comparator
Equality across four bits is the easy half. Two words are equal when every corresponding pair of bits is equal, so with \(E_i = (A_i \oplus B_i)'\):
Four exclusive-NORs and one four-input AND. Extending to any width costs one more XNOR per bit and one more AND input, and the delay does not change at all.
Magnitude needs the procedure you would use by hand. To compare 1011 with 1001 you do not evaluate anything; you scan from the most significant end, skip the positions where the two words agree, and stop at the first position where they differ. Whichever word has the 1 there is the larger, and nothing below that position can change the verdict. Stated formally: \(A > B\) if bit 3 decides it, or if bit 3 is equal and bit 2 decides it, or if bits 3 and 2 are equal and bit 1 decides it, and so on. \"Bit \(i\) decides it in favour of \(A\)\" is \(A_iB_i'\), the one-bit result of Section 1, so
Each term is guarded by the equality of every bit above it, which is exactly what \"skip the positions where they agree\" means. Evaluating both expressions against all 256 pairs of four-bit words confirms that they agree with the arithmetic comparison on every one.
The structure is the same in every position, so a comparator of any width is written down immediately: the term for bit \(i\) is the one-bit result at \(i\) ANDed with all the \(E\)s above it. Notice that this is a parallel-prefix arrangement and not a ripple: the products \(E_3\), \(E_3E_2\) and \(E_3E_2E_1\) can all be formed at once, so no term waits for another. That is why the comparator escapes the penalty the ripple adder pays.
\(A = \) 1011 \(= 11\), \(B = \) 1001 \(= 9\). The bitwise equalities are \(E_3 = 1\) (both 1), \(E_2 = 1\) (both 0), \(E_1 = 0\) (1 against 0) and \(E_0 = 1\) (both 1). Substituting into the \(A > B\) expression, the first term \(A_3B_3' = 1 \cdot 0 = 0\); the second \(E_3A_2B_2' = 1 \cdot 0 \cdot 1 = 0\); the third \(E_3E_2A_1B_1' = 1 \cdot 1 \cdot 1 \cdot 1 = 1\). So \(A > B\), decided at bit 1, and the fourth term is irrelevant. \((A = B) = E_3E_2E_1E_0 = 0\) because \(E_1 = 0\), and every term of \((A < B)\) contains either \(A_1'\) or a zero \(E\), so it is 0 as well.
For the timing, use the model of Chapter 16: \(\Delta = 10\ \text{ns}\) for a basic gate and \(2\Delta\) for anything in the exclusive-OR family. The \(E_i\) appear at \(2\Delta\); the AND level of the magnitude expression finishes at \(3\Delta\) and the OR level at \(4\Delta\):
Compare that with obtaining the same answer by subtraction on a four-bit ripple adder, which takes 80 ns before the sign bit is even valid, and on a sixteen-bit one, 320 ns. The comparator's figure is 40 ns at four bits and would still be 40 ns at sixteen if a sixteen-bit block could be built — and Section 3 explains why in practice it cannot.
Counting gates for one four-bit package: four exclusive-NORs for the \(E_i\); one four-input AND for the equality output; four ANDs and one four-input OR for \(A > B\); the same again for \(A < B\); and eight inverters for the complemented literals. That is fifteen gates plus inverters, against twenty-four for a four-bit ripple adder, so the comparator is both smaller and twice as fast. The widest AND gate has five inputs, and this is the fan-in problem of Chapter 16 in a new guise: an eight-bit comparator would need a nine-input AND, and a sixteen-bit one a seventeen-input AND, which is why four bits per package is again the standard.
3 Cascading Inputs and the 7485
The 7485 is a four-bit magnitude comparator with three outputs and, unusually for an MSI part, three extra cascading inputs \(I_{A>B}\), \(I_{A=B}\) and \(I_{A<B}\). Their purpose is to let one package say \"as far as my four bits go the two words are identical, so the decision belongs to somebody else\". The package's own four-bit results are combined with the cascade inputs like this:
The package's own verdict wins outright; the cascade input is looked at only when the package's four bits are equal, in which case it is passed straight through. The equality output is an AND, because the words are equal overall only if both this package and everything cascaded into it report equality.
Wiring two packages into an eight-bit comparator now needs no extra logic at all. The outputs of the package holding bits 3 to 0 drive the cascading inputs of the package holding bits 7 to 4, and the more significant package's outputs are the answer. Figure 17.2 shows the arrangement.
The least significant package has nothing cascaded into it, and how its cascade inputs are tied matters. They must be set to \(I_{A>B} = 0\), \(I_{A=B} = 1\), \(I_{A<B} = 0\) — the code for \"equal\". The reasoning is that these inputs describe the comparison of all the bits below the ones this package handles, and there are none, so the empty comparison is an equality. Tying \(I_{A=B}\) low instead is the classic wiring error: the chain can then never report equality, since \((A=B)_{out}\) is an AND that always has a zero in it, and two identical words are reported as unequal without any output ever going high to say which is larger.
Cascading in series costs time. A package's own \(E_i\) signals are ready at \(2\Delta\) and its outputs \(2\Delta\) later, so a single package settles at \(4\Delta\). Each further package in the chain adds one AND level and one OR level, \(2\Delta\), because its own comparison has been ready all along and only the cascade path through it is new:
| Packages | Word length | Delay | Comment |
|---|---|---|---|
| 1 | 4 bits | 40 ns | \(4\Delta\) |
| 2 | 8 bits | 60 ns | \(6\Delta\) |
| 4 | 16 bits | 100 ns | \(10\Delta\) |
| 8 | 32 bits | 180 ns | \(18\Delta\) |
That is \(2\Delta\) per package, exactly the ripple penalty of Chapter 16 in a different circuit, and the cure is the same. For long words the packages are arranged as a tree rather than a chain: the equality outputs of several packages are ANDed together and the magnitude outputs merged by a small network, so the depth grows as \(\log\) of the number of packages instead of linearly. A 32-bit comparison then costs about \(8\Delta\) rather than \(18\Delta\). The 7485 data sheet shows both arrangements, and the trade is the familiar one: the tree needs extra gates outside the packages, the chain needs none.
4 Parity Generators and Checkers
Chapter 4 introduced parity as the cheapest error-detecting code there is: append one bit to a word so that the total number of 1s is even (even parity) or odd (odd parity). The circuit that forms that bit is a parity generator, and the circuit that tests it at the far end of the link is a parity checker. Both are the same piece of hardware.
The reason is the exclusive-OR. For two variables \(A \oplus B\) is 1 when exactly one input is 1; extended to \(n\) inputs by association, \(D_{n-1} \oplus \dots \oplus D_1 \oplus D_0\) is 1 whenever an odd number of the inputs is 1. That is precisely the definition of odd parity, so
The even-parity bit is 1 when the data already contains an odd number of 1s, which is what makes the total even. The odd-parity bit is its complement, so one inverter converts a generator of either kind into the other — which is why the 74180 and 74LS280 bring out both.
Note that this is the same function as the sum output of the full adder in Chapter 16, \(S = A \oplus B \oplus C_{in}\). A full adder is a three-bit parity generator with a majority circuit attached, and that is not a coincidence: the least significant bit of a sum is the parity of the bits being added.
Because exclusive-OR is associative, the \(n-1\) gates needed can be wired in any order, and the order decides the speed. A chain — each gate taking the previous gate's output and one new data bit — is \(n-1\) gates deep. A balanced tree pairs the inputs, then pairs the results, and is only \(\lceil \log_2 n \rceil\) deep. The gate count is identical:
| Inputs \(n\) | XOR gates | Chain depth | Chain delay | Tree depth | Tree delay | Speed-up |
|---|---|---|---|---|---|---|
| 4 | 3 | 3 | 60 ns | 2 | 40 ns | 1.50 |
| 8 | 7 | 7 | 140 ns | 3 | 60 ns | 2.33 |
| 9 | 8 | 8 | 160 ns | 4 | 80 ns | 2.00 |
| 16 | 15 | 15 | 300 ns | 4 | 80 ns | 3.75 |
| 32 | 31 | 31 | 620 ns | 5 | 100 ns | 6.20 |
Taking an exclusive-OR as \(2\Delta = 20\ \text{ns}\). Thirty-one gates in a chain take 620 ns; the same thirty-one gates in a tree take 100 ns. Nothing has been bought except a different arrangement of the same silicon.
The 74LS280 is the standard part: nine data inputs, an even output and an odd output, eight exclusive-OR gates internally in a tree four levels deep. Nine inputs rather than eight is deliberate — it takes a byte plus an incoming parity bit, so the same package generates parity at one end of a link and checks it at the other. To generate, tie the ninth input low and use eight of the inputs for the data; to check, apply the eight received data bits and the received parity bit to all nine, and read the output that should be low. If the transmitter used even parity the whole nine-bit group contains an even number of 1s when nothing has gone wrong, so the odd output is the error flag.
This is also how memory parity was implemented for two decades of personal computers. A byte-wide memory bank was built from nine chips rather than eight; the ninth stored the parity bit written by a 74LS280 during every write cycle, and a second 74LS280 recomputed it during every read. A disagreement drove a non-maskable interrupt, which is why a failing memory chip announced itself as a “parity error” rather than as silently wrong arithmetic. The whole mechanism costs one chip in nine, two MSI packages and about 80 ns — an excellent return for detecting the single commonest hardware fault in a memory array.
5 The Chapter 4 Parity Link, Built From Gates
Chapter 4 described a seven-bit ASCII character sent with an eighth bit added for even parity, and left the circuit as a description. It is worth building now, because it is small enough to trace completely and it shows what the code can and cannot do.
At the transmitter. Seven data lines \(D_6 \ldots D_0\) enter a parity generator: six exclusive-OR gates in a tree of depth \(\lceil \log_2 7 \rceil = 3\), so \(P\) is valid \(6\Delta = 60\ \text{ns}\) after the character is presented. Eight lines then leave.
At the receiver. All eight received lines — the seven data bits and the parity bit — enter a checker: seven exclusive-OR gates, again a tree of depth 3, again 60 ns. Its output is
If nothing has been corrupted the eight bits contain an even number of 1s by construction, so \(E = 0\). Any single bit flipped in transit changes the count by one, making it odd, so \(E = 1\) and the error is flagged.
ASCII 'm' is 6D hexadecimal, or 1101101 as seven bits. It contains five 1s, an odd number, so the even-parity generator outputs \(P = 1\) and the transmitted byte is 11101101 with the parity bit leading — six 1s, even.
Suppose bit 2 is corrupted so that the receiver sees 11101001. That is five 1s, odd, so the checker gives \(E = 1\) and the byte is rejected. Now suppose bits 2 and 3 are both corrupted, giving 11100101: six 1s again, even, and \(E = 0\). The receiver accepts a character that is not the one that was sent.
Compare with the letter 'A', 1000001, which contains two 1s. Here \(P = 0\), the transmitted byte is 01000001, and the same reasoning applies.
That is the exact scope of the code, and it is worth stating plainly because it is examined often. A single parity bit detects any odd number of errors in the protected group and is blind to any even number. It cannot say which bit is wrong, so it cannot correct anything; the receiver's only remedy is to ask for the character again. Locating the error needs the several overlapping parity checks of the Hamming code in Chapter 4, whose parity bits are each generated by exactly the kind of exclusive-OR tree built here — a \((7,4)\) Hamming encoder is three of these trees with different inputs, and its decoder is three more feeding a 3-to-8 decoder, which is the subject of Chapter 18.
One practical note about the delay. The 60 ns of the generator sits between the moment the character is stable and the moment the byte may be clocked onto the line, and the 60 ns of the checker sits between reception and the moment \(E\) may be sampled. Neither is on the same path, so they do not add: each end has its own 60 ns budget, and it is the slower of the two that limits the link.
6 The Array Multiplier
Binary multiplication done on paper is easier than decimal, because every digit of the multiplier is 0 or 1 and so every partial product is either zero or a copy of the multiplicand. For \(A = 1101\) and \(B = 1011\):
| Step | Partial product | Shift | Running total |
|---|---|---|---|
| \(b_0 = 1\) | 1101 | 0 | 00001101 = 13 |
| \(b_1 = 1\) | 1101 | 1 | 00100111 = 39 |
| \(b_2 = 0\) | 0000 | 2 | 00100111 = 39 |
| \(b_3 = 1\) | 1101 | 3 | 10001111 = 143 |
\(13 \times 11 = 143\), and the product of two four-bit numbers needs eight bits, since the largest is \(15 \times 15 = 225 < 256\). In general an \(n\)-bit multiplicand and an \(m\)-bit multiplier give an \((n+m)\)-bit product.
Every element of this procedure has an obvious gate. The partial product bit at row \(i\), column \(j\) is \(a_j\) if \(b_i = 1\) and 0 otherwise, which is simply
so an \(n \times n\) multiplier needs \(n^2\) two-input AND gates and nothing else to form all the partial products — all of them at once, in one gate delay. The shifting is not hardware at all, merely which wire goes to which adder input. What remains is adding the \(n\) rows, and that is done with \(n-1\) rows of adders, each one adding the next partial product to the running total. Figure 17.4 draws the four-bit case.
Counting the hardware: \(n^2\) AND gates; \(n-1\) adder rows of \(n\) cells each, of which the rightmost cell in every row has no carry input and can be a half adder. Taking a half adder as two gates and a full adder as six, from Chapter 16:
| Size | AND gates | Half adders | Full adders | Total gates | Worst-case delay |
|---|---|---|---|---|---|
| \(4 \times 4\) | 16 | 3 | 9 | 76 | 180 ns |
| \(8 \times 8\) | 64 | 7 | 49 | 372 | 500 ns |
| \(16 \times 16\) | 256 | 15 | 225 | 1636 | 1140 ns |
The gate count grows as \(n^2\) — doubling the word length quadruples the multiplier — which is why the multiplier is the largest block on the die of any signal-processing part, and why cheap microcontrollers leave it out and multiply in software instead.
Take a cell's delay from the Chapter 16 model: a full adder gives its sum after two exclusive-OR levels, \(4\Delta\) from its data inputs and \(2\Delta\) from its carry input, and its carry after \(2\Delta\) from any input. The AND gates deliver every partial product at \(\Delta = 10\ \text{ns}\).
Tracing the longest path through Figure 17.4 gives the times at which each product bit becomes valid: \(P_0\) at 10 ns straight from its AND gate, \(P_1\) at 30 ns from the first adder row, \(P_2\) at 70 ns, \(P_3\) at 120 ns, and the top four bits \(P_7 \ldots P_4\) at 180 ns, which is the figure for the whole multiplier. Repeating the trace for other widths gives
so \(8 \times 8\) takes 500 ns and \(16 \times 16\) takes 1140 ns. The delay is linear in \(n\) even though the gate count is quadratic, because the critical path crosses the array once — down through the \(n-1\) adder rows and along the last of them — rather than visiting every cell.
The array is also easy to lay out, which matters as much as the gate count. Every cell is identical, every connection is to a neighbour, and the whole block is a rectangle that tiles without long wires — properties that make it the natural choice on silicon and in an FPGA fabric, and the reason the regular array survived long after cleverer schemes were known. One consequence to be aware of is that the multiplier as drawn handles unsigned operands only. Feeding it 2's-complement numbers gives the wrong answer, because the most significant bit of each operand carries a weight of \(-2^{n-1}\) rather than \(+2^{n-1}\), and the array has no way of knowing that. The usual remedies are to convert both operands to magnitude form, multiply, and fix the sign afterwards, or to use Booth's algorithm, which recodes the multiplier so that runs of 1s are handled in one step.
Two further improvements are worth naming even though they belong to a later course. Replacing the ripple rows with carry-save adders, which pass carries diagonally downwards instead of sideways, removes the within-row ripple from all but the final row and roughly halves the constant. Adding the partial products in a Wallace tree, which is to the array what the parity tree of Section 4 is to the parity chain, reduces the depth to \(O(\log n)\) at the cost of irregular wiring. Both keep the \(n^2\) AND gates, because those are irreducible: the product genuinely depends on all \(n^2\) pairwise products of the input bits.
7 Summary and Key Results
| Function | Equations | Gates and delay |
|---|---|---|
| One-bit comparator | \(G = AB'\), \(E = (A \oplus B)'\), \(L = A'B\) | 3 gates; the outputs are a one-hot code, so \(L = (G+E)'\) |
| 4-bit equality | \((A=B) = E_3E_2E_1E_0\), \(E_i = (A_i \oplus B_i)'\) | 4 XNOR + 1 AND; \(2\Delta + \Delta = 30\) ns |
| 4-bit magnitude | \((A>B) = A_3B_3' + E_3A_2B_2' + E_3E_2A_1B_1' + E_3E_2E_1A_0B_0'\) | 15 gates; \(4\Delta = 40\) ns, independent of width |
| 7485 cascade | \((A>B)_{out} = (A>B) + (A=B)I_{A>B}\) | \(+2\Delta\) per package; tie \(I_{A=B} = 1\) on the least significant one |
| Parity generator | \(P_{even} = D_{n-1} \oplus \cdots \oplus D_0\) | \(n-1\) XOR gates; \(\lceil \log_2 n \rceil\) levels as a tree, \(n-1\) as a chain |
| Parity checker | \(E = R_{n} \oplus \cdots \oplus R_0\) | Same circuit; detects any odd number of errors, blind to any even number |
| Array multiplier | \(pp_{ij} = a_j b_i\), then \(n-1\) adder rows | \(n^2 + 2(n-1) + 6(n-1)^2\) gates, \((8n-14)\Delta\) delay |
8 Common Mistakes
The cascading inputs report the comparison of all the bits below the package, and for the least significant package there are none, so the correct code is \"equal\": \(I_{A=B} = 1\) with the other two at 0. Tying \(I_{A=B}\) low puts a permanent zero into the AND that forms \((A=B)_{out}\), so the chain can never report that two words match — and since neither magnitude output goes high either, the circuit produces all three outputs low, a state the truth table says is impossible. Leaving the pin floating on a TTL part is worse, because it reads as a soft 1 and works on the bench until the layout changes.
A chain and a tree use the same \(n-1\) exclusive-OR gates and give the same answer, so the chain is not wrong; it is merely several times slower, and the difference grows with the word length. At 32 bits it is 620 ns against 100 ns. The same reasoning applies to any associative operation built from two-input gates — a wide AND, a wide OR, a sum of many terms — and balancing the tree is free.
An \(n \times n\) array multiplier contains \(O(n^2)\) gates but settles in \(O(n)\) time, because the critical path crosses the array once instead of visiting every cell. Confusing the two leads to the belief that a \(16 \times 16\) multiply must take twenty times as long as a \(4 \times 4\) one, when in fact it takes about six times as long. Area and delay are separate budgets and must be estimated separately.
9 Chapter Review
1. Design a two-bit magnitude comparator from first principles and give its three output equations. How many gates does it need?
With \(A = A_1A_0\) and \(B = B_1B_0\), define \(E_1 = (A_1 \oplus B_1)'\) and \(E_0 = (A_0 \oplus B_0)'\). Equality needs both: \((A=B) = E_1E_0\). For magnitude, bit 1 decides unless it is equal, in which case bit 0 does: \((A>B) = A_1B_1' + E_1A_0B_0'\) and \((A<B) = A_1'B_1 + E_1A_0'B_0\). Checking all sixteen pairs confirms these. The cost is two exclusive-NORs, one two-input AND for equality, two ANDs and one OR for each magnitude output, and four inverters — nine gates plus inverters. The delay is \(2\Delta\) for the \(E_i\) plus one AND and one OR level, so \(4\Delta = 40\) ns, the same as the four-bit comparator.
2. Two 7485 packages are cascaded to compare eight bits, and a technician ties the cascading inputs of the more significant package to 0, 1, 0 and feeds the less significant package from the more significant one. What does the circuit do?
It compares the words in the wrong order, so it reports the comparison of \(A_3A_2A_1A_0\) against \(B_3B_2B_1B_0\) unless those four bits are equal, in which case it defers to bits 7 to 4. In other words it treats the low nibble as the more significant one. It will still report equality correctly, because equality is symmetric in the two halves, which is what makes the fault so easy to miss: a test that only checks matching words passes. It fails as soon as the two words differ in both halves — for instance \(A = \)
00010000and \(B = \)00000001, where the correct answer is \(A > B\) and the circuit says \(A < B\).3. A 16-bit word is to be given an even-parity bit. How many exclusive-OR gates are needed, how should they be arranged, and what is the delay? How does the answer change if the word grows to 32 bits?
Fifteen gates, since \(n\) inputs always need \(n-1\) two-input exclusive-ORs whatever the arrangement. Wired as a balanced tree the depth is \(\lceil \log_2 16 \rceil = 4\) levels, so with an exclusive-OR at \(2\Delta = 20\) ns the parity bit is valid after 80 ns; wired as a chain the same fifteen gates would be fifteen deep and take 300 ns. At 32 bits the gate count rises to 31 but the tree depth rises only to 5, so the delay goes from 80 ns to 100 ns — doubling the word length costs one extra gate delay. In practice one would use four 74LS280 packages and combine their outputs with a fifth stage.
4. A memory system stores each byte with one even-parity bit. During a read the checker returns \(E = 0\). What can be concluded, and what cannot?
Only that the nine bits read back contain an even number of 1s. That is consistent with no error at all, and equally consistent with two bits having been corrupted, or four, or six, or eight. What can be concluded is the negative: no single bit error has occurred, and more generally no odd number of them. What cannot be concluded is that the data are correct, and nothing whatever can be said about which bit might be wrong, so no correction is possible. A memory that must survive single-bit failures uses the Hamming code of Chapter 4, which for eight data bits needs four check bits rather than one and can both locate and repair a single error.
5. Compare a 16-bit ripple-carry adder with a \(16 \times 16\) array multiplier in gates and in delay, and explain why the ratios are so different.
The adder is \(16 \times 6 = 96\) gates and takes \(2 \times 16 \times \Delta = 320\) ns. The multiplier is \(256 + 2 \times 15 + 6 \times 15^2 = 1636\) gates and takes \((8 \times 16 - 14)\Delta = 1140\) ns. So the multiplier costs about seventeen times as many gates but only about three and a half times as long. The reason is that the adder is one row of cells, so both its area and its critical path are proportional to \(n\); the multiplier is an \(n \times n\) array, so its area is proportional to \(n^2\) while its critical path still only has to cross the array once, down the rows and along the last one, which is proportional to \(n\). Area follows the number of cells; delay follows the longest path through them, and the two need not scale alike.