510.84 
 
 ■ 
 
 l?6r 
 
 ILLINOIS UNIVERSITY DEPARTMENT 
 
 no. 841 
 
 OF COMPUTER SCIENCE 
 
 cop. 2 
 
 
 
 REPORT 
 
UNIVERSITY OF 
 
 ILLINOIS LIBRARY 
 
 AT URBANA-CHAM^AlGN 
 
 The person charging this material is re- 
 sponsible for its return to the library from 
 which it was withdrawn on or before the 
 Latest Date stamped below. 
 
 Theft, mutilation, and underlining of books are reasons 
 for disciplinary action and may result in dismissal from 
 the University. 
 To renew call Telephone Center, 333-8400 
 
 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN 
 
 FEB i 2 RKU 
 
 L161— 0-10% 
 
uiucDCS-R-76-8i+i 
 
 
 7* 
 
 NOR NETWORK TRANSDUCTION PROCEDURES BASED ON CONNECTABLE 
 
 AND DISCONNECTABLE CONDITIONS 
 (Principles of NOR Network Transduction Programs NETTRA-Gl 
 
 and NETTRA-G2) 
 
 by 
 
 Y. Kambayashi and J. N. Culliney 
 
 December, 1976 
 
 DEPARTMENT OF COMPUTER SCIENCE 
 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 
 
 URBANA, ILLINOIS 
 
« 
 
UIUCDCS-R-76-841 
 
 NOR NETWORK TRANSDUCTION PROCEDURES BASED ON CONNECTABLE 
 
 AND DISCONNECTABLE CONDITIONS 
 (Principles of NOR Network Transduction Programs NETTRA-G1 
 
 and NETTRA-G2) 
 
 by 
 
 Y. Kambayashi 
 J. N. Culliney 
 
 December, 1976 
 
 Department of Computer Science 
 
 University of Illinois at Urbana-Champaign 
 
 Urbana, Illinois 6l801 
 
 This work was supported in part by the National Science Foundation under 
 Grant No. DCRTS-OS 1 ^!. 
 
Digitized by the Internet Archive 
 
 in 2013 
 
 http://archive.org/details/nornetworktransd841kamb 
 
iii 
 
 ACKNOWLEDGMENT 
 
 The authors are grateful to Professor S. Muroga for 
 his guidance and careful reading of this report. The authors 
 would like to thank Dr. H.C. Lai for his valuable discussions 
 throughout the period of this research, and Mrs. Ruby Taylor 
 for typing it. 
 
IV 
 
 TABLE OF CONTENTS 
 
 1. INTRODUCTION 1 
 
 2. BASIC PROCEDURE 3 
 
 3. NOR NETWORK TRANSDUCTION PROCEDURE BASED ON 
 
 CONNECTABLE AND DISCONNECTABLE CONDITIONS 13 
 
 4. MODIFICATION OF THE NETWORK TRANSDUCTION 
 
 PROCEDURE 
 
 5. COMPUTER PROGRAMS AND EXPERIMENTS 36 
 
 5.1 A Program Realizing Procedure NTCD 
 
 49 
 
 5.2 A Program Realizing Procedure NTCDG 
 
 5.3 Comparison of the Programmed Procedures NTCD and NTCDG. . 54 
 
 6. CONCLUDING REMARKS 62 
 
 References 63 
 
1. INTRODUCTION 
 
 Based on the concept of compatible sets of permissible functions 
 (CSPF's) discussed in a previous paper, [5], network transduction (trans- 
 formation and r eduction ) procedures have been developed to derive simplified 
 networks from given feed-forward multiple-output networks of NOR gates. In 
 this paper, one of the major categories of transduction procedures is dis- 
 cussed. Unlike the pruning procedures discussed in [3] which are unable to 
 create new connections, transduction procedures of this category are able 
 to make new connections among gates (or external variables) . 
 
 First, conditions for the connectability and disconnectability of 
 a connection from a NOR gate (or external variable) to another NOR gate are 
 established. Based on these conditions, a basic transduction procedure is 
 proposed which essentially deals with only a single gate of a given network 
 (although others may be affected as a consequence). From this, a more sophis- 
 ticated transduction procedure is developed by adapting the basic procedure 
 for efficient repetitive application. This procedure attempts to enable the 
 removal of connections and gates throughout the network. A third transduc- 
 tion procedure is created from the second by causing it to focus upon the re- 
 moval of a specific gate. 
 
 In the transductions, various orderings of gates are employed which 
 define their priorities during the performance of various operations. Since 
 these orderings affect the efficiency of the procedures, the choice of ap- 
 propriate orderings is discussed. 
 
 Computer program implementations, designated NETTRA-G1 and NETTRA-G2, 
 were written in FORTRAN IV for the two transduction procedures other than the 
 basic procedure. (A reference manual, [2], is available for users of the 
 programs.) Some modifications are discussed which were made of the original 
 
procedures in the interest of computational efficiency. Then, computational 
 results by these programs are presented. 
 
 Modifications of the two programs have been made which allow them 
 to perform network transduction under fan- in, fan-out, and level restrictions. 
 The corresponding alterations of the programs will be discussed elsewhere. 
 
 The notations and basic concepts defined in [5] will be used through- 
 out this paper. 
 
 Let W be the total number of connections except connections from 
 output terminals. The cost of a network is represented by 
 
 AR + BW. 
 
 Here, A and B are cost coefficients. In this paper A = 100 and 
 B = 1 are chosen. Therefore, the reduction of the number of NOR gates is 
 more important than the reduction of the number of connections. 
 
2. BASIC PROCEDURE 
 
 In this section, a basic network transduction procedure based on 
 connectable and disconnectable conditions is developed. More advanced 
 transduction procedures are discussed in succeeding sections. 
 
 f 
 Definition 2.1 A gate or an input terminal , v., is said to be 
 
 connectable to a gate v. with respect to a set of permissible functions of v., 
 
 G(v.), if (1) the output function of v. remains in G(v.) after adding con- 
 3 3 3 
 
 nection c.., and (2) the network obtained after this input addition is loop- 
 free. 
 
 Definition 2.2 Connection c. is said to be disconnectable from 
 ij 
 
 a gate v. with respect to a set of permissible functions of v., G(v.), if 
 
 the output function of v. remains in G(v.) after removing c.. from the net- 
 
 3 3 iJ 
 
 work. 
 
 The following two theorems are bases of the transduction procedures 
 to be developed. The proofs are obvious. 
 
 [51* 
 Theorem 2.1 A gate or an input terminal, v., is connectable 
 
 to a gate, v., with respect to set G(v.) if and only if the following condi- 
 tions are satisfied: 
 
 (1) For all d such that f (d) (v.) = 1, 
 
 G (d) (v.) = or *. 
 3 
 
 where f (v.) is the d-th component of the output vector of 
 gate v. . 
 
 tThe concept of "input terminals" was introduced in [5] to simplify notational 
 expressions in the many cases where equivalent treatment of gates and external 
 variables is necessary. Since in this paper only non-complemented variables 
 are assumed to be available to the network, the terms "input terminals" and 
 "external variables" can be considered interchangeable. 
 
 ^Theorem 5.3 in [5]. 
 
(2) v. is not contained in S(v.) where S(v.) denotes the set of 
 1 J J 
 
 successor gates of gate v.. 
 
 [5] + 
 Theo rem 2.2 Connection c.. is disconnectable from gate v. 
 ij 6 J 
 
 with respect to set G(v.) if and only if the following condition is satis- 
 fied: For all d such that f (v.) = 1, either: 
 
 G (d) ( v .) = * or 
 J 
 
 V f(d) w - 1 
 
 veIP(v.) 
 
 v^v. J 
 
 1 
 
 where IP (v.) denotes the set of all immediate predecessor gates of gate v.. 
 
 (Note that in both theorems, v. may be an external variable. In 
 
 . e , Ad) . (d) , 
 such a case, f(v) is x .) 
 
 Definition 2.3 K(v.), the set of connectable functions to gate v. 
 
 J J 
 
 with respect to G(v.) is the set of all functions such that the function 
 
 realized by v. remains in G(v.) after adding any one of the functions as an 
 
 input of v. . 
 J 
 
 Lemma 2.1 The set K(v ) of all connectable functions to a gate v. 
 
 J J 
 
 with respect to G(v.) is given, in vector representation, by: 
 
 K (d) (v ) = for all d such that G (d) (v.) = 1, and 
 J J 
 
 K (d) ( v .) = * for all other d's. 
 J 
 
 Lemma 2.2 If the functions in any subset of K(v.) are added simul- 
 
 J 
 
 taneously as inputs to gate v., the resulting function realized by v. remains 
 in G(v.) . 
 
 Clearly, if f (v . ) is in K(v.) and v. i S (v . ) , v. is connectable to 
 
 tLemma 4.1 in [5] 
 
v, with respect to G(v,). 
 
 Definition 2.4 Let Q(v.) denote the set of all input terminals 
 
 and gates which are connectable to v. with respect to G(v.). Input term- 
 j j 
 
 inal or gate v in Q(v.) is said to be an essential input of v. with re- 
 spect to G(v.) if gate v. with input connections from all elements in 
 (Q(v.) - {v.}} realizes a function not contained in G(v.). Let Q (v.) denote 
 the set of all input terminals and gates which are essential inputs of v 
 with respect to G(v.). A v. in Q(v.) which is not an essential input with respect to 
 
 G(v ) (i.e., not in Q (v ) ) is called a non-essential input with respect to G(v.). 
 J o J J 
 
 If v. is an essential input of v. with respect to G(v.), a connec- 
 i 3 3 
 
 tion from v. to v. is necessary to maintain an output function of v. within 
 G(v.). 
 
 Lemma 2 . 3 Input terminal or gate v. in Q(v.) is an essential input 
 of v. with respect to G(v.) if and only if there exists at least one d such 
 
 that: 
 
 G (d) (v.) = 0, f (d) (v.) = 1, and \/ f (d) (v) = 0. 
 
 V£Q(V.) 
 
 Definition 2.5 The component f (v.)(=l) for each d for which the 
 
 condition in Lemma 2.3 holds is said to be an essential 1 , with respect to 
 
 G(v.), of the essential input v. of v.. 
 3 i 3 
 
 Note that an input terminal or gate v. is an essential input to a 
 
 gate v. with respect to G(v.) if and only if the vector representation of f(v.) 
 
 + 
 contains essential l's with respect to G(v.). 
 
 tNote that while K(v.) has a vector representation, set Q(v.) does not. 
 
 -J J 
 
 * The qualifying phrase "with respect to G(v.)" may sometimes be omitted when 
 it is clear from the context of the discussion. 
 
Definition 2.6 If there exists an input v. of a gate v. and a d 
 
 such that: 
 
 G (d) (v.) = and f (d) (v.) = 1, 
 J i 
 
 then v. is said to cover G (v.), either or both of v. and f ( v ^) mav be 
 referred to as a cover of G (v.), and G is said to be covered . 
 
 A basic network transduction procedure based on the preceding con- 
 cepts is as follows: 
 
 Procedure 2.1 [Procedure RI ] (a procedure to Replace Inputs of 
 a particular gate v..) 
 
 (1) Select a particular gate v. in a given network. 
 
 (2) Calculate a set of permissible functions, G(v.), for v.. (A compatible 
 set of permissible functions, G (v.) may be used.) 
 
 (3) Calculate a set K(v.) of connectable functions with respect to G(v.). 
 
 J 3 
 
 (4) Calculate the set Q(v.) of connectable input terminals and gates with 
 respect to G(v. ) . 
 
 (5) Calculate the subset Q (v.) of all essential inputs in Q(v.). 
 
 (6) Select a subset, Q', of Q(v.) satisfying: 
 
 W - Q ' - Q( V' 
 
 /\f(v) e G(v ). 
 
 veQ f J 
 
 (7) Let the new set of inputs for v. be Q', resulting in a modified network. 
 Calculate CSPF's for this network, individually removing (redundant) con- 
 nections satisfying the conditions for disconnectability (see Theorem 
 2.2). 
 
 (8) If the network obtained after Step (7) is of less cost than the original, 
 or if all possible subsets Q' have been exhausted in Step (6), terminate 
 the procedure. Otherwise, restore the original network, return to Step 
 
(6), and select a new Q' not previously chosen. 
 
 The following example demonstrates the use of Procedure RI. 
 
 Example 2.1 Fig. 2.1 shows a network which realizes the function 
 f = x x x 2 v x^ -x^. 
 
 Functions realized at the input terminals and gates are as follows: 
 
 f(v ) = x = (0 1111) 
 
 f(v 2 ) =x =(0 011 11) 
 
 f(v ) = x = (0 1 1 10 1) 
 
 f(v 4 ) =(1011 010 0) 
 
 f(v ) = (0 000 0011) 
 
 f(v,) =(0 000 1010) 
 
 f(v ) =(0 100 000 0) 
 
 f(v_) =(1100 110 0) 
 o 
 
 f(v ) = (1111 000 0) 
 f(v 1Q ) =(1010 1010) 
 Fig. 2.2. (a) shows the same network; the illustration, however, is 
 simplified due to the omission of input terminals. 
 
 (1) Gate v_ is selected. 
 
 o 
 
 (2) G (v ) is calculated as follows (see [5] for general procedure). 
 
 c o 
 
 First, G (v_) is calculated from G (v,). 
 c 5 c 4 
 
 G c (v 4 ) = f(v ) =(1011 010 0), 
 
 f(v 6 ) v/ f(v ) =(0 100 1010), 
 
 f(v 5 ) =(0 000 0011), 
 
 G c (v 5 ) =(0*00 *0*1). 
 
 For all d such that G^ d) (v ) = 1, G^ (d) (v.) = 0. For all d such that 
 
 tlnput terminals are omitted in all succeeding network illustrations for 
 simplicity. 
 
