Logic Synthesis with AND and OR Gates in Two Levels:Design of Multiple-Output Networks with AND and OR Gates in Two Levels.

Design of Multiple-Output Networks with AND and OR Gates in Two Levels

So far, we have discussed the synthesis of a two-level network with a single output. In many cases in practice, however, we need a two-level network with multiple outputs; so here let us discuss the synthesis of such a network, which is more complex than a network with a single output.

An obvious approach is to design a network for each output function separately. But this approach usually will not yield a more compact network than will synthesis of the functions collectively, because, for example, in Figure 30.4, the AND gate h, which can be shared by two output gates for fi and fj , must be repeated in separate networks for fi and fj by this approach.

Before discussing a design procedure, let us study the properties of a minimal two-level network that has only AND gates in the first level and only OR gates for given output functions f1, f2,…, fm in the second level, as shown in Figure 30.4, where “a minimal network” means that the network has a minimum number of gates as the primary objective and a minimum number of connections as the secondary objective. The number of OR gates required for this network is at most m. Actually, when some functions are expressed as single products of literals, the number of OR gates can be less than m because these functions can be realized directly at the outputs of the AND gates without the use of OR gates. Also, when a function fi has a prime implicant consisting of a single literal, that literal can be directly connected to the OR gate for fi without the use of an AND gate. (These special cases can be treated easily by modifying the synthesis under the following assumption.) However, for simplicity, let us assume that every variable input is connected only to AND gates in the first level and every

function fi, 1 ≤ i ≤ m, is realized at the outputs of OR gates in the second level. This is actually required with some electronic realizations of a network (e.g., when every variable input needs to have the same delay to the network outputs, or when PLAs which will be described in Chapter 45 are used to realize two-level networks).

Multiple-Output Prime Implicants

Suppose that we have a two-level, multiple-output network that has AND gates in the first level, and m OR gates in the second (i.e., output) level for functions f1, f2,…, fm (as an example, f1, f2, and f3 are given as shown in the Karnaugh maps in Figure 30.5). The network has a minimum number of gates as the primary objective, and a minimum number of connections as the secondary objective. Let us explore the basic properties of such a minimal network.

Property 30.1: First consider an AND gate, g, that is connected to only one output gate, say for fi, in Figure 30.4. If gate g has inputs xg1, xg2,…, xgp, its output represents the product xg1xg2 …xgp . Then, if the product assumes the value 1, fi becomes 1. Thus, the product xg1xg2 …xgp is an implicant of fi . Since the network is minimal, gate g has no unnecessary inputs, and the removal of any input from gate g will make the OR gate for fi express a different function (i.e., in Figure 30.5, the loop that the product represents becomes larger, containing some 0-cells, by deleting any variables from the product and then the new product is not an implicant of fi ). Thus, xg1, xg2,…, xgp is a prime implicant of fi.

Property 30.2: Next consider an AND gate, h, that is connected to two output gates for fi and fj in Figure 30.4. This time, the situation is more complicated. If the product xh1xh2 …xhq realized at the output of gate h assumes the value 1, both fi and fj become 1 and, consequently, the product fi fj of the two functions also becomes 1 (thus, if a Karnaugh map is drawn for fi fj as shown in Figure 30.5, the map has a loop consisting of only 1-cells for xh1xh2 …xhq). Thus xh1xh2 …xhq is an implicant of product fi fj. The network is minimal in realizing each of functions f1, f2,…, fm; so, if any input is removed from AND gate h, at least one of fi and fj will be a different function and xh1xh2…xhq will no longer be an implicant of fi fj. (That is, if any input is removed from AND gate h, a loop in the map for at least one of fi and fj will become larger. For example, if x1 is deleted from M: x1x2x3 for f1f2, the loop for x2x3, product of the remaining literals, appears in the maps for f1 and also for f2 in Figure 30.5. The loop in the map for f2 contains 0-cell. Thus, if a loop is formed in the map for f1f2 as a product of these loops in the maps for f1 and f2, the new loop contains 0-cell in the map for f1 f2. This means that if any variable is removed from xh1xh2 …xhq, the remainder is not an implicant of f1f2.) Thus, xh1xh2…xhq is a prime implicant of the product fi fj . (But notice that the product xh1xh2…xhq is not necessarily a prime implicant of each single function fi or fj, as can be seen in Figure 30.5. For example, M: x1x2x3 is a prime implicant of f1f2 in Figure 30.5. Although this product, x1x2x3, is a prime implicant of f2, it is not a prime implicant of f1 in Figure 30.5.)

When the number of variables is small, we can find all multiple-output prime implicants on Karnaugh maps, as illustrated in Figure 30.5 for the case of three functions of four variables. In addition to the maps for given functions f1, f2, and f3, we draw the maps for all possible products of these functions; that is, f1 f2, f2 f3, f1 f3, and f1 f2 f3. Then, prime-implicant loops are formed on each of these maps. These loops represent all the multiple-output prime implicants of given functions f1, f2, and f3.

