2.3 Minimization goals and gate cost

Why this matters

Two circuits can compute the same function and still differ a lot in size, speed and cost. Before you can minimize anything you have to decide what you are minimizing, and the answer depends on what the circuit is made of. This section fixes the measures, gives a cost model you can compute with, and shows that a single kind of gate, NAND or NOR, is enough to build everything.

Learning goals

Name the four things a minimization can try to reduce: gates, gate inputs, levels and gate kinds, and say how the gate-input count differs from an expression's literal count.
Compute the transistor cost of a circuit of two-input gates from a cost table.
Explain why circuits with the same number of gates can differ in cost.
Rebuild NOT, AND and OR from NAND gates alone and from NOR gates alone.
Count the gates of a NAND-only or NOR-only circuit for a given function.

Intuition first

Think of a function as a recipe and a circuit as a kitchen that cooks it. Two kitchens can serve the same dish, one with five stations and one with two. The smaller kitchen needs less space and fewer cooks, and a dish passing through fewer stations arrives sooner. A third kitchen may use fewer stations but expensive ones. Minimizing a circuit means choosing among such kitchens, and you cannot choose until you know whether you care about space, speed, or the price of the equipment.

In circuits the recipe is a Boolean function and the equipment is gates. The laws of the previous two sections give you many circuits for one function, and this section gives you the yardsticks to compare them.

What "minimal" can mean

Definition 2.3.1(measures of a circuit).

A circuit can be measured in four ways. Its gate count is the number of gates. Its gate-input count is the total number of inputs on the gates of that particular circuit, which is also the number of wire ends that land on a gate. Its levels, or depth, is the largest number of gates on a path from an input to the output. Its gate kinds are the types of gate it uses, which matter because some kinds are cheaper than others.

The gate-input count is not the literal count of Section 2.1, which is a property of an expression: the number of variable occurrences in it, plain or complemented. The two are related but different. The expression $AB + CD$ has four literals, while its direct circuit of two AND gates and one OR gate has six gate inputs, two on each gate. When you quote a gate-input count, say whether the inputs of inverters are counted.

Each measure matters for a reason. Every extra gate costs chip area and, in a packaged part, money. In some technologies a gate with more inputs is slower, and the number of inputs a gate can have is limited, so fewer inputs per gate is better. A signal must pass through every gate on its path, so fewer levels means a shorter delay. And since the gate kinds differ in how they are built, a circuit with the same number of gates can be cheaper or dearer than another. None of the four measures decides everything, and a circuit that is best in one can be worse in another.

A cost model for two-input gates

The course measures a two-input gate by the number of CMOS transistors it needs: NOT 2, AND 6, OR 6, NAND 4, NOR 4, XOR 8 and XNOR 8.^{F (fact ch02/gate-cost-model)} We use that model throughout, with one condition that is easy to forget: the numbers are for gates with two inputs. A three-input gate usually costs more, and the model gives no number for it. A NOT has one input, and its cost of 2 is the smallest in the list.

The table has a pattern. A NAND is the cheapest two-input gate, and an AND is a NAND followed by an inverter, which gives 4 plus 2 equals 6. The same holds for OR and NOR. So NAND and NOR are the natural gates of this technology, and a plain AND or OR pays for an extra inverter.

ReadingThe numbers depend on the circuit style

A static CMOS exclusive-or gate is commonly drawn with 12 transistors when it must make the inverted inputs itself, and with 8 when they are already available; transmission-gate designs use 8 or fewer.^{F (fact ch02/xor-cmos-12)} So the 8 for XOR in the table is a number for one particular design, not a law. The model is a way to compare circuits on paper. A real design flow counts transistors, or more usually other resources, with its own tools.

Example 2.3.1(costing the circuits from Section 2.1).

The five-gate circuit of Section 2.1 has three AND gates and two OR gates, all with two inputs. Each costs 6, so the circuit costs 30. The simplified circuit has one OR gate and one AND gate and costs 12. Both circuits are below, drawn from the same checked drawings as before.

Figure 2.3.1. The original circuit: three AND gates and two OR gates.

Figure 2.3.2. The simplified circuit: one OR gate and one AND gate.

Simplifying also cut the levels. The longest path in the first circuit passes through three gates and the longest in the second through two. Both numbers come from the drawings, and the quiz below asks you to check them. All three measures improved at once here. They do not always.

Example 2.3.2(same shape, different kinds).