8 
 
 v l 
 
 "2 
 
 v. 
 
 V 
 
 10 
 
 V/ 
 
 Fig. 2.1 Given network for f in Example 2.1. 
 
G (d) (v ) = 1, G (d) (v c ) = 0. For all d such that G (d) (v.) = and 
 
 c 4 c 5 c ^ 
 
 f^(v ) v f^ d \v ) = 0, G^(v ) = 1 (necessary to assume 
 
 f (d) (v,) = 0). For all other d, G (d) ( Vt .) = *. Similarly, G (v ) 
 4 CD co 
 
 is calculated using G (v c ) , f(v n ), and f(v Q ). 
 
 c D y o 
 
 G (v ) = (**** * 1 * 0). 
 c 
 
 (3) The set, K(v Q ), of connectable functions to v is simply determined. 
 
 o o 
 
 K( v )=(*** * * * *) . 
 8 
 
 (6 ) 
 
 (4) The following v. are found to satisfy f (v.) = 0: 
 
 i l 
 
 v 2 , v y v 6 , v ? , v 9 , and v^. 
 Since all except v satisfy v. t S(v_), 
 
 J 1 o 
 
 Q(v g ) = {v 2 , v 6 , v 7 , v 9 , v 1Q }. 
 
 (5) Of the elements of Q(v ), only v„ is an essential input to v Q with re- 
 
 spect to G (v „) since 
 c 8 
 
 G (8) (v 8 ) = 0, fW( V =l,and\A (8) (v)=0. 
 8 2 veQ(v 8 ) 
 
 Wv 2 
 
 Thus 
 
 Q (v.) = {v 9 }. 
 
 (6) Let Q' be {v ,v }. A new connection is added from v to v (see Fig. 
 
 2. D bo 
 
 2.2(b)). 
 
 (7) During the calculation of CSPF's, the connection from v, to v. is re- 
 
 b 4 
 
 moved. Since 
 
 G (v.) = f(v.) = (1 1 1 10 0), 
 
 c 4 4 
 
 f(v ) = (0 000 1011), 
 
 f(v,) = (0 000 1010), 
 b 
 
 f(v ? ) =(0 100 000 0), 
 connection c clearly satisfies the condition for disconnectability 
 (Theorem 2.2) and can be removed as shown in Fig. 2.2(c). 
 Continuing the calculation of CSPF's, connection c Q A is also found to 
 
10 
 
 Vt 
 
 V/ 
 
 '10 
 
 x. 
 
 x. 
 
 (a) Initial network. 
 
 '10 
 
 v^ 
 
 1 
 
 -J. f 
 
 (b) Network after choice of Q' = (v 2 ,Vg) for Vg. 
 
 (c) Network after removal of c^ ^. 
 
 Fig. 2.2 Example for Procedure RI. 
 
11 
 
 X-, 
 
 V 
 
 10 
 
 V. 
 
 X, 
 
 (d) Network after removal of Cq £. 
 
 ^3 
 
 x 2 A 
 
 x_ 
 
 X, 
 
 x,. 
 
 > f 
 
 (e) Final network, v, Q removed. 
 
 Fig. 2.2 (cont.) Example for Procedure RI. 
 
12 
 
 be removable after determining G (v ) : 
 
 c 6 
 
 G (v ) = (**** 10**), 
 
 f(v ) = (0 101 010 1), 
 
 f(v ) =(1111 000 0). 
 
 After the removal of c , , the outputs of v and v in the resulting 
 
 network (Fig. 2. 2 (d)) have obviously become identical. Consequently, 
 
 V is replaced by v to produce a final network with one less gate 
 10 6 
 
 (see Fig. 2.2(e)). 
 (8) The cost of the original network was 713. Since the cost of the final 
 network has been reduced to 611, the procedure terminates. 
 
 This same result could be achieved by choosing Q 1 = {v v -, n } i n Step 
 6. 
 
13 
 
 3. NOR NETWORK TRANSDUCTION PROCEDURE BASED ON CONNECTABLE 
 AND DISCONNECTABLE CONDITIONS 
 
 In this section, an efficient network transduction procedure is de- 
 veloped based on Procedure RI of the previous section. In Procedure RI there 
 are many possible choices in Step (1) (selection of the particular gate for 
 the procedure) and Step (6) (selection of a new input set for the gate) . In 
 order to find the best possible result obtainable by a series of applications 
 of the procedure, an impractical number of combinations of these choices must 
 be exhausted. For this reason, an efficient method for the repetitive ap- 
 plication of the procedure is desirable. In this section, such a procedure 
 using a preference ordering is given. This procedure allows connections and 
 disconnections of connections to be made throughout the network without the 
 necessity of recalculating the CSPF's each time. Also, upon termination of 
 the procedure, CSPF's are known for all gates, enabling other transduction 
 procedures to be applied for possible further reduction. 
 
 An example is given to explain the procedure. 
 
 Example 3.1 Fig. 3.1(a) shows a network which realizes the fol- 
 lowing 4-variable function f: 
 
 f = x.x x. s/ x.x„ \/ x.x„ v x n x. v x_x. . 
 134 12 13 14 34 
 
 This network is the first solution found during a logical design by a Branch- 
 
 and-Bound method ' for function f. 
 
 Let an ordering r be defined as follows: 
 
 r(v.) = i-4 for i, 5 <_ i <_ 14 (gates) 
 
 r(v.) = i+10 for i, 1 <^ i _< 4 (input terminals). 
 
 When an input set for a gate is determined, the use of v. with larger r(v.) 
 
 is preferred (thus, input terminals are most preferred). 
 
14 
 
 The functions realized at gates and input terminals are as follows; 
 
 f(v i ) =x 1 = (° 000 0000 1111 1111) 
 
 f (v ) =x 2 =(0 000 1111 0000 1111) 
 
 f(v 3 ) - x = (0 1 1 0011 0011 0011) 
 
 f(v 4 ) = x = (0 1 1 0101 0101 010 1) 
 
 f(v 5 ) =(1110 1110 1111 100 1) 
 
 f(v 6 ) = (0 000 0000 0000 0010) 
 
 f(v ) =(0 000 0000 0000 010 0) 
 
 f(v 8 ) = (0 001 0001 0000 000 0) 
 
 f(v g ) =(1000 1000 1000 100 0) 
 
 f(v 1Q ) = (1111 0000 1111 000 0) 
 
 f(v n ) = ( 1110 1110 0000 000 0) 
 
 f(v 12 ) = (0 001 0001 0001 000 1) 
 
 f(v 13 ) =(1010 1010 1010 1010) 
 
 f(v 14 ) = (1100 1100 1100 110 0). 
 
 CSPF's for gates v_, v., v 7) and v are as follows: 
 
 jo/ o 
 
 G c (v 5 ) = (1110 1110 1111 100 1), 
 
 G (v.) = (0 00* 000* 0000 0*10), 
 c o 
 
 G c (v ? ) = (0 00* 000* 0000 1*0), 
 G c (v g ) =(0 001 0001 0000 0**0). 
 
 Sets of connectable functions with respect to these CSPF's are: 
 K(v ) = (0 00* 000* 0000 0**0), 
 K(v )=(**** **** **** **o*) 
 K(v ) = (**** **** **** *o**) 
 K(v ) = (***0 ***0 **** ****). 
 
 These sets are used in the next few steps to transform the network. 
 
 There are no gates or input terminals connectable to v other than 
 the three gates, v , v , and v fi , already connected. 
 
15 
 
 v 
 
 13 
 
 v 
 
 Ik 
 
 V 
 
 12 
 
 v. 
 
 V 
 
 10 
 
 x, 
 
 V 
 
 11 
 
 ;=i 
 
 v f 
 
 X. 
 
 v r 
 
 (a) Given network. 
 
 (b) Network after replacement of input set for v^. 
 
 v 
 
 13 
 
 v 
 
 Ik 
 
 V, 
 
 Xi 
 
 V 
 
 1Q 
 
 X, 
 
 7 
 3 — x 
 
 v 
 
 12 
 
 v, 
 
 11 
 
 X, 
 
 \ 
 
 V<- 
 
 (c) Network after replacement of input set for v . 
 
 Fig. 3.1 Networks for Example 3.1. 
 
16 
 
 (d) Network after replacement of input set for Vn. 
 
 v 
 
 10 
 
 X, 
 
 V 
 
 11 
 
 V 
 
 13 
 
 V 
 
 Ik 
 
 x. 6 
 
 X, 
 
 v f 
 
 X. 
 
 v r 
 
 (e) Final network — after replacement of input set for v 
 
 11' 
 
 Fig. 3*1 (cont. ) Networks for Example 3«1« 
 
Considering v & , though, v^ , v ? , v g , v g , v 1Q , v^, v 12 , and v 
 
 17 
 
 14 
 
 are all connectable to it. Furthermore, v 10 and v.. 1 are essential inputs 
 since: 
 
 f (11) (v 1() ) = 1, f (11) ( Vi )= for i = 4,7,8,9,11,12,14; 
 
 f (7) (v 1;L ) = 1, f (7) ( Vi )= for i = 4,7,8,9,10,12,14. 
 
 There are no other essential inputs to v,. Since: 
 
 6 
 
 f(v ) v f ( v ) =(1111 1110 1111 000 0) and 
 
 G (vj = (000* 000* 0000 0*10), 
 c 6 
 
 in order to realize a function in G (v^) an additional function is needed 
 
 c 6 
 
 from the set 
 
 (**** * * * * **** 1*0 1). 
 
 The function 
 
 f(v.) v f(v.,) = (1 1 1 1101 1101 110 1) 
 4 14 
 
 is in the set, and the selection of v. and v,, as inputs to v, (in addition 
 
 4 14 6 
 
 to the essential inputs, v and v ) is consistent with the preference 
 
 ordering r. 
 
 The new input set for v, is {v., v. _, v. .. , v 1 ,}, and the result 
 
 6 4 ID ii 14 
 
 is shown in Fig. 3.1(b). CSPF's chosen for the inputs of v, are as follows 
 
 o 
 
 (covers for 0-components of G (v.) are selected in accordance with r) : 
 
 c 6 
 
 G ( C ) m (* 1 * * * 1 * * * 1 * 1 * * 1) , 
 
 c 4,6 
 
 G (c.,. r ) = (1 * * * 1 * * * 1 * * * 1*0*), 
 c 14, 6 
 
 c 11,6) V U ; ' 
 
 G(c ) = (**** **** **n* **o*") 
 c v 10,6' V ; * 
 
 Next, v , v , v , v , v , v , v , and v are found to be con- 
 nectable to v.,. By a calculation similar to that for v , , {v_, v, n , v n . , v..} 
 / 6 J 10 11 13 
 
 is chosen as the input set for v . This change leaves v with no output con- 
 nections, and it can be removed, resulting in Fig. 3.1(c). CSPF's for the 
 
18 
 
 input connections are chosen as follows: 
 
 G c (c 3 7 ) ■(**!* * * 1 * * * 1 1 * * 1), 
 G (c 13 -) - (1 * * * 1*** 1*** 10**), 
 
 G(c ) ■ (* 1 * * *]** * * * * * o * *\ 
 c K 11, 7' V u ;, 
 
 G (c ) = (**** * * * * *t** * n * *^ 
 c 10, 7 ; l ± v ). 
 
 Connectable input terminals and gates to v_ are: v , v, , v 7 , v_, 
 
 v , v , and v , . v , v , and v , are selected as inputs to v R , and the 
 result is shown in Fig. 3.1(d). 
 
 Consideration of the input set for v leaves it unchanged. 
 
 The CSPF is determined for v as follows: 
 
 c 11 c 11,6 c 11,7 
 
 Thus, 
 
 =(*11* * 1 1 * **** *00*). 
 
 K(v )=(*00* *00* **** ****) 
 
 and only v , v , and v 10 are connectable to v . 
 1 o LZ 11 
 
 In order for v to realize a function in G (v ) , an input func- 
 tion is required from the set 
 
 (*00* *00* * * * * * 1 1 *) . 
 Input terminal v is both a member of this set and an essential input. 
 Therefore, the connection c._ . - is redundant. 
 
 Gate v 19 , now without output connections, may be removed from the 
 network. The final network is shown in Fig. 3.1(e). Two gates have been 
 removed during this transduction procedure. 
 
 In order to facilitate the selection of input sets for gates, the 
 concept of effective connectability is introduced. 
 
 Definition 3.1 Input terminal or gate v. is said to be effectively 
 
19 
 
 connectable to gate v. with respect to set G(v.) if and only if it is con- 
 J J 
 
 nectable and there exists at least one d satisfying: 
 
 f (d) (v.) = 1 and G (d) (v.) = 0. 
 
 If input terminal or gate v. is connectable but not effectively 
 
 connectable to gate v. with respect to set G(v.), then for every d such that 
 
 G (v.) = 0, f (v.)=0 must hold. Therefore, even if such a v. were to 
 j i i 
 
 be connected to v., the connection would not enable the enlargement of CSPF's 
 for other inputs of v.. For this reason, the effectively connectable condi- 
 tion is used advantageously in place of the connectable condition. 
 
 Theorem 3.1 If input terminal or gate v. and gate v. satisfy the 
 
 condition: 
 
 IS(v.) => IS(v.), 
 
 then v. is not effectively connectable to v. with respect to G (v.) as calcu- 
 1 J c j 
 
 lated by Procedure RSCS given in [5], 
 
 Proof Assume that v. is effectively connectable to v. with respect 
 i J 
 
 to G (v.). Then there exists at least one d satisfying: 
 
 f (d) (v.) = 1 and G (d) (v.) = 0. 
 i c 3 
 
 Since v. is connected to every gate v to which v. is connected, for each 
 
 such v, f (v) = (see Fig. 3.2). By the use of Procedure RSCS *- J to 
 
 calculate CSPF's, G (d) (v.) = *, because f (d) (v) = and f (d) (v.) = (im- 
 
 c J J 
 
 plied by G (v.) = 0) . This, of course, contradicts the original assum- 
 tion that G ^ (v ) = 0. 
 
 Q.E.D. 
 
 For example, in the network of Fig. 3.3, v. (j =1,2,3) is not ef- 
 
 Jj 
 fectively connectable to v. .. , _ _ , . , N t m , 
 
 i, (k=l,2,3; k^j). Thus, Theorem 3.1 can be used 
 
 tThis corresponds to the triangular condition in [1] . 
 