Paramount Prime Implicants

Suppose we find all multiple-output prime implicants for the given functions. Then, if a prime implicant P appears more than once as prime implicants for different products of functions, P for the product of the largest number of functions among these products of functions is called a paramount prime implicant for P in order to differentiate this P from other multiple-output prime implicants. As a special case, if P appears only once, it is the paramount prime implicant for P.

For example, among all multiple-output prime implicants for f1, f2, and f3 (i.e., among all prime implicants for f1f2, f2f3, f1f3, and f1f2f3 shown as loops in Figure 30.5), the prime implicant x1x2x4 appears three times in Figure 30.5. In other words, x1x2x4 appears as a prime implicant for the function f1 (see the map for f1 in Figure 30.5), as a prime implicant for f2, and also as a prime implicant for the product f1f2 (in the map for f1f2, this appears as L: x1x2x4). Then, the prime implicant x1x2x4 for f1 f2 is the paramount prime implicant for x1x2x4 because it is a prime implicant for the product of two functions, f1 and f2, but the prime implicant x1x2x4 for f1 or f2 is a prime implicant for a single function f1 or f2 alone. In the two-level network, x1x2x4 for the product f1f2 realizes the AND gate with output connections to the OR gates for f1 and f2, whereas

x1x2x4 for f1 or f2 realizes the AND gate with output connection to only the OR gate for f1 or f2, respectively. Thus, if we use x1x2x4 for the product f1 f2 instead of x1x2x4 for f1 or f2 (in other words, if we use AND gates with more output connections) then the network will be realized with no more gates. In this sense, x1x2x4 for the product f1 f2 is more desirable than x1x2x4 for the function f1 or f2. Prime implicant x1x2x4 for the product f1 f2 is called a paramount prime implicant, as formally defined in the following, and is shown with label L in a bold line in the map for f1f2 in Figure 30.5; whereas x1x2x4 for f1 or f2 alone is not labeled and is also not in a bold line in the map for f1 or f2. Thus, when we provide an AND gate whose output realizes the prime implicant x1x2x4 , we can connect its output connection in three different ways, i.e., to f1, f2, or both f1 and f2, realizing the same output functions, f1, f2, and f3. In this case, the paramount prime implicant means that we can connect the largest number of OR gates from this AND gate; in other words, this AND gate has the largest coverage, although some connections may turn out to be redundant later.

Definition 30.2: Suppose that when all the multiple-output prime implicants of f1,…, fm are considered, a product of some literals, P, is a prime implicant for the product of k functions fp1, fp2,…, fpk (possibly also prime implicants for products of k – 1or fewer of these functions), but is not a prime implicant for any product of more functions that includes all these functions fp1, fp2,…, fpk. (For the above example, x1x2x4 is a prime implicant for the product of two functions, f1 and f2, and also a prime implicant for a single function, f1 or f2. But x1x2x4 is not a prime implicant for the product of more functions, including f1 and f2, that is, for the product f1 f2 f3.)

Then, P for the product of fp1, fp2,…, fpk is called the paramount prime implicant for this prime implicant (x1x2x4 for f1 f2 is a paramount prime implicant, but x1x2x4 for f1 or f2 is not). As a special case, if P is a prime implicant for only one function but not a prime implicant for any product of more than one function, it is a paramount prime implicant (B: x1x3x4 for f1 is such an example in Figure 30.5).

In Figure 30.5, only labeled loops shown in bold lines represent paramount prime implicants.

If a two-level network is first designed only with the AND gates that correspond to the paramount prime implicants, we can minimize the number of gates. This does not necessarily minimize the number of connections as the secondary objective. But in some important electronic realizations of two-level

networks, such as PLAs (which will be explained later) this is not important. Thus, let us consider only the minimization of the number of gates in the following for the sake of simplicity.

Design of a Two-Level Network with a Minimum Number of AND and OR Gates In the following procedure, we will derive a two-level network with a minimum number of gates (but without minimizing the number of connections as the secondary objective) by finding a minimal number of paramount prime implicants to represent the given functions.

Procedure 30.1: Design of a Multiple-Output Two-Level Network That Has a Minimum Number of Gates Without Minimizing the Number of Connections We want to design a two-level network that has AND gates in the first level and OR gates in the second level. We shall assume that variable inputs can be connected to AND gates only (not to OR gates), and that the given output functions f1, f2,…, fm are to be realized only at the outputs of OR gates.

Suppose we have already found all the paramount prime implicants for the given functions and their products.

1. Find a set of a smallest number of paramount prime implicant loops that covers all 1-cells in Karnaugh maps for the given functions f1, f2,…, fm. In this case, maps for their products, such as f1 f2, need not be considered. If there is more than one such set, choose a set that has as large loops as possible (i.e., choose a set of loops such that the total number of inputs to the AND gates that correspond to these loops is the smallest).