Take $AB + CD$ . An AND-OR circuit uses two AND gates and one OR gate, which costs 6 + 6 + 6 = 18. Replace all three gates by NAND gates and the function does not change, and the cost is 4 + 4 + 4 = 12. The circuits have the same number of gates, the same number of literals and the same number of levels. Only the gate kind differs. Section 2.4 explains why replacing every gate by a NAND is allowed here.

Figure 2.3.3. An AND-OR circuit for AB + CD.

Figure 2.3.4. The same function from three NAND gates.

Universal gates

Definition 2.3.2(universal gate).

A gate kind is universal if every Boolean function can be built from gates of that kind alone. The lecture calls NAND and NOR the universal gates.^{F (fact ch02/universal-gates)}

To show that NAND is universal it is enough to build NOT, AND and OR from it, since every expression is made from those three. A NAND whose two inputs are tied together is a NOT, because $\overline{X} = \overline{XX}$ . An AND is a NAND followed by that NOT, because $XY = \overline{\overline{XY}}$ . An OR is a NAND of two inverted inputs, because $X + Y = \overline{\overline{X}\,\overline{Y}}$ . The last identity is one of DeMorgan's laws, which Section 2.4 covers.

Only NAND gates (6 NAND).

Figure 2.3.5. NOT, AND and OR built from NAND gates only, from top to bottom: one gate, two gates and three gates.

The same idea works for NOR, with the roles of AND and OR swapped. A NOR with tied inputs is a NOT, because $\overline{X} = \overline{X + X}$ . An OR is a NOR followed by that NOT, because $X + Y = \overline{\overline{X + Y}}$ . An AND is a NOR of two inverted inputs, because $XY = \overline{\overline{X} + \overline{Y}}$ . Figure 2.3.6 shows the three constructions.

Only NOR gates (6 NOR).

Figure 2.3.6. NOT, OR and AND built from NOR gates only, from top to bottom: one gate, two gates and three gates.

Universal does not mean cheaper. Under the cost model, a NOT made from a NAND costs 4 against 2 for a real NOT, an AND from two NANDs costs 8 against 6, and an OR from three NANDs costs 12 against 6. Rebuilding gate by gate is the safe way to convert a circuit, not the efficient way. A smarter conversion rewrites the expression first, as the next example shows.

Fewest universal gates

Example 2.3.3(B(A + C) in one kind of gate).

We want to implement $B \cdot (A + C)$ using as few gates as possible, all NAND or all NOR.

Start with the direct translation: the OR gate becomes three NANDs (an inverter on each of A and C, then a NAND), the AND gate becomes two (a NAND and an inverter). That gives five gates and a cost of 20.

Only NAND gates (5 NAND). 5 gates in all.

Figure 2.3.7. B(A + C) translated gate by gate into NAND gates: five gates.

Rewriting first does much better. Multiply out to get $AB + BC$ . That is an AND-OR circuit, and an AND-OR circuit becomes a NAND-NAND circuit directly, so three NAND gates suffice, with a cost of 12.

Only NAND gates (3 NAND). 3 gates in all.

Figure 2.3.8. B(A + C) as AB + BC in three NAND gates.

For NOR, the original form is already close. The OR of A and C is one NOR followed by an inverter. But the NOR of two inverted signals is an AND, so we can drop that inverter and invert B instead: $B \cdot (A + C) = \overline{\overline{B} + \overline{A + C}}$ . This needs a NOR for A and C, a NOR with tied inputs for the inverted B, and a final NOR, which is three gates and a cost of 12.

Only NOR gates (3 NOR). 3 gates in all.

Figure 2.3.9. B(A + C) in three NOR gates.

Three gates is the smallest count for this function in either kind: an exhaustive search over every circuit of two or fewer two-input NAND gates, and over every one of NOR gates, with A, B and C as the only inputs, finds none that computes it. The plain OR-and-AND circuit also costs 12 under the model, so converting to a universal gate did not make this one cheaper, only uniform.

Gate counts also change with the function. Exclusive-or needs four NAND gates, shown below, which cost 16 against 8 for an XOR gate in the model.

Only NAND gates (4 NAND). 4 gates in all.

Figure 2.3.10. Exclusive-or from four NAND gates. The first gate's output is shared by the other two.

Course conventions

How CSE 369 writes this

Gates in drawings have distinctive shapes, and a bubble means NOT, on an output or on an input. A NAND is an AND with a bubble on the output, and a NOR is an OR with a bubble on the output. The cost table above is for two-input gates; this book never applies it to a gate with more inputs.

