48.

[Top] [Next] [Prev]

3.1 Multilevel Logic

Given a Boolean function expressed in min-term or max-term canonical form, you now know how to reduce it into a minimal two-level form with the fewest terms and literals. Let's consider the function (A,B,C, D,E,F,G):
= ADF + AEF + BDF + BEF + CDF + CEF + G
It is already in its minimal sum of products form. Its implementation as a two-level network of AND and OR gates requires six 3-input AND gates and one 7-input OR gate, a total of seven gates and 19 literals (see Figure 3.1(a)).

We can do better if we replace the two-level form with a so-called factored form. We express the function with common literals factored out from the product terms whenever possible.

By recursively factoring out common literals, we can express the function as:

= (AD + AE + BD + BE + CD + CE) F + G = [(A + B + C) D + (A + B + C) E] F + G = (A + B + C)(D + E) F + G
Expressed as a series of expressions, each in the two-level form, becomes
= XYF + G X = A + B + C Y = D + E
When written this way, the function requires one 3-input OR gate, two 2-input OR gates, and a 3-input AND gate, a total of four gates and nine literals. The intermediate functions X and Y count as literals in the final expression for .

The implementation from the factored form is shown in Figure 3.1(b). You can significantly reduce the number of wires and gates needed to implement the function, but this implementation probably has worse delay because of the increased levels of logic. In general, multi-level implementations are more gate efficient than two-level implementations but have worse propagation delay.

In this section we will be concerned with two issues: how to express logic networks solely in terms of NAND and NOR gates, and how to take advantage of multilevel logic to reduce the overall gate count.

3.1.1 Conversion to NAND/NAND and NOR/NOR Networks

The canonical forms you have studied so far are expressed in terms of AND and OR gates, but you will rarely encounter these in digital systems. The underlying technologies are more efficient at implementing NAND and NOR gates. In fact, AND and OR gates are most commonly realized by following a NAND or NOR gate with an inverter. In addition, NAND and NOR functions are complete; that is, a function expressed in terms of AND, OR, and NOT operations can be implemented solely in terms of NAND or NOR operations. Frequently, you will be confronted with the task of mapping a network with an arbitrary number of levels of AND and OR gates into one that consists only of NAND or NOR gates. We will begin the discussion with two-level networks and extend it to multilevel networks.

Visualization: DeMorgan's Theorem and Pushing Bubbles The conversion process depends critically on DeMorgan's theorem. Recall that
and that

In essence, a NAND function can be implemented just as well by an OR gate with its inputs inverted. Similarly, a NOR function can be implemented by an AND gate with its inputs complemented. The conversion from one form to the other is often called "pushing the bubble." This is simply a way to remember DeMorgan's theorem. As the bubble "pushes through" an AND shape, it changes to an OR shape with bubbles on the inputs. Similarly, pushing the bubble through an OR shape transforms it to an AND shape with bubbles on the inputs.

Figure 3.2 summarizes the relationship between OR gates and NAND gates. An OR gate is logically equivalent to a NAND gate with its inputs inverted. Similarly, an AND gate is equivalent to a NOR gate with its inputs complemented. This is shown in Figure 3.3.

The schematic symbols on either side of the in Figures 3.2 and 3.3 can be freely exchanged without changing the function's truth table.

AND/OR Conversion to NAND/NAND Networks Consider the simple gate network in Figure 3.4(a). Let's replace the first-level AND gates by their NOR equivalents and the OR gate by its NAND equivalent. The equivalent circuit is shown in Figure 3.4(b). Note that the output inversion at the first-level gates matches the input inversion at the second level. These cancel each other out, as shown in Figure 3.4(c). Both the first- and second-level gates are NAND. Unfortunately, this does not properly conserve the bubbles at the first-level inputs and the second-level outputs. This is corrected in Figure 3.4(d), where we have replaced the NAND gates with their equivalent forms. Now the bubbles are properly matched.

As a shortcut, you can simply insert matching inversions at the first-level outputs and second-level inputs to convert an AND/OR network to a NAND/NAND network.

AND/OR Conversion to NOR/NOR Networks Suppose you are now restricted to mapping the AND/OR network into a NOR-only network. As a shortcut, you can simply replace the first-level AND gates with NOR gates (AND with inverted inputs) and the second-level OR gate with a NOR gate.

But this is not logically equivalent. Every time a new inversion is introduced, it must be balanced by a complementary inversion. To correct the problem, we introduce additional inverters at the inputs and the output (see Figure 3.5).


To keep track of the need for inverted inputs to the first-level gates, we use the notation for active low inputs: \A, \B, \C, and \D. Since it is common to have both a Boolean variable and its complement available as circuit inputs, the conversion may not lead to additional inverters. Similarly, the extra inverter at the output can be eliminated if the circuit can be transformed so that the function is computed in negative logic. In other words, the output is connected to an input expecting an active low signal.

