Logic Synthesis with a Minimum Number of Negative Gates:Logic Design of MOS Networks.

Logic Design of MOS Networks

A MOS logic gate can express a negative function and it is not directly associated with a simple logic expression such as a minimal sum. So, it is not a simple task to design a network with MOS logic gates so that the logic capability of each MOS logic gate to express a negative function is utilized to the fullest extent. Here let us describe one of few such design procedures that design transistor circuits directly from the given logic functions [7,8].

A logic gate whose output represents a negative function is called a negative gate. A MOS logic gate is a negative gate. We now design a network with a minimum number of negative gates. The feed-forward network shown in Figure 35.1 (the output of each gate feeds forward to the gates in the succeeding levels) can express any loopless network. Let us use Figure 35.1 as the general model of a loopless network.

The following procedure designs a logic network with a minimum number of negative gates, assuming that only non-complemented input variables (i.e., x1, x2,…, xn) are available as network inputs (i.e., single- rail input logic), based on this model [5,6,9].

Procedure 35.1: Design of Logic Networks with a Minimum Number of Negative Gates in Single-Rail Input Logic We want to design a MOS network with a minimum number of MOS logic gates (i.e., negative gates) for the given function f (x1, x2,…, xn). (The number of interconnections among logic gates is not necessarily minimized.) It is assumed that only non-complemented variables are available as network inputs. The network is supposed to consist of MOS logic gates gi’s whose outputs are denoted by ui’s, as shown in Figure 35.1.

Phase 1

1. Arrange all input vectors V = (x1, x2,…, xn) in a lattice, as shown in Figure 35.2, where the nodes denote the corresponding input vectors shown in parentheses. White nodes, black nodes, and nodes with a cross in a circle, ⊗, denote true vectors, false vectors, and don’t-care vectors, respectively.

The number of 1’s contained in each vector V is defined as the weight of the vector. All vectors with the same weight are on the same level, placing vectors with greater weights in higher levels, and every pair of vectors that differ only in one bit position is connected by a short line.

Figure 35.2 is a lattice example for an incompletely specified function of four variables.

2. We assign the label L(V) to each vector V = (x1, x2,…, xn) in the lattice in Steps 2 and 3. Henceforth, L(V) is shown without parentheses in the lattice.

First assign the value of f to the vector (11…1) of weight n at the top node as L(11…1). If f for the top node is “don’t-care,” assign 0.

In the example in Figure 35.2, we have L(11…1) = 1 because the value of f for the top node is 1, as shown by the white node.

3. When we finish the assignment of L(V) to each vector of weight w, where 0 < w ≤ n, assign L(V′) to each vector V′ of weight w – 1, the smallest binary number satisfying the following conditions:

If f(V′) is not “don’t-care,”

a. The least significant bit of L(V′) is f(V′) (i.e., the least significant bit of L(V′) is 0 or 1, according to whether f is 0 or 1), and

b. The other bits of L(V′) must be determined such that L(V′) ≥ L(V) holds for every vector V of weight w that differs from V′ in only one bit position. In other words, the binary number represented by L(V′) is not smaller than the binary number represented by L(V).

If f (V′) is “don’t-care,” ignore (a), but consider (b) only. [Consequently, the least significant bit of

L(V′) is determined such that (b) is met.]

For the example we get a label L(1110) = 10 for the node for vector V′ = (1110) because the last bit

must be 0 = f(1110) by (a), and the number must be equal to or greater than the label 1 for the top node for vector (1111) by (b). Also, for vector V′ = (1000), we get a label L(1000) = 100 because the

last bit must be 0 = f(1000) by (a), and the label L(1000) as a binary number must be equal to or greater than each of the labels, 10, 11, and 11, already assigned to the three nodes (1100), (1010), and (1001), respectively.

4. Repeat Step 3 until a label L(00…0) is assigned to the bottom vector (00. . .0). Then the bit length of L(00. . .0) is the minimum number of MOS logic gates required to realize f. Denote it by R.

