Logic Synthesis with NAND (or NOR) Gates in Multi-Levels:Design of NAND (or NOR) Networks in Single-Rail Input Logic.

Design of NAND (or NOR) Networks in Single-Rail Input Logic

In Section 34.2, we discussed the design of a multi-level NAND networks in double-rail input logic, using the map-factoring method. Now let us discuss the design of a multi-level NAND network in single-rail input logic (i.e., no complemented variables are available as inputs to the network) using the map-factoring method. First let us define permissible loops on a Karnaugh map. A permissible loop is a rectangle consisting of cells that contains the cell whose coordinates are variable values of all 1’s (i.e., the cell marked with the asterisk in each map in Figure 34.5), where i is one of 0, 1, 2, …. In other words, a permissible loop must contain the particular cell denoted by the asterisk in each map in Figure 34.5, where this permissible loop consists of 1-cells, 0-cells, d-cells (i.e., don’t-care cells), or a mixture. All permissible loops for three variables are shown in Figure 34.5.

In the following, let us describe the map-factoring method. The procedure is the same as Procedure 34.1 except the use of permissible loop, instead of rectangular loop of 2i-cells at any place on the map, for representing a gate.

Procedure 34.2: The Map-Factoring Method: Design of a Network in Single-Rail Input with as Few NAND Gates as Possible.

We want to design a network with as few NAND gates as possible, under the assumption that non-complemented variables but no complemented variables are available as network inputs.

1. Make the first permissible loop, encircling 1-cells, 0-cells, d-cells, or a mixture of them. 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, when a function f = x ∨ y ∨ z

is given, let us choose the first permissible loop, as shown in Figure 34.6(a), although there is no reason why we should choose this particular loop. (There is no guiding principle for finding which loop should be the first permissible loop. Another loop could be better, but we cannot guess at this moment which loop is the best choice. Another possibility in choosing the first permissible loop will be shown later in Figure 34.7(a).) The loop we have chosen is labeled 1 and is entirely shaded. Then, NAND gate 1 is drawn. Since the loop represents x, we connect x to this gate.

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

In the above example, a new permissible loop is chosen as shown in Figure 34.6(b), although there is no strong reason why we should choose this particular permissible loop. This loop represents product yz, so y and z are connected to the new gate, which is labeled 2.

To this new NAND gate, we further connect the outputs of some 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 permissible loop is entirely shaded.

If we prefer not to connect gate 1 to gate 2 in the above example, we get the network in Figure 34.6(b). Ignoring the shaded loop for gate 1, the new permissible loop is entirely shaded and is labeled 2, as shown in Figure 34.6(b).

b. If we choose to connect some previously drawn gates to the new gate, encircle and shade the area inside the new permissible loop, excluding the shaded loops of the previously drawn gates which are connected to the new gate. In other words, the new permissible loop, except its portion inhibited by the shaded areas associated with the outputs of the connected previously drawn gates, is shaded.

In the above example, if we choose to connect gate 1 to gate 2, we obtain the network in Figure 34.6(b′). The portion of the new permissible loop that is not covered by the shaded loop associated with gate 1 is shaded and labeled 2.

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

Termination condition: When a new permissible 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 (i.e., the shaded loop associated with the output of the new gate contains all the 0-cells on the entire map, but no 1-cell).

Let us continue Figure 34.6(b). If we choose the new permissible loop as shown in Figure 34.6(c), and if we choose to connect gates 1 and 2 to the new gate 3, the above termination condition has been satisfied; in other words, all the 0-cells on the entire map constitute the shaded loop associated with the output of the new gate 3.

We have obtained a network of NAND gates for the given function. Depending on what permissible loops we choose and how we make connections among gates, we can obtain different networks. After several trials, we choose the best network.

As an alternative for the network for f obtained in Figure 34.6(c), let us continue Figure 34.6(b′). If we choose the new permissible loop as shown in Figure 34.6(c′), and gates 1 and 2 are connected to gate 3, we satisfy the termination condition in Step 3, and we have obtained the network in Figure 34.6(c′), which is different from the one in Figure 34.6(c).

If we choose the first permissible loop 1, as shown in Figure 34.7(a), differently from Figure 34.6(a), we can proceed with the map-factoring method as shown in Figure 34.7(b), and we obtain the third network as shown in Figure 34.7(c). Of course, we can continue differently in Figures 34.7(b) and (c). Also, the first permissible loop can be chosen differently from Figure 34.6(a) or 34.7(a), but it is too time-consuming to try all possibilities, so we have to be content with a few trials. We need a few trials to gain a good feeling of how to obtain good selections, and thereafter, we may obtain a reasonably good network. For the above example, f = x ∨ y ∨ z , the network obtained in Figure 34.7, happens to be the minimal network (the minimality of the number of gates and then, as the secondary objective, the minimality of the number of connections can be proved by the integer programming logical design method.) [4,6]. D As might be observed already, any permissible loop in the case of four variables represents a product of non-complemented literals (e.g., the loop chosen in Figure 34.6(b) represents yz) by letting the permissible loop contain the cell with coordinates, w = x = y = z = 1, whereas any rectangular loop of 2i cells, which does or does not contain this cell, represents a product of complemented literals, non-complemented literals, or a mixture as observed previously.

Extension of the Concept of Permissible Loop

By defining permissible loops differently, we can extend the map-factoring method to designing NAND gate networks with some variables complemented and others non-complemented as network inputs. This is useful when it is not convenient to have other combinations of complemented variables and non-complemented variables as network inputs (e.g., long connections are needed). For example, let us define a permissible loop as a rectangular loop consisting of 2i cells which contains the cell with coordinates, x = y = 0 and z = 1. Then, we can design NAND networks with only x , y , and z as network inputs. Some functions can be realized with simpler networks by using some network inputs complemented. For example, the function in Figure 34.7 can be realized with only one NAND gate by using x , y , and z as network inputs, instead of three gates in Figure 34.7(c). Complemented inputs can be realized at the outputs of another network to be connected to the inputs of the network under consideration, or can be realized with inverters. When these network inputs run some distance on a PC board or a chip, the area covered by them is smaller than the case of double-rail input logic because the latter case requires another set of long-running lines for having their complements.