THE DIGITAL LOGIC LEVEL - Structured Computer Organization - page 153

AND gate computes one row of the truth table, as indicated. Finally, all the product
terms are OR ed together to get the final result.
The circuit of Fig. 3-3(b) uses a convention that we will use repeatedly
throughout this topic: when two lines cross, no connection is implied unless a
heavy dot is present at the intersection. For example, the output of gate 3 crosses
all six vertical lines but it is connected only to C . Be warned that some authors use
other conventions.
From the example of Fig. 3-3 it should be clear how we can derive a general
method to implement a circuit for any Boolean function:
1. Write down the truth table for the function.
2. Provide inverters to generate the complement of each input.
3. Draw an AND gate for each term witha1intheresult column.
4. Wire the AND gates to the appropriate inputs.
5. Feed the output of all the AND gates into an OR gate.
Although we have shown how any Boolean function can be implemented using
NOT , AND , and OR gates, it is often convenient to implement circuits using only a
single type of gate. Fortunately, it is straightforward to convert circuits generated
by the preceding algorithm to pure NAND or pure NOR form. All we need is a way
to implement NOT , AND , and OR using a single gate type. The top row of Fig. 3-4
shows how all three of these can be implemented using only NAND gates; the bot-
tom row shows how it can be done using only NOR gates. (These are straightfor-
ward, but there are other ways, too.)
One way to implement a Boolean function using only NAND or only NOR gates
is first follow the procedure given above for constructing it with NOT , AND , and OR .
Then replace the multi-input gates with equivalent circuits using two-input gates.
For example, A D ), using three

two-input OR gates. Finally, the NOT , AND , and OR gates are replaced by the cir-
cuits of Fig. 3-4.
Although this procedure does not lead to the optimal circuits, in the sense of
the minimum number of gates, it does show that a solution is always feasible.
Both NAND and NOR gates are said to be complete , because any Boolean function
can be computed using either of them. No other gate has this property, which is
another reason they are often preferred for the building blocks of circuits.

+ B + C + D can be computed as ( A + B ) + ( C +

3.1.4 Circuit Equivalence

Circuit designers often try to reduce the number of gates in their products to
reduce the chip area needed to implement them, minimize power consumption, and
increase speed. To reduce the complexity of a circuit, the designer must find an-
other circuit that computes the same function as the original but does so with fewer