Then make all previously obtained L(V ) into binary numbers of the same length as L(00 . . . 0) by adding 0’s in front of them such that every label L(V ) has exactly R bits. For the example, we have R = 3, so the label L(11 . . . 1) = 1 obtained for the top node is changed to 001 by adding two 0’s.

Phase 2

Now let us derive MOS logic gates from the L(V)’s found in Phase 1.

1. Denote each L(V) obtained in Phase 1 as (u1,…, ui, ui+1, …, uR). As will be seen later, u1,…,ui, ui+1,…, uR are log functions realized at the outputs of logic gates, g1,…, gi, gi+1,…, gR, respectively, as shown in Figure 35.1.

2. For each L(V) = (u1,…, ui, ui+1,…,uR) that has ui+1 = 0, make a new vector (V,u1,…, ui) (i.e., (x1,…, xn, u1,…, ui)) which does not include ui+1,…, uR.

This means the following. For each i, find all labels L(V)’s whose (i + 1)-th bit is 0 and then for each of these labels, we need to create a new vector (x1,…, xn, u1,…, ui) by containing only the first i bits of the label L(V). For example, for u1 = 0 (i.e., by setting i of “ui + 1 = 0” to 0), the top node of the example lattice in Figure 35.2 has the label (u1, u2, u3) = (001) which has u1 = 0 (the label 1 which was labeled in Step 3 of Phase 1 was changed to 001 in Step 4). For this label, we need to create a new vector (x1, x2, x3, x4, u1,…, ui), but the last bit ui becomes u0 because we set i = 0 for ui+1 = 0. There is no u0, so the new vector is (x1, x2, x3, x4) = (1111), excluding u1,…, ui. (In this sense, the case of u1 = 0 is special, unlike the other cases of u2 = 0 and u3 = 0 in the following.) For other nodes with labels having u1 = 0, we create new vectors in the same manner.

Next, for u2 = 0 (i.e., by setting i of “ui+1 = 0” to 1), the top node has the label (u1, u2, u3) = (001) which has u2 = 0. For this label, we need to create a new vector (x1, x2, x3, x4, u1), including u1 this time. So, the new vector (x1, x2, x3, x4, u1) = (11110) results as the label L(1111) = 001 for the top node. Also, a new vector (11010) results for L(1101) = 001, and so on.

3. Find all the minimal vectors from the set of all the vectors found in Step 2, where the minimal vectors

are defined as follows. When ak ≥ bk holds for every k for a pair of distinct vectors A = (a1,…, am) and

Phase 3

The bit length R in label L(00. . .0) for the bottom node shows the number of MOS logic gates in the network given at the end of Phase 2. Thus, if we do not necessarily choose the smallest binary number in Step 3 of Phase 1, but choose a binary number still satisfying the other conditions (i.e., (a) and (b)) in Step 3 of Phase 1, then we can still obtain a MOS network of the same minimum number of MOS logic gates as long as the bit length R of L(00. . .0) is kept the same. (For the top node also, we do not need to choose the smallest binary number as L(l l…), no matter whether f for the node is don’t-care.)

This freedom may change the structure of the network, although the number of logic gates is still the minimum. Among all the networks obtained, there is a network that has a minimum number of logic

gates as its primary objective, and a minimum number of interconnections as its secondary objective. (Generally, it is not easy to find such a network because there are too many possibilities.) D Although the number of MOS logic gates in the network designed by Procedure 35.1 is always minimized, the networks designed by Procedure 35.1 may have the following problems: (1) the number of interconnections is not always minimized; (2) some logic gates may become very complex so that these logic gates may not work properly with reasonably small gate delay times. If so, we need to split these logic gates into a greater number of reasonably simple logic gates, giving up the minimality of the number of logic gates. Also, after designing several networks according to Phase 3, we may be able to find a satisfactory network.