Pitfalls

Common pitfall

Treating the cost table as a law of nature. It counts transistors of two-input gates in one circuit style, and real counts depend on the style.
Forgetting the inverters. In a NAND-only circuit every inversion is a NAND with tied inputs, and it counts as a gate and costs 4.
Judging cost by gate count alone. The AND-OR and NAND-NAND circuits for AB + CD have the same gate count but cost 18 and 12.
Leaving a NOT or an input bubble in a drawing that is supposed to use only NAND or only NOR gates. Every inversion must be made by one of the allowed gates.
Calling a circuit the smallest without trying other forms of the function. The expression you start from decides which circuits you find: B(A + C) took five NAND gates directly and three after rewriting.

Check your understanding

Take the quiz (4 questions)

Exercises

Exercise 2.3.1

Use the cost table to find the transistor count of the four-NAND exclusive-or circuit and compare it with one XOR gate.

Hint

Count the gates in the figure and multiply by the cost of one NAND.

Solution

The circuit has four NAND gates, and each costs 4, so the total is 16. A single XOR gate costs 8 in the model, so here the gate that the model offers directly is half the cost of the rebuilt one. The model's 8 is for one circuit style, though: a different style gives a different number, and so the comparison is only as good as the model.

Tags: Warm-upGates and schematics

Exercise 2.3.2

Draw NOT, OR and AND using only NOR gates, and say how many gates each takes.

Hint

A NOR with its inputs tied is a NOT. For OR, undo a NOR. For AND, invert both inputs of a NOR.

Solution

NOT is one NOR with both inputs connected to the input. OR is a NOR followed by a NOT, so two gates. AND is a NOR of two inverted inputs, so one NOR plus two NOR inverters, three gates. The figure shows all three, drawn and checked.

Only NOR gates (6 NOR).

Figure 2.3.11. The NOR constructions, from top to bottom: NOT with one gate, OR with two gates and AND with three gates.

Tags: StandardGates and schematics

Exercise 2.3.3

Implement $A + BC$ with NAND gates only, and then with NOR gates only. How many gates does each use?

Hint

For NAND, write it as a NAND of two things. For NOR, use the OR-over-AND distributive law to turn it into a product of sums.

Solution

For NAND, the OR of A and B&C is a NAND of the inverted pieces: $A + BC = \overline{\overline{A} \cdot \overline{BC}}$ . The inverted A is a NAND with tied inputs, the inverted product is a NAND of B and C, and the outer gate is one more NAND. That is three gates.

Only NAND gates (3 NAND). 3 gates in all.

Figure 2.3.12. A + BC in three NAND gates.

For NOR, the distributive law gives the product of sums $(A + B) \cdot (A + C)$ . A product of sums is the NOR of the NORs of its sums: $(A + B) \cdot (A + C)$ $= \overline{\overline{A + B} + \overline{A + C}}$ . That is also three gates.

Only NOR gates (3 NOR). 3 gates in all.

Figure 2.3.13. A + BC in three NOR gates.

Tags: StandardGates and schematicsBoolean algebra

Exercise 2.3.4

Show with a derivation that $X + Y$ can be written using only NAND operations, and find which part of your result is a NOT.

Hint

Put two bars on the whole expression, then push the inner bar through the sum with DeMorgan's law.

Solution

Each line follows from the one above by the law beside it.

Step-by-step simplification; each line names the law used to get from the line above
Expression	Law used
$X + Y$
$= \overline{\overline{X + Y}}$	Double negation
$= \overline{\overline{X}\,\overline{Y}}$	DeMorgan

The last line is the NAND of $\overline{X}$ and $\overline{Y}$ . Each $\overline{X}$ is a NAND of X with itself, so the circuit uses three NAND gates: two inverters and the final NAND.

Tags: StandardBoolean algebra

Exercise 2.3.5

Build the exclusive-nor of A and B, which is 1 when A and B are equal, from NAND gates only. How many gates does your circuit use, and what does it cost under the table?

Hint

The exclusive-nor is the complement of the exclusive-or, and you already have a NAND circuit for the exclusive-or.

Solution

Take the four-gate exclusive-or and add a NAND whose two inputs are both connected to the exclusive-or's output, which inverts it. That gives five NAND gates and a cost of 20, against 8 for an XNOR gate in the model.

Only NAND gates (5 NAND). 5 gates in all.

Figure 2.3.14. Exclusive-nor from five NAND gates.

Tags: ChallengeGates and schematics