Logic Synthesis with NAND (or NOR) Gates in Multi-Levels:Design of NAND (or NOR) Networks in Double-Rail Input Logic by the Map-Factoring Method.

Design of NAND (or NOR) Networks in Double-Rail Input Logic by the Map-Factoring Method

NAND gates and NOR gates, which are realized with MOSFETs, are often used in realizing integrated circuit chips, although logic gates that express negative functions which are more complex than NAND or NOR are generally used. (A “negative function” is the complement of a disjunctive form of non complemented variables. An example is xy ∨ z.) NAND gates are probably more often used than other types of logic gates realizing negative functions because a NAND gate in CMOS has a simple connection configuration of MOSFETs and is fast.

Let us consider representing a NAND gate on a Karnaugh map. The output of the NAND gate with inputs x, y, and z shown in Figure 34.1(a) can be expressed as the loop for xyz consisting of only 0-cells on the map in Figure 34.1(b). (Recall that this loop represents product xyz on an ordinary Karnaugh map in the previous chapters.) In this case, it is important to note that only 0-cells are contained inside the loop

and all the 1-cells are outside. This is because the output of this NAND gate is the complement of the AND operation of inputs, x, y , and z (i.e., xyz ). Thus, if all the 0-cells in the map can be encircled by a single rectangular loop representing a product of some literals (i.e., the number of 0-cells constituting this loop is 2i where i is a non-negative integer), the map represents the output of a NAND gate whose inputs are the literals in the product represented by the loop. The value of f is 0 for x = y = z = 1 (i.e., x = z = 1 and y = 0) in both Figures 34.1(a) and (b). The value of f is 1 if at least one of x, y , and z is 0.

Next, connect a new NAND gate (numbered gate 2) to the output of the above NAND gate (i.e., gate 1) and also connect inputs w and z to the new gate, as shown in Figure 34.2(a). Unlike the case of gate 1 explained in Figure 34.1, the output f of this new NAND gate is not expressed by the entire loop for wz in Figure 34.2(b), but is expressed by the portion of the loop (i.e., only 0-cells inside the loop for wz) because the input of gate 2 from gate 1 becomes 0 for the combination, w = x = z = 1 and y = 0, and consequently f becomes 1 for this combination (if there were no connection from gate 1, the rectangular loop representing wz contains only 0-cells, like gate 1 explained in Figure 34.1). This may be interpreted as the rectangular loop representing wz for gate 2 being inhibited by the loop for gate 1, as shown in Figure 34.2(b). The remainder of the loop (i.e., all 0-cells, which is actually all the 0-cells throughout the map) is encircled by a loop and is shaded. This shaded loop represents the output of gate 2 and is said to be associated with the output of gate 2. In other words, the loop (labeled wz) which represents wz denotes NAND gate 2, whereas the shaded loop (labeled 2) inside this loop in Figure 34.2(b) denotes the output function of gate 2. Notice that the entire loop for gate 1 is shaded to represent the output function of gate 1, because gate 1 has no inputs from other gates (i.e., gate 1 is inhibited by no other shaded loops) and consequently the loop representing gate 1 coincides with the shaded loop representing the output of gate 1 (i.e., the shaded loop associated with the output of gate 1).

Now let us state a formal procedure to design a NAND network on a Karnaugh map.

Procedure 34.1: The Map-Factoring Method: Design of a Network in Double-Rail Input Logic with as few NAND Gates as Possible

1. Make the first rectangular loop of 2i cells. This loop may contain 1-cells, 0-cells, d-cells, or a mixture. Draw a NAND gate corresponding to this loop. As inputs to this gate, connect all the literals in the product that this loop represents. Shade the entirety of this loop.

For example, let us synthesize a network for f = wy ∨ xy ∨ z shown in the Karnaugh map in Figure 34.3(a). Let us make the first rectangular loop as shown in Figure 34.3(a). (Of course, the first loop can be chosen elsewhere.) This loop represents product wx . Draw gate 1, corresponding to this loop and connect inputs w and x to this gate. Shade the entirety of this loop because this gate has no input from another gate and consequently the entirety of this loop is associated with the output function of gate 1.

2. Make a rectangular loop consisting of 2i cells, encircling 1-cells, 0-cells, d-cells, or a mixture. Draw a NAND gate corresponding to this loop. To this gate, connect literals in the product that this loop represents.

Up to this point, this step is identical to Step 1. Now, to this new gate, we further connect the outputs of some or all of the gates already drawn, if we choose to do so. There are the following possibilities:

a. If we choose not to connect any previous gate to the new gate, the new loop is entirely shaded.

b. If we choose to connect some or all of the previously drawn gates to the new gate, encircle and shade the area inside the new loop, excluding the shaded loops of the previously drawn gates connected to the new gate. The shaded loop thus formed is associated with the output of this new gate.

Let us continue our example of Figure 34.3. Let us make the loop labeled y shown in Figure 34.3(b) as a next rectangular loop consisting of 2i cells. Draw the corresponding gate 2. Connect input y to gate 2 because this loop represents y . If we choose to connect the output of gate 1 also to gate 2 (i.e., by choosing the case b above), the shaded loop labeled 2 in Figure 34.3(b) represents the output of gate 2.

3. Repeat Step 2 until the following condition is satisfied:

Termination condition: When a new loop and the corresponding new gate are introduced, all the 0-cells on the entire map and possibly some d-cells constitute the shaded loop associated with the output of the new gate.

Continuing our example, let us make the loop labeled z as a next rectangular loop consisting of 2i, as shown in Figure 34.3(c). Draw the corresponding gate 3 with input z connected. Choosing the case b in Step 2, connect the output of gate 2 as input of gate 3. (In this case b, we have three choices; that is, connection of the output of gate 1 only, connection of the output of gate 2 only, and connection of both outputs of gates 1 and 2. Let us take the second choice now.) Then, the output of gate 3 is expressed by the shaded loop labeled 3 in Figure 34.3(c). Now, the termination condition is satisfied: all the 0-cells on the entire map constitute the shaded loop associated with the output of new gate 3. Thus, a network for the given function f has been obtained in Figure 34.3(c).

For the sake of simplicity, the example does not contain d-cells. Even when a map contains d-cells, that is, cells for don’t-care conditions, the map-factoring method, Procedure 34.1, can be easily used by appropriately interpreting each d-cell as a 0-cell or a 1-cell only when we examine the termination condition in Step 3. D

Notice that we can choose different loops (including the first one in Step 1) in each step, leading to different final networks.

Networks with AND and OR Gates in Two Levels, as a Special Case

If we circle only 1-cells possibly along with some d-cells but without any 0-cells in each step, we can derive a logic network with NAND gates in two levels, as illustrated in Figure 34.4(a). This can be easily converted to the network with AND and OR gates in two levels shown in Figure 34.4(b).

Consideration of Restrictions Such as Maximum Fan-in If the restriction of maximum fan-in or fan-out is imposed, loops and connections must be chosen so as not to violate it. With the map-factoring method, it is easy to take such a restriction into consideration. Also, the maximum number of levels in a network can be easily controlled.

The Map-Factoring Method for NOR Network A minimal network of NOR gates for a given function f can be designed by the following approach.

Use the map-factoring method to derive a minimal network of NAND gates for fd, the dual of the given function f. Then replace NAND gates in the network with NOR gates. The result will be a minimal network of NOR gates for f.