LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN #0 yjr Report No. U25 ' r \ DESIGN OF OPTIMAL ONE- BIT ADDER NETWORKS BY INTEGER LINEAR PROGRAMMING by Lih-Er Shiau January 15, 1971 NOV 9 1972 UNIVERSITY OF JLLINOiq CHAMPAIGN DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS Digitized by the Internet Archive in 2013 http://archive.org/details/designofoptimalo425shia Report No. k25 DESIGN OF OPTIMAL ONE- BIT ADDER NETWORKS BY INTEGER LINEAR PROGRAMMING* by Lih-Er Shiau January 15, 1971 Department of Computer Science University of Illinois Urbana, Illinois 6l801 This work was submitted in partial fulfillment of the requirements for the degree of Master of Science in Computer Science in the Graduate College of the University of Illinois, January 1971 and supported in part by the National Science Foundation under Grant No. NSF GJ-503. Ill ACKNOWLEDGEMENT The author is very grateful to his advisor, Professor S. Muroga, for his guidance and criticism in the preparation of this thesis. The author also wishes to thank Mr. T. K. Liu for the many con- structive ideas he put forth and the many helpful suggestions. This work was supported in part by the National Science Foundation under Grant No. NSF GJ-503. iv CONTENTS SECTION Page 1. INTRODUCTION 1 2. DESIGN OF A ONE-BIT ADDER 3 3. INTEGER LINEAR PROGRAMMING AND THE IMPLICIT ENUMERATION ALGORITHM ... 6 k. FORMULATION OF A NETWORK SYNTHESIS PROBLEM 11 k.l Threshold Gate 11 k.2 Feed-Forward Network and All-Interconnection Network Formulation . 13 4.3 Formulation for One-Bit Adder Synthesis Problems 16 4.3.1 Objective Function 17 4.3.2 Basic Gate Characterizing Inequalities 18 4.3.2.1 Gate Descriptive Inequalities 18 4.3-2.2 Input Value Inequalities 26 U.3.2.3 Mixed-Gate Network 28 4.3.3 Additional Inequalities 29 4.4 Self-Dual Function 38 5. PROCEDURE FOR DESIGNING AN OPTIMAL NETWORK 40 6. COMPUTATIONAL RESULTS kl APPENDIX: REFERENCES 66 SECTION 1 INTRODUCTION The main object of this paper is to design an optimal network for one-bit adder (the elementary unit of an adder), where the optimality is defined as : (1) The number of gates in the network is minimized first, then (2) the number of connections (from external inputs to gates) and interconnections (between pairs of gates) is minimized, secondarily. The problem of designing optimal networks for one-bit adder is first formulated as an integer linear programming problem and then solved by the implicit enumeration method. Outline of this method will be discussed in Section 3« For detailed description, see the references [6], [9], for example. The computer code used for the network synthesis is discussed in the reference [10]. The problem formulation is based on the inequality represen- tation of threshold gates. This is a general formulation because conventional switching gate, such as AND, OR, NAND or NOR, can be considered as a special threshold gate with appropriate specification. In this paper, we will formulate four one-bit adder problems corresponding to various combinations of switching gates and solve them by integer linear programming. These four cases are: (1) all NOR gates, (2) NOR and AND gates, (3) NOR and NAND gates, and (k) AND and OR gates. Results of these problems will be given in Section 6. SECTION 2 DESIGN OF A ONE- BIT ADDER Let us consider the addition process in the i-th bit position of an adder (the i-th "block in Fig. 21). C. . S. l-l l-l i-1 i — i — s A C i-2 Bi-1 Figure 2.1 As figure 2.1 indicates , there may be a carry from the (i-l)th block, and the i-th block will produce not only a sum digit but it also will produce a carry to the (i+l)-th block. Each block of Fig. 2.1 has the same function. We call it "one-bit adder". An one-bit adder is therefore a 3- input (augend, addend, carry- in) and 2-output (sum and carry-out) device which implements the truth table : A. l B. i c i-i s. 1 c. 1 Augend Addend Carry-in Sum Carry- out 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Table 2.1 The truth table defines two switching functions, sum and carry. The corresponding Boolean expressions are: CARRY = AB + BC + CA SUM = ABC + ABC + ABC + ABC The carry function clearly points out that the carry is 1 when two of the three inputs are 1, i.e., when a majority of the inputs is 1. We therefore call it "majority function". For the sum function, we can see easily from the truth table 2.1 that whenever odd number (1 or 3) of the three inputs (A,B,C) are l's, the sum is 1. We call this function "odd parity function". The design of one-bit adder is thus equivalent to the design of a network which can accept 3 inputs and whose two outputs C and S can realize the majority function and the odd parity function, respectively. SECTION 3 INTEGER LINEAR PROGRAMMING AND THE IMPLICIT ENUMERATION ALGORITHM This section presents the definition of the integer programming problem and the outline of the implicit enumeration algorithm for solving this problem; for details of the algorithm refer to [6], [9], and [10], Definition of integer programming An integer programming problem with n unknown variables and m constraints can be stated as follows: Minimize c x subject to b 4- A x > where [c 1 , . .., c n ], c i > i = 1, ..., n b - tb r ..., bj and A = [a. .] ij ran are coefficient matrices and x - [x^, . • • , x n ] is an n-dimensional vector of unknown variables x_ , . . . , x . In this 1 n report all the variables x!s are assumed to be the values of or 1 and all coefficients assume only integer values. Our problem is to assign or 1 to each component of x such that the inner producti of c x is minimum and the constrains, b 4- a x > 0, are satisfied. Implicit enumeration algorithm The implicit enumeration algorithm has been computationally proved to be one of the most efficient methods for solving the (0, 1) - variable type problems. It picks up an optimum feasible solution by implicitly enumerating all the 2 solutions without explicitly and exhaustively examining all of them. Let us start with several definitions: l^i "o lution : '.•.'lien all the components of x are assigned to 1 or 0, x is called a solution. Feasible solution : If a solution satisfies the constrains, b f A x > 3. it is called a feasible solution. Infeasible solution : If a solution does not satisfy the constrains, b + A x > 0, it is called a infeasible solution. (k) ptimal feasible solution : A feasible solution which minimizes the product c x. Partial solution : If only part of the components of x are assigned to binary' values or 1, then x is called a partial solution. (6) Free variable : Variables which are not assigned to and 1 in a partial solution are called free variables. ^) Fixed variables : Variables which are assigned to or 1 in a partial solution are fixed variables. (8) Completion : A completion of a partial solution is a solution obtained by assigning binary values to all the free variables of the partial solution, The outline of the implicit enumeration algorithm is shown in Figure 3»1> With a given partial solution S and the incumbant (the s = s CHK-IEQ Check inequ. with present^ partial solution, (S°) (otherwise) (if feasible) (if some free variables of S must be assigned to or 1 so that b + Ax > can be satisfied) (S ) with assigned free variable form (s 1 ) if infeasible) ACMT-VAR By assigning a free variable of (S or S 1 ) to 1, form (S 2 ) Compare with in- cumbent solution Keep better one as incumbent BACKTRACK : Locate the rightmost element of present partial solution (S or S ) which is not underlined. If none exists, terminate; otherwise change the sign of the element, underline it and delete all elements to the right Figure 3*1 Implicit enumeration algorithm feasible solution having the smallest value of the objective function obtained so far) , the block entitled "CHK-IEQ," is entered. At this point the program examines whether some of the free variables must be assigned to 1 or if the constraints b 4- A x > are to be satisfied. If so, assign them to their proper values. Scanning throuth the inequalities until no more free variables can be assigned, S with these assigned free variables becomes a new, partial solution S . Next the partial solution S is checked to determine which of the following three cases occures: (1) Feasible: If the completion of S obtained by setting all free variables to is feasible, then it is com- pared with the incumbent and the better one (the one with smaller c x) of these two is maintained as the incumbent. The backtrack procedure is initiated to 2 obtain a new partial solution S by changing some of the assigned variables according to a certain rule. (Refer to [6], [9l). (2) Infeasible: If, regardless of whatever binary values are assigned to the free variables of S , there are at least one in- equality which is not satisfied, then all the completions of S will not be feasible solutions and thus S is discarded immediately by initiating the backtrack proce- dure. The backtrack procedure forms a new partial 2 1 solution S from S . (3) Augment S : If neither of the above two cases occurs, a free 2 variable is assigned to 1, forming S . The choice of this free variable greatly affects the convergence 10 and it should be made in an appropriated way according to the type of a particular problem being solved. (For our network synthesis problems, the choice is based on the desirability order of gates [k]. The detailed expla- nation can be found in [k] , [9] and will not be described in this report). 1 2 After replacing S with S , the entire procedure is repeated by reenter- ing the block "CHK-INQ". By cycling through this procedure repeatedly, the computation results in the implicit enumeration of all possible solutions. When the computation terminates, if there is an incumbent, then the incumbent is the optimum solution. Otherwise, the problem is infeasible. The checking procedure of each inequality such that one of the cases (l), (2) or (3) is quickly identi- fied 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. 3.1 (the subroutine which augments the partial solution when (3) occurs) [9], to a given particular problem speeds up the convergence. 11 SECTION k FORMULATION OF A NETWORK SYNTHESIS PROBLEM In our formulation of logic design approach by integer linear program- ming, a network is assumed to be synthesized with threshold gate, because a threshold gate is a unified expression of many different types of gates. Conventional switching gates such as OR, AND, NOR and NAND may be considered as special threshold gates with thresholds and weights appropriately specified. k.l Threshold Gate Definition of Threshold Gate : A threshold gate as shown in Figure h.l, is a logic gate which consists of a real we ight vector w = [w , w , . . . , w ] and a real threshold T such that the output P of the gate is n Z w n x.y' > T 0=1 n / . n if Z w, x7 ; < T - 1 i=l i l ~ (k.l) where all possible combinations of values of the input variables -(1) -(2) ^(2 n ) (i) x , x_, ..., x are ordered as x , x , . . . , x and x\ (£ = 1, ..., n where n is the number of inputs) is the value of x , in the j-th input com- bination x J , V is the output of the gate when the inputs vector has the value x . 12 Figure ^.1 The output P of the threshold gate represents a threshold function of the variables x , n For one-bit adder network problem,, we only consider n = 3 since there are only 3 external inputs (carry- in, addend and augend) to the network. o The 2 =8 possible input combinations are as follows: ?*' = ( o ) :7< 2 > - ( 1 ) & . , ; o i o ) £ k) = 1 ' i 1 ) x<5) . , i o ) xT< 6 > = ; i 1 ) & . 1 ; i 1 o ) ^ - , ' i 1 1 ) We call x (j = 1, ..., 8) the j-th input vector of the 3 inputs. 13 The conventional switching gates such as OR, AND, NOR and NAM) gates are the threshold gate with their weight vectors w"s and thresholds T's specified as Table k.l Type of gate Weight vector w threshold T OR [1, 1, -.., 1] 1 AND [1, 1, -.., 1] Sum of weights n ( .Z w. = n) 1=1 i NOR [-1, -1, ..., -1] NAND [-1, -1, ..., -1] Sum of weights +1 n (j£-, w.+l = -n+l) Table k.l Weights and Thresholds of conventional switching gates, (where n is the number of inputs). Therefore formulation for the network synthesis problem with threshold gate covers those cases with the conventional switching gates. By discussing only the formulation procedures with threshold gate, we can discuss all cases of different conventional switching gates. k.2 Feed-Forward Network and All-Interconnection Network Formulation We restrict the network to be synthesized to be a feed-forward net- work of threshold gates. A feed- f orward network is the most general case of loop-free network, and is a network in which all threshold gates are arranged in a line and each gate can receive the inputs only from Ik the external inputs x/s and the outputs from its preceding gates P.'s (i > (the gate number under consideration)). Figure k.2 Feed-forward network (two-outputs) The formulation of a feed-forward network is by no means computationally most efficient. Thus, an efficient formulation which is called all- inter- connection network formulation is picked up and used in our one-bit adder synthesis problems. In an all- interconnection network (as shown in Fig. 4.3)? all possible interconnections are permitted between every pair of gates. Using all- interconnect ion network formulation method to formulate our synthesis problems does not destroy our restriction of feed-forward network. Because in our computer program, we prohibit these connections which will raise loops in our networks. Also it has the advantages over the feed- 15 Figure k.3 All-interconnection network (two outputs) 16 forward formulation, such as uniform treatment of gates regardless of gate numbers, the freedom of interconnections and preclusion of more solutions which are equivalent by permutation of gates. k.3 Formulation For One-Bit Adder Synthesis Problems In this section we will explain the formulation of the following four one-bit adder synthesis problems by integer linear programming: (1) Network with only NOR gate (2) Network with NOR and AND gates (3) Network with NOR and NAND gates (h) Network with AND and OR gates Based on the integer linear programming problem in the previous section, our synthesis problems consist of: (1) The objective function c x for R gates feed-forward network (see section U.3-1) (2) The basic gate characterizing restrictions (see section U.3.2) (3) The additional restrictions to reduce the computation time (see section 4.3-3) It might be pointed out that the additional restrictions are not necessary in a theoretical sense. However, these narrow the region of solutions of the integer programming problem and thereby reduce the computa- tion time greatly. All the restrictions in our problems can be expressed in term of linear inequalities. Before going into the generation of those restrictive in- equalities, let us first assume that our network is formulated with the all- interconnection network formulation. And, since one-bit adder is a network 17 with 3 inputs (addend, augent and carry-in) and 2 outputs (sum and carry- out), we can restrict that our network comprises of R threshold gates, 3 external variables (>: . x , x ) and 2 outputs (S and C). The following notations denote these binary variables used in our formulation: k k v .: The connection from external input x , to gate k. When v* = 0, JO X/ it implies there is not connection between them. k k w .: Weight of the connection v.. x.n : The 0-th input variable of the j input vector x ^ , where j =1, ..., 8. ¥., : The interconnection from gate i to gate k. ¥.. = implies no lk : lk interconnection between them. ., : Weight of the interconnection ¥._ . lk lk T : The threshold of the k-th threshold gate in the network. P. : The output value of the i-th gate under the j-th input vector 1*) - (xp } , *ti\ J*h. 3 U.3-1 Objective Function To find an optimal network, first we minimize the number of gates. This can be done by starting with only one gate (k = l). If the problem is in feasible, then increase the number of gates by 1 and try again. Repeat this procedure until we can get feasible solutions (for detail see section 5) Therefore, for a specific number of gates (R), the only thing we should consider for our objective function is to minimize the sum of the following two: 18 (l) The number of external connections to each gate k 3 ( Z vj , and &=1 l (2) The number of internal connections to each gate k from other gates R 1=1 itk Symbolically, our objective function is: p Q "D Min [ Z ( Z v 1 ! 4- Z ¥ )] k=l 0=1 l i=l 4 . 3» 2 Basic Gate-Characterizing Inequalities These inequalities are derived from the definition of threshold gate with modification. They include (l) gate descriptive inequalities and (2) input value inequalities. The former is used to describe the gate used in our problems. In the following pages, we will discuss the derivation and the modification k. 3- 2.1 Gate Descriptive Inequalities Let us consider any threshold gate, say gate k, in a feed- forward network (Fig. h.k). Inputs to gate k can come from the external inputs (i.e., x,, I = 1, 2, 3) and the outputs of the gates preceding gate k(i.e., P., for all i > k). Weights corresponding to x, are w, (i = 1, 2, 3) and those corresponding to P. ' s are a. (i # k). But since we use all- interconnection network formulation method to formulate our synthesis 19 k+1 Figure k.k A threshold gate in a feed- forward network problems, we can assume that every gate i (i > k or i < k but i 1= k) in our network can feed gate k. Thus by the definition of threshold gate (equa- tion k.l) we have: ,(d) "k if Z w k xV 5 ' + L a., p[^ > T. « . £ I i=1 ik i - k i±k (J+.2a) ,(j) if z w, x 7 d; + z a.. p: j; < T. p. I i , - ik l - k i£k - 1 (4.2b) k = 1 ... , R According to whether P. (J) ,(j) k 1 or P^. u ' = 0, only one of the two inequa- lities (k.2) holds. Now, we can eliminate the "if - condition" in (k.2) by introducing a sufficiently large positive number U to (k.2) and rewrite (k.2) as: 20 Z w* x^ + Z a.. P^ - T. > - U (1-R (tj) ) (4.3a) , ., ,0 i . , lk 1 k — k ' v ^ / £=1 i=l iik z w k x^ + z a.. P :*>' - t. . , lk l k-k v w» / il=l i=l i=k It is easy to prove that (4.3) is actually equivalent to (4.2) because when p) = 1, (4.3b) becomes non-restrictive and (4.3a) becomes the same as (4.2a). Whereas P/ = 0, then (4.3a) becomes non- restrictive and (4.3b) K. becomes the same as (4.2b). As shown in Table 4.1, since the values of the weights of all the logic gates (OR, AND, NOR and NAMD) are either 1 or -1 (if input connection exists), then the following relationships between weights (w ? and a. ) and input 1/ IK Xr connections/interconnections (v„ and Y... ) must hold: ' • lk (1) If the input connestion/interconnection exists (i.e., v =1 and/or Y . = l) then the corresponding weight (w and/or a., ) is set to either: (a) w k . = v k , , a., = ¥.. if weight is 1 (4.4a) v i I ' lk lk or (b) w^ = v^ , a = - !F. if weight is -1 (4.4b) Xj kj ' IK IK (2) If the input connection/ interconnection does not exist (i.e., k k v, = and/or \|r. n = 0) then the weight (w. and/or a.. ) corre- 1 lk & ' ik sponding to this input connection/interconnection is set to zero (i.e., w„ = and/or a., = 0). ' t lk 21 Based on the above relationships, inequalities (h.3) can be rewritten as follows : (l) If weight is 1 (i.e., AND gate and/or OR gate) Z v k xV" + Z ♦.. p!^ - T. > - U (1 - R^) „ , c 7 6 , - lk i k— k ' £-1 i=l ij* Z v k xV 1 ' + Z t., P. - t. i! . _ ik i k— k y *=1 1=1 1 J=k - Z v k ySp - Z *,. P?^ - T. < U P^' _ , _ * i . _ ik l k— k-1 1 i=l (k.5) (h.6) 4k i\. — J_ • • • • a X\ 3 si, . . . , 8 By introducing the new variable $(p = Jr., P. (d) (^.7) ik ik i inequalities (U.5) and (^.6) with the non- linear terms ^. P. can be rewritten as the following linear forms: 22 (l) If weight is 1 (AND gate and/or OR gate) i/=l i=l i=i * * i=l lk k- k ife k = 1, . .. , R J = -*-j • • • > ® (2) If weight is - 1 (NAND gate and/or NOR gate) i^k 1./.N R / . \ / . \ - z v. x, j; - z p;. 3 ' - t, < u p; j; . n x, Z . - lk k — k - 1 lo=l 1=1 .1* k = 1, . .., R j = 1, ..., 8 The non- linear relation (4.7) (4.8) (4.9) P-£ = ^- k P. will be expressed as linear inequalities later. Gate descriptive inequalities for logic gates, OR, NOR, AND and NAND will be given in the following: (l) Gate descriptive inequalities for OR gate OR gate has threshold T = 1 and weights l's. Substituting T = 1 into (4.8), we have o -p Z v* x { P + Z ?[p > 1 - U (1 - P (j) ) JLl * Z i=l lk ~ k (4.10) 23 =1 4* £=1 1=1 k = 1, ... , R d = l, . . . , 8 (2) Gate descriptive inequalities for NOR gates NOR gate has threshold T = and weights -l's, substituting T = into (4.9), we get z v^xp } + z 3^ } 1-UP. « , i i . _ lk — k £=1 i=l k = 1, ..., R (3) Gate descriptive inequalities for AND gate AND gate has weights l's and threshold T = sum of the weights of input connections and interconnections to gate k 3 k R k = Z w,+ z a (some w/s and/or a ' s might be if I) n .6 -, IK // IK Z=l 1=1 l{fc the corresponding v»'s and/or ^ ' s are 0) 3 k R = Z v. + Z t., (by relationship (U.Ua) £=1 ^ i=l liC 2k Substituting this threshold T into inequalities (k.Q) , we obtain: Z v\ x^ } + Z ^ - ( Z v) + Z V) > - U (1 . P^ } ) 4=1 ' i=l 1K i=l ' 1=1 lK " k ifk i^k 33 3 R (^.12) Z v* x J) + Z 0<£) - ( Z v* + Z * ) + 1 < U P^ } 4=1 J * 1=1 1K 1=1 Z 1=1 i^k i^k Now let us introduce a new variable y such that: y U ) _ ^ _ o U ) r ik lk p ik (U.13) then we can rewrite (k.12) as z v* (1- x ( , d) ) + z r^ } < u (l - p^) H=l ' 1=1 lk ~ k i+k Z v* (1 - rSp) + z r^ > 1 - U P^ 0=1 i=l >.1U) i+k k = 1, ..., R i = l, . . . , 8 Inequalities (U.lU) are the gate descriptive inequalities for AND gate. Equation (U.13) will be expressed as inequalities later. (k) Gate descriptive inequalities for NAND gate Weights and threshold of NAND gate are -l's and T = (sum of the weights of input connections and intercon- nections to gate k) + 1 25 3 k R k £ w* 4- Z a.+l (same w ' s and/or a ' s might be a n ." . - ik ik «=1 W 1=1 ik (^.15) if the corresponding v 's and ty., ' s are 0) 3 k R = - Z v. _ 2 \Jr + 1 (by relationship (^.4b)) i=l * i=l lk Substituting this threshold T into (k-,9) and again setting 7.7. .K IK. (4) ty., - : ~ . v r. , we obtain the gate descriptive inequalities for NAND gate as follows: o R Z v) (1 - x^) + Z 7^ > 1 - U (1 - P^ } ) 0=1 l i=l lk " k ilk Z v k (1 - x^) + Z yty < U p. (d) e=i * * i=i lk " k ilk k = 1, ..., R j = l, ..., 8 For the synthesis problem where the complemented inputs are available to a network, the gate descriptive inequalities is further modified by 3 ~k ( i ) simply adding the term Z v< (1 - Xi ) to the left hand side of our descrip- tive inequalities (^.8 and U.9). Here (1 - x ) stands for the complement of the external input variable x^ , and Vg, the connection between (l - x, ) and gate k. For example. AND gate descriptive inequalities can be written as: z v" *y + z v* (l - *y J ) + z p,.J' > i - u (l - p; 3) ) i=i l :=i l " i=i lk - k ik 26 ?L = -L ) » • • • K j = 1, . . . , 8 and OR gate descriptive inequalities can be written as: A v i 4 3) - A ; * C 1 - 4 3) > - A ^ > i - mi - i 3) ) i=l lo-± 1=1 i w Z v k £ xfK Z v*U-x[ i) )+ S P^ 1 < u f i)=k k = 1, ..., R j = 1, ..., 8 4.3.2.2 Input Value Inequalities The non- linear equation (U.9) p (j) = ^. k Pp) (U.16) i = 1, 2, ..., R, i J= k J = 1, 2, ..., 8 can be expressed as linear inequality forms < - 2 pfj" + t., + P. (^.17a) - lk lk i -, . o(d) p (j) - 1< P ik - P ± (4.i7b) i = 1, ■ . . , R, i )= k j = 1, . . . , 8 27 This can be proved as shown below: In (4.17) if one or both of ^ and P:*" are 0, then (4.17a) forces p;j^ to be 0; whereas if \|f and P:^ i lK IK X are both 1, then (4.17b) forces £.^ to be 1. This is just what equation IK (4. 16) represents. Whereas in (4.16) when 3.~/ = 1, it forces both ty and P:^ to be 1, and when 3 )}' = 0, then at least one of i|r and P.^ should 1 ' ik ' ik 1 be 0. By the same way the non- linear equation (4.13) ik ik p ik i = 1, . . . , R, i f k j = 1, . . . ; 8 can be expressed as linear inequalities: < *ik - 4k' - Ai ] (U.lB) < * + eg + rjj' i = 1, . . . , R, i f k We used (4.17) and (4.18) in our NOR, NOR-AND, and NOR- NAM) problems, and it worked, no problems at all. But when we solved AND-OR problem, we found that the number of the inequalities generated from the input value inequalities (4.17) and (4.18) is as many as 2304 (for R = 9). It took too much computation time to check through all of them. Furthermore, these in- equalities needed a very large memory space to store them. For these reasons, we gave up using (4.17) and (4.18) in the AND and OR problem and replaced 28 them by: p:, - 2i, + p)J'+ 2 7., > o ik lk i ik — - 3 ^P +3t, - P^ - U 7^ > (1+.19) xk ik i ik — ' - z p:^ + u p: j '^ > o i=l lk x - 4k i = 1, .o., R j = 1, . . . , 8 The number of inequalities generated from ( 1 +.19) is 122U (R = 9), which is about half the number generated from (^.17) and (^.18). U.3.2.3 Mixed-Gate Network A mixed-gate network is difined as a network in which different types of gates can be used. In this report we only consider the mixed-gate net- works with two different kinds of gate types (e.g., NOR and AND, NOR and NAND and AND and OR). The type of each gate k inside a network will be identified by a new type variable \. (if more than two kinds of gates are used in one network, we can use more type variables to distinguish one type from another). The value of \ can be either 1 or 0. Thus after solving k the problem, from the value of \ , we will imow what type gate k represents in the network. Variable \ is added in the gate descriptive inequalities. The way of adding A. to gate descriptive inequalities will be explained K. in the following example: In a network of a mixture of NOR gates and AND gates, if we let 29 ^ = 1 imply that the gate k is a NOR gate and X = implies that gate k is an AND gate, then the gate descriptive inequalities for these two types of gates can be rewritten as: o R Z vj xl j) + Z (3^ < + U (1 - F^h + U (1 - \) £=1 * Z i=l ^ x K O IS Z v* x^ + z (3^ > 1 - U Pp) - U (1 - ^) i=l i=l and (1+.20) n R Z v* (1 - x^ } ) + L 7^ < U (1 - Pp' } ) + U ^ /(/ — J_ -L — -L Z v* (1 - xp } ) + Z 7^ } > 1 - U p£ J) - U \ £=1 i=l k = 1, . .. , R j = 1, . . . , 8 When X = 1, then obviously the last two inequalities of (U.20) become non- restrictive and the first two are the gate descriptive inequalities of NOR gate (see equation (U.ll)). When K = 0, the first two become non- restrictive and the last two are the gate descriptive inequalities which specify AND gate (see equation (k.lh)). J-i-. 3 » 3 Additional Inequalities Our implicit enumeration algorithm has a tendency that the smaller the region of all solutions, the faster the covergence. Hence our effort was directed to preclude unnecessary solutions by adding extra inequalities 30 so that the solution region becomes smaller without eliminating any nec- essary optimum solutions. In other words, we add more constrains so that solutions which are obviously not optimal or those which can be easily ob- tained from other solutions by permuting variables, are suppressed. The constraints which are used in our problems will be given in the following (some of them were discussed in [11]): (l) Output Condition (used in all of our h problems) Each gate, except the output gates (gates 1 and 2), has at least one output connection connected to other gates. Otherwise, this gate becomes meaningless and thus can be deleted from network. Inequalities for this condition is: R Z a.. > 1 k=l lk " (U.21) 4i i = 3> . . . , R (2) General Triangular Condition (i) For NOR, NOR-ANL and NOR-NAND problems: Suppose that three gates are connected as shown in Fig. h**?. Gate j has no output connections connected to other gates except gate k. (no other output connections) Figure h.^ Triangular condition (a) 31 It is easily proved that if all the interconnections \|r. ., ^- V f ty are 1, the network is not optimal, thus introducing inequalities: Jk *« + *ik + V^ 2 + t z . *jt (1 *- 22) i, j, k = 1, ..., R i I s J, J !=k, i |=k Even if the i-th gate in Fig. 4.5 is replaced by an external variable x- (i = 1, 2, 3), the above property is still true. Then from (4.22) we obtain 1= It, 3 } k = 1^ • • • j R i - 1, 2, 3 (ii) For AKD-OR problem: If three gates are connected as shown in Fig. 4.6, then the net- work is not optimal if t. ., i r . 1 and \|r are all 1. Therefore, the ij 1 k jk following inequalities should be added as a constraint: i |= j, i ^ k, J J= k i, j, k = 1, ..., R Even if we replace gate j by an external input x* (i = 1, 2, 3)> the above property is still true. 32 So we have V i +V i + *jk2 2 1 + k, 3 > k = 1, . . . } R I = 1, 2, 3 (U.25) (even with other connections) (gates i, j, k can be either AMD gates or OR gates) Figure h.6 Triangular Condition (b) - for AND-OR problem only (3) Input Restriction Inequalities These inequalities give the restriction to the inputs of gates. Since they are different for different problems, let us discuss them separately. 33 (i) In all NOR gate one-bit adder network problem: Each gate, except the output gates, has at least one connection or two interconnections 3 k R 2 L v + L t., > 2 (1+.26) 4=1 l i=l 1K ik k = 3 > • • • ) R 4 = 1, 2, 3 (ii) In NOR and AND one-bit adder mixed-gate network problem: There is at least one input to the NOR gate and two inputs to the AND gate 3 R L v) + L * +\ >2 (4.27) 4=1 * i=l lk k i^k k = 1, . . . , R (iii) In NOR and NAND one-bit adder mixed-gate network problem: There is at least one input to each gate. If there is only one input, then no matter what type the gate is, the output is always the complement of the input. When this case happens, we can restrict the gate to be a NOR gate. Inequalities for this restriction can be written as: 1=1 l i=l lk k ifk k = 1 , ..., R (iv) In AND and OR one-bit adder mixed-gate network problem: There are at least two inputs to each gate 3h 3 k 3 "k R Z Vo + Z v, + Z V... > 2 i=l ^ i=l A i=l lk " M* k = 1, ., R (4.29) (h) Extensive Triangular Condition (i) In NOR and AND one-bit adder mixed-gate network problem: If three gates are connected as shown in Fig. 4.7 Can have other out- put connections (at least one of gate j and gate k must be AND gate) Figure 4.7 Extensive triangular condition for NOR and AND mixed-gate network problem. If gate k, gate j or both are AND gates, then the general triangu- lar condition still holds even if gate j has other output connections. Therefore: 35 T|r., + t. . + \[f .. < 2 + *-. lk ij jk - j *ik + *« + V < 2 + \ (U.30) -*-> <] > k - 1, • • • > R i i= j, i j= k, j )= k Replacing gate i by an external input x«: v i + v * + v * 2 + ^ v i + v x + v * 2 + \ (MD j, k = 1, . .. , R 3 t k M, 2, 3 (ii) In NOR and NAM) one-bit adder mixed-gate network problem: Three gates are connected as shown in Fig. k.Q other output connections (if gate j is NOR, then gate k is HAND and vice versa) Fig. k.Q Extensive triangular condition for NOR-NAND mixed-gate net- work problem. 36 If gate j is a NOR gate and gate k is NAND or vice versa, then the general triangular condition still holds even if gate j has other output connections. Therefore: *u + * ik + v^ 2 + (i - V + \ *« + *ik + V < 2 + ^ + & - V (^.32) (fc-33) i (= j, i 1= k, j ): k Replacing gate i by an external input x : v " + *i + V s 2 + x j + (l ■ V j , k = 1, . . . , B i = 1, 2, 3 (5) Other Conditions (used in the AND and OR mixed-gate network problem) The following two conditions are only used in the AND and OR mixed-gate network problem: (i) Suppose gate i feeds gate k, if they are of the same type (both are AND gates or OR gates). Then gate i must feed at least one gate other than gate k. Otherwise, this is not optimal because if we de- lete gate i from the network and simply connect the input connections 37 of it directly to gate k, the output of gate k does not change at all (this is explained in Fig. U.9). (no other out- put connections) (gate i and gate k are of same type ) equivalent inputs of gate i) Figure k.$ This restriction can "be expressed as: R L * > 1 - K - \ - (1 - f ) jfck R i Vl . >i- ci-v- (i- V- 1 - * ik ) (h.3h) i f k = X, . . . , R i U The first inequalities of (^.3*0 prohibit both gate i and gate j to be AND gates, and the second one prohibits them to be all OR gates, (ii) At least one AND gate and one OR gate is desired in our network. 38 Thus (k.35) R 2 *-. > 1 i=l 1_ R Z *>. < R - 1 i=l X " 4.4 Self- Dual Function In this section, we will discuss a special kind of logic function named self-dual function and explain how to make use of the properties of self- dual function in some of our mixed-gate network problems. At first, we will introduce the dual function of a switching function. A dual function f (x) of a switching function f(x) is defined as f(x). If for a function f(x), its dual function f (x) turns out to be the function itself (i.e., f(x) = f (x))rthen function f(x) is called a self-dual function. Now let us go back to our majority function (carry) and odd parity function (sum) for the one-bit adder. In Section 2, the majority function was given as: C = ab + be + ca The dual function of it is: C d = (a+b) (b+c) (c+a) = abc + ab + be + ca = ab(c-fl) + be + ca = ab + be + ca = C 39 Also the odd parity function was given as: S = abc 4- abc 4- abc + abc The dual function S is S = (a + b 4- c) (a + b + c) (a 4- b + c) (a + b 4- c) = (ab + ac 4- ab + b + be 4- ac 4- be) (ab 4- ac + ab 4- b + be 4- ac 4- be) = (ac 4- ac + b) (ac 4- ac 4- b) = abc 4- abc + abc 4- abc = S Thus both the majority function and the odd parity function are self- dual functions. The properties of the self-dual function can be made use of for solving our AND-OR and NAND-NOR mixed-gate one-bit adder network problems to reduce the computation time. For, once we get half the optimal networks, then by applying the self-dual properties of the majority function and the odd pa- rity function, the other half of optimal networks can be easily obtained by only interchanging the gate types in the optimal networks we already have. The restrictions that the first gate (in a network) must be an OR gate and NOR gate are added into the AND and OR and the NAND and NOR mixed-gate problems, respectively. Thus both problems result in the optimal network with their first gates, the OR gate and the NOR gate, respectively. By inter- changing gate types, we can get the other optimal networks (with their first gates the AND gate and the NAND gate) by ourselves, thus greatly saving computation time. ko SECTION 5 PROCEDURE FOR DESIGNING AN OPTIMAL NETWORK To design an optimal network, we need first to minimize the number of gates. Then, under this minimized number of gates, minimize the number of connections and interconnections. The procedure for designing an optimal network is discribed as follows: (1) Set R =1 (If we know a lower bound of the number of gates re- quired for realizing the given switching functions by some other means, set R to this number). (2) Formulate a set of inequalities for a R gate all- interconnect ion network and possible inequalities corresponding to the restrictions imposed (mentioned in the previous section). Solve this problem, minimizing the number of connections and interconnections, by using the implicit enumeration algorithm of integer linear programming. If this has a solution, it is an optimal solution, so stop. Otherwise, go to step (3). (3) Increase R by 1 and return to step (2). The whole procedure will terminate in a finite number of steps if the problem is feasible for some R. in SECTION 6 COMPUTATIONAL RESULTS Our four one-bit adder network synthesis is: problems have been solved. All the computations were done on IBM/75 I» Results of these problems such as the computation time spent on each problem, the number of iterations, the number of optimal networks obtained in each problem, the number of gates and the number of connections and interconnections, etc., are given in Table 6.1 through 6.3. Also pictures of all the optimal networks are given after these tables. k2 w CD •H -P ■H H cd o d Sh a 1 QJ N C 1 H PO o H oo c co OJ CM CX) o c VO VO LT\ VO S -H *\ •s *» *\ OA H t- on