For example, suppose that the three functions of four variables, f1, f2, f3, shown in the Karnaugh maps in Figure 30.5 are given. Then, using only the bold-lined loops labeled with letters (i.e., paramount prime implicants), try to cover all 1-cells in the maps for f1, f2, and f3 only (i.e., using the only top three maps in Figure 30.5). Then, we find that more than one set of loops have the same number of loops with the same sizes. AKLCDMNFHJ, one of these sets, covers all functions f1, f2, and f3, as illustrated in Figure 30.6.

2. Construct a network corresponding to the chosen set of paramount prime implicant loops.

Then, the network of 13 gates shown in Figure 30.7 has been uniquely obtained. Letter N (i.e., x1x2x3x4), for example, is a paramount prime implicant for the product f1 f2 f3, so the output of an AND gate with inputs, x1, x2, x3, and x4 , is connected to the OR gates for f1, f2, and f3.

3. Then delete unnecessary connections, or replace some logic gates by new ones, by the following steps from the logic networks derived in Step 2, by considering whether some Karnaugh maps have a paramount prime implicant loop that is inside another one, or adjacent to another one.

a. If, in a Karnaugh map for a function fi, there is a paramount prime implicant loop that is inside another one, then the former is not necessary, because the 1-cells contained in this loop are covered by the latter loop. Thus, we can delete the connection from the AND gate corresponding to the former loop to the OR gate for fi, without changing the output functions of the logic network.

For example, loop K in the map for f2 is inside the loop C in Figure 30.6. Thus, we can delete K from the map for f2, because the 1-cell in K is covered by the loop C. This means that we can delete the connection (shown with * in Figure 30.7) from the AND gate labeled K in Figure 30.7. Similarly we can delete the loops N from the maps for f1 and f2, and accordingly, the connections (shown with * in Figure 30.7) from the AND gates labeled N to the OR gates for f1 and f2.

b. If, in a Karnaugh map for a function fi, there is a paramount prime implicant loop that is adjacent to another one, we may be able to expand the former by incorporating some 1-cells of the latter without having any 0-cells and at the same time replace the loop by the expanded loop (i.e., the number of logic gates unchanged). If we can do so, replace the former loop by the expanded loop. The expanded loop represents a product of fewer literals. Thus, we can delete the connection to the AND gate corresponding to the expanded loop without changing the output functions of the logic network.

For example, loop K in the map for f1 has an adjacent loop A. Then we can replace the loop K by a larger loop (i.e., loop B in Figure 30.5) by incorporating the 1-cell on its left, which represents the product x1x3x4. Also, K appears only in the map for f2, beside K in the map for f1. K in the map for f2 is concluded to be eliminable, so the AND gate for K in Figure 30.7 can be replaced by the new gate for B, keeping the number of logic gates unchanged. This means that we can delete the connection of input x2 (shown with ** in Figure 30.7) to the AND gate labeled K in Figure 30.7 (i.e., this is essentially replacement of K by B). Thus we can delete in totally, 4 connections from the logic network shown in Figure 30.7, ending up with a simpler network with 13 gates and 41 connections.

When the number of paramount prime implicants is very small, we can find, directly on the maps, a minimum number of paramount prime implicants that cover all 1-cells in the maps for f1, f2,…, fm (not their products) and derive a network with a minimum number of gates, using Procedure 30.1. But when the number of paramount prime implicants is many, the algebraic procedure of Section 4.6 in Ref. 5 is more efficient.

Procedure 30.1 with the deletion of unnecessary connections, however, may not necessarily yield a minimum number of connections as the secondary objective, although the number of gates is minimized as the primary objective. If we want to have a network with a minimum number of connections as the secondary objective, although the network has the same minimum number of gates as the primary objective, then we need to modify Procedure 30.1 and then delete unnecessary connections, as described as Procedure 5.2.1 in Ref. 5. But this procedure is more tedious and time-consuming.

Networks That Cannot be Designed by the Preceding Procedure Notice that the design procedures in this section yield only a network that has all AND gates in the first level and all OR gates in the second level. (If 0-cells on Karnaugh maps are worked on instead of 1-cells in Procedure 30.1, we have a network with all OR gates in the first level and all AND gates in the second level.) If AND and OR gates are mixed in each level, or the network need not be in two levels, Procedure 30.1 does not guarantee the minimality of the number of logic gates [6].

These two problems can be solved by the integer programming logical design method (to be mentioned in Chapter 34, Section 34.5), which is complex and can be applied to only networks of a small number of gates.

Procedure 30.1 has important applications, such as PLAs, it but cannot be applied for designing large PLAs. For multiple-output functions with many variables, absolute minimization is increasingly time-consuming. Using BDD (described in Chapter 29), Coudert, Madre, and Lin extended the feasibility of absolute mini- mization [2,3]. But as it is becoming too time-consuming, we have to give up absolute minimization, resorting to heuristic minimization, such as a powerful method which is called MINI [4] and was later improved as ESPRESSO [1].