M mm B Digitized by the Internet Archive in 2013 http://archive.org/details/resultsofsynthes789cull / - - 1-789 /; i a t < RESULTS OF THE SYOTHE! TIMAL I AND OB OATE8 POUR-Vi BY A 131ANOH- AND- ROUND CO! by J.N. Culliney T. Nakagawa S. Muroga March 197^ DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS The Library of trie JUN 9 197G University 01 Illinois at Urbana • Champaign :» ♦ UIUCDCS-R-76-1 INSULTS OF THE SYNTHESIS OF OPTIMAL NETWORKS OF AND AND OR GATES FOR FOUR- VARIABLE SWITCHING FUNCTIONS BY A BRANCH- AND- BOUND COMPUTER PROGRAM J.N. Culliney T . Nakagawa S . Muroga March 1976 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 This work was supported in part by the National Science Foundation under Grant No. GJ-^0221. TABLE OF CONTENT;. 1. INTRODUCTION . SYNTHESIS OF OPTIMAL NETWORKS 2.1 Simplification of Synthesis Problem by Consideration -j of NPN-Equivalence Classes 2.2 Choice of NPN-Equivalence Class Representative Functions 5 2.3 Optimal Networks and Use of Optimal Network Listing 6 ?.k Observations Concerning the Optimal Network Synthesis Results . . .15 3. ANALYSIS OF COMPUTATION TIME AND PROGRAM- RELATED STATISTICS 18 h. CONCLUSIONS 37 LIST OF REFERENCES 39 APPENDIX A: LIST OF NPN-EQUIVALENCE CLASSES AND RELATED DATA UO APPENDIX B: OPTIMAL NETWORK LISTING ^7 1. INTRODUCTION The purpose of this paper is twofold: (l) to present all optimal feed-forward networks* of AND and OR gates for each of almost every switching function of four or fewer variables and (?) to present statistics of the computations which resulted in the optimal networks. The authors know of no previous work which approaches this in the scope of the proven optimal AND/OR network results obtained. The 65,536 different switching functions of four or fewer variables can be grouped into 222 so-called "NPN- equivalence classes" for the purpose of generating networks of AND and OR gates to realize the functions. In this work, all optimal networks of AND and OR gates were found for each of 219 of these 222 classes. In the case of the remaining 3 equivalence classes, networks were obtained, but they were not proven to be optimal due to excessive computation time (it is possible they are not). The program which obtained the optimal networks utilizes a "branch- and-bound" algorithm "-. This program, ILLOD-(ANDOR-B) ' (for ILlinois LOgical Design with AND and OR gates by Branch-and-bound method), was written in FORTRAN, and the implemented branch-and-bound algorithm generally parallels that developed (see [3], O], [8], [9], [10], and [11]) for the synthesis of optimal networks of NAND gates. ILLOD-(ANDOR-B) is capable of designing feed-forward, optimal, single- or multiple-output networks of AND and OR gates under various optimality criteria and optional fan- in, fan-out, and/or level restrictions. However, the results presented here were not obtained under any of these latter three restrictions. + "Optimal network" may have different meanings for different readers. Here, the meaning is a network with the least number of connections among those with the least number of gates. Section 2 describes in greater detail the way in which the optimal network synthesis problem was organized for efficient solution, gives instructions for obtaining optimal networks realizing desired functions of four or fewer variables from those optimal networks listed in Appendix R for NPK- equivalence class representative functions, and makes certain observations concerning the optimal networks synthesized. The performance of the program in solving the synthesis problems is analyzed in Section 3. Section k reviews the contents of earlier sections and presents some conclusions. A list of NPN- equivalence classes and corresponding representative functions is given in Appendix A. Additional information related to the synthesis of optimal networks for each representative function is included. As mentioned, all distinct optimal networks for each representative function are shown in Appendix B. . SYNTHKSIS OF OPTIMAL NETWO This section gives the organization of the synthesis problem, to find complete sets of optimal AND/OR networks for all switching functions of four or fewer variables, which enabled its (almost complete) solution in a feasible amount of computation time. In addition, the use of the listing of optimal net- works for NPN- equivalence class representative functions in Appendix B to obtain optimal networks for any given function of four or fewer variables (except one in the three NPN- equivalence classes for which optimal networks were not obtained) is described. 2.1 Simplification of Synthesis Problem by Consideration of NPN-Equivalen-e Classes To directly synthesize all optimal feed-forward networks of AND and OP gates for each of 65,536 switching functions of four or fewer variables would require an enormous amount of computation time. There exists, however, a means by which the synthesis problem can be drastically reduced in nature. The 65,536 functions of four or fewer variables can be partitioned into only 222 "NPN- equivalence classes." Two switching functions,^ and fp, are said to be NPN- equivalent (i.e., are in the same NPN- equivalence class) if one, say f , can be obtained from the other, f , by: (l) negating one or more variables of f ; (2) permuting the variables of f ; and/or (3) negating ff 2 (i.e., f 2 )o An NPN- equivalence class has the property that an optimal network of AND and OR gates for one function in the class can be directly and (relatively) easily changed into an optimal network (always with the identical configuration of gates and connections) for any other function of the same class. Thus, finding all optimal networks for one function (called an NPN- equivalence class representative function) chosen from each of the 222 NPN- equivalence classes implicitly results in a determination of all of the optimal networks for all 6^,536 switching functions of four or fewer variables. This was, in fact, the approach taken. Of the 222 NPN-equivalence classes: 208 contained functions of exactly four variables; 10, functions of exactly three variables; 2, functions of exactly two variables; 1, functions of exactly one variable; and 1, functions of zero variables. Functions of three or fewer variables were treated as degenerate four- variable functions. In the four-variable case, it is possible for an NPN-equivalence class to have as many as 768 members: 16 (number of different combinations of complementing four variables ) x 2.k (number of different ways to permute four variables) x 2 (function complemented or not) ~ 768 Since different combinations of negations and permutations often produce the same function from a given one, many NPN-equivalence classes have fewer than 768 members. The average size for an NPN-equivalence class for functions of four or fewer variables is approximately 295 members (although no class has exactly 295 members). Choice of IT rN-lvjui valence Class Representative Functions In order to precisely express different four-variable functions in a shorthand manner (i.e., rather than writing out the or 1 values of th function for all 16 possible input combinations), a hexadecimal notation was chosen. This four digit hexadecimal representation for a given function, f, is derived by expressing the column (or row) of f's values in a truth table in hexadecimal digits. For example, the function f defined by the truth table in Fig. 2.2.1 is denoted "17AC" in hexadecimal notation. i = 1 2 1 J h 5 6 7 8 9 10 11 12 13 Ik 15 x (i) = 1 1 1 1 1 1 1 1 4 i] = 1 1 1 1 1 1 1 1 4 i] = 1 1 1 1 1 1 1 1 ^ = 1 1 1 1 1 1 1 1 f(. (i) ) = 1 1 1 1 1 1 1 1 V J V jk w ; tlr," "17AC" Fig. 2.2.1 Example of hexadecimal representation of a function. The hexadecimal (base lb) digits A,B,C,D,E, and F correspond, respectively, to the base 10 values 10,11,12,13,1'+, and 15. With this defined, the manner in which the N.PN- equivalence class representative function was chosen for each class can be simply stated: the function selected as the representative of each NPN-equivalence class was that function having the hexadecimal representative of smallest value among all members of the respective class. 2.3 Optimal Networks and Use of Optimal Network Listing In Appendix B there appears a listing of networks of AND and OR gates which realize the chosen representative functions of the 222 NPN- equivalence classes of four or fewer variables. In the case of all but 3 classes, the networks listed for each representative function consist of all distinct optimal networks which exist for that function. In some cases (to be discussed shortly), additional optimal networks can be obtained by certain combinations of complementing variables, permuting variables, and/or interchanging gate types (i.e., the simultaneous change of all OR gates to AND gates or vice versa), but the newly obtained networks are not considered distinct. None of the 219 classes for which proven optimal networks were obtained required more than seven AND and OR gates. For the representative functions (hexadecimal ) 1669, I6E9, and 6996 of the remaining 3 classes (nos. I83, 206, and 222, respectively), networks were obtained which realize the functions, but which are not known to be optimal (in each of these cases, due to excessive computation time, the branch-and-bound program which would have either established optimality or led to an improved solution was terminated short of completion). The networks which were obtained required eight gates in the case of functions 1669 and I6E9 (representative classes no. 183 and no. 206) and nine gates in the case of function 6996 (no. 222). Additional computations established that no networks of P than eight gates exist which realise functions 1669 or I6E9. This was proven by running the branch-and-bound program with a cost bound restricting it to consideration of networks of seven or fewer gates. For both function 1669 and l6E9 the program ran to completion without having encountered a solution feasible under the cost bound. Similar attempts to establish a lower bound on the number of gates necessary to realize function 6996 were not made due to the likelihood of an excessive computation time requirement. Table 2.3.1 shows the distribution of representative functions of n variables found to optimally require R gates (n = 0,1, ..., h; R = 0,1, .„., 9) (in the case of the two 0-variable and 1- variable representative functions, the optimal solutions were obvious and did not require the use of a computer. ) Number of Number of Number of Number of Number of Number of Gates in 0-variable 1-variable 2-variable 3-variable ^--variable Optimal Represent. Represent. Represent. Represent. Represent. Network Functions Functions Functions Functions Functions 1 1 1 1 1 1 2 1 2 3 1 k Ik h 3 57 5 1 88 6 35 7 8 8 2 9 i f For this representative function, optimal networks of fewer gates may exist, Table 2.3.1 Distribution of NPN- equivalence class representative functions. It would not have been difficult to generate all optimal networks for all 65,536 switching functions of four or fewer variables (except those in equivalence classes no. 183, no. 206, and no. 222) from the results obtained for the 222 representative functions. However, it would be obviously impractical to include all such networks in this paper. Even providing a table of the negations and permutations required to convert optimal networks for representative functions into optimal networks realizing desired non-representative functions would require an estimated Gh additional pages. Hence, in order to conserve space, a simple method to obtain optimal networks for non- representative functions by the conversion of those listed for representative functions is outlined. From this, the frequent user of these results can easily create his own computer program to determine the specific conversion steps necessary for a given function. The infrequent user may find it feasible to determine these steps by inspection. Given a function f which is not among those NPN- equivalence class representative functions for which optimal networks are listed in Appendix B and for which optimal networks are desired, proceed as follows: (l) Perform all 768 possible combinations of the following three steps ((a), (b), and (c)) for f, recording all combinations for which f is invariant and noting a combination (there may be one or more) which produces the function f ' with the hexadecimal representation of least value . (a) Complement any zero, one, or more variables of f (16 possibilities). (b) Perform any permutation of the variables of f (2k possibilities). (c) Complement the resulting function or leave uncomplemented (2 possibilities). Function f is tl -ntatr. on for - i valence ^lass of which C is a member. Look in Append ' o find all optimal networks for f ' . Convert each optimal network, N' , realising f ' into an optimal netw< N, realizing f by recalling the combination of steps (la), (lb), and (lc) which led to f and performing the following corresponding steps: (a) Permute the variables in N' in a manner inverse to that in which they were permuted in step (lb). (E.g., if x. were permuted to x. in (lb), every occurrence of x. and x. in N' should be replaced J J J by x. and x., respectively.) (b) Complement the same variables in the resulting network which were complemented in step (la). (c) If the function was complemented in step (lc), interchange the gate types, AND and OR, for every gate in the network and complement every variable in the network inputs. (h) If desired, generate additional (though not fundamentally different) optimal networks by regarding f ' as identical to f and, for every network N' realizing f* (f), following steps (ja), (3b), and (3c) for each combination of steps (la), (lb), and (lc) under which f was found to be invariant in step (l). Steps (3a) and (3b) are purposely in reverse order of their (la) and (lb) counterparts. This is to reduce possible confusion which might otherwise arise in cases where some variables are both permuted and complemented. 10 For functions which are among the chosen NPN- equivalence class representative functions, steps (l) and (If) can still be used to find additional (hut not fundamentally different) optimal networks. In certain circumstances, knowledge of these alternative networks may be important (e.g., when reducing the number of gate delays between a critical variable and the network output). In order to illustrate the preceding method to determine optimal networks for all functions of four (or fewer) variables, consider the function f shown in truth table form in Table 2.3.2. Its hexadecimal representation is seen to be D686. By looking at the Ust of representative functions in Appendix A, f is found not to be a representative function . Performing step (l) of the above process, f with hexadecimal representation I69E is revealed to be the representative function of the equivalence class to which f belongs (again see Table 2.3.2). By locating I69E in the list in Appendix A, the number of the equivalence class is determined to be 201. f is obtained from f by complementing x, (step (la)); permuting x^ and x^ (step (lb)); and complementing the resulting function (step (lc)): f'(x 1 ,x 2 ,x ? ,x J| ) = f(x 1 ,x. 3 ,x 2 ,x i+ ). Also as a consequence of step (l), complementing and interchanging variables x ? and x^ is found to leave the function f unchanged (this information is used in step (h))\ f(x 1 ,x 2 ,x 3 ,x [+ ) = f( Xl ,x^,x 3 ,x 2 ), 11 Followin ), one optimal network fur f (shown in Fie. . .1) is obtained from Appcn ; Fig. . . illustrates the conversion of this network into an optimal network for f. First, according to step (3a), variables x p and x^ are interchanged (when only two variables are involved, a permutation and its inverse are identical), resulting in 1 he network shown in Fig. 2.3.2 (b). Next, following step (3b), variable :■:, is complemented wherever it appears in the network, resulting in Fig. 2.3.2 (c). Finally, according to step (3c), the gate types, AND and OR, are interchanged for every gate in the network, and every variable in the network inputs is complemented. This results in the optimal network for f shown in Fig. 2.3.2 (d). This network is the only distinct optimal network for f. If another distinct optimal network had eidstoc for f, there would have been a corresponding second optimal network listed in Appendix B for f, the NPN- equivalence class representative function. In this particular case, following step (k) (interchanging and complementing variables x g and x, in Fig. 2.3.2 (d)) just results in the same optimal network (gates 2 and 5 are simply interchanged). This does not always occur, however, and Fig. 2.3.3 shows an example of an optimal network (for the representative function of class no. 208) and its variations obtained through the use of step (h) based on information from step (l). 12 x l X 2 X 3 \ f 1 "\ 1 1 1 1 1 1 J 1 *> 1 1 1 1 1 1 1 1 1 J 1 1 %l 1 1 1 1 1 1 1 J 1 1 -\ 1 1 1 1 1 1 1 1 ' 1 1 1 1 J D 6 1 1 1 1 1 1 1 1 >k 1 6 J 9 J J Table 2.3.2 Truth table of function f for which optimal networks are desired ■and its JWN- equivalence class representative function f ' . Fig. 2.J.1 Optimal network given in Appendix B for function f of Table 2.3.2. _ ' - f * X. *2 ^3 X 2 x I] (a) Original optimal network realizing f ' . (b) Network in (a) with variables x and x interchanged. ^2 *3 X l + X 2 X 3 x, x. (c) Network in (b) with variable x, complemented. (d) Network in (c) with gate types interchanged and input variables complemented. Optimal network for f. Fig. 2.3.2 Conversion of optimal network for f* (hexadecimal: 169s) into optimal network for f (hexadecimal: D086). 14 (a) Optimal network given in Appendix B for the representative function, f, of class no. 208 (hexadecimal representation: I78E). (b) Additional optimal network for f simply derived from (a) by recognition of the fact that f(x 1 ,x 2 ,x 3 ,x 1+ ) = f(x 1 ,3C 2 ,x lf ,x| X 2 X 3 x k *1 OR ^2 — 1 x_ A OR A — > x? c i — s — r "4 - 3 f OR 1 (c) Additional optimal network for f simply derived from (a) by recognition of the fact that f(x V C 2' x 3 >\ : f ( x 1 ^ 2 ,x 3 ,x 1| ) (d) Additional optimal network for f simply derived from (a) by recognition of the fact that f(x 1 ,x 2 ,x 3 ,x i| ) = f(x 1 ,x 2 ?vfc — '- ■ 0ptlmal network for function f, hexadecimal representation ±m, and three additional optimal networks obtained from it by steps (l) and i'4) of method to generate a complete set of optimal networks for a given funotio ■hscrvatioiK. Ami • . • i • r 1 1 pg bhe optimal Network ::ynUi<-.: i ;■ Of all the representative functions, only five, DOB. , and 212, have optimal networks of four levels (again note that optimal networks were not established for three representative functions). Of these, only nos. P03 and 204 have optimal networks exclusively of four levels. No representative functions have optimal networks of five or more levels. Optimal two-level networks were found for 92 representative functions, and 12? representative functions have optimal networks of three levels. Fig. 2.4.1 illustrates the distribution of representative functions having optimal solutions of different numbers of levels (the three functions for which optimal networks were not established are not considered in Fig. 2.4.1). The two functions having optimal networks of both two and three levels are no. 124 and no. 147. O-level optimal networks 1- level opt imal networks 4- level optimal optimal optimal networks networks networks Fig. 2.4.1 Numbers of representative functions having optimal networks of different numbers of levels. (Note that three functions for which optimal networks were not established are omitted. ) Although, in 92 cases, conventional methods capable of synthesizing optimal two-level restricted networks can obtain results shown here for functions of four or fewer variables, these conventional methods can not prove that their two-level-restricted optimal networks are also non- level-restricted optimal 16 networks (obviously, they frequently are not). Thus, in these cases, the branch- and -bound program was still necessary to establish optimality under no level restrictions. Table 2.14,1 gives the number of representative functions found to have s distinct optimal solutions, s = 1,2, ..., 7* Almost all representative s, number of distinct optimal solutions number of functions with exactly s optimal solutions number of functions with s "best known" solutions t 1 179 l 2 31 2 3 6 h 1 5 1 6 7 l Corresponds to the three cases in which optimal networks were not established, Table 2.4.1 Number of representative functions found to have s distinct optimal solutions, s = 1>2, ..., 7« functions have only one or two distinct optimal solutions. The greatest number of distinct optimal solutions found, occuring for class no. 212, is seven. Only one optimal network for one representative function, no. 212, has a gate with a fan-out of three. Forty representative functions have, at least one optimal network containing a gate with a fan-out of two (networks obtained for representative functions nos. 1.8.3, 206, and 222 also contain gates 17 With a fan-out of two, but are not included in this total). 177 r< functions have optimal networks which consist exclusively of ga h a single fan-out. No gates appear in any of the optimal networks with a fan-out greater than three. Just five representative functions have optimal networks containing a gate with a fan-in of five (networks found for class nos. 183 and 206 also contain gates with a fan-in of five, but are not included in this total). None had a gate with a fan- in greater than five in its optimal networks. 18 3. ANALYSIS OF COMPUTATION TIME AND PROGRAM- RELATED STATISTICS As previously stated, the computer program which obtained the optimal AND/OR networks presented in this report is ILLOD-(ANDOR-B) J' 1 -'- 1 . This program was written in FORTRAN, compiled by the FORTRAN H (OPT 2) Compiler, Level 18 (Sept 69), executed under OS/MVT (20.6), and timed by the system- supplied routine STEPZ on an IBM 360/75J computer. ILLOD- (ANDOR-B) is capable of designing optimal single- or multiple-output networks of AND and OR gates under various optimality criteria (e.g., minimum number of gates, minimum number of connections, minimum number of gates plus connections, minimum number of connections among those solutions having minimum number of gates, etc.) and optional fan-in, fan-out, and/or level restrictions. In addition, the program requires a "cost bound" which can be used to speed the computation in cases where there is a known limit on the cost of optimal solutions. When a feasible solution is known to exist, though no definite limit on the possible optimal cost is known, any reasonably large number will usually suffice as a cost bound. In the optimal network syntheses which were performed for this report , no fan-in, fan-out, or level restrictions were imposed on the networks to be synthesized . For each synthesis problem, the cost bound was set at 9 gates and 99 connections (it can be easily shown that no more than 9 AND and OR gates and 72 connections are needed to realize a four-variable function). The optimal network synthesis problems serve as an excellent test set for the study and analysis of the capabilities and characteristics of the I.LL0D- (ANDOR-B) program - both as an example of branch-and-bound algorithms and as a tool for obtaining optimal, or, possibly, merely feasible, solutions to synthesis problems of networks of AND and OR gates. As a consequence of this opportunity, this section is included in the present report. Number of cases Number of cases , '. r of Number of cases first feasible has first feasible has gates in optimal first feasible optimal numl one more gate solution is optimal of gates only than optimal 1 1 2 1 3 3 1 k 1 2 5 1 Table 3*1 Number of 3-variable representative functions with optimal networks of \ gates for which first feasible solutions are at certain distances from optimal. Number of cases Number of cases Number of cases Number of Number of cases first feasible first feasible first feasible es in optimal first feasible has opt. no. has one more has two more ution is optimal of gates only gate than opt. gates than opt. 1 1 2 1 1 3 8 3 3 k 28 20 9 5 20 55 12 1 6 3 2k 7 1 7 7 1 le 3-2 Number of U-variable representative functions with optimal networks of R es for which first feasible solutions are at certain distances from optimal. 20 The branch-and-bound algorithm first seeks a feasible solution to "bound" further "branches" which must be searched in the quest for optimal solutions. For example, if a feasible solution consisting of five gates is found, there is no further need to pursue a potential solution -when it becomes apparent that more than five gates will be needed. Finding a first feasible solution as quickly and as nearly optimal as possible is critical to the efficiency of a branch-and-bound algorithm. For problems in which optimal networks were synthesized for functions of three and four variables, respectively, Tables 3.1 and 3.2 show the number of cases in which the first feasible solutions obtained were at certain "distances" from the corresponding solutions found to be optimal. For the three-variable functions, the first feasible solutions were optimal in 50% of the cases and had the optimal number of gates in 80% of the cases. These percentages were 29% and 82%, respectively, for functions of four variables for which optimal networks were determined. Tt is also of interest to see how soon the first optimal and last optimal solutions were found by ILLOD-(ANDOR-B). Between the time of locating the last optimal solution for a particular synthesis problems and the end of the computation, there is a period in which the program must implicitly exhaust all remaining potential solutions (since the last optimal solution can not be known to be such until all remaining possibilities have been eliminated). Hence, it seems appropriate to compare the average times for achieving the first feasible solution, the first optimal solution, the last optimal solution, and the end of the computation for each of the two categories of problems: the sysnthesis of optimal networks for functions of three variables and the synthesis of optimal networks for functions of four variables. These statistics are shown in the form of grpahs in Fig. 3*1 and Fig. 3.6, respectively, where averages have •pti.mal.ly gal i tions of three variables; ); 1,2, ..., Y for Functions of four variables). The three functions of four variable:; re not completed (representative functions of NFN-equivaJcn.-e classes noi , an.: ') were no1 considered in Fig. 3.6. Both Fig. 3.1 and Fig. 3.6 are immediately followed by four additional graphs showing, for each group of functions optimally requiring R gates, the minimum, average, and maximum time required to achieve: the first feasible solution (Figs. 3.2 and 3. 7), the first optimal solution (Figs. 3.3 and 3.8), the last optimal solution (Figs. 3.U and 3.9) and the completion of the computation (Figs. 3-5 and 3. 10). It is interesting to view the data of these graphs (Figs. 3.1 through 3.10) at percentages of total computation times rather than as absolute computation times. This perspective reveals the relative amounts of time spent in the various aspects of the solutions of the problems and how they vary with changes in the number of gates, K, of the optimal network. Figs. 3.11 and 3.15 show the average percentages of total computation times required to find first feasible, first optimal, and last optimal solutions for the respective cases of three-variable and four- variable functions, respectively. Fig. 3.11 and Fig. 3.15 are both immediately succeeded by three additional graphs showing, for each group of functions optimally requiring F, gates, the minimum, average, and maximum percentages of total computation Percentages are first found for each individual function within a grouping; "average percentage" refers to the averaging of these percentages for functions within the respective grouping. 22 times required to achieve: the first feasible solution (Figs. 3.12 and 3.l6), the first optimal solution (Figs. 3.13 and 3.17), and the last optimal solution (Figs. 3.1U and 3.18). The exact data upon which Figs. 3.1 through 3.10 and Figs. 3 .11 through 3.18 are based is given in Table 3.3 and Table 3.k, respectively. Note that due to the computational environment (multi-programming) measured elapsed computation time usually varies from run to run for the same problem (perhaps as much as 1 or 2% for intervals on the order of 100 seconds or more and sometimes up to 50$ or more for intervals on the order of .01 seconds). Therefore, a repetition of the calculations can not be expected to precisely give the same results shown in Tables 3-3 and 3«^. To prove that at least eight AND and OR gates are required for net- works realizing functions in NPN- equivalence classes no. 183 and no. 206, two network syntheses were attempted by ILLOD-(ANDOR-B) under a cost bound of seven gates. In 1222.26 and 1281.19 seconds, respectively, ILL0D- (AND0R-B) established the non-existence of seven gate realizations for these two classes. 7 .7 .6 .5 .1+ • 3 .1 09 08 07 06 05 Oil 03 02 01 -^^~ AL AVERAGE TIME TO FIND L OPTIMAL SOLUTION AVERAGE TIME TO FIND FIRST OPTIMAL SOLUTION AVERAGE TIME TO FIND FIRST FEASIBLE SOLUTION 1 (1) 2 (1) 3 U (3) 5 (1) NUMBER OF GATES IN OPTIMAL NETWORK (parentheses give number of functions in each category) Fig. 3»1 Computation time: first feasible, first optimal, last optimal solutions, and total, for 3-variable NPN- equivalence class representative functions. 2k c o\cc f- VO ITN sffi'ioojts mi awii nouviouod a o° CD C -H O H •H o5 -P !> o3 I -p on to P £ ft ^ o o p o •H -P d m 0 O -P w a3 -P P h c efl a3 QJ •x-H a> CD -P 5n M Pi Pi g3 O ra 03 R •H R w w ct3 H o 3 CD S J> CD •H CD CJ p -h a •H .P CLJ 2 O i-l a3 a3 co 0) 0) I si s EH H EH H EH raws ;>] CO W S ^ raws k3o i — 1 K h-q O H ffi ,-q o HfQH H H ffl H FH h m h 6hHR co D , h H R CO D pq H EH CO £> cc < i-q c K . K O H O H OHO hhto < Ph P^ CO g p4 Ph CO nTK \ kl -; COXt-vc ir\ j- ■HO^X) t^\o u^ _3 co scuiooas m awix noiivimwdo R -p p o •H P P o •H P O P 3 cr3 oo 'h -p P R £ ft o > ° £ O W TO S o p 3 -H cu S P £ X H £ soft S w ^ R T3 CU P H w 03 p ra •h o3 - Co H cu cti o M 0) 03 Ch CD R O ra 03 R H •H p3 ~ e .h 3 cu p S > & •H CD 0) P vH I * H -P %> g t> K n3 3 CVJ to •H O CD P H ca ct? . I • \ ^ ' / v*** 1 — — ■-I— oa>ccr-\£> \r\ j co <\i o w . 13 S 31 1J ' 1 c r-\ *H cS O 0) CH > •s •H S w -P 3 aJ £ C -P 0) •H w 2 C 0) O Jh •H ft Lf\ ■P 0) . d h m ■P 3 w • a w hn S cd •H H P4 u o scL-iooas mi ami ndiivithwdo HCOhlO H tflhlO !! EH S H 3 ^ a B < O ft O s wehp; H O ft O S hOCO < Pl, O CQ 2 h O CO [SJ ^ v ~T ooxcor— vo i^ ^acof-vo in -* rn oj ^g'g&'S o o o sauoo3s m awix NoiiviMNDD c 3 o H ^ H 0> si CD H .£> cd •H -p a? •H 0) !> ■H -P I ft O O -P O <+H O q £ w 3 3ch £ O •H -H X -P S H -P O a3 -a io -p c d a3 H CD a3 w ♦< £ CD 0) -H *h hfl-P ft a3 ft CD Sh O ?h (D > -P W a3 ux w •xH H O DJ J> cu a . -H C •H ,C CD o H 03 03 !> O -H ■p r*; m a> CU I -P s 3 ■H J- oo bO •H 9.6 10000 1000 CO o o w CO £3 g M H E-l O O 100 AVERAGE TOTAL TIME AVE, RAGE TIME TO FIND LAST OPTIMAL SOLUTION AVERAGE TIME TO FIND FIRST OPTIMAL SOLUTION AVERAGE TIME TO FIND FIRST FEASIBLE SOLUTION NUMBER OF GATES IN OPTIMAL NETWORK (parentheses give number of functions in each category) Fig. 3.6 Computation time: first feasible, first optimal., last optimal solutions, and total, for if- variable NPN- equivalence class representative functions. h, ill! I f N T f ilium — mi . ITN *> ^$ m sciMooas mi arai wonvindwoo H EH § co w s H K 3 o W EH A R3 ^ S R K ,_q o l EH _ « 3 o H H PQ H EH M m M H h m m fe H R Ft, H EH co b _ CO !b X K < h-3 < o w o S fx< fo CO C K < ri S (X o w o H o w o < fin Cm CO jgj Pn fo CO V t ,, 1 O 3 s&uooas ;u awn, Noixvindwoo H ,Q a •H fl *H O 03 •H > -P 1 o3 -H/ • -P W 3 ^H C ft O o S Ch •H O -P o w CJ C C £ o p 3 -H 03 O •H £ w -P oi T3 0) -P C H C 03 P •H W •s W CD o3 ^ faD cu ft o3 Ch W w o3 ?h M •H 03 •N ^H H 3 cu o Fi !> a> •H CD CJ sd -h £ •h ,£ a; S o H o3 P r— O •H . +3 3 no CJ 1 w O H H O H < EH EH S EH EH V\ w R += %% O 0) H O 03 C P 0) H P 05 g-H £ a 1 •H CD x JL OJ ft C 0) 03 H • ft W •< (li U CD -H O hO ?n -H 03 03 -P ?h > a CD I C f>-=J- si 03 ft ^ o cd 1 ^ ^ £ w p •H CD o3 C £ P •H -H C S P sayooas m awn, iioixvindroo o H bfl •H ft cu w Sd 0) O fn ■H ft P CD o3 fn ^ w ft w 2 o3 O H o o 1 EH ft HCQriO | EH ft IeH ft HfflhlO H GO ft O H P ^3^g H p X a; En i-H <£ O ft O Ci> K Eh t-q > O ft O ft ft EH ft H O ft O SlhOta < ft O 00 S ft O GO P fj *> J -J I 1 \ | > i 1 J] ■ ' ■ I ILLL \II m-J £ c R-2 scLiooas in aici, Nonvindwoo 0) C O •H P !h O S3 O C o ft £ P ra o5 G 0) P o t> si •H •H ft +-* P si 03 o H P o o C w 0) CO si H CD S ctf 5h •H ft X —i CD crt P !4 ft O w T7 w S3 P 03 o3 M H at o •v rH CD CD hn CD a o3 ;> £ Jn a j CD (1) •H H > fi 05 cri O > ai •H •\ si g O a* 3 P CD Fi 1 •H T5 ft SSj CO Mh •H M ft S. H •H si CD a* H ON a.) ft • in 05 ro •H W U • CI) 03 bn B > •H •H 1 r.-j P -J" 29 AVERAGE PERCENTAGE OF TOTAL TIME TO FIND LAST OPTIMAL SOLUTION AVERAGE PERCENTAGE OF TOTAL TIME TO FIND FIRST OPTIMAL SOLUTION AVERAGE PERCENTAGE OF TOTAL TIME TO FIND FIRST FEASIBLE SOLUTION NUMBER OF GATES IN OPTIMAL NETWORK (parentheses give number of functions in each category) Fig. 3.11 Percentages of total computation time: first feasible, first optimal, and last optimal solutions for 3-variable NPN- equivalence class representative functions. 30 o pi K < Sp Eh CO K < O H f-P O Pm H EH &h <; M O g EH Q hH ft Eh CO K O H Eh P^ i-l O M . EH W P M D • EH p S S EH P) S > h H H 0< O H ft < O B h O CO S O ft ft o O CO P-4 s- 15 a CO ►J K s ° fS -s d B fe c 0) PS > H "ri 3WIi NOIIVifHWOO 1VX0J, id SDViNaoaad w CU bO as H •P 03 c s (U tH O -P w M ft w CU O en ft H -P o E W 3 M 0) E .H o •H Cm a X 0) CO 1) H 6 > g cu l> TJ .H •H C Xi 2 a5 O rr 03 cu •\ | CU O ■ - hO -P Uh 05 S m CU • a) e CI) ca > -H 1-1 C 03 -P ,Q o SJ •H - C ■H P> m ° M O 3 -H 5 c E -p 3 •H 03 i «M C -P rn •H d cu £ ft !h > 6 O •H o cp +-> o 01 en w -P rH H C C • 03 O CU oo -P •H W -P 0) • -P d M bO H ft •H ft o cu ft o W H $ tf T? ^ vo ua j ro wii noixvJiMifDo ivjoiL jd aoviMaoHad w 0) hO CI) 03 H -P rQ C -H w cj o3 w 5-i CD w CO 03 0) l> T3 «H •H C ^ 2 03 CJ O 1 05 CU *\ 1 CU o r^H hO -P E 05 k.' U O • CU E (1) W > -H H C 03 -P rQ o 03 •H •< C •H •P E O M o 3 -H 01 c E P !> r' •H 03 i cm C P> CO •H 3 iu S ft !h > E O •H O cm H^ o 01 CVI 02 +3 H H 13 C . 03 O d) on P> •H C2 O -P OJ • ■P Pi Sh ':: iH ft •H Cm O QJ ft M M I -^ *13 i s w -J C M o 8 * awn iioixvindi'OD ivxoi jo aDviaaaa&i H 1 w s > £ sd 3 CD ^ o £ -H g •H •H ^ -P X o 0) t> 03 o3 H C E ,Q pi O cri m T3 -P •H C Sh 03 CD aj !> S > •H -.-H l -P 0) -P oo 03 bO •P 05 C ^ C ?H O o 0) +> (D 03 03 m ^ -P a ft -v 3 o CD g ft • H ^H P S -P £ O Pi W •H O H w c o 03 •H <+A 03 H 2 O H o W cri 0) 0) H o J- br •H p! H crt •P a w CU trt - i •P a5 <1) o ■P U Ph co <1> 5 a) Ph H ; : w s fn <1J •H •H a; £ Tl •H •tH r. X! =1 ^ a) CU •N 1 0) O is; hfl -p i^i fi •S 0) 8 3 -p ■8 O •H p •tH -P o •H -p a U 1 a •H -p P P 1 o 0) > •H o Ch -P n CO H H w P £ d O CD PO -p •H cu o -P -p 2 ?H hD H Ph •H HH O CD Cn O w ?H £ EH g EH EH EH P K pq S < O H 1-3 O O Fl PC < K W S O H Ft O O Fl W pq S K < O H ri O Ph RBhWH Ph Eh eiPhBh Ph EH EH Ph W H O H EH S fe < ^ Pl, m m w o O • E-i > Ph IME IND EASI OLUT O M EH . eh W Q co b s s s < fi Ft pm H H W O s! O Eh Ph Cm W H t-l «) < -o °§ W CU hO CD o5 H i£ F> P -H CD W O o5 ?H CD CD HH Ph -P S w 3 ^ S -H •a hh x 05 CD e t> CD a si a3 o 05 O faO HJ a5 Jh CD CD B Z ,5 a5 -P •n a S o w w o5 H o CD O id H •H g. CD I E on bO •H Ph ■H. P a & o o H ■P o HJ <4H o •H -P 05 > I h3 CD •H HH 4^ a5 o ■P d H o w Ik o t-3 O l-H K < O fM EH EH O * E-i W £? S >hH <; O EH Eh CO EH i-^l EH HH ft O O CO O ft rn S k <; o —. fl ^ n> E o g •H s •H •H ^ P X o cu O erf erf H £ 6 rQ d o tti ft T5 -p ■H 3 *H a; erf CD erf !> £ > •H *\ •H i P 0) P~ BJ bo P erf c fn C Fh O O a; cd •H ft in !> -P CU erf erf M Fh P S3 ft •\ 2 O CD g ft •H !h p H P 1 3 W o H ra C O erf •H ft CO H s o H o w erf CD CD F O a) bn •H C H ctl P CD • ■P ftr- OO fl O erf aj > • CJ P ■H bO !h w g ■H (1) en rr 1 ft ft H CD S 1 1 i j o o :;: rH ON o r-l fi • H Q H O 8 o CM o o 1 1 o o H o 00 ON > CO vO VO v5 H Eh ' H • O H d ON CM • O t — H CM o rH d CO LTN • o LTN ITN d .CN CO H CM • CO H • H H -3- O CO ►J j rH • o CM d CM • O LTN CM vo' • co H H d o VO d O -t rH VO CM H CO CM UA CO • • o CM ON H t— r-\ PO CM CM m a EH < ^ h S CQ 0&4-J- > < iX 35 4 y . t '-, ■r 1 .Tl •v (1) rH u erf •rl •r P H Ph i-i O P H ' W ft )h n •H «H a) .v H CD CJ H 01 ,o .,-■ •H fn t/J erf ^ CD CH C p <+H w O ^i •rl ri CO +-> erf ?H 11 +J O 3 Ch c Pi t= ra • ^ U 0) o CJ p3 n fl O § -P •H •p fc c erf •rl o N x •H •H Crf -P H g crt erf •P CD T3 rt ^H i_l ft crf Fi ^ ^: ^ •\ n O ^ H p £j erf cu •rl ■p c ki o •H -p K fa T5 O *v CI n CD gfl P crf a m CJ u CD o •H !> •H a; < P> ^ d -p rH n fl C ) w •rl CO H w a) a; 0) Fi -p H •rl erf 4-' -P hn erf ft H O fi 36 H s H p O h-l CO - ON o o CO -d- UA OA O O -d" on vd H ON o vo -d- CO -d- t— ON r— o d _d- On CO H CM UA H CO on H -d- -d* _d" ON o d vo co d UA H O H O d o H d vo UA _d d UA -d- H vo ON VO -d- CT) CM -d- LTN on H d UA VO o H H O d o o d o d c— p w El •H ra CD CD •H H -C ,Q . O cc3 t- 03 -H ^H «N 3 g : T3 a aj ^ W Ch CM d O •> H to w a; a ii e o •H . H (X ■P -P O •« g C -d- O H .s •h «h on p n3 ch II P o ^ E! ft ft S eT •« o o W U !s C , bO O H -H ci x! P P O n3 O aj n P 0) >H H ^ 5h cc3 O O CD ch ?h w (D W ,kj bO C H a3 O p P -H r^ d 4J p cu 3 a> p H C ^ o CD ra K ft o H~\ 1 i § fi -H < •H 4J X ft ^ «5 o -H S CD ^ -^ ^ ^ ra-P 5 k5 cc3 H E! ■H JN r^j £ C co 2 «5 CD ^ -P •H ^ eg ch m •d «3 £ g cc •H ">-p bD 5> Pi a M O -rl a im 5h p t\ CD W ^ > !h a 1 < -H CD this information could be used as the basis for an extrapolation of the results (with respect to computation time) of the sampling. The authors are indebted to Yuko Culliney, Eisuke Muroga, and Yoko Muroga for their help in editing computational results and figures. 39 LIST OF REFERENCES I] C.R. Baugh, T. Ibaraki, T.K. Liu, and S. Muroga, "Optimum gn using NOR and NOR- AND gates by integer programming," Report No. , pt. of Comp. Sci., Univ. of 111., Urbana, 111., Jan. 1969. P] J. Culliney, "Use and description of the CALCOMP program to draw networks of logic gates," Report No. UTUCDCS-R-7 3-580, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., June 1973* 3] E.S. Davidson, "An algorithm for NAND decomposition of combinational switching functions," Report R-382, Coordinated Sci. Lab., Univ. of 111., Urbana, 111., June 1968. k] E.S. Davidson, "An algorithm for NAND decomposition under network constraints," IEEE Trans. Comput., vol. C-l8, pp. IO98-IIO9, Dec. 1969. 5] T. Ibaraki, T.K. Liu, C.R. Baugh, and S. Muroga, "Implicit enumeration program for zero-one integer programming," Report No. 305, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Jan. 1969. 6] T. Nakagawa, "A branch-and-bound algorithm for optimal AND-OR networks (The algorithm description)," Report No. h62, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., June 1971. 7] T. Nakagawa, "Reference manual of FORTRAN program ILLOD-(AND-OR-B) for optimal° AND- OR networks," to be published as a report, Dept. of Comp. Sci., Univ. of 111., Urbana, 111. '8] T. Nakagawa and H.C. Lai, "A branch-and-bound algorithm for optimal NOR networks (The algorithm description)," Report No. i+38, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Apr. 1971. [9] T. Nakagawa and H.C. Lai, "Reference manual of FORTRAN program ILLOD-(NOR-B) for optimal NOR networks," Report No. 488, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Dec. 1971. 10] T. Nakagawa and S. Muroga, "Exposition of Davidson's Thesis^' An algorithm for NAND decomposition of combinational switching systems'," File UIUCDCS-F-71- 869, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Aug. 1969. II] T. Nakagawa, H.C. Lai, and S. Muroga, "Pruning and branching methods for designing optimal networks by the branch-and-bound method," Report No. 471, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Aug. 1971- ko APPENDIX A: LIST OF NPN-EQJJIVALENCE CLASSES AND PELATED DATA For each NPN- equivalence class of four or fewer variables, the following information is given: Column 1 Column 2 The number of the equivalence class, through 222. Classes are numbered 1 Column 3 The hexadecimal representation of the representative function for each equivalence class. Classes are ordered according to increasing value of hexadecimal representations of representative functions. The number of variables upon which every function of the equivalence class is dependent. Column k The cost of the first feasible solution found by the branch-and- bound synthesis algorithm for each representative function. Cost is 100 times number of gates plus number of connections (e.g., cost = 832 means 8 gates and 32 connections). Column 5 The optimal cost of solutions (networks) found for each representative function. Column 6 The number of optimal solutions actually found by the branch-and- bound algorithm for each representative function. Many of these are considered to be equivalent. Column 7 The number of "distinct" optimal solutions (networks) among those optimal solutions found by the branch-and-bound algorithm. The text explains which networks are not considered distinct. Column 8 The time (in seconds) required for the computer program implementation of the branch-and-bound algorithm to find the first feasible solution for each representative function. Column 9 The time (in seconds) required for the computer program implementation to find the first optimal solution for each representative function. Column 10 The time (in seconds) required for the computer program implementation to find the last optimal solution for each representative function. Column 11 The total time (in seconds) required for the computer program implementation to implicitly exhaust all potential networks for the realization of each representative function. Ul Optimal netwox'ks for class nos. 1 and ?2 were obvious and i-termined without a computer. For class nos. 183, 206, and 222, information given pertains to the networks of least cost found as far as the computer program implementation of the branch-and-bound algorithm was permitted to run. These networks may or may not be optimal and many or may not constitute an exhaustive list even if optimal. 42 DIST. EQUIV. NO. OPT. OPT. TIME TIME TIME CLASS HEX. OF F.F. OPT. SOLN. SOLN. FOR FOR FOR TOTAL NUMBER REP. VAR. COST COST FOUND FOUND F.F. F.O. L.O. TIME 1 0000 _ — 1 (found without computer) 2 0001 4 205 104 1 1 0.03 0.11 0.11 0.16 3 0003 3 201+ 103 1 1 0.04 0.12 0.12 0.17 It 0006 1+ 310 308 1 1 0.05 0.27 0.27 0.42 5 0007 it 308 205 1 1 0.04 0.32 0.32 o.4o 6 000F 2 203 102 1 1 0.02 0.08 0.08 0.13 7 0016 1+ ltl5 415 1 1 0.07 0.07 0.07 1.55 8 0017 1+ 1+12 409 3 1 0.06 2.91 3.33 3.78 9 0018 4 310 310 1 1 0.05 0.05 0.05 0.26 „ ^ y 10 0019 1+ 309 309 1 1 0.05 0.05 0.05 0.26 11 001B 1+ 308 307 1 1 0.05 0.25 0.25 0.35 12 001E 1+ 413 4lO 1 1 0.05 1.40 1.40 1.86 13 0011' 1+ 307 306 1 1 0.05 0.42 0.42 0.54 14 003C 308 307 1 1 0.05 0.24 0.24 0.37 - 1 #— 15 003D 4 1+12 308 1 1 0.06 1.33 1.33 1.45 16 003F 3 306 204 1 1 0.05 0.23 0.23 0.31 _ -. - y IT OO69 it 520 517 1 1 0.08 9.72 9.72 13.16 18 006B It 517 413 1 1 0.05 12.63 12.63 13.09 19 oo6f 1+ 1+11 309 1 1 0.05 1.40 1.40 1.52 20 007E 4 1+12 309 1 1 0.06 1.35 1.35 1.46 ^ y , . 21 007F 4 1+09 205 1 1 0.05 0.60 0.60 0.67 22 OOFF 1 _ 1 _ 1 (found without comput- ar) 23 0116 1+ 520 520 1 1 0.08 0.08 0.08 11.15 21+ 0117 4 516 512 6 1 0.08 1.00 7.39 20.17 s~* y 25 0118 4 1+15 415 1 1 0.08 0.08 0.08 1.06 -1 \ ,-\ 26 0119 1+ - 413 411 1 1 0.07 0.17 0.17 i.4o 27 011A 4 klk 4l4 1 1 0.06 0.06 0.06 1.01 1 — 1 28 011B 4 412 410 1 1 0.06 0.18 0.18 1.38 29 011E 4 518 515 1 1 0.07 1.70 1.70 10.55 30 011F 4 411 409 2 1 0.05 0.33 0.73 1.78 31 012C 4 4l4 4l4 1 1 0.06 0.06 0.06 1.03 32 012D 4 413 413 1 1 0.05 0.05 0.05 1.07 33 012F . 4 411 411 2 1 0.05 0.05 0.19 1.37 34 013C 4 413 413 1 1 0.06 0.06 0.06 1.01 35 013D 4 412 412 1 1 0.06 0.06 0.06 1.05 _ ^ ^ y 36 013E 4 517 514 2 2 0.08 O.56 7.09 10.36 37 013F 4 4io 409 3 2 0.06 0.18 I.56 2.03 38 0168 4 520 520 1 1 0.10 0.10 0.10 10.46 r\ y ~~ 39 OI69 4 519 519 1 1 0.08 0.08 0.08 8.65 >+0 016A 4 518 516 1 1 0.07 0.17 0.17 11.52 4l 016B 4 517 515 1 1 0.08 0.53 0.53 8.40 42 oi6e 1+ 517 514 2 2 0.07 0.94 7.66 11.10 ^3 oi6f 1+ 515 513 2 2 0.09 0.95 8.44 12.05 44 017E It 517 515 2 2 0.08 0.50 6.82 9.97 ^v 1 T ^5 017F it 513 410 3 1 0.08 0.37 2.00 2.41 46 0180 It 310 310 1 1 0.03 0.03 0.03 0.21 47 0181 4 309 309 1 1 0.05 0.05 0.05 0.23 -1 r\ \ 1+8 0182 4 415 415 1 1 0.07 0.07 0.07 1.04 -. y s**. 1+9 0183 4 413 411 2 2 0.05 0.17 0.45 1.60 50 0186 4 520 520 1 1 0.07 0.07 0.07 9-39 DIST. EQUIV. NO. OPT. OPT. TIME [ME TIME CLASS HEX. OF F.F. OFT. SOLN. SOLN. FOR FOR FOR 1 'AL NUMBER REP. VAR. COST COST FOUND FOUND F.F. P.O. L.O. 51 0187 k 517 515 10 3 0.09 0. • 18. 52 OI89 k 308 308 1 1 O.Oh O.OU .0'+ 0.22 5? 018 B k 1+12 1+09 1 1 0.05 1.28 1.28 1.75 5U 018F 1+ 1+11 llll 2 1 0.06 0.06 . 1.51 55 0196 k 625 625 1 1 0.11 0.11 0.11 155. 56 0197 k 621 617 15 3 0.08 k.k3 198.8P 255. 57 0198 k kak 1+11+ 1 1 0.03 0.03 0.03 1.12 58 0199 k kl2 1+10 1 1 0.07 0.15 0.15 1.1+2 59 019A k 518 516 2 2 0.08 0.1+1 1.1+5 9.98 60 019B h 516 512 1+ 1+ 0.09 1.07 11.50 16.63 61 019E k 622 619 3 3 0.12 2.85 107.1+3 172.08 62 019F k 515 513 2 1 0.07 2.68 6.26 20.95 63 01A8 1+ kl3 1+11 1 1 0.06 0.18 0.18 1.31 61+ 01A9 k Ul2 1+10 1 1 0.05 0.16 0.16 1.16 65 01AA 1+ 308 308 1 1 0.05 0.05 0.05 0.22 66 01AB k 307 307 1 1 0.05 0.05 0.05 0.22 67 01AC 1+ M3 U13 1 1 0.05 0.05 0.05 1.00 68 01AD k i+12 1+12 1 1 0.06 0.06 0.06 1.10 69 01AE 1+ 1+12 1+12 1 1 0.05 0.05 0.05 1.15 70 01AF k 1+10 1+08 1 1 0.06 1.56 1.56 2.1U 71 01BC 1+ 517 511+ 2 2 0.10 0.95 7.12 11.08 72 01BD k 516 513 2 2 0.09 1.67 8. 71+ 13.^3 73 01BE 1+ 516 515 2 2 0.08 0.35 7.89 12.07 7^ 01BF k 513 1+10 3 1 0.05 0.37 1.97 2.58 75 01E8 k 517 515 3 1 0.07 0.15 O.85 12.08 76 01E9 k 516 5ll+ 3 1 0.08 0.18 O.78 9. 21+ 77 01EA k 1+12 1+12 1 1 0.07 0.07 O.07 1.21+ 78 01EB k 1+11 1+11 1 1 0.06 0.06 0.06 O.98 79 01EE k 1+11 1+10 2 2 0.05 0.15 0.79 1.32 80 01EF k 1+10 1+09 2 1 0.07 0.20 O.89 1.1+5 81 01FE k 51^ 1+11 2 1 0.08 0.1+3 1.10 I.58 82 033C 3 1+12 1+12 1 1 0.07 0.07 0.07 1.02 83 033D k 516 513 6 2 0.09 1.25 6.81 10.50 81+ 033F 3 1+09 1+08 9 1 0.05 0.17 2.1+5 2.88 85 0356 1+ 516 1+12 1 1 0.07 0.1+2 0.1+2 l.!+3 86 0357 k 306 306 2 1 0.05 0.05 0.18 0.37 87 0358 k 1+13 hl3 1 1 0.06 0.06 0.06 1.08 88 0359 h 517 515 5 3 0.09 0.29 5.36 9.3!+ 89 03 5A k 1+12 1+12 1 1 0.05 0.05 0.05 1.00 90 035B k 1+11 kn 1 1 0.05 0.05 0.05 1.08 91 035E k 516 513 1+ 2 0.08 0.86 7.9^ 11.55 92 035F h 1+09 1+08 6 1 0.06 0.18 1.85 2.21 93 0368 k 519 519 1 1 0.08 0.08 0.08 11.1+0 9^ O369 k 623 620 1 1 0.10 5.81 5.81 15^.32 95 O36A k 517 515 1 1 0.06 0.20 0.20 IO.96 96 O36B k 516 5ll+ 1 1 0.08 0.53 0.53 9.69 97 O36C k 517 515 1 1 0.09 0.17 0.17 11.55 98 O36D k 621 617 3 3 0.11 2.1+9 70.80 155.02 99 O36E k 516 513 2 2 0.08 2.18 6.19 9.87 100 O36F k 511+ 512 2 1 0.08 1.03 10.25 13.16 44 DIST. EQUIV. no. OPT. OPT. TIME TIME TIME CLASS HEX. OF F.F. OPT. SOLN. SOLN. FOR FOR FOR TOTAL NUMBER REP. VAR. COST COST FOUND FOUND F.F. F.O. L.O. TIME 101 037C 4 516 513 2 2 0.08 O.83 7.94 11.35 102 037D 4 515 514 2 2 0.09 0.82 7.43 11.05 103 037E 4 516 514 2 2 0.10 1.18 5.94 9.62 104 03C0 3 308 308 1 1 0.04 0.04 0.o4 0.20 105 03C1 4 412 4io 1 1 0.05 0.16 0.16 1.18 106 03C3 3 307 307 1 1 0.05 0.05 0.05 0.23 107 03C5 4 412 4io 1 1 0.07 0.84 0.84 1.25 108 03C6 4 516 512 1 1 0.09 O.65 0.65 11.17 109 03C7 4 411 409 1 1 0.05 0.24 0.24 1.60 110 03CF 3 306 306 2 1 0.06 0.06 0.21 0.35 ill 03D4 4 516 514 3 2 0.09 0.24 0.80 11.05 112 033)5 4 4ll 411 1 1 0.06 0.06 0.06 1.21 113 03 D6 4 620 516 1 1 0.10 0.80 0.80 8.93 114 03D7 4 4io 410 2 1 0.06 0.06 0.60 I.65 115 03D8 4 412 412 1 1 0.08 0.08 0.08 1.06 116 03D9 4 516 513 7 5 0.08 0.98 6.57 10.13 117 03DB 4 411 4ll 1 1 0.07 0.07 0.07 1.07 118 03DC 4 4ll 4ll 1 1 0.05 0.05 0.05 1.02 119 03DD 4 4io 409 2 1 0.07 0.25 0.82 1.34 120 03DE 4 515 513 1 1 0.10 0.33 0.33 10.22 121 03FC 3 410 409 2 1 0.07 0.22 0.84 1.29 122 0660 4 520 512 5 1 0.10 6.56 8.22 17.08 123 0661 4 625 618 1 1 0.10 50.49 50.49 85.80 124 0662 4 518 513 5 2 0.08 1.28 5.34 IO.96 125 0663 4 622 616 1 1 0.11 50.12 50.12 90.75 126 0666 4 516 409 1 1 0.07 1.18 1.18 1.63 127 0667 4 620 512 1 1 0.09 10.67 10.67 15.31 128 0669 4 730 723 1 1 0.14 974.30 974.30 1796.71 129 o66b 4 726 618 1 1 o.i4 135.12 135.12 168.77 130 o66f 4 619 513 2 1 0.10 6.93 10.62 14.56 131 0672 4 517 512 1 1 0.07 5.55 5.55 9.86 132 0673 4 516 514 1 1 0.08 4.84 4.84 9.02 133 0676 4 516 410 1 1 0.08 6.01 6.01 6.44 134 0678 4 623 618 1 1 0.13 4.29 4.29 163.56 135 0679 4 727 722 2 2 0.11 86.38 1210.90 2135.63 136 067A 4 621 615 1 1 0.12 93.52 93.52 178.14 137 067B 4 620 618 2 1 0.09 4.33 73.24 117.55 138 067E 4 620 513 1 1 0.08 85.28 85.28 89.32 139 0690 4 520 520 1 1 0.10 0.10 0.10 8.09 140 0691 4 519 519 1 1 0.08 0.08 0.08 7.24 l4l 0693 4 518 518 1 1 0.08 0.08 0.08 7.35 142 0696 4 518 518 1 1 0.10 0.10 0.10 6.97 143 0697 4 722 517 1 1 0.12 2.48 2.48 io.4o 144 069F 4 618 516 2 1 0.10 0.88 5.98 9.49 145 o6bo 4 518 516 1 1 0.08 0.36 O.36 10.83 146 o6bi 4 518 518 1 1 0.08 0.08 O.08 7.04 147 06B2 4 517 515 2 2 0.09 0.34 3.82 7.18 148 06B3 4 516 515 1 1 0.08 4.87 4.87 9.57 149 06 b4 4 517 515 1 1 0.09 o.4o o.4o 7.69 150 06B5 4 517 517 1 1 0.08 0.08 0.08 7.17 D3BT. 5QUIV. NO. OPT. T. TIME TIME TIME JLASS HEX. OF F.F. OPT. SOLN. SOLN. FOR GAL DUMBER REP. VAR. COST COST FOUND FOUND V.F. P.O. l,.0. T i ME 151 00B6 4 516 514 1 1 0.08 0.40 O.V) 7.29 B7 4 618 515 1 0.10 1.08 • } >9 10.00 153 06B9 4 622 619 p 2 0.10 O.85 57.57 10a. 154 06BD k 621 618 2 2 0.12 1.19 60. 100.23 155 06F0 4 kl3 413 1 1 0.08 0.08 0.08 1.67 156 06F1 4 517 517 1 1 0.08 0.08 0.08 Y. 157 06F2 4 .'*!." 412 1 1 0.08 0.08 0.08 1.05 158 06f6 4 If 11 411 2 1 0.05 0.05 0.55 1.15 159 06F9 h 621 620 2 1 0.10 0.45 59.39 109.77 160 0776 4 516 411 1 1 0.10 5.42 5.42 5.86 161 0778 k 621 515 2 2 0.08 0.62 5.33 9.67 162 0779 4 725 618 1 1 0.14 54.73 54.73 101.29 163 077A 4 620 513 1 1 0.10 6.51 6.51 10.10 164 077E 4 620 514 1 1 0.12 78.16 78.16 81.92 165 07BO 4 516 512 1 1 0.07 O.69 O.69 9.69 166 07B1 4 516 513 1 1 0.08 4.61 4.61 7.15 167 07B4 4 516 514 1 1 0.08 0.43 0.43 7.81 168 07B5 k 515 513 2 1 0.07 0.27 7.81 10.80 169 07B6 4 620 516 1 1 0.10 57.51 57.51 61.32 170 07BC 4 516 515 1 1 0.08 4.56 4.56 7.97 171 07E0 k 516 512 1 1 0.08 0.80 0.80 12.23 172 07E1 4 620 616 3 2 0.10 3.01 3.63 117.94 173 07E2 4 516 513 4 2 0.09 5.23 6.88 10.50 Yjk 07E3 4 515 513 3 1 0.10 O.50 6.37 9.07 175 07E6 k 516 411 1 1 0.08 4.66 4.66 5.07 176 07E9 4 724 620 2 1 0.12 2.67 3.05 118.17 177 07F0 k 411 409 1 1 0.07 0.15 0.15 1.34 178 07F1 4 515 513 8 3 0.09 0.30 5.40 8.39 179 07F2 4 411 411 2 1 0.07 0.07 0.55 0.99 180 07F8 4 515 513 2 1 0.08 0.20 5.11 10.07 181 OFFO 2 306 306 2 1 0.05 0.05 0.21 0.33 182 1668 4 730 724. l8 + 2. 0.13 5.92 2231.72 4148.03 183 I669 4 835 829 T 12 + 2 + 0.13 (computat: Lon not completed) 181+ 166A k 727 722 12 2 0.13 27.60 1481.30 3668.40 185 166B k 831 724 7 1 0.15 278.97 1011.23 1656.23 186 i66e k 725 618 1 1 0.12 86.26 86.26 140.16 I87 167E 4 72U 616 3 1 0.14 98.95 103.56 155.31 188 1681 4 625 625 1 1 0.12 0.12 0.12 75.38 189 1683 4 623 620 1 1 0.11 6.70 6.70 84.91 190 1686 4 518 518 1 1 0.08 0.08 0.08 6.29 191 1687 4 622 619 2 2 0.10 6.77 45.31 85.61 192 1689 4 624 624 1 1 0.12 0.12 0.12 68.74 193 168b 4 622 619 1 1 0.11 6.49 6.49 83.68 194 168E 4 517 517 1 1 0.08 0.08 0.08 6.60 195 1696 4 517 517 1 1 0.08 0.08 0.08 6.34 196 1697 4 826 618 6 1 0.15 11.01 63.88 96.56 197 1698 4 518 518 1 1 0.10 0.10 0.10 6.59 198 1699 h 622 619 2 2 0.13 6.39 42.21 75.46 199 169A k 517 517 1 1 0.06 0.06 0.06 6.62 k6 EQUIV. CLASS NUMBER 200 201 202 203 20*+ 205 206 207 208 209 210 211 212 213 2lU 215 216 217 218 219 220 221 222 NO. HEX. OF REP. VAR. 169B l69E 16A9 16AC 16AD i6bc 16E9 177E 178E 1796 1798 179A 17AC 17E8 18E7 19E1 19E3 19E6 1BD8 IBEk 1EE1 3CC3 6996 h k 1+ k k 1+ k k h h 1+ k k k k 1+ k k k k k 3 k OPT. F.F. OPT. SOLN. COST COST FOUND DIST. OPT. SOLN. FOUND 621 516 728 622 726 621 832 72U 516 621 516 516 620 72k 622 621 621 621 516 516 726 516 91+0 618 516 723 617 720 516 827 617 515 618 51^ 516 616 720 620 517 618 618 515 516 620 516 928 t 2 2 1 1 2 $ 3 k 6 1 2 Ik 36 2 1 k 2 16 2 2 2 t 1 1 1 1 1 b 1 1 1 1 1 7 2 1 1 1 1 1 1 1 1, TIME FOR F.F. 0.12 0.10 0.13 0.10 0.15 0.10 0.18 0.11+ 0.09 0.10 0.08 0.09 0.10 0.13 0.10 0.11 0.12 0.10 0.08 0.10 0.13 0.08 0.20 TIME FOR F.O. TIME FOR L.O. TOTAL TIME 6.6U 0.10 IB. Ik 68.35 111.86 70.21 (computat 191U.8U 0.^0 1.01 0.20 0.09 2.65 1+.8.1 0.53 8.15 8.01+ 0.86 0.20 0.10 6.21* 0.08 (computat 1+8.59 3.6U IB. Ik 68.35 1037.56 70.21 ion not c 1920.76 1+.26 58.5^ 0.20 3.62 96.01 1380.10 52. k6 8.15 57.^3 51.^5 7.52 3.^6 1+2.78 3.63 ion not c 80.7^ 6.62 1251.66 153.09 11+72.78 73.89 orapleted) 1961+.26 7-5 1 * 103.90 7.72 7.01 122.01 3665.52 91.09 13.36 100. 7^ 92.70 10.08 7.20 79.81+ 7.02 ompleted ) + Due to excessive time, the computation was terminated short of completion for this problem. Hence the results of least cost obtained prior to termination are not known to be optimal. Least known cost, number of solutions of least known cost are substituted for "OPT. COST," etc. 1*7 AITENDDC B: OPTIMAL NETWORK LISTING For each NPN-equivalence class of four or fewer variables, except class no. l83, 206, and 222, all distinct optimal networks of AND and OF gates are given which realize the corresponding representative function. In the majority of cases, just one such optimal network exists, although others have up to seven. For class nos. 183, 206, and 222 those networks having fewest connections, among those known with the least number of gates, are given. They may or may not be optimal (in either case, networks for class nos. 183 and 206 are known to have the optimal number of gates), and, even if optimal, those networks listed may not constitute complete sets of optimal networks for the corresponding representative functions. See the text for directions in determining optimal networks for functions which are not chosen NPN-equivalence class representative functions. Also, for many equivalence classes, certain simple combinations of variable negations and permutations and interchange of AND and OR gate types may produce additional optimal networks (again, see text for more details). [2] These networks, drawn by computer-controlled plotter , use the symbols A, B, C, and D in place of x^ x g , x , and x^, respectively. Each network is labelled with the corresponding NPN-equivalence class number of which the realized function is representative ("REP. CLASS"), the hexadecimal representation of the representative function realized ("REP. FN.") and the cost of the network ("COST") - defined as the number of connections plus 100 times the number of gates. REP. CLRSS REP. FN. 0000 COST 11 REP. CLASS REP. FN, 0001 COST 10W 0003 o — > n — r o — R R — I A ^ 5= OR | 2i c — o — OR 3 REP. REP. CLASS FN. 4 0006 COST 308 s — e — R REP. REP. CLASS FN. COST 0007 205 REP. REP. CLASS FN. COST 6 OOOF 102 n -> o — B — 5= R 2 REP. REP. CLASS FN. 7 0016 COST 415 OR U tl fi- fl 3 D — B — B — 4 o — !=f n OR OR REP. REP. CLASS FN. COST 8 0017 409 Ef fi — 5- 2 B — C — — R 3 REP. REP. CLASS FN. 9 0018 OR COST 310 a — c — o — fl B — c D — fl REP. REP. CLASS FN. COST 10 0019 309 OR B — D REP. REP. CLASS FN. OR 2 11 "~ 1 001 a — 1 H i OR 3 COST 307 REP. REP. CLASS FN. COST c — n B — !! — D — 0R 2 1 12 A — OOIE R -> 410 u — 4 i L B d OR 3 c — o — fl REP. REP- r . QT CLASS FN. COST 13 OOtF 306 OR 2 R OR REP. REP. CLASS FN. COST 14 003C 307 R B — c — o — OR lb UU 2 a — ■ H i B — c — OR 3 REP. REP. CLASS FN. COST -> REP. REP. CLASS FN. COST 16 003F 204 OR 4 R H> jj OR OR e c — o OR ^\ REP. REP. CLASS FN. COST 17 0069 517 R n OR OR REP. CLASS REP. FN. COST 006B 413 B — c — — OR R B — c — B — OR REP. REP. CLASS FN. 19 006F 1 cos: 30' B — c — o — OR 3 R OR REP. REP. CLASS FN. COST 20 007E 309 R B — C — o — OR REP. REP. CLASS FN. COST 21 007F 205 B C — OR _2j R REP. REP. CLASS FN. CO' 22 OOFF A— -> JEfl IE R REP. REP. CLASS FN. COST 23 0116 520 o — fl B — fl OR h-> o — OR a c — OR fl REP. COST 24 0117 512 s — o — 1 fl h 31 OR h> fl E fl REP. REP. CLASS FN. 25 OIK COST 415 4 p OR fl — B — OR fl H 2 fl — B — 8- REP. REP. CLRSS FN. COST 26 0119 411 OR R> i fl — 8 = fl 2 c p — B — ' c — o — fl ,~^ 3 1 1= c — n — fl 4 REP. REP. CLASS FN. COST 27 OUR 414 OR M OR c — o — fl fl r 3j REP. REP. CLRSS FN. COST 28 011B 410 OR R> Lj REP. REP. CLASS FN. COST s= OR 4 f R 2 29 01 OR l B — OR 5 c— J D — fl 3 c D — fl REP. REP. CLASS FN. COST 30 01 IF 409 o — B OR c o — fl OR a — fl REP. CLASS REP. FN. COST fl 31 012C 414 8 — c — fl 6 — C — B fl - fl - OR fl — 6^ fl L .3J = fl REP. REP. CLASS FN. COST 32 012D 413 fl — B — 1 A 2 OR fl fl REP. REP. CLASS FN. COST 33 012F 411 OR ? 1a fl B c o — REP. REP. CLASS FN. COST 34 013C 413 fl - L fl OR B c o — fl fl- B c fl REP. REP. CLASS FN. COST 35 013D 412 fl - OR REP. REP. CLASS FN. COST B — c — OR 4 __J n — fl 2 36 OH UH,| B — c — OR 5 B — c — o — fl 3 - — s=or fl OR OR REP. REP. CLASS FN. COST 36 013E 514 LLx REP. REP. class FN. COST IE », 37 013F 409 DR 4 1 1 OR l -> . *— R 3 J |E fl 8= 2 37 01 t n — OR 3 — REP. REP. CLASS COST -» w — 5E R s3 R - REP. REP. CLASS FN. COST 38 0168 520 fl 4=7 6 s= A 5 = c — o — R OR H> i R fl E R R s h REP. REP. CLASS FN. COST 39 0169 519 OR -> 8^ OR TJ R R — REP. REP. CLASS FN. COST 40 016A 516 E R E R OR = R 8 — c — OR - R REP. REP. CLASS FN. COST 41 016B 515 _ r e a R - : 0R c — n — OR OR fl REP. REP. CLASS FN. COST 42 01SE 514 fl 3 OR B — C fl = 0R OR REP. REP. CLASS FN. COST 42 016E 514 8 c D — OR - fl B — c — o — OR 4_ § = OR 5 — fl REP. REP. CLASS FN. COST 43 016F 513 fl 3 OR -» c — o — fl B 5^ OR B C — OR OR REP. REP- CLASS FN. COST 43 016F 513 fl REP. REP. CLASS FN. COST B — OR 4 n — fl 2 44 017E 515 UH 1 ~> B — c — o — OR 5 ?! — B — c — o — fl 3 B — C — — fl s= OR OR REP. REP. CLASS FN. COST 44 017E 515 B — C D OR fl fl REP. REP. CLASS FN. COST 45 017F 410 B c — OR fl 3 OR REP. REP. CLASS FN. COST fl — 4fi 01? e — 1 = fl 2 n L OR i B — B — c — o — fl - — ' 3 IE REP. REP. CLASS FN. COST fl 2 47 0181 309 OR -> fl E fl ■— E fl fl REP. REP. CLASS FN. COST 48 0182 41S OR -> REP. REP. CLASS FN. COST B — c — fl 2 49 0183 411 DR 14 OR l L> \= fl 3 B — c — fl — o — OR fl fl REP. REP. CLASS FN. COST 49 0183 411 OR a — B — s= fl B fl B — ! = o — fl fl REP. REP. CLASS FN. COST 50 0186 520 OR h> l c o — OR 1= fl s — a — fl fl REP. REP. CLASS FN. COST 51 0187 515 OR H> 1 B — C — fl fl B — OR - 1 ?E A REP. REP. CLASS FN. COST 51 0187 515 r R — a — 1 d — n 4 OR — o — OR fl E fl 8 — fl REP. PEP- CLASS FN. COST 51 0187 515 OR REP. REP. CLASS FN. COST n 2 52 01! Oh 1 ». OR B r — OR D — OR REP. REP. CLASS FN. 53 018B COST 409 fl fl fl B — c — D — fl 4 REP. REP. CLASS FN. COST 54 018F 411 OR B — s= n E fl E fl fl - fl REP. REP. CLASS FN. 55 COST 625 OR «= R 2 REP. REP. CLASS FN. LUbi OR 56 0197 617 R n OR I i- _r L> OR 6 » — • — R 5 &= ;= OR 8= R 5 R OR 6 « — 9 — R 5 REP. REP. CLASS FN. COST 56 0197 617 OR -» §=0R t — o — OR « — R - S= OR « — 8 — OR REP. REP- ,___ CLASS FN. COST 56 0197 617 R -> R B — B — c — o — R c — R REP. REP. CLASS FN. COST 57 0198 414 OR REP. REP. CLASS FN. COST 410 c — o—i R 2 58 0199 OR 4 1 L i= R 3 ?= 6= B — R 2 REP. REP. CLASS FN. 59 019A COST 516 OR 4 R 3 uh ,h 1 c — o — 1 = R 5 c o — 6 = OR R R E fl REP. REP. CLBSS FN. COST 59 019A 516 OR OR B — Q — R HOR REP. REP. CLASS FN. COST 60 019B 512 OR 4 R REP. REP. CLASS FN. COST fl — B — OR 4 c — o — ' R 2 60 01 fl — D — OR i B — c — OR 5 R 3 B — c OR c — o — OR R REP. REP. CLASS FN. COST 60 019B 512 R - 3 OR s= OR R B — c OR REP. REP. CLASS FN. COST 60 019B 512 Ft — B OR R B c — D — R OR OR REP. REP. CLASS FN. COST 61 019E 519 OR \ HOR.h R -> H B — OR FT B — OR R c D — R REP. REP. CLASS FN. COST 61 019E 619 R OR OR B — 5= OR B 5^ OR 6 R REP. REP. CLASS FN. COST 61 019E 619 B B — c — R 3 OR 5= R 2 REP. REP. CLRSS FN. COST 62 019F 513 OR V 8= R 3 j UR i -» 8= R ! = OR 8 = R REP. REP- CLASS COST 63 01R8 411 I R OR -» S= R REP. REP. nncr CLRSS FN. COST 64 01R9 410 OR u 6= R 3 OR H> i R REP. REP. CLRSS FN. COST 65 01RR 308 H — B — c — n — R OR -» 8 R REP. REP. CLASS FN. COST 66 01RB 307 s — ?= R 8= R OR i B — 1= R REP. REP. CLRSS FN. COST R 67 01AC 413 R 4 OR R REP. REP- CLASS FN. COST 68 01AD 412 R 4 OR i R B — a — c — n — R 3 REP. REP. CLASS FN. COST 69 01AE 412 R OR i REP. REP. CLASS FN. COST 8= OR 2 70 01AF 408 R 4 fl l c - ■ o — -» L^= OR 3 REP. REP. CLRSS FN. COST B — OR 4 o — 71 OIBC 514 b- _r H 2 C — Oh 1 L> °\ B — o — A 3 OR B — c — R OR REP. REP. CLRSS FN. COST 71 OIBC 514 c — 8 OR - R R ?= D — OR OR OR REP. REP. CLRSS FN. COST 72 OIBD 513 R -> REP. REP. CLRSS FN. COST B — c — OR 4 B — c — o — R 2 72 OIBD 513 uH ,h B — 8= OR 5 fl-J R 3 B — OR OR R REP. REP. CLASS FN. COST 73 01BE 515 ft — B C D R OR B c — o — R EOR OR B — OR h 5 REP. REP. CLASS FN. COST 73 01BE 515 R -> 1 REP. REP. XASS FN. COST - fl — R 2 1 74 01BF 410 OR 4 OR 1 -> B — B — c — o — R 3 ft = R RFP REP. CLASS FN. COST B — 2 75 01E8 515 B — OR R Uh v. — ' c — -> 5 3 1 R — B — R ' 4 1= fl OR 8 : fl REP. REP. CLASS FN. COST 76 01E9 514 fl OR -> fl p — 1 = fl REP. REP. CLASS FN. COST 77 OlEA != fl OR I 8 — c — o — fl 2 REP. REP. CLASS FN. COST 78 01EB 411 fl 3 OR I -> fi- J fl — fl 4 REP. REP. CLASS FN. COST a — H 2 79 01EE 410 OR 4 UH l -} fl — a — c — o — fl 3 = fl REP. REP- CLASS FN. COST 1= OR 2 79 01E - fl l UH 3 — ' REP. REP. CLASS FN. COST S3 OR 2 80 OlEF 409 c — o — fl 4 H 1 -» R — OR 3 REP. REP. CLASS FN. COST fl — H 2 81 OlFE 411 OR 4 1 -> OR fl — 8 — c — — fl 3 H fl h— B — C fl REP. REP. CLASS FN. COST 82 033C 412 r e c — fl OR -> REP. REP. CLASS FN. COST B — B — D — OR 3 c — n 2 83 0330 513 UR l -> fl — a — OR 5 Ft — B — c — n 4 - — B — c — R « iaoR OR REP. REP. CLASS FN. COST 83 033D 513 a c — OR R REP. REP. CLASS FN. COST c — R 2 84 033F 408 fl — B — OR 3 OR l -» R — B — R 4 - — REP. REP. CLASS FN. COST B — c — R 2 85 03< OR 4 ■ l UR 1 R — D — R 3 REP. REP- CLASS FN. COST R — o — R 2 86 0357 306 OR l -» B — c — R 3 R B — 5 R B— I B c — R R - REP. REP. CLASS FN. COST 87 0358 413 m OR R — o — R 2 REP. REP. CLASS FN. COST 88 0359 515 fl — R 4 OR 1 B J 5= _r ^> B — B — c — K H — c- fl — o — R 2 REP. REP. CLASS FN. COST a — B — 'I- B — B — 88 03^ >9 51b OR 3 1 R 4 UR i _r -> R 5 I fl OR ?= OR REP. REP. CLASS FN. COST 88 0359 515 S= f0rT fl -> I fl Iffl REP. REP. CLRSS COST 89 035R 412 i — c — fl OR -> ! = fl fl REP. REP. CLASS FN. COST 90 035B 411 D — fl OR ■ c — fl OR OR REP. REP. CLASS FN. COST 91 035E 513 B — Q OR - fl -» \= OR 4 1 8 — H 2 B — c — OR 5 B — — fl 3 REP. REP. CLASS FN. COST 91 035E 513 OR l REP. REP. CLASS FN. COST 8 — c — 2 92 035F 408 OR 4 OR i -» H — fl 3 w — 1= R H — ? = fl REP. REP. CLASS FN. COST 93 0368 519 |- s= fl D — fl OR -> B c — OR EOR fl fl REP. REP. CLASS FN. COST 94 0369 620 fl OR 1 I — HOR — ' fl R B c — fl REP. REP. CLRSS FN. COST 95 036R 515 fl — a c fl OR fl OR fl REP. REP. CLASS FN. COST 96 036B 514 H — B — c — D — fl - OR HOR fl fl REP. REP. CLRSS FN. COST 97 036C 515 B H n L_ OR B — D — OR OR fl H B c — n — fl REP. CLRSS 98 REP. FN. COST 036D 617 a — c — fl OR -> OR B — OR fl fl REP. REP- CLASS FN. COST 98 036D 617 fl OR fl fl OR OR OR REP. REP. CLASS FN. COST 98 036D 617 fl OR 3 1 fl — H 2 OR 5 B — B — c — fl 4 REP. REP. CLASS FN. COST 99 036E 513 OR fl OR OR 8 — C — D — OR REP. REP. CLASS FN. COST 99 036E 513 fl REP. REP. CLASS FN. COST < ; 0R , ? = fl 2 100 03E UH i 5= OR 5 ft — ' H 3 OR ?= fl OR REP. REP. CLASS COST 101 03/i. SI 3 ■ — c — o — OR fl -> REP. REP. CLASS FN. COST = OR 4 h — fl 2 101 03^ UH i I — i— OR 5 B — B — c — fl 3 - — OR a — c — D — OR fl REP. REP. CLASS FN. COST 102 037D 514 = fl OR h^ i fl OR OR REP. REP. CLASS FN. COST 102 037D 514 B — c — D OR - fl -> B — c — fl 4 EOR OR B c — OR REP. REP. CLASS FN. COST 103 037E 514 fl l \- OR 3 1 fl — B — l : — 3 — OR 4 B — B — c — fl REP. REP. CLASS FN. COST 103 037E 514 fl — J OR fl REP. REP. CLASS FN. COST 104 03C0 308 B — B — c — fl OR fl o — C REP. LflSS 105 r REP. FN. COST a — c — R 2 ~l 03C1 410 OR 4 R l -> fl — fi — n 3 REP. REP. CLASS FN. COST B — c — fl 2 106 03C3 307 OR l -» R H — c — fl 3 - — fl — 5 — o — OR 2 REP. REP. CLASS FN. COST 107 03C5 410 R — OR 3 c J H i -> B — c — OR 4 REP. REP. CLASS FN. COST g^ OR 4 B — c — 2 108 03C6 512 OR l -> B — D — OR 5 R — fl 3 REP. REP. CLASS FN. COST B — c — 2 109 03( OR 4 "noR i i R — T — fl 3 REP. REP. CLASS FN. COST != A 2 Ill) 03CF 306 OR l -> R — 3 B — c — OR fl r — B — fl 3j REP. REP. CLASS FN. COST 111 03D4 514 fl ~ OR OR a — fl REP. REP. CLASS FN. COST 111 03D4 514 fl 3 fl OR R = fl REP. CLASS (-N. COST 112 0305 41! B — I C fl OR i ! = OR I fl RFP. R 031 ! a OR -» 8 — c — fl " 2 REP. CLASS 114 REP. FN. COST 03[ 17 410 B — fl - 3 ' OR i -> o — r B B — c — fl - 14 flEP. 5 FN. REP CLAS COST OR 4 e- c- _ = fl 2 116 n 03 D9 513 L UH 1 -> OR 5 B - - H 3 , B OR OR A H B — c — fl REP. REP. CLASS FN. COST 115 03D8 412 B — o — fl OR -> fl REP. REP. CLASS FN. COST 116 0309 513 fl ' OR i fl OR B — OR REP. REP. CLASS FN. COST 116 0309 513 r B — B — 1 OR 4 fl OR B- c — fl 5 B c — B OR REP^ REP. CLASS FN. COST 116 03D9 513 OR fl n B Z o — OR OR - REP. REP. CLASS FN. COST 116 03D9 513 n — OR fl B c — I R REP. REP. CLRSS FN. COST 117 03DB 411 n R OR R R R REP. REP. CLASS FN. COST 118 03DC 411 OR OR H — R 2 a — b — c — R 4 REP. REP. CLASS FN. COST 119 03DD 409 OR JJ B — c — R RFP. REP. CLASS FN. COST H — 2 H- 120 03DE 513 R Uhi n OR I— — i o — J~ L> 5 3 i n — u — R ' 4 R z — OR OR 3 REP. REP. CLASS FN. COST 121 03FC 409 R 8 OR N — I OR 5= OR c — o — OR HEP. PEP- CLASS FN. COST 122 0660 512 R -> REP. REP. CLASS FN. COST s — B — OR >4 s=J R 2 124 06f uh B — B — OR 5 '— c — o — P 3 1 OR 2 REP. REP. ( ^__ CLASS FN. COST « s 1 3 123 0661 618 9 — R 6 R 1 B — -» s= c — o — OR 4 n— J B — OR 5 5- OR 2 REP. PEP. CLASS FN. COST c — o — OR 3 124 0662 513 R i -» B — B — OR 4 1 = : 0R 5 C OR R — ' OR REP. REP. CLASS FN. COST 125 0663 616 OR h 4 OR R -> 5= OR — i c — D — OR REP. REP. CLASS FN. COST 126 0666 409 OR R -> c — o — OR 2 REP. REP. CLASS FN. COST 127 0667 512 R 5 c— 1 n — OR 3 R i H> B — B — OR 4 R OR OR c — D = 0R h — B OR REP. REP. CLRSS FN. COST 128 0669 723 R 11 OR h R OR OR H — B — OR REP. REP. CLRSS FN. COST 129 066B 618 R s — B — R 2 REP. REP. CLRSS FN. COST' 130 066F 513] DP a c — D — R 3 Oh l -> Un ^ 1 o — n 5 K R OR c — D OR OR REP. REP. CLASS FN. COST 131 0672 512 R OR OR REP. REP. CLRSS FN. COST 132 0673 514 OR h 4 "OR - 5 R !^j OR -n 8= OR REP. REP. CLASS FN. COST 133 0676 410 OR fl -> 8 = 5 = i= fl 2 RFP. R CLRSS OR 134 0678 618 ■ — i fl 3 UR i r -» OR 5 1 = fl i, )R c — o — fl H — e — )R fl REP. REP. CLASS FN. COST 135 0679 722 9 — B — fl 6 fl 7 OR i E fl fl OR OR c D — OR i — T". REP. REP. CLASS FN. COST 135 0679 722 fl 8= OR 2 REP. REP. CLASS FN. COST fl 5 136 067A 615 fl i C Uh , J -* fl 6 r — ■ e — OR 4 OR — ' fl 9 — B fl B — z — Q — fl fl H o fl REP. REP. CLASS FN. COST 137 067B 618 OR b 5= OR B — fl OR REP. REP. CLASS FN. COST 138 067E 513 a — 8 — OR fl E fl E fl fl 4 s — B — c— D — fl REP. REP. CLASS FN. CC 139 0690 c OR B c — A R 6 C D — fl fl — c — o — fl REP. REP. CLASS FN. COST 140 0691 519 ! — H — ' B — c — a — fl 4_ B C o — fl OR fl B c D — fl 4 = fl REP. REP. CLASS FN. COST H B B fl 141 0693 518 | c D — OR fl E fl fl REP. REP. CLASS FN. C! 142 0696 OR r c fl B C — fl B — c — o — fl 4 fl REP. REP. CLASS FN. COST 143 0697 517 OR fl B — C n — fl B — c— D — fl 4 REP. REP. CLASS FN. C 144 069F OR fl — c — n — fl 5 OR r fl « — 1= fl REP. REP. CLASS FN. COST 145 06B0 516 w — SE fl OR -> I | ( , « fl H — E fl u fl I S REP. REP. CLASS FN. COST 146 06B1 518 OR -> B — 5= fl 2 REP. REP. CLASS FN. COST 147 0682 515 OR 5 H 3 UR t J L> H — 1= D — fl 4 OR n s=1 OR OR H c OR REP. REP. CLASS FN. COST 147 06B2 515 fl u — 8= OR 2 REP. REP. CLASS FN. COST H OR 3 148 06B3 515 fl l -> H — c — OR 14 s — B — OR 5 B — c — o — H H — fl 2 REP. REP. CLASS FN. COST 149 06B4 515 OR 4 fl 3 UR H> I B — 8= fl 5 c o — R B — E fl B n — fl REP. REP. CLRSS FN. COST 150 06B5 517 R — c — Q — fl 4 OR c — OR fl a r — q — fl REP. REP. CLASS FN. COST 151 06B6 514 fl OR fl fl ~ fl B H — n — fl REP. REP. CLRSS FN. COST 152 06B7 515 OR OR B — C OR h 6 fl if- °3 fl REP. REP. CLASS FN. COST 153 06B9 619 B — a — c — o — fl 4 OR fl fl H B z — D OR OR 3 REP. REP. CLRSS FN. COST 153 06B9 619 OR h 6 fl B c — D — OR — ' c — n — OR fl B — n — fl fl - REP. REP. CLASS FN. COST 154 06BD 618 OR 1= OR 2 REP. REP. CLASS FN. COST 4 154 06B0 618 n — UH 3 ; H i -» fl 5 s= OR 6 ■ ' fl REP. REP. CLASS FN. 155 06FO H — fl OR -» fl 1 l REP. REP. CLASS FN. COST 156 06F1 517 e fl fl 4 R 5 OR -> 8 — fl REP. REP. CLASS FN. COST 157 06F2 412 H — ?= o — fl OR B — 1 = fl 2 REP. REP. CLASS FN. COST 158 06F6 411 fl 3 OR If J o — J -> 1 = fl 4 fl SEOR OR &EOR REP. REP. CLASS FN. COST 159 06F9 620 fl ~> \= OR 2 REP. REP. CLASS FN. COST 160 0776 411 OR 3 fl 1 j "7> fl — B — OR 4 c — D — fl — a — c — n — fl 2 REP. REP. CLASS FN. COST 161 0778 515 OR 5 fl — B — fl 3 OR i l -> f) — H — fl 4 H — OR 2 REP. REP. CLASS FN. COST 161 0778 515 H — c — D — OR 3 fl l B — fl 5 -> B — fl — a — OR 4 a — OR 2 REP. REP. CLASS FN. LUoi fl 5 - — a 162 0779 618 c — o — OR 3 H i i -> fl 6 H — a — OR 4 - fl 5 S — fi- ll— OR 2 - REP. REP. CLASS FN. COST 163 077A 513 c — o — OR 3 -> B — fl 1 a — a — B — OR 4 B — B — c — OR 2 REP. REP. CLASS FN. COST 164 077E 514 fl 5 c — o — OR 3 H l -> B — a — OR 4 B — B — REP. REP. CLASS FN. COST c — n — OR 4 fl 2 165 O7B0 512 R — B — Mor i -> c — o — OR 5 fl 3 fl 1= OR h 2 ■ OR REP. REP. CLPSS FN. COST 166 07BI 513 5= OR - A -> B 8= OR A H — A REP - REP - ,«T CLRSS COST 167 07B4 514 OR -> OR 8 — — A A p— 9 — C — A REP. REP. CLRSS FN. COST 168 07B5 513 OR -> S=OR S=10R R B — OR a — s OR REP. REP. CLASS FN. COST 169 0786 516 A i SE OR H c-H °=0R a— B — OR REP. REP. CLASS FN. COST 170 07BC 515 A -> 5= c o — REP. REP. CLASS FN. COST OR 4 d — i B — A 2 171 07E0 512 *h OR 5 fl" — A 3 & Z 0R OR h — c OR 8 — fl B — fl R — 8 — C fl REP. REP. CLASS FN. COST 172 07E1 616 OR c — 8 — c — o — fl 2 REP. REP. CLASS FN. COST OR 172 07E1 616 fl — ' 5 — fl 3 OR l 1 L> OR 6 ff — B — fl 5 OR fl — D — fl y Ufr OR 8 — OR REP. REP. CLASS FN. COST 173 07E2 513 ft — D — 5= fl OR B — C OR REP. REP. CLASS FN. COST 173 07E2 513 OR - fl fl OR fl H — B D — A REP. REP. CLASS FN. COST 174 07E3 513 OR 1= OR 2 REP. REP. CLASS FN. 175 07E6 COST 411 OR 3 f.M B o — j B — B — OR 4 ?= I fl OR - 1 6 fl i — 8 = fl pep. RE p - „„„ CLASS FN. COST 176 07E9 620 OR -> . REP. REP. CLP55 COST » = ^1 177 07F0 409 OR 4 n — 1— fl 3 OR -> fl c — o — OR - fl 3 REP. REP. CLASS FN. COST 178 07F1 513 n — fl OR fl c — o — fl c — o — OR 5 1 = fl " 3 H — B — fl 4 REP. REP. CLASS FN. COST 178 07F1 513 OR h> i o — OR B — — fl - B — c — OR OR REP. REP. CLASS FN. COST 178 07F1 513 fl fl REP. REP. CLASS FN. COST 179 07F2 411 1= fl 3 UH > H — B — Q — fl 4 _- R fl 5 — R REP. REP. CLASS FN. 180 07F8 COST 513 fl fl REP. REP. CLRSS FN. COS 1 181 OFFO 30' OR OR OR B c — ft — n r g c3 fl D — fl - REP. REP. CLRSS FN. COST 182 1668 7214 OR fl 4, fl OR OR OR h 5 OR REP. REP. CLRSS FN. COS) 182 1668 72 fl :4 OR IB fl s= OR fl — i a B — c — D — fl - REP. REP. CLRSS FN. COST 183 1669 829 o — fl fl fl fl EOR OR OR OR OR - REP. REP. CLASS FN. COS 183 1669 82 fl 8= R 2 ■ OR l- R 3 , OR REP. REP. CLASS FN. COST 184 166R OR H> 5 S=1 fl 8= fl i c — != S^ DR 2 REP. REP. CLASS COST n 4 8= OR 3 184 166A 722 R 1 -> R 6 « — c — OR 5 8= OR 7 9 — C EOR R H — o — .-I HOR I 7 R REP. REP. CLASS FN. COST 185 166B 724 R 5 I H R OR i OR R 4 9 — ' c — OR 3 REP. REP. CLASS FN. COST 187 167E 616 c — fl R OR R -> 5= OR 2 REP. REP. CLASS l-N. LU5i 1= c — o — R 5 1 186 166E 618 c — o — OR 3 R i ^ fl — B — R 6 fl — 8 — OR 4 ■ -4 R |E L H — B — §E R E R - PEP. REP. CLASS FN. COST 188 1681 625 H" — o — fl fl - 6 OR -» B — C OR 3 REP. REP. CLASS FN. COST (5 o — OR fl IE fl 189 1683 620 OR >= fl fl E fl fl REP. REP. CLASS FN. COST 190 1686 516 OR B — H 2 REP. REP. CLASS FN. COST fl — 5= 191 1687 619 Oh 3 B — B — c — — ' fl OR J L> 4 i c — u — OR h 61 1 — fl s 5 — C — o — ~1 0R 2 REP. REP. CLASS FN. COS 4 191 1687 61- 1 .- UK 3 I H ! H> fl 6 — ' fl — i— c— fi — OR 5 fl B c — o — fl H B — I 8= A II R REP. REP. CLASS FN. COST 192 1689 624 E fl — OR B — c — fl 2 REP. REP. B — B — 5= CLASS FN. COS UH 3 ii 193 1688 61 OR i H 4 J ^ B — c — OR 6 b — c— IT — fl 5 fl 5E 2 PEP. REP. CLASS FN. COST {= R 3 194 168E 517 OR t -> 1= fl 4 8- != fl 5 {= I fl fl t= fl REP. REP. CLRSS COST 195 1696 517 OR -> fl _ij S=OR fl OR 3 REP. REP. CLRSS FN. COST 196 1697 618 OR 6 fl 1 fl H — 8 — fl B — I- fl B fl - REP. REP. CLASS FN. COST 197 1698 518 OR -» c — — fl 2 REP. REP. CLASS FN. COST OR 3 — i 198 1699 619 B — B — fl 4 OR I K> OR 6 \= fl 5 B — B fl c o — OR EOR REP. REP. CLASS FN. COST 198 1699 619 S = OR h 5 c — o — OR I 6_ fl -> fl A REP. REP. CLASS FN. COST 199 169A 517 5 = fl n ? o — fl OR OR B — D — OR - fl != fl REP. REP. CLASS FN. 200 169B fl OR l B — 8 fl 8= fl REP. REP. CLASS FN. COST 201 169E 516 4 o — fl OR B — cH 1 fl 2 REP. REP- CLASS FN. B — c — OR 5 fl — B — 8= H — — ' fl 3 202 16A9 OR -* 1 = OR 6 fl 4 8= fl 7 fl e — B fl OR B — OR REP. REP- CLASS FN. COST 203 16AC 617 OR fl ?= B n-H OR OR fl B — C OR fl REP. REP. CLASS FN. 204 16AD r oR ,r ; != OR 2 REP. REP. CLASS FN. COST 205 16BC 516 fl 5 8 { = OR 3 fl 1 J" -> » — — OR u 1= I R l- OR —i fl — ? = OR fl REP. REP. CLASS FN. COST 206 16E9 827 fl fl 8 OR -> \= OR 2 REP. REP. CLASS FN. COST fl 5 207 177E 617 H — o — OR 3 fl l l -> fl 6 —i B — 1 c — OR 4 B — 8= fl S= OR fl REP. REP. CLASS FN. COST 208 178E 515 n — o fl OR B — 8= fl 2 REP. REP. CLASS FN. COST uh , 209 1796 618 o — fl 3 OR 1 _T -> OR 6 fl 5 6E jr— B — ' fl 2 REP. REP. CLASS FN. 210 1798 COST 5m c — OR 5 fl 3 uh ,h o — B — c — o — fl 4 i= R B — REP. REP. CLASS FN. COST 211 179R 516 fl — c — fl ft — B D fl OR B — o — OR 5 fl — o — OR 6 fl fl 3 REP. REP. CLASS FN. 212 17RC B — c — fl OR o — fl 2 REP. REP. CLRSS FN. COST B — — OR 5 212 17RC 616 a — B — fl 3 OR i _r ^> B — c — OR 6 — fl — c — fl 4 c = fl 2 REP. REP. CLHbb rn. a — o — OR 4 « 212 HRC B — B — fl 3 i OR U i y B — o — OR 6 B — c — fl 5 f) — ' o — OR OR fl B B — 5 — c — REP. REP. CLASS FN. COST 212 17RC 616 fl fl - OR H> i P= RFP REP. OR CLRSS FN. 2 B — 212 17RC c — fl 5 s — D — OR H i . -> 3 i 6 — u — fl i 6 B — c — OR l 4 h OR 2 REP. REP CLRSS FN. 212 17A t — H 6 8= OR 3 H i §= OR 4 • -* I ■ — OR 8= OR §= OR REP. REP. CLRSS 212 17RC 616 > OR "Ifi - r OR != R i HOR 6 REP. REP. CLASS FN. COST 213 17E8 720 R -> R R = 0R OR = 0R §4 OR PEP. REP. CLASS FN. COST 213 17E8 720 R -> OR = 0R 6 R J? — REP. REP. CLASS FN. COST 214 18E7 620 n B c — R OR -> c — o — R 2 OR 3 i = R 14 REP. REP. CLASS FN. COST 215 19E1 517 H — OR -> B a — D c — R 2 COST 618 fl — R 2 RFP. REP. H — i— c — ncr. ni_i . CLASS FN. b — c — o — CLASS FN. COST OR 3 216 19E3 B — c — o — OR 5 217 19E6 618 R 4 _r Uh 1 -> R 3 _r Uh 1 -> OR 6 - — 5= OR 6 B~ e — R 5 B — R 4_ c — n — OR R R R REP. REP. CLASS FN. COST 218 1BD8 515 OR R R R = R REP. REP. CLASS FN. COST 219 1BE4 516 OR S= OR a r B — B — R B — B — c — o — R R REP. REP. CLASS FN. COST 220 1EE1 620 OR ' l a — *= R H R R R REP. REP. CLASS FN. COST 221 3CC3 516 OR OR 5 8= A 2 w — ■ — REP. REP. CLASS FN. COST OR 6 R 3 1 222 6996 928 41 UM l -» OR 7 A 1 = OR 8 A 9 OR l OR 8 — c — OR 8 A H — — A REP. REP. CLASS FN. COST 222 6996 928 B — c — H — — OR A ?= A — OR i I. Report No. UlUriv. _ - - HBLIOGRAPMIC DATA HEET ^__ Tv'^'Tin-: SYNT OF OPTIMAL NETW GATES FOR FOUR-VARIABLE SWITCHING FUNCTIONS BY A BRANCH-AND- BOUND COMPUTER PROGRAM Authorise J.N. Culliney, T. Nakagawa, and S, Muroga Performing Organization Name and Address Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 6l801 2. Sponsoring Organization Name and Address National Science Foundation 1800 G Street, N.W. Washington, D.C. 20550 3. Recipient 1 * 5- Report hair 8- Performing Organization Krp<. N<> - 1J[ - - - 10. Proje< 1 'Talk/Work Una No. 11. ( ontr.K 1 (.rant No. 7 GJ-U0221 13. Type of Report & Period ( overed Technical u. 15. Supplementary Notes 16. Abstracts This report presents the results, in the form of network diagrams, of the synthesis of optimal feed-forward networks of AND and OR gates for representative functions of 219 of the 222 NPN-equivalence classes into which functions of four or fewer variables can be categorized. (Optimality here meaning minimization of the number of gates as the primary objective and minimization of the number of connections as the secondary objective. No fan-in, fan-out, or level restrictions are imposed.) Based on these results, instructions are given for obtaining optimal networks for desired functions of four or fewer variables which are not representative functions. The branch-and-bound computer program ILLOD-(ANDOR-B) was used to obtain the optimal networks presented. Utilizing the optimal network synthesis problems as a convenient test set for the program, its resultant performance is analyzed. The effect on computation time as the complexity of synthesized networks increases is also studied. 17. Key Words and Document. Analysis. 17o. Descriptors Logic design, logic circuits, logical elements, programs (computers). 17b. Identifiers/Open-Ended Terms Optimal networks, branch-and-bound method, AND/OR networks, ILLOD-(ANDOR-B), four- variable switching functions, NPN-equivalence classes. 17e. C.OSATI Field/Group 18. Availability Statement Release Unlimited 19. Security Class (This Report) UNCI ASS1FIED 20. Security Class (This Page UNCLASSIFIED 21- No. of Pages 92 22. Price FORM NTIS-3S ( 10-70) USCOMM-DC 40329-P7! jun u m *r •l ■M UNIVERSITY OF ILLINOIS-URBANA 510.84 IL6R no. CC02 no 788-793(1976 Internal report / 3 011 2 088402653