CX) a\ ,£> o\ ON -3" in . CO UA c— o oo O -H •s •\ 5 fn H H CD > S S S W CD CD CD 6 H H H CD S rQ & o ,g H CD P o ft O £> H S ^ < u O ^ O ,P < ft ft ft , ft ^H O d ft ft fn T3 CD d CD £ CO H H OJ VD £ H s g -p £ w

LTN LTN •H so VD t- CO U P On ON Q\ On d) cd •\ •\ »\ •\ ,£> h OJ H H _=r g w H t— 3 p S M g rH H H 0) g ,Q 8 -° & H 0) < ft s o S P ,0 H ^ ^ O fn O P S ft _ ft H O >d ft « ^H T3 0) t3 0) C 0) O ft 9 "S C P cd P Oh s S cd a) O OJ bO bD H AND pro K O ■8 H < 5h O Sh ,0 S ft ^ p fc CD d ft « !h d CD T3 CD Pi O ft Pi -P C -P cd -p ft J35 co cO co co CO o CD bQ So 8 M § d w P> CO w 2 o d PC I o -d CD M S CD X •H S CD CD X •H a 6 e S 0J M U | fH £ CD p -P a> d Pi •H H to a) S3 S iH •H P> -P ft CJ O CD a *H a CD o «d C) Ti CO