V. 
 
 20 
 
 Fig. 3.2 Configuration in which v. is not effectively 
 
 connectable to v.. 
 3 
 
 v. 
 
 tA 
 
 —I 
 
 V. 
 
 Fig. 3»3 Configuration in which no pair of gates v. , v. , 
 v. are effectively connectable. 1 2 
 X 3 
 
21 
 
 to exclude certain candidates for effectively connectable input terminals 
 and gates. 
 
 While determining the set of effectively connectable gates and 
 input terminals for a gate v., suppose a gate v. is encountered which is 
 effectively connectable to v. and whose CSPF has already been calculated. 
 In such a case, the addition of a connection from v. to v. might necessi- 
 tate a recalculation of the CSPF for v. since a new output connection for 
 
 v. will have been created. In addition, if there exist gates in P(v.) 
 J i 
 
 whose CSPF's have already been calculated, these may also require recalcu- 
 lation. This process would involve excess calculation time; hence, connec- 
 tions are added only when no recalculation of CSPF's is necessary. A con- 
 dition for this is given in the following lemma. 
 
 Lemma 3.1 Let G (v.) and G (v ) be CSPF's for gates v. and v. 
 
 c 1 c j 1 j 
 
 respectively. If the following conditions are satisfied, v. is effectively 
 connectable to v. and the CSPF for v. does not change by adding a connec- 
 tion from v. to v.: 
 i J 
 
 (1) For every d such that G ^(v.) = 1, G ^(v.) = 0. 
 
 c j c x 
 
 (2) Gate v. is connectable to v.. 
 
 i J 
 
 (3) There exists at least one d such that G (v.) = and 
 
 c 3 
 
 G (d) (v.) = 1. 
 c 1 
 
 Proof: For all d such that G (v.) = or *, the value of G (v.) 
 
 c j c 1 
 
 is unchanged by the addition of a connection from v. to v.. If there exists 
 
 i J 
 
 a d such that G (v.) =G (v.) =0,v. is not connectable to v.. If there 
 c J c l l 3 
 
 exists a d such that G (d) (v.) = 1, f (d) (v.) = and G (d ^(v.) = *, then the 
 
 c J 1 c 1 
 
 d-th coordinate of the vector representing the CSPF for v. must be 0, and 
 thus, the CSPF would change in making the new connection. 
 
 Condition (3) is a sufficient condition for the connectability of 
 
22 
 
 of v. to v. to be effective connectability . 
 
 Q.E.D. 
 
 Ordering r affects the results of the network transduction proce- 
 dure. When networks having various characteristics are desired (e.g., low 
 cost, small maximum fanout, small number of levels, etc.), the following ad- 
 ditional conditions (the condition that for every input terminal v. and gate 
 
 v , r(v.) > r(v.), is retained in each case) may be used to determine an or- 
 j ± 3 
 
 dering r. 
 
 Suppose a reduction of the number of gates is of primary importance. 
 Since it is generally more likely that a gate with smaller fan-out can be re- 
 moved then a gate with larger fan-out, the following condition is imposed. 
 For gates v. and v. such that IS(v.)| > |lS(v.)|, 
 
 r(v.) > r(v.) , 
 
 where |lS(v.)| denotes the number of elements in IS(v.). Especially, the use 
 of a gate with only a single output connection should be avoided. 
 
 If it is desired to design a network using fan-out restricted gates, 
 gates with smaller fan-out should be assigned larger values of r. 
 
 If a network is desired with a small number of levels, a gate whose 
 predecessors form a subnetwork of fewer levels should have a larger value of 
 r. 
 
 Another possibility for the purpose of reducing the number of gates 
 
 is to prefer the use of gates with fewer predecessors. In other words, if v. 
 
 and v. satisfy I P (v . ) I > I P (v . ) I , 
 J i J 
 
 r(v. ) > r(v.) . 
 J i 
 
 Thus, functions which are produced by smaller subnetworks are preferred. As 
 a simplification, the gate level of a gate can be substituted for the number 
 
23 
 
 of its predecessors. A gate in a lower level (i.e., closer to the output 
 gate(s)) generally has more predecessors than a gate in a higher level. 
 
 The following definition introduces an operation needed in the net- 
 work transduction procedure to be given. 
 
 Definition 3.1 The operation A is defined as follows: 
 
 1A0 = 1A1 = 1A* = 0A1 = *A1 = 1, 
 0A0 = OA* = *A0 - *A* = 0. 
 The operation A which is both commutative and associative is sum- 
 marized in Table 3.1. 
 
 A 
 
 
 
 1 
 
 * 
 
 
 
 
 
 1 
 
 
 
 1 
 
 1 
 
 1 
 
 1 
 
 * 
 
 
 
 1 
 
 
 
 Table 3.1 The operation A. 
 
 The network transduction procedure based on connectable and discon- 
 nectable conditions is formally given as follows: 
 
 Procedure 3.1 [Procedure NTCD] (a Network Transduction procedure 
 based on Connectable and Disconnectable conditions) 
 
 (1) Calculate f (v.) for each gate v. in the network. 
 
 (2) For each connection from an output gate v.,p<i_<p+m, to its cor- 
 responding output terminal v., j = i + R, G (c..) is given by: 
 
 G (c..) = z. , 
 c ij x-p 
 
 where z is the &-th output function. 
 
 (3) Select a gate v for which no CSPF has yet been calculated, but for which 
 CSPF's of all output connections have been calculated. There will always 
 
24 
 
 exist at least one such v at this step until all gates have been ex- 
 hausted. If no such gate v exists, go to Step (6). Determine a CSPF 
 for gate v by using the equation: 
 
 G c ( v= no c (c kj ). 
 
 Vj £lS(v k ) 
 
 (4) Change the input set of gate v selected in Step (3) . 
 
 (4-1) Select effectively connectable gates and input terminals for v . 
 
 K. 
 
 (4-1-1) Calculate the set K(v ) of functions connectable to v with re- 
 spect to G (v. ) . 
 c k 
 
 (4-1-2) Let Q"(v k ), Q"(v ) = Q^'(v k ) U Q^Cv^, denote a set of gates 
 and/or input terminals which represent a set of input candidates for v.. 
 (4-1-3) Let Q"(v ) be the set of all gates satisfying Lemma 3.1 
 for connectability to v . 
 
 (4-1-4) Initially, let Q''(v t ) be the set of all input terminals which 
 are effectively connectable to v . 
 
 (4-1-5) Add to QV^^) all gates which are effectively connectable to v, 
 and whose CSPF's have not yet been calculated. 
 
 (4-2) If there exists a single-output gate v. which is originally connec- 
 ted to v (i.e., v.eIP(v, )) and which satisfies the following condition, 
 k l k 
 
 remove v. from Q"(v ) and from the network: For every d such that 
 
 Gc (d) (v k ;=o, 
 
 Vf^Cv) V AG (d) (v) = l. 
 veQ^(v k ) veQ^(v k ) 
 
 v^, 
 
 i 
 
 Apply this test to each single-output gate in IP(v ). 
 
 (4-3) Determine a set, Q CO, of essential inputs for v . 
 
 (4-4) Select a new input set Q' for v by the following method. If 
 
 Q' / IP(v ), then the ordering r must be recalculated. 
 
 K. 
 
 tFor certain orderings r, skipping this recalculation would not be too harmful, 
 
■^ 
 
 (4-4-1) Initially, let Q' = Q (v, ) . 
 
 o k 
 
 (4-4-2) Add every v., v eQ''(v,), to Q' which satisfies the following 
 
 1 ilk 
 
 conditions: v.^Q' and for at least one d such that G (v, ) = 0, 
 i c k 
 
 f (d) (v.) = 1 andV (d) (v) - AG (d) (v)=0. 
 l v c 
 
 ve( 
 v^v. 
 
 veQ^(v k ) veQ^(v k ) 
 
 (4-4-3) If for every d such that G ( (v.) = 0, 
 
 Vf^Cv) V AG< d) (v)=l 
 
 veQ'nQj(v k ) veQ'nQ'^(v k ) 
 
 is satisfied, recalculate ordering r if Q 1 is different from the original 
 input set for v and go to Step (5) . 
 
 K. 
 
 (4-4-4) Add v. to Q' if v. satisfies the following conditions: v.eQ"(v ), 
 ix x k 
 
 v. is not currently a member of Q 1 , and there exists at least one d such 
 
 that G (d) (v ) = 0; f (d) (v.) = 1 if v.eQ'^v) or 
 c k x x 1 k 
 
 G c d) (v.) = 1 if v eQ"(v.); and 
 
 "- x i k 
 
 V f (d) (v) v AG< d) (v) =0. 
 veQ' Qj(v k ) veQ' fl Q!^) 
 
 The v selected is the one with largest value of r(v.) among those satis- 
 i x 
 
 fying these conditions. Go to Step (4-4-3). 
 
 (5) Calculate CSPF's for connections from gates and input terminals in Q* to 
 
 v, by the following method, 
 k 
 
 (5-1) Let H = Q"(v ) PI Q'. Calculate a vector G as follows: 
 
 If G (d) ( Vl ) = *, set G (d) = *. 
 c k 
 
 If G Cd) (v) = 1, set G (d) = 1. 
 c k 
 
 If G^(v ) = and G^ d *(v) = 1 for at least one veH, set G = *. 
 c k c 
 
 (d) 
 Otherwise, set G =0. 
 
 After connections from gates in H have been added to v , G can be regarded 
 
 as representing a CSPF for v for the remaining inputs (Q' - H) . 
 
26 
 
 (5-2) Calculate G (c ) for v.eQ'-H by the following equation: 
 
 G (c ) = {GD(Vf(v))} # f(v.) 
 C lk r(v)>r(v ) X 
 veQ'-H 
 
 Go to Step (3). 
 
 (6) Recalculate f(v.) for each gate v remaining in the network. If there 
 
 exist v. and v. such that 
 i J 
 
 f(v.) e G (v.) and v, t S(v.), 
 1 c J i J 
 
 then replace output connections from v. by output connections from v , 
 removing v. from the network. If successful, recalculate CSPF's for 
 gates in the network and repeat this step. 
 
 This procedure does not calculate CSPF's for input terminals since 
 they are generally not useful. However, if they are desired, a new step - 
 similar to Step (3) for gates - can be inserted prior to Step (6) to accom- 
 plish this. 
 
 In Procedure NTCD, Q' is determined by the ordering r. Following 
 are two alternative selection criteria: 
 
 (1) Remove as many originally connected gates and input terminals 
 as possible. 
 
 (2) Select Q' which has the minimum number of elements. 
 
 Selection criterion (1) is used to attempt to produce a relatively 
 large change in a network's configuration. By changing a network's configur- 
 ation, other known network transduction procedures may be able to be applied 
 which could not be effectively applied to the original network. (A similar 
 criterion was incorporated in the computer program NETTRA-G1 described in 
 Section 5.) Selection criterion (2) can be used in network design with fan- 
 in restricted gates. 
 
 tNormally, G.(c ) need not be calculated if v is an input terminal. 
 
 1 1 K. X 
 
27 
 
 A relatively simple additional calculation can be performed in Step 
 
 (5) of Procedure NTCD to produce generally larger CSPF's. Suppose a CSPF has 
 
 already been determined for at least one output connection, c.., of a gate v . 
 
 If for some d, G^ (c.) = 1, then G (v.) = 1 is known even though CSPF's 
 c ij ex 
 
 for other output connections of v. may not yet have been calculated. Thus, in 
 
 Step (5), if there exists any output connection, c.., of any input v. of v for 
 
 which a CSPF, G (c..), has already been calculated, and G (c..) = 1 for some 
 c ij c ij 
 
 d for which G (v ) = 0, then the d-th coordinate of every vector representing 
 
 a CSPF for some input connection to v can be assigned the value *. 
 
 This is accomplished by the addition of the following condition to 
 
 those listed in Step (5-1). 
 
 If G (v, ) = and G (c.) = 1 has been calculated for at least one 
 c k c ij 
 
 output connection, c.., of v. where v.eQ', set G = *. 
 
 13 i 1 
 
28 
 
 4. MODIFICATION OF THE NETWORK TRANSDUCTION PROCEDURE 
 
 In this section, a modification of Procedure NTCD is given which fo- 
 cuses on the removal of a specific gate of a network. 
 
 The following notation will facilitate explanation of the modified 
 procedure. T(v ) represents the set of all gates which are neither successors 
 
 of v nor v itself: 
 
 T <V ■ \ - s( v - { V- 
 
 This modification of Procedure NTCD seeks the removal of a specific 
 gate, v , by first attempting to enlarge, to a maximum extent, the set of per- 
 missible functions for v . This increases the probability that one of the fol- 
 lowing will occur: 
 
 (1) G (v„) will contain some function f(v) (veT(v„) U V T ). In such 
 
 c a a i 
 
 a case, v can be replaced by v. 
 
 (2) For all d, G (v.) / 1. In this case, G (v.) contains the func- 
 
 c £ c Jc 
 
 tion which is always 0, and v. can be removed from the network. 
 
 This is essentially accomplished by adding connections from input 
 terminals and gates in T(v ) to gates in S(v.) in order to replace as many in- 
 put connections from other gates in S(v ) as possible and to increase the size 
 of the CSPF's for those connections which cannot be replaced. Basically, this 
 involves a modification of Step (4) of Procedure NTCD and the selection of a 
 special type of ordering r. 
 
 In the following transduction procedure, an ordering r satisfying the 
 conditions below is assumed. 
 
 (1) 1 < r(v.) < R for v. e V_, 
 i i G 
 
 R+l < r(v.) < R+n for v. e V x . 
 — l — l I 
 
29 
 
 (2) For every gate v in T(v £ ) and every gate v fc in S(v^) U {v^>, 
 
 r (v ± ) > r (v k ). 
 
 Procedure 4.1 [Procedure NTCDG] (A Network Transduction procedure, 
 based on Connectable and Disconnectable conditions, modified to concentrate on the 
 
 removal of a specific Gate) 
 
 (0) Select gate v . Calculate S(v ) and T(v ) and select an ordering r. 
 
 Assume S(v,,) ^ <J> • Do not alter S(v ) or T(v ) during the remainder of the 
 procedure. 
 
 (1) Calculate f(v.) for each gate v. in the network. 
 
 (2) For each connection from an output gate v. belonging to S(v ) U {v }, 
 p < i _< p+m, to its corresponding output terminal v., j = i+R, G (c..) is 
 
 given by: 
 
 G (c. .) = z. 
 c ij l-p 
 
 where z is the (i-p)-th output function. 
 
 (3) Select a gate v in S(v ) U {v } for which no CSPF has been calculated, 
 but for which CSPF's of all output connections have been calculated. There 
 will always exist at least one such v at this step until all gates in 
 
 S(v ) U {v } have been exhausted. Determine a CSPF for gate v by using the 
 equation: 
 
 w- no c <c k .). 
 
 v.eIS(v. ) 
 
 l k 
 
 If k = £, go to Step (6). 
 
 (4) Change the input set of gate v selected in Step (3) . 
 
 (4-1) Select effectively connectable gates in T(v ) and effectively connectable 
 
 input terminals for v. with respect to G (v, ). Connect all such gates and input 
 
 k c k 
 
 terminals to v, . 
 k 
 
 (4-2) If there exists a single-output gate v. in S(v ) U {v } which is connected 
 to v (i.e., v. e IP(v )) and which satisfies the condition (Theorem 2.2) for 
 
30 
 
 disconnectability from v, with respect to G (v, ) , then disconnect v, from 
 
 k c k i 
 
 v and remove it from the network. Apply this test to each single-output gate 
 in IP(v k ) - T(v a ). 
 
 (4-3) For each gate in S(v„) U {v„} which is connected to v, and which is not 
 
 £ £ k 
 
 a single-output gate, check whether or not it satisfies the condition (Theorem 
 2.2) for disconnectability from v, with respect to G (v ) . If so, disconnect 
 
 K. C K. 
 
 it from v . Selection priority for this test is the reverse of ordering r. 
 
 (4-4). If a gate in T(v ) or an input terminal, v., which is connected to v 
 
 satisfies the following condition, remove the connection from v. to v : For 
 
 every d such that G (d) (v k ) = and f (d) (v t ) = 1, 
 
 V f <d) (v) - 1 
 veIP(v k )n [T(v A )U V x ] 
 
 v?*v. 
 1 
 
 Selection priority for this test is the reverse of ordering r. 
 
 (5) Let Q' denote the set of inputs for v after the completion of Steps (4-1) 
 
 to (4-4). Calculate CSPF's for connections from gates in [S(v ) U {v }] n Q' 
 
 to v by the following method. 
 
 (5-1) Let H be the set of input terminals and gates which are in Q f but not 
 
 in S(v ) U {v }. Calculate a vector G as follows: 
 
 If G (d) (v) = * , set G (d) = *. 
 c k 
 
 If G (d) K) = 1 , set G (d) = 1. 
 c k 
 
 If G^ d (v k ) = "0 and f (d) (v) = 1 for at least one veH, 
 set G (d) - *. 
 Otherwise, set G = 0. 
 For inputs from gates in S (v ) U {v }, G can be regarded as a CSPF for v . 
 
 X/ As K. 
 
 (5-2) Calculate G (c ) for v. e S(v ) U {v } by the following equation: 
 
 C IK 1 Xt JG 
 
 G c (c. k ) = {GD(\/f(v))} // f(v.). 
 
 r(v)>r(v ) 
 veQ'-H 
 
 Go to Step (3) . 
 
31 
 
 (6) If there exists v. in T(v ) U V satisfying 
 
 1 X X. 
 
 f(v.) E G c (v £ ) 
 v can be replaced by v.. If v has no output connections, it can be 
 removed from the network. 
 
 At several points in Procedure NTCDG, variations exist to the course 
 of the procedure as formulated above. Incorporation of such variations into 
 the procedure can alter the emphasis (e.g., the above formulation of the pro- 
 cedure places a relatively high value on the removal of gate v and the ease 
 of computation, a relatively lower value on the attainment of a final network 
 with few redundant connections, and no value at all on the calculation of 
 CSPF's for gates in T(v )) of the transduction. Three examples of possible 
 variations in the procedure are given below. The corresponding changes in 
 emphasis of the transduction are obvious. 
 
 A. Step (4-2) can be followed by a similar step for attempting the removal of 
 single-output gates in T(v ) connected to v . If successful, this would 
 
 A/ K, 
 
 result in the immediate removal of one gate from the network, although 
 the possibility of removing v may be adversely affected as a consequence. 
 
 B. Somewhere in Step (4), a test can be made to determine if any single-output 
 gates in T(v ) connected to v can be removed by the addition of connec- 
 tions to v from gates in S(v.) U {v }. This would have consequences 
 similar to those for (A) . 
 
 C. Sets S(v ) and T(v ) can be kept updated during the transduction. Once v 
 
 has been selected in Step (0), the above Procedure NTCDG assumes, in the inter- 
 est of computational simplicity, that S(v ) andTCv^) will remain unchanged. In 
 actuality, however, gates which are originally successors of v at the 
 beginning of the transduction may no longer be such upon its termination. 
 It is convenient not to alter sets S(v ) and T(v ) during the transduction 
 (since ordering r and the functions of certain gates must also be updated) 
 
32 
 
 but the performance of this update will add to the potential power of the 
 transduction with respect to the removal of gate v (since the number of 
 functions available from the members of T(v) is increased). If desired, 
 the update should be done at the beginning of Step (5) whenever the 
 condition 
 
 [s(v £ )u {v^}] n Q' = * 
 
 is detected following Step (4) . 
 
 Another possibility is to carry out the calculation of CSPF's for 
 gates in T(v.) also. The actual computer program implementation of the pro- 
 cedure permits this option. 
 
 The following example demonstrates the application of Procedure NTCDG. 
 
 Example 4.1 The network in Fig. 4.1(a) realizes the following 4-vari- 
 able function f: 
 
 I X„X«X. " X- X« X . ^ X-X—X« ^ X-.X — X* X - X X » X-XftX/. • 
 
 234 124 123 124 134 123 
 
 It consists of 8 gates and 20 connections. 
 
 The functions realized at gates and input terminals are as follows: 
 
 f(v ) =x 1 =(0 000 0000 1111 1111) 
 
 f(v ) =x 2 =(0 000 1111 0000 1111) 
 
 f(v ) = x = (0 1 1 0011 0011 0011) 
 
 f(v,) - x, = (0 1 1 0101 0101 010 1) 
 4 4 
 
 = (1001 0111 1010 110 0) 
 
 = (0 100 0000 0101 0011) 
 
 = (0 010 1000 0000 000 0) 
 
 = (0 000 1100 0000 110 0) 
 
 = (0 001 0111 0000 000 0) 
 
 = (1010 0000 1010 000 0) 
 
 = (1100 0000 1100 000 0) 
 
 =(1000 1000 1000 100 0). 
 
 f(v 5 ) 
 
 f(v 6 ) 
 
 f(v ? ) 
 
 f(v g ) 
 
 f(v 9 ) 
 
 f(v 10 ) 
 
 f(T u ) 
 
 f(v 12 ) 
 
T(v 12 ) 
 
 10 
 
 x. 
 
 x u — t 
 
 V 
 
 X, 
 
 11 
 
 ^3 — i 
 
 V 
 
 x. 
 
 "2> 
 
 S(v 12 ) U (v 12 ) 
 
 ^ 
 
 v„ 
 
 x. 
 
 V 
 
 12 
 
 X 3 =j 
 
 x k —i 
 
 V^ 
 
 x. 
 
 v^ 
 
 33 
 
 (a) Given network. 
 
 T(v 12 )!s(v 12 ) U (v 12 ) 
 
 (b) Final network - after use of Procedure NTCDG 
 
 — - NEW CONNECTION 
 REMOVED CONNECTION 
 
 (gate v np is isolated) 
 
 Fig, k.l Networks for Example k.l, 
 
34 
 
 (0) Select gate v as v of Procedure NTCDG. s ( v ip= fv » v , v , v }. 
 T(v _) = {v fi , v , v }. Let ordering r be selected as follows: 
 r(v.) - 8 + i for i = 1, 2, 3, 4; 
 r(v 5 ) = 1, r(v 6 ) = 2, r(v ? ) = 3, r(v 9 ) = 4, 
 r(v 12 ) = 5, r ( v g ) = 6, r (v 1Q ) = 7, r(v n ) = 8. 
 
 (2) The only gate (in S(v-„) U {v.-}) whose output is connected to an output 
 
 terminal (v.-) is v . 
 
 6 (c. ,,) ■ (1 1 111 10 10 1 1 0) = f. 
 c J , ±J 
 
 (3) v is the only gate with CSPF's calculated for all of its output connec- 
 tions. 
 
 G (v c ) • 6 (c. „) ■ (1 1 111 10 10 110 0). 
 c5 c 5,13 
 
 (4) K(v ) =(0**0 *000 0*0* 00**). 
 
 There exist no input terminals or gates in T(v._) which are connectable 
 
 to v c . Neither v, nor v., satisfies the condition for disconnectability 
 j o / 
 
 from v . 
 
 (5) Calculate CSPF's for connections from v, and v_ to v r . 
 
 6 ID 
 
 G(c £C ) = (0 1*0 *000 0101 0011) 
 c 6,D 
 
 G(c^ c ) = (0*10 1000 0*0* 00**) 
 c 7,5 
 
 (3)' G (vj ■ G (c. .) ■ (0 1 * MOO 0101 0011) 
 
 c6 c 6,5 
 
 (4)' K(v,) = (*0** **** *0*0 **0 0) 
 
 6 
 
 There exist no input terminals or gates in T(v 1<? ) which are connectable 
 
 to v except v and v (already connected). None of v Q , v , or v 
 6 o 10 o y 
 
 10 
 
 satifies any of the conditions for disconnectability from v (Steps 
 
 o 
 
 (4-2), (4-3), and (4-4)). 
 
 (5)' Calculate CSPF for the connection from v. to v , . 
 
 y o 
 
 G (c n J = (* * 1 * * 1 1 * * * * 0) 
 
 c 9,6 
 
 (3)" G (v^) =G(c^ c ) = (0*10 1000 0*0* 00**) 
 c 7 c / ,5 
 
 (4)" K(v )=(**0* 0*** **** ****) 
 
35 
 
 Since f(v,) = (0 1 1 0101 0101 10 1), v, is effectively 
 
 4 4 
 
 connect able to v .No other connectable input terminals or gates in 
 
 T(v, _) exist which are not already connected to v., . Connect v. to v_. 
 12 7 4 7 
 
 Gate v in S(v.._)U {v-.^} does not satisfy the condition in Step (4-3) 
 for disconnectability from v 7 . Input terminals v and v. and gate 
 v e T(v ) also do not satisfy the condition in Step (4-4) for discon- 
 nectability from v ? . 
 
 (5)" Q* = {v., v , v , v ,,}. Calculate CSPF for the connection from v to v . 
 i 4 y J.J. y / 
 
 G(c ) = (**o* 0*1* * * * * ****) 
 
 o>" g c (c 9)6 ) nG c (c 97 ) - 
 
 G c (v g ) = (*001 0*11 *0*0 **0 0) 
 (4)'" K(v ) = (*** **00 * * * * ****) 
 
 Since f(v ) =(0 000 1100 0000 110 0), 
 
 o 
 
 v is effectively connectable to v_ . No other connectable input terminals 
 o y 
 
 or gates in T(v 10 ) exist which are not already connected to v Q . Connect 
 ±z y 
 
 v to v . In Step (4-2), connection c is found to satisfy Theorem 
 
 2.2 for disconnectability with respect to G (v ) : For all d such that 
 
 c 9 
 
 f (d) (v 12 ) = 1, either G^) = * or f (d) (v^ v f (d) (Vg),, f < d ) (v )n/ 
 f (v 1 ) = 1. Remove connection c n „ Q . None of v-, , v , v.., or v n .. 
 
 ±j - j-^»y L o 10 n 
 
 are found to be disconnectable from v in Step (4-4) . 
 
 As a result of Step (4)'", the network shown in Fig. 4.1(b) is ob- 
 tained which consists of 7 gates and 19 connections. Furthermore, the desired 
 gate v has been removed from the network. 
 
36 
 
 5. COMPUTER PROGRAMS AND EXPERIMENTS 
 
 This chapter will discuss procedures NTCD and NTCDG as they have been 
 actually programmed. The programs NETTRA-G1 and NETTRA-G2 realize the proce- 
 dures NTCD and NTCDG, respectively. 
 
 As previously stated, the procedures as programmed are slightly dif- 
 ferent from the procedures as they were specified earlier. This is due to 
 various reasons: programming convenience, considerations of computation time 
 vs. effectiveness, choosing specific methods where only general methods had 
 been specified, etc. 
 
 Each program is complete in itself: reading in the given network, ap- 
 plying the desired transduction procedure, and printing out the resultant net- 
 work. The details necessary to use NETTRA-G1 and -G2 can be found in [2]. 
 
 The procedures realized by these two programs will now be described 
 in detail. For each program, examples will be given of its capabilities in re- 
 ducing the cost of a network and/or changing the configuration of a network. 
 
 5.1 A Program Realizing Procedure NTCD 
 
 In the program NETTRA-G1, it is the subroutine named PROCII which 
 essentially realizes Procedure NTCD. The general flowchart of this subroutine 
 is shown in Fig. 5.1.1. 
 
 For simplicity of the explanation, it will continue to be assumed 
 that only n uncomplemented variables are available to the given network. 
 This means p=n, and let v. correspond to x (for i=l,...,n) (i.e., "input 
 terminal" is synonymous with "external variable") . 
 
 In block 1 of the flowchart, the output functions of all of the 
 gates, f(v.) for i=n+l, n+2,..., n+R, are calculated in a straightforward 
 manner. For all non-output gates, v , i=n-hn+l,n+m+2, . . . ,n+R (i.e., gates with 
 
37 
 
 START 
 
 CALCULATE f(v. )'s AND 
 ,(d) 
 
 INITIALIZE G 
 
 (v.)'s 
 
 FOR i = n+l,n+2,...,n4-R. 
 FORM THE ORDERING 
 GORDER. 
 
 TRY TO REMOVE 
 
 REDUNDANT 
 
 CONNECTIONS 
 
 YES 
 
 UPDATE 
 ARRAYS 
 
 RETURN 
 
 GORDER 
 (GCOUNT) 
 
 INITIALIZE 
 COUNTER: 
 GCOUNT = 
 
 INCREMENT 
 COUNTER: 
 GCOUNT = 
 GCOUNT + 1 
 
 ADD CONNEC TABLE 
 FUNCTIONS, REMOVE 
 ANY UNNECESSARY 
 INPUTS, AND UPDATE 
 G (v. ) FOR ALL v. € 
 
 IP(T k ). 
 
 Fig. 5.1.1 General flowchart of program realizing 
 Procedure NTCD. 
 
38 
 
 no connections to any output terminal), set G (v.) = * for d=l,2,...,2 . For 
 
 c 1 
 
 all output gates, v .,j=l,...,m (i.e., gates with at least one connection to 
 
 the output terminals), set G ' (v ,.) = z. ' for d=l,2, . . . , 2 n . Block 1 also 
 
 c n+j j 
 
 determines an ordering (which has a somewhat different purpose than the order- 
 ing r mentioned earlier) of gates and input terminals and stores it in an array 
 GIRDER such that for v .=G0RDER(i' ) and v. = G0RDER(j'), i'<j' means that v 
 precedes v. in the ordering. The ordering represented by the array G0RDER 
 satisfies the following criterion: for every gate or input terminal, v., and one 
 of its successors, v., v. precedes v. in the ordering. By applying Steps (3), 
 (4), and (5) of Procedure NTCD (see Section 3) to gates G0RDER(1) ,G0RT)ER(2) 
 G0RDER(n+R) successively (ignoring GORDER(i) 'seV ) , one is assured of always 
 knowing the CSPF completely for a gate v before these steps consider it in the 
 
 K. 
 
 procedure (a necessary condition for a valid implementation of the procedure). 
 
 Block 2 simply initializes a counter, the variable GC0UNT, used in 
 the program loop consisting of blocks 3, 4, 7, 8, and 9. GC0UNT points to posi- 
 tions in the array G0RDER. 
 
 Block 3 increments the counter, GC0UNT. The program loop formed by 
 blocks 3,4,7,8, and 9 is executed once for each value of GC0UNT: 1,2,3,... (this 
 corresponds to the repeated execution of Steps (3), (4), and (5) of Proce- 
 dure NTCD for each gate of the network) . 
 
 When GC0UNT is incremented beyond the value n+R, it is detected in 
 block 4 . This signals the termination of the procedure, every gate in the net- 
 work having been scanned; and the program enters block 5. Otherwise, the pro- 
 gram proceeds to block 7. 
 
 In block 5 the procedure has essentially finished. A subroutine is 
 called which quickly searches for and removes certain redundant connections 
 which may still remain in the network (for example, certain new connections 
 that might have been added unnecessarily in block 9) . The removal of such 
 
39 
 
 connections will not cause a change in the output functions of the network. 
 
 At the end of every transformation there are certain "house-keeping" 
 chores which must be performed : updating or restoring values in arrays and 
 variables. This task is done in block 6 . This is followed by a return to the 
 calling subroutine. 
 
 In block 7 , v is the gate or input terminal whose label is contained 
 
 K. 
 
 in the (GC0UNT)— position of the ordering stored in the array G0RDER. This v 
 is the gate or input terminal about to be scanned by the program. 
 
 If v happens to be either an input terminal (v e V ) or an isolated 
 
 K. K. J- 
 
 gate (a gate with no successors : IS(v )=4>), no action needs to be taken. In 
 
 iC 
 
 such a case block 8 returns control to block 3. Otherwise, the program con- 
 tinues to block 9. 
 
 Block 9 performs many functions and is actually quite complex. So 
 block 9 is detailed in Fig. 5.1.2 as consisting of sub-blocks 10 through 23. 
 Block 9 corresponds to Steps (4) and (5) of Procedure NTCD, although super- 
 ficially it may first appear completely different. The variable v here cor- 
 responds to the v chosen in Step (3) of Procedure NTCD. 
 
 In block 9, a set Q' is not developed explicitly as in Step (4-4) of 
 the procedure. New inputs are added one at a time to gate v. by the program, 
 and old inputs are removed one by one (when it is possible to remove them) . 
 However, the end effect, of course, is the same as constructing a set Q 1 (per- 
 mitting Q'DlP(v ) to be non-null) and replacing the set IP(v ) by that Q'. 
 
 Another difference between block 9 of the program and Step (5) of the 
 
 procedure is that block 9 does not calculate G (c..)'s. In place of the calcu- 
 
 lation of G (c.^'s, for all i such that v.eIP(v, ), in Step (5-2) of the proce- 
 c lk i k 
 
 dure, block 9 assigns values (0,l,or"no change") directly to components of the 
 CSPF's of all v. such that v.eIP(v ). It is thus possible to bypass the cal- 
 culations of the CSPF vectors for connections since the CSPF vector of a gate 
 
ko 
 
 10 
 
 11 
 
 START 
 
 ELIMINATE DIS- 
 CONNECTABLE INPUTS. 
 ORDER OTHERS (IN 
 A "LIST L") BY DE- 
 CREASING NUMBERS 
 OF ESSENTIAL l'S. 
 
 13 
 
 TRY TO REPLACE AN 
 
 ELEMENT v. FROM 
 t 
 
 LIST L WITH AN EL- 
 EMENT v FROM LIST C. 
 
 YES 
 
 15 
 
 19 
 
 DISCONNECT v 
 
 FROM v. 
 
 t 
 
 k* 
 
 SEARCH LIST C FOR 
 AN APPROPRIATE EF- 
 FECTIVELY CONNECT- 
 ABLE GATE OR INPUT 
 TERMINAL, v 
 
 CONNECT v TO v, 
 P k 
 
 REEVALUATE LIST 
 L AND REMOVE 
 
 FROM LIST C. 
 
 UPDATE G (v. ) FOR 
 c 1 
 
 EACH CURRENT v. € 
 
 IP(v k ). 
 
 RETURN TO 
 
 LIST ALL EFFECTIVELY CONNECT- 
 
 ABLE v. SATISFYING 
 l 
 
 CERTAIN CONDITIONS IN A 
 
 "LISTC" BY DECREASING NUMBERS 
 
 OF O'S |ING (v, )] COVERED. 
 
 G .K. 
 
 ELIMINATE ANY "SMALLER" 
 THAN OTHERS. 
 
 REMOVE v FROM 
 
 P 
 LIST C AND V. 
 
 FROM LIST L. 
 
 YES 
 
 18 
 
 REORDER 
 LIST L. 
 
 Fig. 5.1.2 Details of block 9 of program realizing Procedure NTCD. 
 
41 
 
 or input terminal can be found simply by taking the component-wise intersection 
 
 of the CSPF vectors of its output connections. Rather than storing the CSPF 
 
 vectors for all of the output connections of a gate (or input terminal) v , 
 
 one need only store a single vector containing the intersection of all of the 
 
 G (c..)'s calculated so far. When every G (c..) for every output connection, 
 
 c.., of v. has finally been intersected with this vector, this vector becomes 
 ij i 
 
 G (v.). Recall the initialization of these vectors as performed in block 1 of 
 c 1 
 
 the flowchart. 
 
 While Step (4-4) of Procedure NTCD did not mention attempting to re- 
 strict the size of the set Q', the implementation of the procedure in block 9 
 implicitly tries to keep the size of Q' "reasonably small". However, this 
 consideration is rather secondary to the preference of the implementation for 
 "new" inputs to v over "old" inputs. For example, block 9 may replace one 
 
 "old" connection, c.. , to v. (i.e., c.. where v.eIP(v, ) with two "new" connec- 
 . . ik k lk l k 
 
 tions (c. , , c , where v , v tfIP(v,)). In such a case, the resulting change 
 
 h k J 2 k j l j 2 k 
 in the configuration of the network is regarded as sufficiently important that 
 
 it more than cancels out the undesirable increase in the number of connections 
 in the network. 
 
 The final important difference between Procedure NTCD and its imple- 
 mentation is to be found in the program's realization of Step (5) of the proce- 
 dure. The suggestion appearing in the last two paragraphs of Section 3 has 
 been incorporated into the implementation of Step (5) to increase the effective- 
 ness of the programmed procedure by possibly allowing larger CSPF's to be calcu- 
 lated for the gates of the network. This, in turn, generally increases the 
 chances to detect and remove non-essential connections and gates. 
 
 Block 10 actually represents two steps. The first step is the elimina- 
 
 + 
 tion of non-essential inputs of v.. This must be done serially though, since 
 
 In this section's discussion and in the program listings, the terms "essential 
 inputs" and "essential l's" are used in a slightly different sense than defined 
 in Definition 2.4 and 2.5: here inputs or "l"*s are essential with respect to 
 IP (v.) rather than with respect to Q(v.). 
 
42 
 removing any inputs to a gate might cause new essential l's (and, hence, per- 
 haps new essential inputs) to be created. 
 
 The remaining inputs to v all have essential l's. They are then 
 
 K 
 
 ordered and stored in an array called "LISTL" (meaning, a list called L) such 
 that the input represented by LISTL(i) has at least as many essential l's as the 
 input represented by LIST(i+l). This is the second step of block 10. 
 
 In block 11, first a search is made for all v, which are connectable 
 
 l 
 
 (excluding any v.eIP(v )) to v and satisfy the conditions given in Steps (4-1-3), 
 
 X K K. 
 
 (4-1-4), and (4-1-5) of Procedure NTCD. Let the set of these v. be denoted Q" 
 
 (note that this Q" is not identical to the one used in Procedure NTCD) . If one 
 
 element, v. eQ", covers every G (v.) =0 covered by another element, v. eQ", 
 i-i c «c i— 
 
 then v. is removed from the set Q" . The remaining elements of Q" are ordered 
 
 x 2 
 and stored in an array called "LISTC" (meaning, a list called C) such that the 
 
 connectable input represented by LISTC (i) covers at least as many 0's in the 
 
 vector representing G (v ) as the connectable input represented by LISTC (i+1) 
 
 (- K. 
 
 covers. 
 
 If list C is empty, control goes to block 23 and then to block 5. 
 Otherwise the program proceeds to the major program loops of block 9, consis- 
 ting of blocks 13 through 22. Block 12 tests for an empty list C. 
 
 Block 13 seeks an element, v , from list C which can be directly sub- 
 
 P 
 
 stituted for an element, v , from list L, such that the substitution would not 
 cause the actual function of v to be outside its set of permissible functions. 
 
 K. 
 
 Block 14 tests if a feasible replacement has been found. If no re- 
 placement is possible, control passes to block 19. If, however, a suitable v 
 and v were chosen, blocks 15 through 18 perform the actual exchange of a con- 
 nection from v and v were chosen, blocks 15 through 18 perform the actual ex- 
 change of a connection from v for the connection from v as an input of gate 
 
 P t 
 
 V 
 
43 
 
 First the connection from v is disconnected from v, in block 15. 
 
 t k 
 
 Also this block connects the new input, v , to v, . 
 
 p* k 
 
 Block 16 removes v from the list C of effectively connectable func- 
 p 
 
 tions and v from the list L of inputs to v . If list L becomes empty by the 
 removal of v ( block 17 test) , the program has replaced all of the original in- 
 puts to v by new ones, and the program moves to the next step in block 23. 
 
 Otherwise the program goes to block 18 where the elements of list L 
 are reordered by decreasing numbers of essential l's. This is necessary since, 
 by the addition of a connection from v to v , some previously essential l's may 
 have become non-essential. Also, other inputs are checked to see if they have 
 become disconnectable after v 's connection. From here, the program returns 
 to block 13 to search for another replacement v if list C is not found to be 
 empty (block 12) . 
 
 Block 19 is reached when it is no longer possible to replace an ele- 
 ment of list L with an element of list C as an input to v . Here, the program 
 first searches for an element of list C which can cover at least one of the 
 vector representing the CSPF of v (i.e., some G (v.) =0) which is currently 
 covered by an essential 1 belonging to one of the original inputs to v . If 
 
 such an input is found, it is assigned the label v , and the program proceeds 
 
 e 
 
 to block 21. If no v can be chosen, this implies that there can be no further 
 replacements of original inputs to v, by elements of list C. In this case, the 
 program searches list C one last time looking for elements which cover at least 
 one G ( v i) = which is currently covered only by the remaining original inputs 
 
 C K. 
 
 to v (i.e., which is not covered by any of the newly connected functions). The 
 group of elements satisfying this criterion are connected to v (unnecessarily 
 added connections will be removed later in block 5) , and control goes to block 
 23. 
 
 Block 20 was discussed as part of block 19. 
 
44 
 
 In block 21 the selected v is connected to v, . 
 e k 
 
 This connection requires the reordering of list L and the removal of 
 v from list C. This is done in block 22 . The program then returns to block 
 13 to try again to find an element of list L which can be replaced by an ele- 
 ment of list C. This may now be possible although it was impossible before 
 
 the connection of v to v, . 
 
 e k 
 
 In block 23 the assignment of covers is made for v. ' s still feeding 
 
 v (this corresponds to Step (5) of Procedure NTCD) . In other words, for each 
 
 (d) t 
 
 G (v ) =0, one of the v. eIP(v ) covering that is selected. Input v is 
 
 C K. IK. X 
 
 then required to produce a 1 output for that 0. This is done by setting G (v.) 
 to the value 1. Although other covers (from other v eIP(v, )) may exist for 
 
 1 K 
 
 that same G (v ) =0, they are not "required" in the same sense as the cover 
 
 C_ K. 
 
 provided by the selected gate. 
 
 Although the program allows the user a choice of several different 
 methods of assigning covers, perhaps the most useful assigns covers in the fol- 
 lowing manner: For each d such that G (v. ) =0, covers are preferred in the 
 
 c k 
 
 order: (1) if for some v. eIP(v.), G (v.) =1 already, no cover need be as- 
 
 i k c i 
 
 signed; (2) otherwise, if for some v eIP(v ) f) V-r, f (v.) = 1, set 
 
 G (d) (v.) =1; (3) otherwise if for some v. elP^ ) f) V_, f '(v.) = 1 and v is 
 ex l k (j l i 
 
 a newly added input to v , set G (v.) =1; (4) otherwise, there must exist 
 
 K. OX 
 
 some v eIP(v, ) D V such that f (v.) =1 and v. does not fall in any of the 
 i k G ii 
 
 three preceding categories, so set G^ CO =1. If any "ties" occur within 
 any of the latter three categories, set G (v ± ) =1 for the v ± (among those 
 satisfying the conditions of that category) first appearing in the sequence 
 G0RDER(1) ,G0RDER(2) , . . . ,G0RDER(n) . 
 
 This calculation will give a slightly different result than the method 
 presented in Step (5) of Procedure NTCD. First of all, it employs the suggested 
 
 tNote that the set Ip (v,) may differ from IP(v ) before entering block 9, 
 
45 
 
 change to Step (5) found in the last two paragraphs of Section 3. Secondly, 
 although the ordering r is not explicitly employed, external variable covers 
 are preferred to gate covers during the calculation. 
 
 After all of the covers for v have been selected and assigned, re- 
 
 K. 
 
 quired components (g (v.) =0) of the CSPF vectors of the immediate prede- 
 cessors of v must be determined and assigned. This is simply done: for every 
 
 d such that G ( (v, ) =1, set G ( (v.) =0 for every v. eIP(v.). 
 c k c i l k 
 
 The completion of block 23 also means the completion of block 9, and 
 the execution of the program moves into block 3 of Fig. 5.1.1. 
 
 In Fig. 5.1.3 is shown an example of the effect of using Procedure 
 NTCD to transform and simplify a given network. Procedure NTCD is applied 
 three times to a network, yielding the same effect as executing the program 
 NETTRA-G1 three times using the output of one execution as the input to the 
 next. 
 
 The original network, too large to be pictured, is displayed in table 
 form in Fig. 5.1.3(a). It consists of 25 gates and 105 connections. The 5- 
 variable function realized by this network is: f (x.. ,x ,x~,x, ,x,-) = 
 
 11111111011010001010000111110011). This network 
 was generated to realize this function by a simple synthesis method which does 
 not attempt to minimize the number of gates in the network produced. Thus, con- 
 siderable redundancy (in the sense of an excessive number of gates and connec- 
 tions) exists in the original network. 
 
 Applying Procedure NTCD to this original network produces the network 
 configuration shown in Fig. 5.1.3(b). This network consists of only 11 gates 
 and 39 connections, and it is produced in just 1.54 seconds by a F0RTRAN IV (H) 
 implementation of Procedure NTCD run on an IBM 360/75 computer. 
 
46 
 
 Fig. 5.1.3 Example of a network transformed by Procedure NTCD as implemented 
 in NETTRA-G1. 
 
 LEVEL GATES OR EXTERNAL VARIABLES 
 OF v. FEEDING v. 
 
 GATE 
 
 V i 
 
 V 6 
 
 V 7 
 
 V 8 
 
 V 9 
 
 v io 
 
 V ll 
 
 V 12 
 
 V 13 
 
 V 14 
 
 V 15 
 
 V 16 
 
 V 17 
 
 V 18 
 
 V 19 
 
 V 20 
 
 V 21 
 
 v 
 22 
 
 V 23 
 
 V 24 
 
 V 25 
 
 V 26 
 
 V 27 
 
 V 28 
 
 v 
 29 
 
 v 
 
 30 
 
 V 8 V 12 
 
 V 15 
 
 V 17 
 
 V 20 V 22 V 24 ' 
 
 X 1 X 2 
 
 X 3 
 
 X 4 
 
 X 5 
 
 X 1 X 3 
 
 X 4 
 
 X 5 
 
 V 7 
 
 X l X 2 
 
 X 3 
 
 
 
 X l X 3 
 
 X 4 
 
 
 
 X l X 3 
 
 X 5 
 
 
 
 X 1 X 3 
 
 V 9 
 
 v io 
 
 V ll 
 
 X l X 2 
 
 X 5 
 
 
 
 X 1 X 4 
 
 X 5 
 
 
 
 X 1 X 5 
 
 V ll 
 
 v 13 
 
 V 14 
 
 X 1 X 2 
 
 
 
 
 x i v io 
 
 V ll 
 
 V 14 
 
 V 16 
 
 X l X 2 
 
 X 3 
 
 X 4 
 
 
 x 2 x 3 
 
 X 4 
 
 X 5 
 
 
 x 2 x 3 
 
 X 4 
 
 V 18 
 
 V 19 
 
 x 2 x 3 
 
 X 5 
 
 
 
 X 2 X 3 
 
 V 9 
 
 V 18 
 
 V 21 
 
 X l X 2 
 
 X 4 
 
 
 
 X 2 X 4 
 
 V 19 
 
 V 23 
 
 
 X l X 2 
 
 X 4 
 
 X 5 
 
 
 x 2 x 5 
 
 V 13 
 
 V 19 
 
 V V 
 
 21 25 
 
 X 3 X 4 
 
 X 5 
 
 
 
 X 4 X 5 
 
 V 14 
 
 V 25 
 
 V 27 
 
 X 3 X 4 
 
 
 
 
 vvvvvvvvvv 
 8 12 15 17 20 22 24 26 28 30 
 
 3 
 2 
 3 
 3 
 3 
 2 
 3 
 3 
 2 
 3 
 2 
 3 
 3 
 2 
 3 
 2 
 3 
 2 
 3 
 2 
 3 
 2 
 3 
 
 2 X 4 V 14 V 23 V 25 V 29 
 
 f(x r x 2 ,x 3 ,x 4 ,x 5 ) = (1111 1111 0110 1000 1010 0001 1111 0011) 
 (a) Original network consisting of 25 gates and 105 connections. 
 
hi 
 
 (t>) Network after first application of Procedure NTCD. Network consists of 
 11 gates and 39 connections; elapsed time is l.^k seconds. 
 
1+8 
 
 x. 
 
 X. 
 
 X, 
 
 (c) Network after second application of Procedure NTCD. Network consists of 
 10 gates and 36 connections; elapsed time from the beginning of the first 
 application is 1.84 seconds. 
 
49 
 
 Applying the procedure to this new network produces the further im- 
 proved network in Fig. 5.1.3(c). This network has 1 less gate and 3 fewer con- 
 nections. The additional computation time required is only .30 seconds. 
 
 An application of Procedure NTCD to this third network produces no ad- 
 ditional improvement (i.e., no reduction in the numbers of gates or connections) 
 in the network. The computation time used for this last step is .30 seconds. 
 
 It is not known whether a network of 9 or fewer gates can be synthe- 
 sized to realize the output function of this network. However, a network of 10 
 gates with only 33 connections is known which produces the same function. 
 
 5.2 A Program Realizing Procedure NTCDG 
 
 In the program NETTRA-G2, it is again the subroutine PR0CII which es- 
 sentially realizes Procedure NTCDG. The specification of appropriate parameters 
 at the time of calling PR0CII determines whether the subroutine will execute 
 Procedure NTCD, Procedure NTCDG, or a third procedure (not discussed here). 
 
 Subroutine PR0CII will execute Procedure NTCDG for the gate v (of 
 Step (0) of the procedure) specified during the call to the subroutine. Al- 
 though NTCDG only deals with a single v , the program NETTRA-G2 calls PR0CII 
 cyclically for every gate of the network until reaching a point where NR unsuc- 
 cessful calls (i.e., resulting in no improvement) have been made following the 
 last call producing an improved network; it then halts. This corresponds to 
 executing Procedure NTCDG once or more for every v e V r . 
 
 The flowchart of PR0CII as it realizes NTCDG is essentially the same 
 as the flowchart already shown in Fig. 5.1.1 and 5.1.2 for PR0CII as it realizes 
 NTCD. The differences are just in the details of the procedure inside a few 
 blocks of the flowchart. The changes necessary for PR0CII to realize Procedure 
 NTCDG are as follows: 
 
50 
 
 In block 1 T(v ) and S(v ) must be calculated in addition to the 
 
 other operations in this block. 
 
 In block 8, besides testing whether v, e V T or IS(v, ) = i>. v, is 
 k I k k 
 
 also tested to determine if it is a member of T(v ). If v e T(v ), control 
 of the program is sent back to block 3. This is because Steps (4) and (5) of 
 Procedure NTCDG (corresponding to block 9) are not executed for gates in T(v ). 
 
 In block 10 , during the elimination of connections from non-essential 
 inputs to v , the connections from non-essential inputs in S(v )U {v } are re- 
 moved first. 
 
 In block 11 , list C is not permitted to contain the names of any of 
 the inputs in the set S(v )(J ^ v ^' Thus, new connections may only come from 
 T(v )or V . (This corresponds to a similar restriction in Step (4-1) of the 
 procedure) . 
 
 In block 18 , as in block 10, when it is necessary to eliminate con- 
 nections from non-essential inputs to v , connections from inputs in 
 S(v ) U {v } are removed first. 
 
 In block 23 , covers are preferred in the order; (1) if, for some 
 v. e IP(v ), G (v.) = 1 already, no cover need be assigned; (2) otherwise, 
 if for some v. e IP(v ) DV , f (d '(v ) = 1, set G* d '(v.) = 1; (3) otherwise, 
 
 1 K. X X CI 
 
 if for some v. e IP(v, )flv f (d) (v.) = 1, and v. e T(v„), set G (d) (v.) = 1; 
 l kG i ix ci 
 
 (4) otherwise, there must exist some v. e IP(v )flV such that f (v ) = 1 
 
 X K. \j X 
 
 and v. e S(v„)U {v„}, then set G (vj = 1. Ties are broken as before, ac- 
 
 l £ £ c i 
 
 + 
 cording to G0RDER . 
 
 These are the only changes necessary to convert the previously given 
 explanation of the flowchart (in Fig. 5.1.1 and 5.1.2) for NTCD into an ex- 
 planation of the same flowchart as it realizes NTCDG. There are, however, 
 
 tActually the program uses another ordering, R0RDER (related to G0RDER) to assign 
 covers and break ties. However, the effect is identical to the above procedure 
 using G0RDER to break ties. 
 
51 
 
 again some differences between Procedure NTCDG as it is specified and Procedure 
 NTCDG as it is programmed. These differences are much the same as those between 
 Procedure NTCD and its corresponding program. 
 
 Step (4-1) of the procedure connects every connectable v e T(v ) U V T 
 to gate v . Then Steps (4-2), (4-3), and (4-4) are used to disconnect the non- 
 essential inputs from v, , preferring to remove connections from gates in 
 S(v ) U {v } first. This is not explicitly done in block 9 although the end re- 
 sult is the same. Block 9 first adds connections to v, (from v. e T(v„)L)V T ), 
 
 k i it I 
 
 one at a time and as many as necessary, to eliminate the greatest possible num- 
 ber of original inputs to v (actually, eliminating as many inputs as possible 
 from gates in S(v ) U {v } is sufficient). And then, in sub-block 19 of block 9, 
 more input connections are added to v, so as to provide covers (from T(v.)UV ) 
 for as many O-components of the CSPF vector G (v ) as possible that are currently 
 covered only by the remaining original inputs (actually, "covered only by gates 
 
 in S(v„) U {v^}" is sufficient) to v, . 
 
 £ £ k 
 
 As in NETTRA-G1, NETTRA-G2 does not calculate G (c..)'s. It calculates 
 the G (v.)'s directly, again as in NETTRA-G1. And also, the suggestion in the. 
 last two paragraphs of Section 3 is incorporated into the realization of Step- 
 (5) of NTCDG (block 23 of the flowchart). 
 
 By setting a certain parameter (called LFLAG) in the call to PR0CII, 
 block 8 will not return control to block 3 for a v e T(v ) as specified by the 
 algorithm. In such a case (caused by setting LFLAG=0) , CSPF's will be calcu- 
 lated for every gate in the network. Of course, this consumes more computation 
 time and frequently produces a different result than the normal case (specified 
 
 by LFLAG=1) where CSPF's are only calculated for v, e S(v„). 
 
 k £ 
 
 Section 5.3 will compare results obtained by Procedure NTCDG used in 
 both of these modes (i.e., LFLAG=0 and LFLAG=1) . 
 
 The final two differences that will be mentioned are the fact that 
 
52 
 
 Fig. 5.2.1 Example of a network transformed by Procedure NTCDG as 
 implemented in NETTRA-G2. 
 
 x. X l 
 
 x i 3== 
 *+ x^ 
 
 S(v ? ) U (v 7 l 
 T(v ) 
 
 X„ 
 
 Xi 
 
 connections 
 which will 
 be replaced 
 by NETTRA-GZ 
 
 a) Original network consisting of 17 gates and 56 connections 
 
53 
 
 connections 
 added by 
 NETTRA-G2 to 
 enable the 
 removal of 
 v^ 
 
 (b) Network after transformation by Procedure NTCDG. Network consists of 
 16 gates and 51 connections. 
 
54 
 
 Step (4-2) of NTCDG is not implemented in the program and order r is not used 
 in the implementation of Step (5). Although order r is not used in the assign- 
 ment of covers, it can be seen that the method actually employed produces ap- 
 proximately the same end result. 
 
 An example of a transformation by Procedure NTCDG is shown in Fig. 
 5.2.1. The original network appearing in Fig. 5.2.1(a) consists of 17 gates, 
 and the transformed network pictured in Fig. 5.2.1(b) consists of only 16 gates. 
 Suppose gate v is chosen as v for Procedure NTCDG. Then the subnet- 
 work (S(v )U {v.,} consists of the gates: v , , v.., v n , , v 01 , and v__. T(v.,) is 
 II b / ib ZL ZJ / 
 
 made up of the remaining 12 gates. Procedure NTCDG is able to find outputs or 
 
 combinations of outputs from subnetwork T(v 7 ) to substitute for connections 
 
 from gate v . The connection from gate v to gate v is replaced by a connec- 
 / 7 lb 
 
 tion from gate v . Similarly, the connection from v 7 to v_„ is replaced by a 
 connection from v_ . Lastly, the combination of inputs from gates v and v _ 
 to gate v„ is replaced by a pair of connections from gates v_ 7 and v^. The 
 removal of a connection from the external variable x to gate v _ is actually 
 done by a "clean-up" pruning procedure included in Procedure NTCDG. 
 
 As a by-product of this transformation, gate v „ and gate v~~ in the 
 transformed network have identical sets of inputs, thus allowing the substitution 
 of the output of either gate for the output of the other. Such a substitution 
 would reduce the size of the network to 15 gates 
 
 5.3. Comparison of the Programmed Procedures NTCD and NTCDG . 
 
 To test the speed and effectiveness of the programmed procedures NTCD 
 and NTCDG, redundant networks, each realizing one of thirty randomly chosen 5- 
 variable functions, were created to generate experimental data. 
 
 Table 5.3.1 shows the "cost" (i.e., size) of each of these original 
 networks and the costs of each of the transformed networks produced by the 
 
55 
 
 respective procedures. The computation times required to obtain the transformed 
 networks are also displayed. The notation used to show network cost is "a:b" 
 where a is the number of gates and b is the number of connections in the network. 
 The computation times are all given in seconds. 
 
56 
 
 Table 5.3.1 Comparison of solution costs and computation times of three pro- 
 grammed transduction procedures for thirty functions of five variables. 
 
 Fn. 
 No. 
 
 Cost of 
 Initial 
 Network 
 
 NTCD 
 
 NTCDG 
 
 (CSPF's calc. 
 
 for S(v ) only) 
 
 NTCDG 
 (CSPF's calc. 
 for all gates) 
 
 Cost 
 
 Time 
 (sec. ) 
 
 Cost 
 
 Time 
 (sec. ) 
 
 Cost 
 
 Time 
 (sec.) 
 
 1 
 
 26:102 
 
 15:45 
 
 2.12 
 
 14:42 
 
 5.75 
 
 14:43 
 
 6.38 
 
 2 
 
 25:100 
 
 14:45 
 
 2.08 
 
 14:45 
 
 5.58 
 
 14:45 
 
 6.94 
 
 3 
 
 25:105 
 
 10:36 
 
 2.05 
 
 11:34 
 
 3.98 
 
 11:34 
 
 4.18 
 
 4 
 
 17:65 
 
 12:39 
 
 .87 
 
 12:34 + 
 
 1.42 
 
 12:34 + 
 
 2.97 
 
 5 
 
 22:92 
 
 11:39 
 
 1.79 
 
 11:36 
 
 2.75 
 
 11:36 
 
 3.38 
 
 6 
 
 18:81 
 
 9:31 
 
 .92 
 
 9:31 
 
 1.20 
 
 9:31 
 
 1.99 
 
 7 
 
 25:100 
 
 12:40 
 
 1.97 
 
 12:40 
 
 3.85 
 
 12:40 
 
 4.43 
 
 8 
 
 21:86 
 
 11:34 
 
 1.09 
 
 12:31 
 
 1.72 
 
 12:31 
 
 3.18 
 
 9 
 
 22:85 
 
 13:43 
 
 1.27 
 
 13:41 
 
 5.30 
 
 13:41 
 
 6.34 
 
 10 
 
 26:106 
 
 13:39 
 
 2.55 
 
 12:37 
 
 4.70 
 
 12:37 
 
 4.33 
 
 11 
 
 27:113 
 
 17:53 
 
 3.16 
 
 15:49 
 
 5.26 
 
 15:49 
 
 8.62 
 
 12 
 
 20:85 
 
 10:36 
 
 1.26 
 
 11:34 
 
 3.08 
 
 11:34 
 
 4.05 
 
 13 
 
 26:110 
 
 15:49 
 
 2.66 
 
 15:48 
 
 4.48 
 
 14.46 
 
 7.18 
 
 14 
 
 27:115 
 
 15:45 
 
 1.99 
 
 14:43 
 
 5.68 
 
 14:43 
 
 6.84 
 
 » 
 
 24:104 
 
 10:29 
 
 1.44 
 
 10:29 
 
 1.69 
 
 10:29 
 
 2.62 
 
 tnetwork derived solely by pruning procedure contained in NETTRA-G2 
 
57 
 
 Fn. 
 
 n4. 
 
 Crfst c^f 
 
 Initial 
 Network 
 
 NTCD 
 
 NTCDG 
 
 (CSPF's calc. 
 
 Hr S( Vjl ) rfnly) 
 
 NTCDG 
 (CSPF's calc. 
 f^r all gates) 
 
 C«5st 
 
 Time 
 (sec) 
 
 C«5st 
 
 Time 
 (sec. ) 
 
 C«5st 
 
 Time 
 (yec) 
 
 16 
 
 27:111 
 
 13:44 
 
 1.97 
 
 13:39 
 
 5.23 
 
 13:39 
 
 8.34 
 
 17 
 
 20:90 
 
 12:45 
 
 1.30 
 
 13:42 
 
 3.77 
 
 13:42 
 
 8.84 
 
 18 
 
 24:98 
 
 12:38 
 
 1.74 
 
 12:37 
 
 2.97 
 
 12:36 
 
 3.78 
 
 19 
 
 26:104 
 
 10:27 
 
 1.61 
 
 11:27 
 
 2.17 
 
 10:27 
 
 3.20 
 
 20 
 
 25:103 
 
 15:46 
 
 2.35 
 
 14:43 
 
 7.93 
 
 15:45 
 
 10.60 
 
 21 
 
 23:82 
 
 14:43 
 
 1.34 
 
 15:41 
 
 2.68 
 
 14:37 
 
 6.86 
 
 22 
 
 25:102 
 
 17:53 
 
 2.59 
 
 16:50 
 
 6.23 
 
 16:50 
 
 10.57 
 
 23 
 
 25:94 
 
 15:47 
 
 1.81 
 
 15:43 
 
 3.65 
 
 15:42 
 
 8.46 
 
 24 
 
 24:102 
 
 14:41 
 
 2.01 
 
 13:39 
 
 4.33 
 
 13:39 
 
 5.83 
 
 25 
 
 19:76 
 
 11:31 
 
 1.07 
 
 12:31 
 
 2.17 
 
 12:31 
 
 4.02 
 
 26 
 
 19:77 
 
 13:39 
 
 1.07 
 
 13:39 
 
 2.95 
 
 13:39 
 
 4.56 
 
 27 
 
 23:97 
 
 12:33 
 
 2.22 
 
 11:31 
 
 3.37 
 
 11:31 
 
 3.85 
 
 28 
 
 22:87 
 
 13:41 
 
 1.26 
 
 13:41 
 
 3.98 
 
 13:41 
 
 4.61 
 
 29 
 
 27:117 
 
 14:48 
 
 2.76 
 
 14:42 
 
 3.42 
 
 13:42 
 
 6.29 
 
 30 
 
 24:93 
 
 15:46 
 
 2.72 
 
 14:45 
 
 4.38 
 
 14:45 
 
 8.46 
 
58 
 
 The thirty 5-variable functions realized by the networks are listed in 
 Table 5.3.2 in hexadecimal notation where each character represents 4 binary bits. 
 For example, function number 1, expressed as 4FA295F6 in the table, expands to 
 (0 1001111101000101001010111110110) 
 
 - I ^X.. , X_ , ^o* ^A ' ^c'* 
 
 For the comparison, Procedure NTCD was applied repetitively starting with 
 an initial network until no further improvements occurred between one application 
 and the next. Procedure NTCDG, however, is automatically iterated in NETTRA-G2 
 and thus did not require programming changes for multiple applications. 
 
 Procedure NTCDG was used in both of the two different modes mentioned 
 in Section 5.2. In one mode, Procedure NTCDG calculates CSPF's and rearranges in- 
 put connections only for gates in the subnetwork S(v ) (where v is the gate fo~ 
 cused on for removal). In the other mode, this is done for all gates of the net- 
 work. 
 
 Table 5.3.3 lists some statistics derived from the results of Table 
 5.3.1. Networks derived by NTCD used a total of 387 gates. This is three more 
 gates than NTCDG (S(v )) required and six more than NTCDG (all). 
 
 To complete transductions of all thirty original networks, the total 
 times required by NTCD, NTCDG (S(v )), and NTCDG (all) were 55, 116, and 172 seconds 
 respectively. It is interesting to note that these times are very close to the 
 proportions: 1 to 2 to 3. It should be mentioned that the times shown are approxi- 
 mately + 10%. 
 
 The row labeled "number of best solutions" shows the number of times 
 each procedure obtained a solution with a cost no greater (in terms of gates, pri- 
 marily, and connections, secondarily) than either of the other two. The row la- 
 beled "number of exclusive best solutions" gives the number of times each proce- 
 dure obtained a solution with a lower cost than either of the other two. 
 
 tFor convenience, let NTCDG (S(v )) and NTCDG (all) refer to Procedure NTCDG used in 
 these two modes, respectively. 
 
59 
 
 Fn. 
 
 Hexadecimal 
 
 Fn. 
 
 Hexadecimal 
 
 Fn. 
 
 Hexadecimal 
 
 N<rf. 
 
 Expression 
 
 Nj{. 
 
 Expression 
 
 N«J. 
 
 Expression 
 
 1 
 
 4FA295F6 
 
 11 
 
 7A871D71 
 
 21 
 
 113E52C2 
 
 2 
 
 A6CDDF18 
 
 12 
 
 AE47BF9F 
 
 22 
 
 960D65C8 
 
 3 
 
 FF68A1F3 
 
 13 
 
 AB9569A2 
 
 23 
 
 1D4C022D 
 
 4 
 
 1EE65240 
 
 14 
 
 88B749B4 
 
 24 
 
 A68E9866 
 
 5 
 
 9E63BE7F 
 
 15 
 
 49C13031 
 
 25 
 
 A8AA5CE8 
 
 6 
 
 0A888103 
 
 16 
 
 96B036A5 
 
 26 
 
 B42A97A8 
 
 7 
 
 49F363CD 
 
 17 
 
 686F271F 
 
 27 
 
 D58A9F11 
 
 8 
 
 8B5809F0 
 
 18 
 
 5B23D763 
 
 28 
 
 4D16B414 
 
 9 
 
 BFD6C6DA 
 
 19 
 
 858EC1CB 
 
 29 
 
 DA182E51 
 
 10 
 
 C6E7103E 
 
 20 
 
 D542DA86 
 
 30 
 
 395722CD 
 
 Table 5.3.2 The thirty 5-variable functions used in experiments, 
 
60 
 
 
 NTCD 
 
 NTCDG 
 (CSPF's calc. 
 fOr S(v £ ) Only 
 
 NTCDG 
 (CSPF'c calc. 
 fOr all gates) 
 
 total number 
 Of gates 
 
 387 
 
 384 
 
 381 
 
 tOtal number 
 Of connections 
 
 1,225 
 
 1,164 
 
 1,159 
 
 tOtal time 
 (in seconds) 
 
 55.04 
 
 115.67 
 
 171.70 
 
 avg. number 
 Of gates 
 
 12.90 
 
 12.80 
 
 12.70 
 
 avg . number 
 Of cOnnectiOns 
 
 40.8 
 
 38.8 
 
 38.6 
 
 avg. time 
 (in secOnds) 
 
 1.83 
 
 3.86 
 
 5.72 
 
 number Of 
 best sOlutiOns 
 
 12 
 
 19 
 
 23 
 
 nO. Of exclusive: 
 best sOlutiOns 
 
 5 
 
 2 
 
 5 
 
 nO. Of times 
 fewest gates 
 
 19 
 
 21 
 
 24 
 
 nO. times exclu- 
 sive fewest gates 
 
 5 
 
 1 
 
 2 
 
 Table 5.3.3 Statistics comparing results by programmed implementations 
 of three transduction procedures on thirty networks realizing functions 
 of five variables. 
 
61 
 
 Similarly, the row labeled "number of times fewest gates" displays 
 the number of times each procedure obtained a network with a number of gates 
 no larger than either other procedure, and the row labeled "number times ex- 
 clusive fewest gates" tells the number of times each procedure derived a 
 network with fewer gates than either of the other two. 
 
 It can be seen, that while the results improve in general going 
 from NTCD to NTCDG(S(v )) to NTCDG(all), a heavy price must be paid in compu- 
 tation time for a relatively small improvement in results. 
 
 It is acknowledged that more reliable conclusions could be drawn if 
 the computational experience comparing Procedures NTCD, NTCDG(S(v )), and 
 NTCDG(all) had been more extensive (e.g., including more functions and using 
 different original network types, different numbers of external variables, or 
 multiple output networks). However, from the available statistics, it seems 
 wise to first use Procedure NTCD on a network to be transformed, followed by 
 the use of Procedure NTCDG(all). 
 
 In general, the repetitive application of Procedure NTCD would quickly 
 eliminate some (relatively) easily removable gates and connections from a given 
 redundant network. Then Procedure NTCDG(all), which is slower, but apparently 
 more powerful, could be used in an attempt to further reduce the network al- 
 ready transformed by Procedure NTCD. 
 
62 
 
 6. CONCLUDING REMARKS 
 
 In this paper, several network transduction proce- 
 dures based on connectable and disconnectable conditions were 
 discussed. Even if a certain transduction procedure does not 
 reduce the cost of a given network, just an alteration of the 
 network's configuration may be helpful by permitting the fur- 
 ther application of other known network transduction proce- 
 dures. 
 
 Further modified versions of Procedure RI can also 
 be made. One important application of such a modified version 
 is in the synthesis of NOR networks under fan-in and fan-out 
 restrictions. This topic will be further discussed elsewhere. 
 
63 
 
 REFERENCES 
 
 [1] 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, 
 Dept. of Comp. Sci. , Univ. of 111., Urbana, 111., Jan. 1969. 
 
 [2] J.N. Culliney, "Program manual: NOR network transduction based on con- 
 nectable and disconnectable conditions (Reference manual of NOR network 
 transduction programs NETTRA-G1 and NETTRA-G2)," Report No. UIUCDCS-R- 
 74-698, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Feb. 1975. 
 
 [3] J.N. Culliney, H.C. Lai, and Y. Kambayashi, "Pruning procedures for NOR 
 networks using permissible functions (Principles of NOR network trans- 
 duction programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2)," Report No. 
 UIUCDCS-R-74-690, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., 
 Nov. 1974. 
 
 [4] Y. Kambayashi and J.N. Culliney, "NOR network transduction procedures 
 based on connectable and disconnectable conditions (Principles of NOR 
 network transduction programs NETTRA-G1 and NETTRA-G2)," Report No. 
 UIUCDCS-R-75-732, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., 
 June 1975. 
 
 [5] Y. Kambayashi and S. Muroga, "Network transduction based on permissible 
 functions (General principles of NOR network transduction NETTRA pro- 
 grams)," to appear as a report, Dept. of Comp. Sci., Univ. of 111., 
 Urbana, 111. 
 
 [6] H.C. Lai, "Program manual: NOR network transduction by generalized 
 
 gate merging and substitution (Reference manual of NOR network trans- 
 duction programs NETTRA-G3 and NETTRA-G4)," Report No. UIUCDCS-R-75- 
 714, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., Apr. 1975. 
 
 [7] H.C. Lai and J.N. Culliney, "Program manual: Nor network pruning pro- 
 cedures using permissible functions (Reference manual of NOR network 
 transduction programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2)," Report 
 No. UIUCDCS-R-74-686, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., 
 Nov. 1974. 
 
 [8] H.C. Lai and Y. Kambayashi, "NOR Network Transduction by Generalized 
 Gate Merging and Substitution Procedures (Principles of NOR Network 
 Transduction Programs NETTRA-G3 and NETTRA-G4)", Report No. UIUCDCS- 
 R-75-728, Dept. of Comp. Sci., Univ. of 111., Urbana, 111., June 1975. 
 
 [9] T. Nakagawa and H.C. Lai, "A branch-and-bound algorithm for optimal 
 NOR networks (The algorithm description)," Report No. 438, Dept. of 
 Comp. Sci., Univ. of 111., Urbana, 111., Apr. 1971. 
 
 [10] T. Nakagawa and H.C. Lai, "Reference manual of FORTRAN program ILLOD- 
 (NOR-B) for optimal NOR networks," Report No. UIUCDCS-R-71-488, Dept. 
 of Comp. Sci., Univ. of 111., Urbana, 111., Dec. 1971. 
 
BIBLIOGRAPHIC DATA 
 SHEET 
 
 1. Report No. 
 
 UIUCDCS-R-76-8U1 
 
 3. Recipient'* Accession No. 
 
 4. Title and Subtitle NQR NETWORK TRANSDUCTION PROCEDURES BASED ON 
 CONNECTABLE AND DISCONNECTABLE CONDITIONS (Principles of NOR 
 Network Transduction 
 Programs NETTRA-G1 and NETTRA-G21 
 
 5. Report Dste 
 12/13/76 
 
 UIUCDCS-R-T^-S^l 
 
 7. Author(s) 
 
 Y. Kambayashi and J.N. Culliney 
 
 8- Performing Organization Rept. 
 No. 
 
 9. Performing Organization Name and Address 
 
 Department of Computer Science 
 
 University of Illinois at Urbana-Champaign 
 
 Urbana, Illinois 61801 
 
 10. Project/Taslc/Work Unit No. 
 
 11. Contract /Grant No. 
 
 NSF Grant No.DCR73- 
 
 12. Sponsoring Organization Name and Address 
 
 National Science Foundation 
 1800 G Street, N.W. 
 Washington, D.C. 
 
 13. Type of Report & Period 
 Covered 
 
 Technical 
 
 14. 
 
 15. Supplementary Notes 
 
 16. Abstracts 
 
 In a previous paper the concept of compatible sets of permissible functions 
 (CSPF's) was introduced and simplification procedures for networks of NOR gates were 
 given based on this concept. These procedures are called NOR-network transduction 
 (trans formation and r eduction ) procedures. 
 
 Here, compatible sets of permissible functions are used to express conditions 
 under which new connections or disconnections may be made in an existing network of NOR 
 gates. Using these connectable and disconnectable conditions, a basic network trans- 
 duction procedure is developed. This forms the basis for the development of a more 
 sophisticated and powerful transduction procedure which is discussed along with possible 
 modifications to improve its efficiency and effectiveness. One major modification is 
 presented in detail. 
 
 Two computer programs, NETTRA-G1 and NETTRA-G2, have been created implementing the 
 advanced transduction procedure and its major modification, respectively. 
 
 17. Key Words and Document Analysis. 17a. Descriptors 
 
 Logic design, logic circuits, logical elements, programs (computers) 
 
 17b. Identifiers/Open-Ended Terms 
 
 Computer-aided-design, permissible functions, network transduction, network transforma- 
 tion, redundant networks, near-optimal networks, program manual, NOR, NAND, CSPF, 
 NETTRA-G1, NETTRA-G2. 
 
 17c. COSATI Field/Group 
 
 18. Availability Statement 
 
 Release unlimited 
 
 FORM NTIS-3B (10-70) 
 
 19. Security Class (This 
 Report) 
 
 UNCLASSIFIED 
 
 20. Security Class (This 
 Page 
 
 UNCLASSIFIED 
 
 21. No. of Pages 
 
 67 
 
 22. Price 
 
 USCOMM-DC 40329-P7 1 
 
m 1 2 1» 
 
5 84 IL6R no C002 no 841(1976) 
 internal report / 
 
 3 0112 088403222