OR/AND Conversion to NOR/NOR Network Now let's consider a gate implementation for a simple expression in product of sums form. We can map this expression into a NOR/NOR network simply by replacing the OR gates with NOR gates and the AND gate with a NOR gate (an AND gate with inverted inputs). You can see in Figure 3.6 that the inversions we introduced cancel each other out.


OR/AND Conversion to NAND/NAND Networks Implementing the expression using NAND-only logic introduces exactly the same problems we have already seen in Figure 3.5. The correct transformation replaces the OR gates with NAND gates (OR gates with inverted inputs) and the AND gate with a NAND gate. To maintain equivalence with the original function, you need to place inverters at the inputs and at the output. This is shown in Figure 3.7.


Generalization to Multilevel Circuits We can extend the transformation techniques to multilevel networks. Consider the function

Its implementation in AND/OR form is shown in Figure 3.8(a).

You can see how we have arranged the logic into alternating levels of AND and OR gates. This makes it easier to observe the places where the conversion to NAND/NAND gates can take place. You simply replace each AND with a NAND and each OR with a NAND in its "alternative" form (OR with inverted inputs).

The application of this procedure is shown in Figure 3.8(b). We have grouped levels 1, 2 and 3, 4 into AND/OR circuits. These can be replaced by equivalent NAND/NAND networks directly.

Note that the literal B input to gate G3 must be inverted to preserve the original sense of the signal wire. Always remember to conserve the introduction of inversions. Any internal signal wires that undergo an odd number of inversions must have an additional inverter inserted in the path.

The final NAND-only network is shown in Figure 3.8(c). We have eliminated an inverter by replacing the B input to G3 with a connection to its complemented literal.

Suppose your target is a NOR-only network. You can take the same approach when the initial network is expressed as alternating OR and AND levels. You should place OR gates at the odd levels and AND gates at the even levels. You can immediately replace these by NOR gates. Any unmatched input bubbles should be corrected by inserting inverters or using the complemented literal where necessary.

It is a little more complicated when transforming alternating AND/OR networks (OR/AND networks) into NOR-only circuits (NAND-only circuits). Nevertheless, you can still apply the same basic techniques.

For example, suppose you want to map the AND/OR/AND/OR network of Figure 3.8(a) into NOR gates. You should invert the inputs to the odd levels while inserting an extra inversion at the output of the even levels. The extra inversions between adjacent even and odd levels can be saved if they cancel each other. This is shown in Figure 3.9(a) between levels 2 and 3, for gates G3 and G4. The final NOR-only circuit is shown in Figure 3.9(b). All but one of the literals have been inverted and an extra inversion has been inserted at the output. You can implement this last inversion by a NOR gate with both inputs tied to the same signal.

Figure 3.10 shows an example in which the circuit cannot be placed into a form that alternates between AND and OR gates. The multilevel function is

= AX + X + D X = BC
Figure 3.10(a) shows the initial AND/OR network. We begin by intro-duc-ing double inversions at the inputs to the last-stage OR gate (Figure 3.10(b)). We propagate these back to the outputs of the two AND gates and the input D (Figure 3.10(c)). Note how the connection to D has been replaced by a connection to its complement to match the bubble on the OR's input.

There is still one problem with this circuit. The NAND gate computes the complement of the function X, not X. To conserve bubbles and the sense of the signals, the NAND output must be inverted before it can be input to the second-stage NAND gate. The final converted circuit is shown in Figure 3.10(d).

3.1.2 AND-OR-Invert/OR-AND-Invert Building Blocks

Up to this point, we have been thinking about multilevel logic circuits constructed from discrete gates. In some digital circuit technologies, such as TTL, primitive forms of multilevel logic are readily available as prepackaged components. Multiple-input AND-OR-Invert (AOI) and OR-AND-Invert (OAI) functions are available as single complex gates in these technologies. We examine these building blocks next.

General Concept Conceptually, an AOI logic block is a three-level logic circuit consisting of AND gates at the first level, an OR gate at the second level, and an inverter at the output. Similarly, an OAI block has OR gates at the first level, an AND gate at the second level, and an inverter at the third level. In essence, several discrete gates are subsumed by a single complex gate, with the internal wiring already done for you.

A function like an AOI may seem a bit odd at first, but remember that it is much easier to build inverting logic like NAND and NOR gates than AND and OR gates in most digital circuit technologies.

Figure 3.11(a) shows the logical view of the AOI block, and Figure 3.11(b) gives a possible implementation in terms of switches. If A and B are true or C and D are true, the normally open switches establish a closed path from false to output Z.