CO -p C CO bf ■H -P ft O O cu • g o S a m vo CD H P CO H h5 OR AND r> NOR NAND Table G.h Gate representations k6 3E w « bO g .d -P •H (D tJ b3 -P •H ^5 I TJ -P ■H -Q I - cr < o AAA « ■H 03 -P cQ O w ■s . •H P fc S -H T3 W C ctf -P K M O A A u A +3 (J o 5 O -P x: o -p (3 •H • l>J vo ,o A o n •H O .Q 50 2 if) < w 0) 13 ho K O 1 -P ■a •p a; u 0) •s ■p ■H rQ I 8 o VD - cr < h £ o O t) 52 c— h p M •H Fn A 53 2 if) r\ 5U w ■8 W o -a 9 •p •H ■a g -p e h CD •s -p i CD c o •H r^ JQ O 55 ON +2 • cd VD bO (X bO O -H cd -H w CD bO u S O cd £ „ 0) s a < CD & Ti -P Cd g, -P -H •H bD i cd CD 43 O O CD 3 CD & c •H -H Pn cd +3 O JD O (O 56 6 w o faD o •*\ 6 6 6 10 1-0 O |u -Q o I 43 H (D T3 in 0) bD -H ■H n5 fe -P ,Q O o o 62 1 6 r^\ r\ J3 O " w O s £ +3 c - cr cr < Q 6 6 6 6 6 -C o Q /"\ W H -P MD a bO • O Pn 3 •H U P 0) -P s i !p •H -P •H 0) o O CO -H H VD ,0 0) Td hD -H •H ctf fe -p 42 O IO |0 ° o 6k (/) l-O IO W -8 O 1 J2 -P U I fi Ih QJ •p •H 66 REFERENCES [1] E. Balas, "An additive algorithm for solving linear problems with zero-one variables/' Operations Research , vol. 13, no. k, pp. 517- 5^+9, July-August I965. [2] B. Fleischman, "Computational experience with the algorithm of Balas," Operations Research , vol. 15, no. 1, pp. 153-155, January-February 19^ [3] F. Glover, "A multiphase- dual algorithm for the zero-one integer programming problem/' Operations Research , vol. 13, no. 6, pp. 879- 919, November-December 1965. [k] E. S. Davidson, "An algorithm for NAND decompositional switching function," Fh.D dissertation, Department of Electrical Engineering and Coordinated Science Laboratory, University of Illinois, 1968. [5] L. Hellerman, "A catalog of three-variable OR-invert AND- invert logical circuits," IEEETEC, vol. EC- 12, no. 3, pp. 198-223, June I963. [6] A. M. G-eoffrion, "Integer programming by implicit enumeration and Balas' method," SIAM Review , vol. 9, no. 2, pp. I78-I9O, April 1967. [7] S. Muroga and T. Ibaraki, "Logical design of an optimum network by integer linear programming - Part I," Report No. 264, Department of Computer Science, University of Illinois, July 1968. [8] 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. [9] T. Ibaraki, T. K. Liu, C. R. Baugh and S. Muroga, "Implicit enumeration program for zero-one integer programming," Report No. 305, Department of Computer Science, University of Illinois, January 1909. [10] T. K. Liu, "A code for zero-one integer linear programming by im- plicit enumeration," Report No. 302, Master thesis, Department of Computer Science, University of Illinois, 1968. [11] C. R. Baugh, T. Ibaraki, T. K. Liu and S. Muroga, "Optimum network design using NOR and NOR-AND gates by integer programming," Report No. 293, Department of Computer Science, University of Illinois, January 1969* NtM 2 i\97e