LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAICN 51084 UQ>r ho. 293-300 cob.2 CENTRAL CIRCULATION AND BOOKSTACKS The person borrowing this material is re- sponsible for its renewal or return before the Latest Date stamped below. You may be charged a minimum fee of $75.00 for each non-returned or lost item. Theft, mutilation, or defacement of library materials can be causes for student disciplinary action. All materials owned by the University of Illinois Library are the property of the State of Illinois and are protected by Article 16B of Illinois Criminal law and Procedure. TO RENEW, CALL (217) 333-8400. University of Illinois Library at Urbana-Champaign 'JUM2 81999 ft 6 1 AJ1. When renewing by phone, write new due date below previous due date. L162 Digitized by the Internet Archive in 2013 http://archive.org/details/optimumnetworkde293baug J- Z-93 OPTIMUM NETWORK DESIGN USING NOR AND NOR-AND GATES BY INTEGER PROGRAMMING by C. R. Baugh T. Ibaraki T. K. Liu S . Muroga January 10, 1969 THE LIE IF THE red 17 1969 Optimum Network Design Using NOR and NOR-AND Gates by Integer Programming C. R. Baugh T. Ibaraki T. K. Liu S . Muroga January 10, 1969 S/P,ff 0SJ. 2^ Abstract In this paper the integer programming formulations of optimum network synthesis problems are demonstrated to be computationally- feasible by actually obtaining all the optimum NOR gate networks and NOR -AND gate networks for three variable switching functions. (80 representative functions of equivalent classes by permutation and negation of variables. ) The algorithm used for solving the integer programs is the implicit enumeration algorithm which was tailored to our problem [91 with algorithmic and programming gimmicks. The total computation time for these 80 functions on the IBM 360/751 was 110 minutes for NOR gate networks and ^k minutes for NOR -AND gate networks. The algorithm which was further modified by taking into consideration the inherent structures of NOR gate networks showed a significant improvement of computation time. With this second algorithm, all the optimum networks under fan-in and fan-out restrictions for the odd parity function which had not been computed before, were computed in 6 minutes and oq seconds. All the optimum NOR-AND gate networks for each of 80 three variable switching functions were also tabulated. Optimum Network Design Using NOR and NOR-AID Gates By Integer Programming 1. Introduction Based on the integer linear programming approach discussed in the previous papers , optimum combinational networks of NOR gates and those of NOR-AND gates have been synthesized. This paper presents computational results. The integer programming algorithm used for solving those problems is the implicit enumeration method which is modified and it is described in detail elsewhere . The algorithm is further tailored to our problems by making use of the particular structures of our problems, improving the computational efficiency greatly over the first algorithm. In this paper all the optimal networks of three variable switching functions with NOR gates and those with the combination of NOR-AND gates are exhausted by integer programming approach. The computation time on IBM 360/751 with the H level FORTRAN IV compiler for NOR networks for all three variable switching function (80 representative functions of equivalent classes by permutation and complementation of variables.) is 110 minutes, and it is further improved by the factor of about 10 times by using the above second algorithm. It takes 5^- minutes for synthesizing optimum NOR-AND combination network for all three variable functions. This result may suggest the computational feasibility of integer programming approach and encourages further investigation. 2. Integer Programming and Implicit Enumeration This section presents the outlines of the integer programming problem and implicit enumeration algorithm for solving it. For detailed description, see the references [6] [9] for example. The computer code used for the network synthesis is discussed in the reference [9]. It is a result of simplicication and modification of the original implicit enumeration algorithm [l] [5] [6] [7] in order to improve computational efficiency. An integer programming problem with n unknown variables and m constraints is in general stated as follows: Minimize c x (2.1) subject to b + A x > 0, where c is an n-dimensional vector of non-negative constants, "B" is an m-dimensional vector of constants and A is an (m x n) matrix of given coefficients, and x is an n-dimensional vector of variables. In our case, all variables x are integers which assume only 1 or 0. Sometimes this is refered to as the zero-one integer programming problem. The implicit enumeration algorithm has been computationally proved to be one of the most efficient methods for solving this type of zero-one problem. It implicitly enumerates all the 2 solutions without explicitly and exhaustively examining all of them, and picks up the best feasible solution. Let us start with several definitions. When all the variables in x are assigned 1 or it will be called a solution . If a solution satisfies the constraints A x + b > 0, it will be called a feasible solution and if not, an infeasible solution . A feasible solution that minimizes c x is an optimum feasible solution . A partial solution S is defined as an assignment of "binary values to a subset of the n variables. Any variables which are not assigned are called free variables . A completion of a partial solution S is a binary assignment to all free variables. Let us outline the implicit enumeration algorithm as it is shown in figure 2.1. With a given partial solution S and the incumbent solution (the feasible solution having the smallest value of the objective function obtained thus far), the block entitled "CHK-IEQ" is entered. At this point, examine whether some of the free variables must be 1 or if each inequality is to be satisfied. Scanning through the inequalities until no more free variables are assigned, S with these free variables assigned becomes a new partial solution S . Next the partial solution S is checked to determine which of the following 3 cases occurs. (1) Feasible: The completion of S obtained by setting all free variables to is found to be feasible. It is compared with the incumbent and the better of the two is maintained as the incumbent. The 2 backtrack procedure is initiated to obtain a new partial solution S by changing some of the assigned variables according to a certain rule.* (2) Infeasible ; If at least one inequality is not satisfied by S whatever binary values are assigned to the free variables, then S is discarded immediately by initiating the backtrack procedure. The back- 2 track procedure forms a new partial solution S from S . (3) Augment S : If neither of the above two cases occur, a free 2 variable is assigned to 1, forming S . The choice of this variable greatly affects the convergence and it should be made according to the type of problem being solved. [7] * The backtrack procedure was first proposed by Glover . A detailed explanation can also be found in [6], [9] and will not be described in this report. 2 After replacing S with S , the entire procedure is repeated by reentering the block "CHK-IEQ". Fig. 2.1 Implicit enumeration algorithm (Augment S ) i_ AGMT - VAR Augement S by assigning a free variable to obtain „2 CHK - IEQ Check inequalities with S . Assign free variables and form S (Feasible) Keep the better solution as the incumbent (infeasible) _i Backtrack 2 forms S By cycling through this procedure repeatedly, the computation results in the implicit enumeration of all possible solutions. When the computation terminates, the incumbent is the optimum solution. The checking procedure of each inequality such that one of cases (l), (2) and (3) is quickly identified is explained in [9]. The implicit enumeration algorithm converges in a finite number of steps, but the efficiency of the algorithm heavily depends on the nature of an individual problem. Our computational experience shows that tailoring the block labeled AGMT-VAR in Fig. 2.1 (the subroutine which augments the partial solution when (3) occurs) to a given particular problem speeds up the convergence. Some aspects of our AGMT-VAR tailored to NOR gate network synthesis will be discussed in Section k. 3. NOR Network Synthesis All the optimum feed-forward NOR gate networks of three variable switching functions are realized by using the formulation described in [11]. Networks are optimum in the sense that the number of NOR gates in the networks is minimized first and the number of interconnections among gates and from external variables is minimized second. The same problem was already solved by L. Hellerman by actually exhausting all the network configurations and then finding the best network among them for each function. When the problem is solved as an ordinary integer program, however, the computation time for all three variable switching functions (80 representative functions of equivalent classes by permutation and complementation of variables) is about 110 minutes* on the IBM 360/751 with the H level FORTRAN IV compiler. This compares favorably with Hellerman' s result consuming about 26 hours on the IBM 7090. Now, the basic configuration for a NOR feed-forward network is shown in Figure 3«1« Let us explain the additional inequalities, which are introduced solely to reduce the computation time by precluding the redundant connections or by partially precluding networks which are equivalent by permutation of gates. The basic formulation of these additional inequalities is the same as that of [11]. The problems we solved have three external variables x_, x p , x„. Let the connection from x_ to the i-th gate be v_ . Let the connection from the i-th gate to the k-th gate (i < k) be cp . Since only completely IK specified functions are considered, each input vectors x = (x , x p , x..) is numbered as x J> j = 1, 2, . . ., 8 from 3T ' = (0, 0, 0) through x = (l, 1, l). The output value of the i-th gate for the j-th input vector 3T" 3 ' is denoted as T-?'. And let p:j*' denote cp., P: J '. i lk lk i * In Section k, this computation time is further reduced by designing a sophisticated AGMT-VAR algorithm. 7 Fig. 3^1 Feed-forward network cp, IE Inequalities for characterizing a feed-forward network with R NOR gates which realizes the function f(x) is as follows. For k - 1, 2, ..., R-l - E v*x ( , d) - 2 P^ } > -U (1- p[ J) ) £=1 ^ l i=l 1K * V „ k „(0') , V Jj) -. 1 TT -d(J) (3-D ,\ *J 'i + = P ir > 1 " U P k X>=1 1=1 = 1, 2, ..., Oj where U is a sufficiently large positive number such that the upper inequality is non-restrictive if p) = and the lower inequality is non-restrictive if P, ' = 1. k For the last gate (the R th gate) Z v* xft - E p^ > if f (x^ j) ) = 1 i=l l £ i=l lR " (3.2) z v* x ( . j) + s P ^ :> i if f (x^ j) ) = o i=l ^ ^ i=l j = J-^ ^- ^ • • » ) o i And in place of the relation p.. = cp., p., we have the inequalities IK IK 1 4 i] - *ik + <$ > - 1 p:*" + cp.. - 2 p^ > o i T ik lk — (3.3) k = 2, 3, -.., R j = 1, 2, . . ., 8. The procedure used in this paper to obtain all optimum solutions proceeds from R = 1 and increases R by 1 each time until the feasible solution is reached. The objective function used is the number of interconnections R k-1 3 k S ( 2 cp + Z O, (3.U) k=l i=l 1K i=l l and therefore its minimization results in the minimum number of interconnections as the secondary objective. In other words, if we find the first feasible R and then exhaust all the solutions which minimizes the objective function (3«^)> all the optimum solutions are obtained. Seemingly the implicit enumeration algorithm has a tendency that the smaller the region of all solutions, the faster the convergence. Hence our effort was directed to preclude unnecessary solutions by adding extra inequalities so that the solution region becomes smaller without prohibiting any necessary optimum solutions. These additional inequalities essentially consist of two types; one is to preclude unnecessary network configurations and the other is to partially suppress the geometrically equivalent networks (i.e. those with permuted gates). They are listed in the following. Proofs are omitted. (l) A NOR gate ( B in Fig. 3.2 (a)) which has only one input from another gate ( A) with only one output, and which is not the output gate is not permitted in an optimum network, because the same 7 7^^^ Fig. 3.2 & -®-d>"~@-*- -^5©""^ Cascaded IX (a) (b) 10 connections function can be realized with two fewer gates, as shown in Fig. 3*2 (b). Hence each gate except the last has at least one input from the external variables or at least two inputs from the other gates, which is expressed by an inequality: 3 k k-1 2 E v- + 2 cp > 2 £=1 Z i=l lk (3-5)* K. — J_j d % • • • « i\— J_« Note that this condition does not hold in general when the fan-in restriction is imposed. (2) Consider any subnetwork which has only one gate which has outputs to gates not in the subnetwork (Fig. 3* 3). Fig. 3' 3 Ordering of inputs ~-»fc (1 J -^ ~-fc — ^ 1 I T ) — ( k \ » r^ v-^ ~-w L>— --^ subnetwork Assume the subnetwork consists of 1 through k. Let the k-th gate is the output gate of this subnetwork. Then we can order the interconnections to the k-th gate from the other gates in the subnetwork such that cp, < cp < . . .<

Fig. 3«^ Triangular interconnections no other output where the J th gate has no outputs except cp . It is easily proved that if J K all of cp. ., cp , cp are 1, the network is not optimum, thus introducing ij -*-K Jk inequalities: *« + *ik + *dk * 2 + £ *Jt (3.7) t=j+l i < j < k < R . Even if the i th gate in Fig. 3.^ is replaced by an external variable x,, the above property is still true. Then from (3«7) we obtain: 12 v i- v i + v^ 2 + R E t+k t=j+l •., (3.8) j < k < R I = 1. 2, 2L (U) This condition is an extension of case (3). Consider any subnetwork which has no outputs except those to the k th gate and where the i th gate and the k-th gate is connected, as shown in Fig. 3' 5* Assume that the subnetwork consists of the (i+l)st to (k l)st gates. Fig. 3*5 Generalized triangular interconnections no other output except > to the k th gate Then the interconnections from the i th gate to the subnetwork are all redundant and therefore can be deleted. This condition is written by an inequality: k-1 E q>. . k-i-1 R < + U ( E E ^i+h i + ^ik^ h=l j=k+l 14 *' J lk (3.9) i = 1, 2, ..., R-2 k = i + 2 ..., R, k-1 where U > E cp. . for all i and k. j=i+l Even if the i-th gate is replaced by an external variable, the above property is still true. In this case the inequality is: 13 k-1 . k-i-1 R E y] <0 + U ( S E (p + (l-v*)) j=i+l * h=l j=k+l 1+n,:) ^ (3.10) £=1, 2, 3 l = lj C. y m • • y R— £_ iv-- 1-rt j ■ • • « -^5 k-1 where U > Z v* for all i and k. j=i+l In the above discussion it was assumed that the subnetwork consists of the gates of the consecutive numbers (i.e. from the (i+l)st to (k-l)st gates) but an extension to the more general case where the subnetwork consists of gates of non-consecutive numbers is possible. (5) A certain geometrical symmetry is also investigated. For example, Fig. 3' 6 shows three gates connected to the last gate. Fig. 3» 6 Symmetry of a subnetwork © In this configuration, it makes no difference to which of three gates the (R-l), (R-2), and (R-3)> the (R-if)th gate is connected. Hence we can impose an ordering such that Ur-1 - ^R^R-S ^ %4,R-3 (3oll) in order to preclude part of the gate configurations which are equivalent by permuting gates. This particular condition is represented by, 11+ VU,R-3 2 VM-2 + (1 * V 3 ,e' + (1 " "fe-2,R> + (1 - U>' (3-12) T'- S-U,H-a * \4,R-! + (1 - tP R-3,E ) + (1 - \-2,R> + (1 " Vl,! 1 Similar types of symmetry conditions are extensively considered and a number of such inequalities are employed in the actual computation. However, the details of each type is not given here. (6) If the interconnection between the i th and (i+l)st gates is known to be 0, these two gates are geometrically equivalent and their output connections can be ordered. Hence we can first order their connections to the last gate as %R * *i+l,B. (3 - 13) If it turns out that cp. _ = ep. then the connections to the (R-l)th gate can be ordered as "i.R-l * "W-l. {3 - lk) This argument continues until cp ^ cp. (k > i+l) eventually holds. After that, no ordering on the connections is permitted. This sequential condition is expressed by the inequality: R-i . , R-i S 2 D " ± cp. . .• Z 2 3 " 1 cp. _ . . + U cp. . _ (3-15) i = 1, 2 } • • • j R~ 2 . 15 (7) Each gate has at least one output, because the network is assumed to have exactly R gates. This condition is expressed by R 2 j=k+l % * X (3.16) for every k = 1, 2., . .„, R-l. The size of the problem is given in Table 3.1, both with a selected subset of the additional inequalities and without them. TABLE 3.1 Size of NOR network formulation Without additional inequalities With additional inequalities R Number of integer programming variables Total number of inequalities % of non-zero coefficients* Total number of inequalities 2 23 ko 11+.58 - 3 52 88 7.12 - h 90 152 Ml 169 5 137 232 2.91 265 6 193 328 2.11 1+15 7 258 kko 1.60 716 * For the function f(x) = 0. For other functions, the sizes of figures are almost equal to those in the table. 16 The formulations of the problems may be characterized by the following properties: (1) There are more inequalities than variables. Therefore the solution region is usually very small. In fact, many problems were found to be infeasible. (2) The non-zero coefficients in the inequalities are fairly sparse. This feature was extensively utilized in our computer program of the implicit enumeration algorithm ^ J in order to speed up the computation. (3) The objective function has only coefficients of or 1. [91 This also simplifies the algorithm and is fully utilized . The implicit enumeration algorithm was used on the NOR synthesis problem and the results are given in TABLE 3*2. The algorithm was set to enumerate all optimal feasible solutions. It also assumed no fan-in and fan-out restrictions. The computation took approximately 110 minutes on the IBM 360/751 for a H 80 representative functions. All networks were identical to Hellerman's. We examined what are influential factors on the speed of our program. The effect of additional inequalities on speed-up was remarkable. Some problems tried for the R=5 formulation was speeded up by the factor of 5 in computation time. As explained in[n] many types of network restrictions such as fan-ins and fan-outs can easily be added to the synthesis problem in the form of inequalities, without the necessity of changing or complicating the program. This is one of the advantages of the integer programming formulation. When the fan-in restriction is imposed, the restrictions 17 CO •H CO CO CO o CO g S co II -P P> &3 H CO -P H co ft co •H C. -P r-1 CO > O -P CO •H <$ fe -H ft CO cd CO ch . d fl o •H ^-v -P M C CO LT\ CO Cd CO O T3 c— ON ON OJ 1 M-P ft-H fl rod -P O o • • ON • LTN • 1 1 h ft co o o H o 1 co g a g co oo «aj o -P ch w t3 g •H C! ,G •P o co !>» &S C! o rd cH CO J- o -4- cs •H tj • • • -P H -p CO ITN CO •4- CO O cd ■p CO LTN vo H co H «h CO < O ft d o •H ^-* LT\ •P H £ co t- o ON VO o (0 cd co O 'd OJ ON LfN OJ o bO-P ft-H c! • • • • • cd 3 -P oo OJ OJ H ft CO O O -d- OO £ s 3 s ° > -H 3 CO ON <; o -P chw s o m •H (U W -P H O o -h £5 cj 3 3 o). For example, P.: is of type GC* because by setting cp = 1, F~ (2) (2) can be covered. P.; is of type G*C* because of Pp = *. The type of each gate is shown. Obviously the type of this partial network is G*C* which is the type of gate 3* Let us describe the procedure in the new AGMT-vAR. If the type of partial network is one of ISL, COV, LTG, the current partial solution is feasible because we use Procedure I in Section 5 of [11]. Otherwise let us identify P. which defines the type of this partial network. K. In the definition of the types G*, VC*, GC*, G*C*, and NWG, free variables are associated with P. such that if these free variables are set to 1, k P, is covered (e.g. in the case of VC*. P n is covered if v„ is set to k k 11, 1, i.e if the corresponding free variable is set to 1. ). This free variable is then specified so that p]_ is covered. For example, Fig. h.1 shows (2) (2) that P.: is identified according to the type of partial network. P_ is of type G*C* and can be covered by connecting gates 2 and 3? i-e by (2) ** setting cp = 1 and specifying P^ = 1 . Other types are similarly * The least desirable is chosen in the definition because unless the gate having the least desirable is made to satisfy the properties of NOR gates, the partial network is not feasible. ** In actual programming, this is done by augmenting the current (o) (2) partial solution by p\% - ! rather than cp = 1 and P^ ' = 1. (2) Subsequently cp and P^ are set to 1 when the partial solution undergoes CHK-IEQ. 25 (3) (J) WG vc* * vc* ■* ■* vc* vc* LTG vc^ 1 vc* -X- ,(d) GC* G*C* 1 G*C* * 1 G*C* G*C* G*C* cov G* cov cov 1 tt cov cov f 1 1 cov 1 cov cov 1 1 cov ,(d) Fig. ,(o) U.l (a) Example of types of P<^ = 0, gates, and the partial network. 26 J x l *2 x 3 1 2 1 3 1 h 1 1 5 1 6 1 1 7 1 1 8 1 1 1 Fig. U.l (b) Assignment of values to x ^J) 27 * (i) treated: An appropriate p in the c?se of G*, GC*, G*C* types or an appropriate v„ in case of VC* is set to 1. However the type NWG is treated differently. If a gate is of type NWG, the isolated gate which has the largest gate number is identified. Let it be y. Then p v is set to 1 where P defines the type of partial network. Setting p , to 1 will force cp , and P JJ to 1. thus covering P, . However if yk rk 7 k p r_ (i.e. p ^_ is not a free variable), all solutions with anyone of isolated gater, connected to gate k have been investigated and do not need to be checked again. This follows from the fact that gate y and any other isolated gate are equivalent with respect to the paritial network (i.e. non-isolated part) since any isolated gate can be connected to any other gate. This approach eliminates the permutation of gate labeling which is inevitable with the feed-forward network. Of course, if we discover that p was already set to 0, then we can simply abandon the v K. current partial solution and go to the backtrack procedure. A comment is given on the case in which the type of the partial network is VC*. If the types is VC*, sometimes more than one external variable can be connected. In our algorithm, among all possible external variables, the external variable which covers the largest number of P =0 not yet covered is connected to the gate. This new AGMT-VAR is used in place of AGMT-VAR shown in Fig. 2.1 and assigns a free variable to 1 according to the type of the partial network. Then CHK-IEQ is applied as before. Other part of algorithm are exactly the same as the general case discussed in the earlier sections and in [9L except that the following objective bound check is added to AGMT-VAR to further speed up the computation. * Note that p:j^ = cp p;^ iK IK K 28 Given a partial solution, a lower bound of the objective function value is estimated according to the rules based on the following properties. If this bound exceeds the objective value of the incumbent, the current partial solution can not give any better solution than that and accordingly it is discarded. (The rest of computation for the current partial solution is skipped and backtrack is immediately applied). The bound estimation is programmed by using the following properties of the network: (1) Exactly R gates are assumed to be used in the network. In other words, each gate has at least one input connection and at least one output connection. (2) According to condition (l) of Section 3> each gate has either at least one input connection from external variable or at least two input connections from other gates. (3) The number of gates each of which is solely devoted to expressing x. (i.e. a gate has only one input which is an external variable x.) is at most three. 1 (U) If the type of gate is GC*, G*C* or NWG, the gate needs at least one more interconnection from another gate, as seen from the definitions of these types. (5) If the type of partial network is VC*, the gate whose type defines the type of partial network needs at least one more connection from an external variable. If this single external variable does not cover all the P?. which are of type VC*, we need to add at least one more external variable. 29 This bound estimation is included in AGMT-VAR and whenever it demonstrates that the current partial solution can not give any better Lbl e solution than the incumbent the backtrack procedure is performed immediately. With all these modifications added, all 15 functions which can be realized with 6 gates were tested on the R= 6 formulation. The improvement was remarkable. The average number of iterations per function is 136.3 and the average computation time for each function is ^.°9 seconds which is favorably compared with the result in Table 3-2 in Section 3 run with the general purpose AGMT-VAR, in which 95^ iterations and h-2.26 seconds on the average were necessary for each function. If the fan-ins and fan-outs restrictions are considered, the rules based upon the above properties (2) and (3) must be modified. All other rules are unchanged. For example let us assume that each gate has maximum fan- ins and fan-outs of 3« Let us examine Figure U.2. Fig. k.2 Modification due to fan- in and fan-out restrictions 30 The single input to gate j is not allowed only if o R— 1 R— 1 S (vi + v£)+ 2 q> + E cp, , < 3 (U.U) t=l * * t=l t:L t=l tk "" tH tij o R— 1 R — 1 and E (v* + v^) + E cp ti + 2 cp tk < 3 # (fc-5) t=l t=l t=l t+1 tt=j t*i Property (3) also must be modified. Using the rules "based on these modified properties, the odd parity function x © Xp © x_ which requires 8 NOR gates when the fan-ins and fan-outs are limited to 3 was' solved. Since there is only one function to be solved, the structure of an optimum network for the function x_ © x © x is taken into consideration. In other words, this function is symmetric in all the three variables x_, Xp and x , and accordingly the interconnections from x. to the last gate are ordered as follows. 7 7 and if v^ = v ' then vl>vl>v[ (k.6)* 6 6 v ^ +1 > V £ J = 1, .2. (^.7) * It can be easily shown that the last gate (the 8th gate) has no external variables connected, if a given function can not be expressed as a conjunction of the product ®f literals and a disjunctive expression. 31 ((k.'j) could "be continued to the gate numbers lower than 6. But the continuation was not incorporated in our program. ) Also two interconnections cjVn and cp ~ are assumed to be 1. This is guaranteed "by the fact that the networks which are constructed by adding one gate to the output of optimum 7 NOR gate networks of x © x © x , give no better realization of x Q, x @ x than those obtained by solving the 8 gate formulation. The problem has 395 variables and 1012 inequalities including additional inequalities. All optimum solutions are shown in Fig. U.3« [13] The network (c) of Fig. k.3 is the same as that found by Tangiguchi et al. The computation took U822 iterations with network (a) occuring at the 1368th iteration, network (b) at l6U7th iteration, and solution (c) at the 3052th iteration. The total computation took less than 6 minutes and 30 seconds on the IBM 360/751* When the program was modified so that only one of the optimum solution is to be found, the time was reduced to 5 mil utes 15 seconds. These computation times are a considerable reduction with respect to the results of Table 3*2 in Section 3» The reduction of the computation is due to the desirability order of types and the all-iterconnection formulation. The all-interconnection network formulation appears to contribute more to the reduction than the desirability order. The desirability order probably has to be changed when different types of gates are to be used. Our computation times are about the same as Davidson's, though exact comparison is very difficult because computers used are different and simple programming gimmicks may further make changes in computation times. 32 x 2 Xi x 2 (a) (b) . (c) Figure U.3". All optimum networks for x. @ Xp © x. 33 Probably one of the advantages of our approach is ease of programming effort. Since we can fully use the information associated with variables of the inequalities, the procedure to determine the types of P, , gates and eventually the partial network is fairly straightforward and simple. Also Property 1 of the NOR gate is automatically taken care of by the CHK-IEQ routine, thus eliminating the procedure for checking this property. Another advantage is the fixed amount of storage needed throughout the computation. In Davidson's "branch and bound algorithm" the amount of storage often grows as the computation proceeds. Thus additional programming must be done in order to recalculate needed information or to use secondary storage. Because of great improvement of the all- interconnection network formulation over the approach of Section 3* improvement in computation time even in the case of multiple -output network design also can be expected with the all-interconnection network formulation. The accurate comparison of the exhaustive method, Davidson's and ours, in terms of the program complexity, computational efficiency, ease of programming and all other aspects, is difficult at this stage because a number of factors should be considered for the comparison and the data obtained so far is not sufficient. Here we tried this new approach to show the flexibility of the implicit enumeration algorithm. In other problems also, it is quite likely that we can achieve a great improvement by considering the intrinsic properties of the problem and incorporating appropriate modifications of the algorithm. Some examples [91 of this approach will be found elsewhere * Our integer programming approach can be extended to the logical design of an optimum sequential network and to the diagnosis of a network, different from Davidson's. 3^ 5. NOR -AM) Network Synthesis One of the important advantages of integer programming formulation is that we can solve a wide variety of problems by simply changing the set of inequalities. Networks composed of NOR and AND gates are represented in inequalities according to the formulation in [12]. Of course the optimum networks are also interesting in their own right. All the optimal networks for 80 three variable switching functions are tabulated under the same optimality criterion as NOR networks. All the notations in this formulation are the same as NOR network case except that we have to introduce new variables indicating whether each gate is NOR or AND. These variables are 9 k , k=l, 2, ..., R. (5.1) 9 = 1 (0) shows that the k th gate is NOR (AND). The basic set of inequalities describing a feed-forward network of R gates is as follows. This formulation is found in [12]. For k = 1, 2, ..., R-l 3 k t*\ k-1 t*\ 3 k k-1 , v = V i *i + = p ik * = v i + = *ik " U (l " P k j) " U 9 k £=1 i=l z=l i=l 3 k (,\ k-1 , x 3 k k-1 f v -2 v x^ ; - 2 p^ ; > -2 v - 2 cp +1-UP JJ -U0 i=l l l i=l 1K i=l Z i=l Ik k K -2 vj xl^- 2 P^.P > - U(l-pf^r U (1-0J i=l ^ ^ i=l lk ~ k k S v k x (j) + 2 ~ (j) ■> " ^^ £=1 l l i=l 2 v* x^+ 2 p^ > 1 - U P k j; - U (l-0 k ) (5.2) 3 — -Lj £- j . . . > O. 35 It may be easily seen that the first twc inequalities are for an AND gate and the others for a NOR gate, depending on the value of 6 associated with these inequalities. For the last gate, if f(x^) = 1, 3 rj ( *\ R_ l /jN 3-n R-l Z v x^ + Z p\^ > S v* + S p - U i»i * * i=l ^ i=l ^ i=l lR R ji^'^'S^- '^ 1 " 9 ^ (5 * 3) and if f(x^) = 0, 3 R M n R-l /.x 3 R R-l - E v*, x^ j - 2 p^ > -I v - E p + 1 - U e R 4=1 * l 1=1 4=1 * i=l Z v ( A ( A E P ^ } > i-u(i-eJ (5.U) 4=1 * * 1=1 1R " R for d = 1, 2, ..., 8. The relation p.? =

1 l lk lk — P i + ^ik " 2 p ±k - ° (5#5) k = 2, 3, ..-, R i = 1, 2, ..., k-1 3 = 1* ^ > • • • y o. Additional inequalities are also incorporated to reduce the computation time. All of those additionals inequalities which were used in the all NOR network case are included except the geometrical symmetry restrictions given by (5) of Section 3« In addition the following two types of inequalities were added. 36 (l) Input interconnections Each AND gate has at least two input interconnections. This constraint is given by 3 k k-1 Z V £ + E p ik ^ 2 " 6 k i=l * i=l lK * Fig. 5-1 Triangular interconnection (5.6) (2) Triangular interconnections Again consider three gates connected together as shown Fig. 5.1« Contrary to the NOR network case, if either of the gates j and k is AND gate, at least one of the three connections cp. ., r o , cp must be ^-3 !k jk even if the j-th gate has outputs other than cp . This condition is given by cp. . + cp + cp < 2 + . ^ij jk ik - j cd. . + cp.. + cp < 2 + 9 n ij Y jk ik - k (5.7) i < j < k < R. When the i th gate is replaced by an external variable, v i + vv^ + (5.8) A + A + ^^ 2 + \ j < k < R I = 1, 2, 3. 37 Together with these additional inequalities ( some of additional inequalities based on the properties which have been discussed are not incorporated because of their excessive number. ) , all the optimal NOR-AND combination networks for each function are solved. The entire computation took about ^k minutes on the IBM 360/751, using a program which includes the general purpose AGMT-VAR. All functions are realized with not more than six gates. The size of each problem and computation time are listed in Tables 5*1 and 5.2. The computation time is graphically given in Fig. 5*2 as well as the NOR network case. The effect of additional inequalities was remarkable. For the R=3 case the computation time was reduced 6 times by incorporating the additional inequalities; and for the R=U case 18 times. Incorporation of other additional constraints such as the constraint that each AND gate should have at least one NOR gate connected to its output, will reduce the computation time further, though these were not actually tried. Also contrary to NOR gate network, no effort was made to improve the computational efficiency of the integer programming algorithm. Of course a significant reduction of computation time can be expected by modifying the algorithm as discussed in Section k. A comparison of computation time with NOR gate networks is shown in TABLE 5«3 where the ratio of the computation time of the NOR- AND network case to that of NOR network case discussed in Section 3 is listed. 38 o * U ra (U (D N C -H 1 -H -P C -H O w H £ CO CM H ra w cd cd cd -P -H rA -H O-p Mni-p -P -H fi fl -H H -H O H 0) t> •H •-> +5 M K (fi CD CO +3 W £ £1 £ ra O -P CD CO •H -H CQ H +3 £ H H SZ! bD-P 3 VD o UA 1 1 cd cd Ch h h CO rt 1 CD CD H >+3 d) <'H P( CD H •H o CO cd •H C -P o CD Cd «H -p -p P o H ft 1 O «h d t~- O -~- • • • H CO o co CO CD CD Ti CM bo ft a cd O >d M CD O CD g CD > -H CO < -Pv_- -d «h h CD O a) -P ft CO • p O co cd 53 a £\ o c M CD -H O W o LT\ J- _=t- t>0-P -H -=f H -=t- co cd cd -p H co t- h m O 00 CD CD a > -p 3 <;-h cd O co t>- H CD O _=r CD S CD > -H CO <£ -P^-- co CD C H O tH^-H O -H -P CO O CO LT\ CX\ ir\ ON -3- \T\ • cd H H OJ H o — R Computation Time Iterations Feasible Infeasible Feasible Infeasible k k.O 6.3 3.8 k.l 5 9.8 Ik.k 8.1 10.2 6 11.3 9.2 On the average a function can be realized by NOR-AND combination network with O.85 fewer gates than that of the NOR network case. The number of interconnections is also reduced by 1.5 on the average. All the optimal networks for three variable function are tabulated in Appendix A. The tabulation also gives all the optimal networks by NAND-OR combination by the following procedure: (l) take the dual of a given function f, (2) find optimal networks for the dual function f by NOR- AND combination and (3) replace NOR by NAND, and AND by OR. These are optimal realizations of f by NAND-OR combination. 1+1 1000.0 - 100.0 10.0 z 1.0 _ .k - 150 200 250 Number of NOR gates I 4 umber of NOR -AND gates Fig. 5« 2 Average computation time per function for NOR and NOR -AND synthesis fe 6. Conclusion Two logical design problems, one with NOR gates only and the other with NOR-AND combination, formulated as integer linear programs were solved by using the implicit enumeration algorithm. NOR gate network synthesis is very important from an engineering view point and has attracted much attention. Integer programming approach to this problem is proved to be computationally feasible and is faster than Hellerman's exhaustive method. Advantages of integer programming approach include its versatility and simplicity to handle a variety of gate types, a variety of network restrictions such as maximum fan-ins restriction, and also various objectives, without changing the algorithm. Simply changing part of the algorithm i.e. the AGMT-VAR, we can have a program of high speed at the sacrifice of the ease of programming, a program of simplicity and generality at the sacrifice of speed, and a wide range of programs between these two extremes. Due to the principle of the implicit enumeration algorithm, we can modify and augment the algorithm so that the intrinsic properties of the problem can be fully used. Section h explored this possibility along with Davidson's work and obtained a improved result in NOR gate network synthesis. Furthermore three networks for the odd parity function were proven to be optimum. By simply changing the inequalities, different problems can be solved. NOR-AND gate networks were thus synthesized by using different set of inequalities. Also we believe that this is the first tabulation of all the optimum networks with NOR and AND gates for all three variable functions. U3 Reference , [1] E. Balas, "An additive algorithm for solving linear p rograms with zero-one variables, " Operations Research, vol. 13, no. h pp. 517-5^9, July-August 1965. [2] M. A. Breuer, "Implementation of threshold nets by integer linear Programming," IEEETEC, vol. EC-lU, no. 6, pp. 950-952, December I965. [3] S. H. Cameron, "The generation of minimal threshold nets by an integer program, " IEEETEC , vol. EC-13, no. 3, pp 299-302, June I96U. [k] E. S. Davidson, "An algorithm for NAND decomposition of combinational switching function," Ph.D. dissertation, Department of Electrical Engineering and Coordinated Science Laboratory, University of Illinois, 1958. [5] B. Fleischman, "Computational experience with the algorithm of Balas, " Oper a tions Re se arch , vol. 15, no. 1, pp. 153-155* January - February 19^7 • [6] A. M. Geoff rion, "Integer programming by implicit enumeration and balas' method," SIAM Review , vol. 9 no. 2, pp I78-I9O, April I967. [7] F. Glover, "A multiphase-dual algorithm for the zero-one integer programming problem, " Operations Research vol. 13, no. 6, pp 879-919* November-December 1955* [8] L. He Herman, "A catalog of three - variable OR- invert and AND- invert logical circuits," IEEETEC , vol. EC-12 no. 3 pp. 193-223, June I963 [9] T. Ibaraki, T. K. Liu, C. R. Baugh, and S. Muroga, "Implicit enumeration program for zero-one integer programming," to be published. [10] T. K. Liu, "A code for zero-one integer linear programming by implicit enumeration, " Master thesis, Department of Computer Science, University of Illinois, I968. [11] S. Muroga and T. Ibaraki, "Logical design of an optimum network by integer linear programming - Part I," Report No. 26k, Department of Computer Science, University of Illinois, July I968. [12] S. Muroga and T. Ibaraki, "Logical design of an optimum network by Integer Linear "programming - Part II, " Report No. 289, Department of Computer Science, University of Illinois, December 1968. [13] K. Taniguchi, N. Tokura, T. Kasami and H. Ozaki, " Logical functions realizable by a planar NAND network, " The Trans, of Electronics and Commu nica tion Engineers of Japan , vol. 51-C, no. 2, pp. 59-65, February 196 8. kh Appendix A: Tabulation 0:.' Optimum NOR-AND Networks Here listed are all the optimum networks for each of all functions of up through three variables, using NOR and/or AND gates. The networks which have the minimum number of interconnections and connections among the networks with the minimum number of gates are chosen as optimal network. The procedure for obtaining the optimum network diagram for a given function follows that of Hellerman's [8]. A function can be represented by a truth table as shown below, by specifying the values of f , f p , ..., fn where f , ..., f~ show the values of the given f for input vectors in the same rows, a, b and c denote the variables of f. a b c f l f 2 1 f 3 1 f k 1 1 f 5 1 f 6 1 1 f 7 1 1 f 8 1 1 1 Let us write eight binary numbers f _, , .... f as follows. 1 o f 8 f 7 f 6 f 5 f U f 3 f 2 f l Sfc — v ' * y— ' " v ' 0. 0. Al grouping the f.'s as shown, we obtain three octal number . This octal number is used throughout Appendix to identify a function. In Tables A2 and A3, only representatives of equivalence class obtained by permutation of variables are listed, reducing 256 functions into 80 representatives. The representative of a given function f can be easily derived by using Table Al, which is taken from Hellerman [8]. The procedure is illustrated by an example. Suppose that the function f has the number 321. The entry for this number in Table Al is 5*213 • This means that f is equivalent to function 213 hy applying permutation 5 which is (ac) as also shown in Table Al. Table A2 shows that function 213 has optimum networks with network numbers U9 and 56. Then Table A3 gives us the actual optimum networks of function 213. To obtain optimum networks of 321, we apply the inverse of permutation 5j which is also (ac), to these networks in Table A3. Twelve of the 80 three -variable functions listed are degenerate in the sense that they are independent of at least one variable. The network diagram numbers for the degenerate functions have the suffix D. They are grouped together at the beginning of Table A3. Table A3 shows all the optimum networks obtained for each function without imposing fan-in restrictions. However all the networks except that of function 026 are optimum even if the fan-in restriction that each gate can have at most three input interconnections is imposed. Function 026 needs one more gate if the above fan-in restriction is imposed. Optimum networks in this case are shown in Fig. Al. A2 Note that if a given function is symmetric in some variables, say a and b, then, among all the optimum networks obtainable by permuting these symetric variables, a and b, only one network is listed in Table A2 and Table A3. The rest of networks can be obtained by simply exchanging the connection from the external variables according to the permutation of variables. A3 1 2 3 1+ 5 6 -1*000 1*001 1*002 -1*003 3*002 -3*003 1*006 10 1*010 1*011 -1*012 1*013 -1+*012 i+*0l3 1*016 20 2*002 -2*003 2*006 2*007 3*006 3*007 1*026 30 1*030 1*031 1*032 1*033 U*032 l+*033 1*036 1+0 2*010 2*011 -6*012 6*013 •2*030 2*031 6*032 50 1*050 1*051 1*052 1*053 1*051+ 1*055 1*056 6o -2*012 2*013 2*016 -2*017 2*032 2*033 2*036 70 6*05^ 6*055 6*056 6*057 -1*071+ 1*075 1*076 100 3*010 3*011 3*030 3*031 -3*012 3*013 3*032 110 3*050 3*051 i+*05i+ l+*055 3*052 3*053 l+*056 120 -5*012 5*013 5*032 5*033 3*016 -3*017 3*036 130 3*05^ 3*055 -3*071+ 3*075 3*056 3*057 3*076 lUo 2*050 2*051 2*051+ 2*055 5*05l+ 5*055 -2*07U 150 1*150 1*151 1*152 1*153 3*152 3*153 1*156 160 2*052 2*053 2*056 2*057 5*056 5*057 2*076 170 2*152 2*153 2*156 2*157 3*156 3*157 1*176 200 1*200 1*201 1*202 1*203 3*202 3*203 1*206 210 -1*210 1*211 1*212 1*213 1+*212 1+*213 1*216 220 2*202 2*203 2*206 2*207 3*206 3*207 1*226 230 1*230 -1*231 1*232 1*233 l+*232 l+*233 1*236 2 1+0 -2*210 2*211 6*212 6*213 2*230 -2*231 6*232 250 1*250 1*251 -1*252 1*253 1*251+ 1*255 1*256 260 2*212 2*213 2*216 2*217 2*232 2*233 2*236 270 6*2 51+ 6*255 6*256 -6*257 1*27U 1*275 1*276 300 -3*210 3*211 3*230 -3*231 3*212 3*213 3*232 310 3*<5° 3*251 l+*25l+ l+*255 -3*252 3*253 l+*256 320 5*212 5*213 5*232 5*233 3*216 3*217 3*236 330 3*251+ 3*255 3*27^ 3*275 3*256 -3*257 3*276 3^0 2*250 2*251 2*251+ 2*255 5*25l4 5*255 2*27U 350 1*350 1*351 1*352 1*353 3*352 3*353 -1*356 360 -2*252 2*253 2*256 -2*257 5*256 -5*257 2*276 370 2*352 2*353 -2*356 2*357 -3*356 3*357 1*376 7 1*007 -1*017 1*027 1*037 6*033 1*057 2*037 -1*077 3*033 l+*057 3*037 -3*077 2*075 1*157 -2*077 1*177 1*207 1*217 1*227 1*237 6*233 -1*257 2*237 1*277 3*233 -l+*257 3*237 3*277 2*275 1*357 2*277 -1*377 Explanatory Example Class of 321 is given by word at intersection of row 320 and column 1, This says 321 is in class of 213 by permutation 5« Negative permutation means the function is degenerate. 5*213 Permutation 1 is the identity Permutation 2 is ( abc) Permutation 3 is ( acb) Permutation 1+ is ( be) Permutation 5 is ( ac) Permutation 6 is ( ab) Table Al. Equivalent classes of functions of three variables. Al+ Table A2: Catalog of all the optimum NOR-AND networks of three variable functions. A5 Function (octal) 000 003 012 017 07^ 077 210 231 252 257 356 377 001 002 006 007 010 Oil 013 Functional expression a'b' a'c a' ab' + a'b a' + V be be + b'c' c a' + c b + c 1 a'b'c' a'b'c a'b'c + a'bc' a'b' + a'c' a'bc a'bc + a'b'c' a'b' 4- a'c Network number ID 5D 8D 9D kD 13D 10D 6d iUd 15D 3D 11D 12D 7D 2D 1 3 7 15 8 6 5h 61 18 No« of gates NOR 1 2 1 1 2 1 3 3 3 2 2 1 2 1 2 1 1 3 3 3 AND 1 1 1 1 1 1 1 1 1 1 1 1 1 No. of inter- connections and connections 2 3 3 1 6 3 2 7 7 k h 3 3 k k 7 k k 8 8 5 1 2 2 1 2 2 1 3 3 3 3 2 1 2 2 2 2 2 3 3 3 A6 Function (octal) Functional expression N itwork number No. of gates No. of inter- connections and No. of levels < NOR AND connections 22 2 1 5 3 )l6 a'b + a'c k 2 k 2 )26 a'b'c + a'bc' + ab'c' 68 2 3 13 2 ff a'b* + b'c' + a'c' 30 1 3 9 2 )30 ab'c' + a'bc 70 k 1 10 3 1 71 3 2 10 3 88 k 1 10 k )31 a'bc + b'c' 85 k 1 9 k )32 a'c + ab'c' 28 2 2 9 2 »33 a'c + b'c' 3k 3 1 7 3 kk 2 2 7 3 36 a'b + a'c + ab'c' 29 2 2 10 2 37 a* + b'c' 17 1 2 6 2 50 a'bc + ab'c 27 3 1 8 2 55 2 2 8 3 51 a'b'c' + a'bc + ab'c 79 3 2 11 3 52 a'c + b'c 11 2 1 5 2 26 1 2 5 3 53 a'b' + a'c + b'c 36 3 1 8 3 5k a'b + ab'c k7 2 2 8 3 55 a'b + a'c' + ab'c lh 3 2 11 3 78 3 2 11 3 56 a'b + b'c 12 2 1 6 2 57 a* + b'c 33 3 1 7 3 i h3 2 2 7 3 p a'b + ab' + a'c' 35 3 1 8 3 U5 2 2 8 3 J6 a'b + ab' + a'c Ik 2 1 7 2 A7 Function (octal) Functional expression Network number No. of gates No. of inter- connections and connections No. of NOR AND levels 150 a'bc + ab'c 4- abc' 80 3 2 11 3 151 a'bc + ab'c + abc' + a'b'c' 101 3 3 Ik 3 152 a'c + b'c + abc' 62 2 2 8 ' 3 153 a'c + a'b' + b'c + abc' 76 3 2 11 3 156 a'c + b'c + be' 13 2 1 7 2 157 a' + b'c + be' 37 3 1 9 3 U6 2 2 9 3 176 ab' + be' + a'c 16 2 1 8 2 177 a' + b* + c' 9 1 1 k 2 200 abc 2 1 3 1 201 abc + a'b'c' 52 3 1 9 3 202 abc + a'b'c 73 1+ 1 9 3 77 h 1 9 3 82 3 2 9 k 90 3 2 9 h 203 abc + a'b' 50 3 1 8 3 206 a'b'c + a'bc' + abc 100 k 2 12 3 10^ k 2 12 k 106 k 2 12 k 109 k 2 12 k 110 k 2 12 k 111 k 2 12 h 112 k 2 12 k 207 a'b' + a'c' + abc 81 3 2 9 3 -J A8 Functio] (octal) i Functional expression Network number No. of gates No. of inter connections and No. of levels NOR AND 4 connections 89 3 2 9 k 9h 3 2 9 k 211 be + a'b'c* 51 3 1 8 3 212 a'c + be 31 1+ 6 3 38 3 1 6 3 6k 3 1 6 It 66 2 2 6 k 213 a'b' + be ^9 3 1 7 3 56 3 1 7 3 216 a'b + a'c + be 72 k 1 9 3 86 k 1 9 k 91 3 2 9 k 95 k 1 9 k 96 k 1 9 k 217 a' + be 1+8 3 1 6 3 61 2 2 6 k 226 abc + ab'c' + a'bc' + a'b'c 105 k 2 12 k 227 a'b' + a'c' + b'c' + abc 99 k 2 12 3 102 k 2 12 k 230 ab'c' + be 8k k 1 9 k 87 3 P 9 k 97 3 2 9 k 232 a'c + be + ab'c' 92 k 1 9 k 93 3 2 9 k ?33 a'b' + b'c' + be 57 i 1 3 1 8 ,_ 3 A9 No. of inter- connections Function (octal) Functional expression Network number No. of gates and connections No. of NOR AND levels 236 a' c + be + a'b + ab'c' 98 k 2 12 3 103 k 2 12 h 107 k 2 12 k 108 k 2 12 h 237 a' + be + b'c* 69 k 1 9 3 83 3 2 9 k 250 ac + be 10 3 5 2 21 2 1 5 3 251 ac + be + a'b'c' 59 3 1 8 3 253 a'b' + c 20 3 5 3 25^ ac + a'b 32 k 7 3 39 3 1 7 3 255 ac + be + a'c' 58 3 1 8 3 256 a'b + c 63 h 6 h 1 65 3 1 6 k 27U ab 1 + ac + a'b Uo 3 1 8 3 275 ab' + ac + a'b + a'c' 60 3 1 9 3 276 a'b + ab' + c kl 3 1 9 3 277 a' + b' + c 23 2 1 5 3 350 ab + ac + be k2 3 1 8 3 351 ab + ac + be + a'b'c' 75 3 2 11 352 ab + c 25 2 1 5 3 353 ab + a'b' + c 53 3 1 8 3 357 a' + b + c 19 3 5 3 2k 2 1 5 3 : 376 a + b + c 5 2 1 1* 2 J Table A3 List of all the optimum NOR -AND combination networks for three variable switching functions. NOR > AND All o I- <_> z 3 r-- O CM o Q CD Li. CM in O CO in p Z O u Li. o CM 6 o CM s o H U o o o o z § o A12 z o o 3 u. ♦ X> o "o O O CO u x> <0 m o <\j 10 <£> o O z 3 u "X) CM o o o o m O z o 3 u. u jO o o CM o Z g o iX> O CVJ z o o z U_ o o u XI * ♦ "XI ♦ "o O z (J> m A13 o z => o z (XI O Z o o z 3 If) m z o o z 3 ro O o z a o z =5 rO O O z A114 z o u z O o z o 8 K o t- u z O z in ro 5 5 o z 2 o z to O 8 $ o i- o 3 u. A15 8 o z z 3 o a o a s s o z o CM o IT) s z o CM O A O A € to Al6 Z O z 23 8 3 "■§ o p a o z c\j ID + on jn CM CM g IS z o t- u z 3 O z ID m CM s £1 u A 8 A17 o 3 o CM CD O I- u 3 Li. r<-> CM r<1 CD CO CO CM « 2 CM o CM 8 8 £ o s 3 Li- fe o CM jo o £1 0*J ro ro 0> A18 3 in o (VI D + 3 o z N c\j CM 8 Z o U z U. ID to CM 8 3 O s s A19 k .=r> (1) (2) '=Oi :=£> :z C>T70R>* -E> (3) (4) dZh c-^> (5) Fig. Al Optimum networks of function 026 when the fan- in is limited to three. A20 APPENDIX B: Ordering of Interconnections In the feed-forward network formulation gates are uniquely labeled 1, 2, ..., R. Usually there are many representations for the same configuration of the optimal network simply by permuting the labels on gates. For example the two networks in Fig. B.l are equivalent under permutation of gate labels. L 3' In order to reduce this obvious redundancy many inequalities are formulated to order the gates. For an example of such inequalities a list of inequalities for the 6 gate feed-forward NOR network will be presented. Since the inequalities were not generated systematically, the list is not complete. Let us denote (l - cp.) by cp. . where cp. . is 1 if there is an interconnection from gate i to gate j and otherwise. Note that the inequalities are for 6 gate NOR networks with unlimited fan-ins and fan-outs. The inequalities corresponding to an R gate NOR network with restrictions on fan-ins and fan-outs can be written in an analogous way. B-l 1. Order Inputs to the R-th Gate (i.e. output gate ) The ordering of connecting gates 1 through R - 1 to the output gate R can be specified as cp > cp for all i > j. This follows from ik — JK that fact that any circuit with cp > cp . and k < £ can be obtained from a circuit in which cp^ > cp for all i > j by permutation of gate labeles, in — JK k and I. '26 s 1>36 2. Ordering the Outputs of All Isolated Gates As was defined previously an isolated gate is a gate which has none of variables, v.'s and cp ' s representing its inputs and outputs 1 jk specified to 1. When the isolated gate is connected to the subnetwork, the isolated gate can often be connected in several ways. Furthermore the networks resulting from these different ways of connecting the gate are often equivalent with respect to permutation of the gate labels. In Fig. B.2 networks (b) and (c) give an example of two different ways of connecting the isolated gate 3* Fie;. B.2 B-2 By examining Fig. B.2 we can see that gates k and 5 of the subnetwork consisting of gates k, 5, and 6 are equivalent with respect to permutation of gate lables and the connection of gate 3 to gate k or 5 (i.e. network (b) is equivalent to network (c) if gate labels k and 5 are permuted). Thus we can restrict cp , < cp for the given subnetwork consisting of gates k,$ and 6 to prohibit network (c). The subnetwork (a) in Fig. B.2 can be specified as ^36 + \6 + * 5 6 (1) for the following reason. The sum in expression (l) assumes the value zero if and only if the gate U,5 and 6 are connected as shown in Fig. B.2 fa) and otherwise it is 1 or greater. Thus we can order the pair of interconnections cp„_ and cp„, under the assumption that the subnetwork 3? 3*+ of Fig. 3' 2 (a) exists. This conditional ordering of gate output inter- connections can be expressed by the following inequality ^<^ 35 +* 3 6 + \6 + V (2) Because if the subnetwork exists, the last three terms of (2) becomes and (2) becomes cp , < cp . Let us call cp , < cp of expression (2) as the ordering portion and + cp ^ + cp, ^ + cp /- as the subnetwork specification portion. Note that the subnetwork specification portion will be positive and expression (2) will be non-restrictive if the subnetwork described by cp , + -cp, ^ + "cp ^ does not exists. All the following inequalities in this section can be similarly interpreted by first examining the subnetwork specification portion B-3 of the inequality and then observing the ordering required on the pair of cp. . variables. a) 5 W 6 **(*) This subnetwork is denoted by cp,-,- + 9^6 * Assuming this subnetwork we can get the following inequalities in terms of isolated gates, according to the above discussion. Ordering Subnetwork ^35 - % + ^56 + \6 ^25 - *35 + *56 + \6 ^15 - *25 + ^56 + ^6 ^23 - ^h + ^35 + H + \6 ^13 * 'lU + % + V + ^6 ^!2<

6 + 2cp 2 5 + ^ ^ Ucp 3 6 + 2C °35 + ^ +8CP 2 3 (3) The subnetwork specification portion of expression (3) is 8cp . The ordering portion is i+cp g + 2cp + cp , < i+q? g + 2cp + cp . which expresses the restrictions B-6 "26 * V