In all other cases, true will be routed to the output through the normally closed switches. For example, if A = 0, B = 1, C = 1, and D = 0, the normally closed switches controlled by A and D will be closed, making the connection between true and the output Z. Switch implementations of OAI circuits look very similar.

The implementation in Figure 3.11(b) uses eight switches. If we had implemented the function using straightforward logic gates, we would need 14 switches: four each for the three 2-input gates and two for the inverter.

The particular circuit in Figure 3.11(a) is called a two-input two-stack AOI gate. This means it consists of two 2-input AND gates (each AND gate corresponds to a stack). A three-input two-stack AOI gate has two 3-input gates at the first level, a two-input three-stack AOI gate has three 2-input gates at the first level, and so on. The number of stacks is exactly the number of inputs to the second-level OR gate. Analogous concepts and terminology apply to OAI blocks.

Implementing Logic with AOI and OAI Blocks Let's start with a simple example. We will implement the XOR function using AOI blocks. Recall that XOR's behavior is described by the equation

A straightforward implementation using discrete gates requires two 2-input AND gates, one 2-input OR gate, and two inverters.

How do we implement this with AOI logic? Simply find the complement of the function in sum of products form. The final inversion in the AND/OR/Invert network will return the function to the sense in which we want it.

The complement of the XOR function, XNOR, is the following:

The circuit is constructed by providing A and B as inputs to the first stack and and as inputs to the second stack. This is shown in Figure 3.12.


The approach for OAI logic implementation is analogous. Using the K-map, we implement an OR/AND function by forming prime implicants around zeros and reading them out in product of sums form.

Example Let's consider the three-variable function F(A, B, C) = S m(2, 4, 6, 7).

Figure 3.13 gives the K-map for its complement, S m(0, 1, 3, 5). In minimized form, the complement is expressed as

Thus F can be implemented by two-input three-stack AOI or OAI gates. The inputs are wired to the literals of the complement of F. For the AOI implementation, you wire to the first stack, to the second, and to the third.

Example A 4-Bit Comparator Let's say your task is to implement a 4-bit comparator. Such a circuit has eight inputs organized as two sets of four input bits, labeled A3 through A0 and B3 through B0. The circuit's single output Z is asserted when A3 = B3, A2 = B2, A1 = B1, and A0 = B0. We assume that we have only inverters, NOR gates, and AOI gates.

Consider the logic for determining the equality of each pair of bits:

F0 = (A0 = B0) = F1 = (A1 = B1) = F2 = (A2 = B2) = F3 = (A3 = B3) =
The comparator function becomes F = F0 F1 F2 F3, which can be equivalently rewritten as the following if we use a NOR gate:

Now we can express the bitwise equality functions in AOI form. Each Fi is already in AND/OR form. Since the NOR gate needs the complements of the Fi at its inputs, these can implemented directly with AOI gates.

Figure 3.14 shows the implementation in terms of AOI gates at the first level and a NOR gate at the second level. Each AOI gate implements the complement of Fi-recall that the complement of equality (XNOR) is difference (XOR). The NOR function, when written as an AND gate with complemented inputs, negates the XOR functions to restore the XNORs.

Under the constraints of this particular problem, there is a real advantage to using these complex gates. Counting each AOI block as a single gate, the schematic of Figure 3.14 uses 13 gates: eight inverters, four AOI gates, and a 4-input NOR gate. An implementation using discrete AND and OR gates (or NOR and NAND gates) would require 8 more gates, since the function performed by the 4 complex gates would be replaced by 12 discrete gates. Even if the use of the AOI blocks represents no savings in circuit area, the transition away from discrete logic offers a considerable advantage in reducing wiring complexity.

TTL AOI Components TTL packaged logic has available a number of AND-OR-Invert circuits (OR-AND-Invert gates are not readily available in TTL).

See Figure 3.15 for a sample collection of schematic shapes. The 7451 package contains two 2-input 2-stack AOI gates. This particular package has 14 pins. The two gates use 10 of these (4 inputs, 1 output times 2), plus power and ground. This leaves two unconnected pins (the 74LS51, not shown in the figure, takes advantage of these previously unused connections by providing one 3-input 2-stack AOI gate and one 2 ¥ 2 gate). Other components include the 7454 2-input 4-stack AOI gate (the 'LS version comes with two 2-input stacks and two 3-input stacks), the 74LS55 4-input 2-stack AOI gate, and the 74S64 AOI gate, constructed from a 4-input stack, two 2-input stacks, and a 3-input stack.


[Top] [Next] [Prev]
This file last updated on 07/07/96 at 18:44:30.
randy@cs.Berkeley.edu;


What is Sarbanes-Oxley[q]
What is Sarbanes-Oxley[q]
ISBN: 71437967
EAN: N/A
Year: 2006
Pages: 101

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net