Hffl 
 
 nraU 
 
 H 
 
 ■ 
 
Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/pruningprocedure690cull 
 

 /yu^* 
 
 PRUNING PROCEDURES FOR NOR 
 NETWORKS USING PERMESSIBLE FUNCTIONS 
 (Principles of NOR network transduction 
 programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2) 
 
 by 
 
 November 197^ 
 
 J. N. Culliney 
 
 H.C. Lai 
 Y . Kambayashi 
 
 The Llbrarv rf 
 
 1 fte 
 
 jf\n i 
 
 ,19(5 
 
UIUCDCS-R-7^-690 
 
 PRUNING PROCEDURES FOR NOR 
 NETWORKS USING PERMISSIBLE FUNCTIONS 
 (Principles of NOR network transduction 
 programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2) 
 
 by 
 
 J. N. Culliney 
 
 H.C. Lai 
 Y. Kambayashi 
 
 November 197^ 
 
 Department of Computer Science 
 
 University of Illinois at Urbana-Champaign 
 
 Urbana, Illinois 
 
 This work was supported in part by the National Science Foundation under 
 Grant No. GJ-40221. 
 

 H^Co^t) ±±± 
 
 UV9' V 
 
 ABSTRACT 
 
 NOR or HAND gate networks designed by non-optimal achieving 
 means often contain an unnecessary number of gates and/or connections. 
 Such networks can frequently be transformed into networks of reduced 
 numbers of gates and/ or connections (while preserving network outputs) 
 by following transduction [ trans formation and re duction ] procedures 
 discussed in the previous paper [1]. This paper will discuss three 
 such procedures of the "pruning procedure" class of transduction procedures 
 refining the basic ideas discussed in a previous paper [1], Any trans- 
 duction procedure which only has the capability to remove existing connec- 
 tions (and, hence, possibly gates), without being able to create new 
 connections, is classified as a pruning procedure. Although pruning 
 procedures are thus limited in their power, they are generally simpler 
 and more quickly executed than more powerful types of transduction 
 procedures. 
 
 Of the three pruning procedures discussed in this paper, the 
 first is based on the concept of "Compatible Sets of Permissible Functions" 
 (CSPF's), the second is based on "O-Fixed Maximum Sets of Permissible 
 Functions" (OFMSPF's) for connections, and the third is based on "1-Fixed 
 Maximum Sets of Permissible Functions" (lFMSPF's) for gates. The use of 
 the latter two guarantees single-irredundant networks (i.e., networks in 
 which no single connection alone can be removed without causing an error 
 in the network outputs), while the use of the former does not. The 
 relative advantages of each are discussed. 
 
IV 
 
 KEYWORDS 
 
 Descriptors 
 
 Logic design, logic circuits, logical elements, programs (computers) 
 Identifiers/Open-Ended Terms 
 
 Computer-aided-design, permissible functions, network transfor- 
 mation, pruning, redundant networks, S-irredundant networks, NOR, NAND, 
 MSPF, CSPF, 1FMSPF, OFMSPF 
 
V 
 
 TABLE OF CONTENTS 
 
 Page 
 
 1. INTRODUCTION 1 
 
 2 . PRUNING PROCEDURE BASED ON CSPF CALCULATION k 
 
 2 . 1 The Modified Procedure 5 
 
 2 . 2 Computer Program and Example 19 
 
 3. PRUNING PROCEDURES BASED ON NECESSARY AND 
 
 SUFFICIENT CONDITIONS 31 
 
 k. EXPERIMENTS k2 
 
 5. CONCLUSIONS V7 
 
 REFERENCES ^9 
 
1. INTRODUCTION 
 
 Networks which are designed by procedures known in switching 
 theory and/ or further transformed by more recently developed transformation 
 procedures are generally not optimal. In [l], network simplification 
 procedures of any given networks based on permissible functions are intro- 
 duced. These "transduction" ( Transf ormation and Re duction ) procedures can 
 remove connections and/ or gates efficiently. 
 
 A (group of) connection (s) is said to be redundant if no network 
 outputs change (of course unspecified components can change) as a result of 
 removing it. A procedure to remove such redundant connections without 
 creating new connections is called a pruning procedure . (Thus a resultant 
 network is always a subnetwork of the original.) A single connection is 
 said to be single -redundant (or S -redundant ) if no specified network outputs 
 change as a result of removing it alone. A network without any S-redundant 
 connections is called an S-irredundant network . By comparing the outputs 
 of the original network with the outputs of a network without a particular 
 connection we can easily determine whether or not this connection is redun- 
 dant. This procedure is simple but time-consuming. In this paper, instead 
 of such a simple-minded procedure, more efficient pruning procedures using 
 permissible functions [l] are discussed. Also, in this paper, two new sub- 
 sets, a 1-fixed maximum set of permissible functions (lFMSPF) and a O-fixed 
 minimum set of permissible functions (OFMSPF), of an MSPF will be defined 
 for pruning procedures. 
 
Each of an NEPF, a 1FMSPF, and a OFMSPF is uniquely defined for 
 each connection in a network. However, a CSPF is not unique. In this 
 paper we develop a procedure to calculate CSPF's which is suitable for 
 pruning procedures and other network transductions. A pruning procedure 
 using CSPF's has the following advantages and disadvantage. 
 
 (a) It requires a shorter calculation time. 
 
 (b) CSPF's are calculated and can be used in further procedures 
 which will be discussed elsewhere. 
 
 (c) Since only a sufficient condition for a redundancy of a 
 connection is used, a redundant connection sometimes can not be 
 detected by the procedure. 
 
 In order to avoid the difficulty of (b), pruning procedures 
 using OFMSPF 's or lFMSPF's will be introduced. These procedures have 
 the following advantage and disadvantage. 
 
 (a) After application of either pruning procedure, an S-irredun- 
 dant network is always obtained. 
 
 (b) Calculation time is longer than the pruning procedure using 
 CSPF ' s . 
 
 A proper combination of these pruning procedures will be a useful 
 procedure. These procedures are programmed in FORTRAN IV. Based on the 
 computer programs implemented, a comparison of the procedures is given. 
 The reference manual for these programs NETTRA-PG1, NETTRA-P1, and 
 NETTRA-P2 is prepared as [2]. 
 
 The procedure to calculate CSPF's developed in this paper can 
 be used in other network transductions which are not discussed in this 
 paper . 
 
 The notations and basic concepts in [1] will be used throughout 
 this paper. 
 
Let W be the total number of connections except connections 
 from output gates to output terminals. The cost of a network is repre- 
 sented by 
 
 AR + BW. 
 
 Here, A and B are cost coefficients. In this paper A = 100 and 
 B=l are chosen. Therefore the reduction of the number of NOR gates is 
 more important than the reduction of the number of connections. 
 
2. PRUNING PROCEDURE BASED ON CSPF CALCULATION 
 
 In the previous paper [1] an elementary procedure to calculate 
 CSPF's was given. Since a set of CSPF's is not unique for a non-trivial 
 given network, it may be possible to find a set of CSPF's which is 
 generally more suitable than most others for use in certain pruning 
 procedures (such as the pruning procedures described in this section) 
 and in certain network transduction procedures (see Section 2.2 of [2] 
 for an example of a network transduction procedure employing a set of 
 CSPF's). In this section, the elementary procedure to calculate a set 
 of CSPF's will be modified in an attempt to generate such desirable sets 
 of CSPF's. 
 
 Generally, the modifications will try to achieve the following 
 two goals : 
 
 (a) choosing a set of CSPF's such that as many CSPF's as 
 possible consist only of O's and *'s 
 
 (b) choosing a set of CSPF's such that each CSPF is generally 
 large (i.e., it contains many elements). 
 
 Achieving the first goal will produce an efficient pruning 
 of the given network since any gate or connection whose CSPF is solely 
 O's and *'s can be safely removed ("pruned") from the network. And, 
 achieving the second goal will likely result in more opportunities for 
 further network transformations (by other procedures). 
 
Both of these goals are desirable in view of an over-all 
 attempt (employing several different types of network transduction 
 procedures )to reduce the cost of a given network; and, in general, 
 striving for one of these goals will likely result in , at least, the 
 partial achievement of the other. However, in cases where these goals 
 become conflicting, goal (a) will be regarded as the primary objective 
 since these modified procedures are, first of all pruning procedures. 
 
 2.1 The Modified Procedure 
 
 The calculation procedure of a set of CSPF's which is proposed 
 in this section is divided into three substeps : the Initialization, 
 the Main Calculation, and the Final Step. These will be described in 
 Sections 2.1.1, 2.1.2, and 2.1.3, respectively. 
 
 2.1.1 Initialization 
 
 The use of the Initialization Step requires the introduction of 
 
 a set of vectors to be used in intermediate steps during the calculation 
 
 of the final set of CSPF's. Let I (v.) be an "intermediate vector" for 
 
 c 1 
 
 the calculation of G (v.). The 2 components of each I (v.) will consist 
 
 CI CI 
 
 of *'s, O's, or l's. Originally, for each ^eV^ ^, I c 0^ = * for 
 d= l,2,...,2 n . During the Initialization and Main Calculation Steps, 
 many of these *'s will be changed to l's and O's. Setting any 
 
 jU)/ ) = or 1 will imply that G^(v. ) must be or 1, respectively, 
 c i c 1 
 
 Eventually every I (v.) will be, component -for -component, identical to 
 
 c 1 
 
 (cl), x -(a) 
 
 each desired G^v.) (i.e., eventually, ij dJ (v.) = G^ ; (v.) for every 
 d=l,o..,2 and i = 1, .. . ,n + R). 
 
6 
 
 It is best to think of each I (v.) as merely a vector of *'s, O's 
 and l's rather than a set of functions. This is due to the fact that, 
 whereas a * component appearing in a CSPF vector indicates that both a 
 and a 1 are allowed values in that component position, a * component 
 appearing in a vector I (v.) could have this same meaning or, at times, it 
 could indicate that the required value (*, 0, or l) for that component 
 has not as yet been determined. So, most of the time, the set of functions 
 represented by each I (v. ) is not only not a compatible set of permissible 
 functions, but it is likely not even to be a set of permissible functions. 
 
 As previously stated, the Initialization Step about to be 
 
 ( d ) n 
 
 described will assume that, originally, I ; (v.) = * for d=l,2,..„,2 ; 
 
 i = 1,2, . . . ,n + R. For convenience, the I ' s will be referred to as 
 ' ' c 
 
 intermediate CSPF's (although they may not actually be CSPF's until 
 near the end of the Main Calculation Step) since they are always inter- 
 mediate, component -wise, between the vector (*■*...*) and the vectors 
 representing the respective G 's. 
 
 During the Initialization Step, components of the CSPF's are 
 calculated which are independent of any preference orderings . In other 
 words, no matter what method is used to calculate a set of CSPF's, these 
 components will not vary between one calculated set and another. After 
 this step, these "pre-assigned" components (assigned to the intermediate 
 CSPF vectors) will be used in the next step in order to determine large 
 CSPF's efficiently. 
 
 t Within certain restrictions. For instance, the method must only be 
 a single -pass algorithm. 
 
Three ordering -independent cases exist: 
 
 (a) If a gate v is connected to an output terminal v which 
 
 x R + i 
 
 is required to realize z , then set the initial values 
 lW{T 1 )-.W,d- 1 .2,....f. 
 
 (b) If there exists a gate v. such that the initial value of 
 
 (d) 
 
 I c ^ V i^ iS ls then a11 ° f its in P uts are required to be for this 
 
 component. More formally, if 1^ '(v.) = l. then for all v.€lP(v. ) ,1^ ( Y )=0. 
 
 c 1 j i c v y 
 
 (c) If there exists a gate v. such that the initial value of 
 
 ( d) 
 
 I (v.) is and if there exists only one input connection (from 
 
 a gate or external variable v.) such that f '(v.) = l, then the 
 
 J 3 
 
 d-th component of the intermediate CSPF vector (and, hence, the CSPF 
 
 vector itself) for v. is required to be 1. More formally, if 
 
 l (d) (v.) = 0, v eIP(v. ), u , v r (v) = 0, and f (d) (v.) = l, then I (d) (v.) = L 
 c i j i veIP(v. J ' ,V c j 
 
 v=v. x 
 
 J 
 
 First, complete the computations for case (a). Since the 
 given network is loop-free, there exists at least one gate which is 
 connected only to an output terminal. After (a) all ordering -independent 
 components of the CSPF' s for such gates will be calculated. 
 
 Now define an ordering, r , of gates. This ordering can be 
 defined in any way such that all successors of a gate precede it in the 
 
 ordering. This requirement may be expressed as: If v.eS(v.) and 
 
 v .v.eV" , then r (v. )>r (v.). Now starting with v.=v.(eV ) such that 
 l' i G o v i o ,i i j Cj 
 
8 
 
 r (v.) >r (v) for every other v e V , and proceeding in the order 
 o j o « 
 
 dictated by r , initialize the intermediate CSPF's of the inputs of each 
 
 v as directed in cases (b) and (c) for each gate v. . 
 i ! 
 
 However, since pruning will occur during the Main Calculation 
 (Section 2.1.2) at the same time as CSPF's are being determined, the 
 straight -forward, repeated applications of (b) and (c) would probably produce 
 unnecessary requirements . For example, suppose there is some redundant 
 connection c.. which exists during the Initialization Step, but which will 
 
 J 
 
 later be removed during the Main Calculation Step. Since c.. is in the 
 
 network during the Initialization Step, following the directions of (b) 
 
 ( c\ ) 
 strictly would result in the, perhaps unnecessary, requirement that I '(v.)=0 
 
 (d ) ( d) 
 
 (and, hence, G (v. )=0) for every d such that I (v. )=1 (indicating 
 
 G^ (v. )=l). Furthermore, this unnecessary restriction could propagate into 
 
 the members of P(v.). Note that such restrictions are indeed required if 
 J 
 
 there is to be no pruning of redundant connections from the network, however 
 this is not the case here. 
 
 In order to prevent the occurrence of these unnecessary restrictions, 
 (b) must be modified. 
 
 First, let an essential input to a gate be defined as follows: a 
 gate or external variable v., v.eIP(v. ), is said to be an essential input 
 
 3 J 
 
 G (v. 
 c v 1 
 
 of gate v. with respect to G (v. ) if there exists at least one d, 1<&<2 
 
 for which G^ (v.)=0, y , vf(a)(v)=0, and f ldj (v.)=l. Such a v. is 
 
 V 
 
 "essential" for v. since the removal of the connection, c.. from v. to v. 
 
 would violate the requirement G^ ; (v ) = 0. 
 
 c i 
 
 Since 1^ ^(v.)=0 implies G( d )(v.)=0, the condition in (c) can be 
 c i c i 
 
 conveniently used as a sufficient condition for determining essential inputs, 
 Vy to v\; and, thus, (b) can be replaced by the following modification, (b ' ) 
 
(b') If I (v.) = l, then for every v.eIP(v.) for which there exists 
 some d, l<d<2 n , such that I^ d ^(v. )=0, U , ^f^(v)=0, and 
 
 c 
 
 1 V€lP(v i ) 
 
 V^V. 
 
 f (d) (v.) = l, set l (d) (v.) = 0. 
 
 j c y 
 
10 
 
 2.1.2 Main Calculation 
 
 In this step, the rest of the values of the CSPF's (i.e., those 
 not already determined by the Initialization Step) will be calculated. 
 This is accomplished by the following steps: 
 
 (a) Select the gate or external variable v. which is first in 
 
 the ordering r . Remove connections to v. from non-essential inputs. t 
 o 1 
 
 Set G'VO equal to the value of I^(v. ), d=l, 2, ..., 2 n . 
 
 (b) Assign requirements to the intermediate CSPF vectors of v. 's 
 inputs according to the already calculated G (v.). These assignments 
 are of two types: the assignment of "required 0's" (detailed in 
 (b-l)) and the assignment of "covering l's" (detailed in (b-2)). 
 
 (b-l) For each d such that G (v. ) = 1, set I ; (v) = for every 
 
 v€lP(v. ). 
 
 1 
 
 (b-2) For each d such that G (v. ) = 0, choose a "cover" and 
 
 c i 
 
 assign a "covering 1" (if one does not exist already) in the 
 
 following manner. 
 
 (b-2-l) If G^(v. ) = and there exists v.(eIP(v.)) such 
 c i 31 
 
 that the current value of F (v.) = l, then choose 
 
 c 3 
 
 ( d) 
 v. as a cover of G (v. ) = (nothing need be set 
 3 c 1 
 
 since I (v.) is already assigned the value 1. 
 
 (b-2 -2) Otherwise if G^(v. ) =0 and there exists an 
 
 c 1 
 
 external variable v.(eIP(v.)) such that f (v.)=l, 
 
 J ■*■ J 
 
 (d ) 
 then select v . as a cover of G (v,) = and set 
 3 c i y 
 
 i (a) ( T .) = i. 
 
 c 3 
 
 t This must be done under certain restrictions as noted in Section 2.2.1. 
 
11 
 
 \,v.; = w onere exist ga" 
 
 (b-2-3) Otherwise, for G^ ^(v. ) = there exist gates 
 
 v , v , ..., v. (eIP(v. )) such that f (v. ), 
 J l J 2 J k X J l 
 
 . .., f (v ) = 1, then choose v. (l< i< k) as 
 
 J k J £ ~ ~ 
 
 a cover for G^ (v.) = such that I (v ) 
 
 c ^ c h 
 
 currently contains at least as few * components 
 
 as any of v , ..., v. , v. , ..., v. . If 
 J l z l-\ 3 &+l J k 
 
 there is a tie, choose the v with the most 
 
 h 
 
 output connections among those tied. If there 
 is still a tie, choose the v. appearing earliest 
 
 in some ordering r (e.g., r = r or r = the reverse 
 ordering of r ) and satisfying all of the previous 
 conditions (i.e., f (v. ) = 1, I (v. ) has the 
 
 fewest number of * components, and the greatest 
 number of output connections, in the respective 
 
 groups). Set 1^ (v. ) = 1. 
 c ' H 
 
 (c) Select the next gate or external variable, v., in the 
 ordering r . If none remain, the procedure terminates. Otherwise, 
 
 set G (v.) equal to the value of r (v.) for d=l,2,...,2 , remove 
 c v 1 ex 
 
 connections to v. from non-essential inputs, and return to step (b). 
 
12 
 
 At this point, 2 of the 3 main advatages of this modified procedure 
 over the elementary procedure in [1] can "be described (the third advant- 
 age is in the Final Step, described in the next section). 
 
 The first of these advantages is in the use of the intermediate 
 CSPF's. Consider the subnetwork in Fig. 2.1.2.1 (a). Suppose that these 
 k gates are ordered by r in the following way: r(v. ) >r(v. ) >r(yj >r(v ) . 
 
 J 1 Xj K 
 
 Further suppose that CSPF vectors for v. and v. have already been deter- 
 
 mined and that G (v ) and G (v.) have both been assigned the value 0. 
 c j c 1 
 
 Figo 2.1o2.1 (a) shows the situation (for the d-th components) 
 
 just prior to executing step (2) of the elementary procedure or substep 
 
 (b) of the Main Calculation Step of the modified procedure for v.. It 
 
 is assumed that these same steps have just previously been executed for 
 
 fd) 
 
 v., resulting in the requirement G (c .) = 1 (if the elementary procedure 
 J c kj 
 
 is being used) or I (v ) = 1 (if the modified procedure is being used) 
 
 C K 
 
 in order to provide a cover for G (v.) = 0. 
 
 Continuing from this point by the elementary procedure, gate 
 
 Cd ) 
 
 v„ is choosen by the ordering r to cover G (v. ) = 0. This causes the 
 * c i 
 
 assignment of the value 1 to G '(c».) (see Fig. 2.1.2.1 (b)), resulting 
 
 C ' !(/1. 
 
 ( &) 
 
 in G (v») = 1 later in the procedure. 
 
 However, one can see that such an assignment was unnecessary 
 
 since G\Z(c. .) = 1 implies that G^(v. ) must be 1 and, therefore, 
 c kj r c v k ' ' 
 
 ( d.) 
 
 G c (v ) = is actually already covered by v . But the elementary proce- 
 dure is incapable of detecting these "already existing" covers. 
 
13 
 
 level: 
 
 p + 2 
 
 P + l 
 
 (a) Situation preceding 
 calculations for gate 
 
 
 G (d) (v.) = 
 
 c y 
 
 V. . 
 
 1 
 
 (b) Situation following 
 elementary procedure. 
 
 G (d) (c w .) = l 
 c kj 
 
 G (d) (v-) = 
 
 ^ d) (c # J^l 
 
 C Xj-L 
 
 (c) Situation following 
 modified procedure. 
 
 tf^-i 
 
 G (d) (v 
 c 
 
 Fig. 2.1.2.1 Determining components of CSPF vectors, 
 
Ik 
 
 Further notice that the unnecessary assignment of G (c».) = l 
 
 C •&! 
 
 could propagate throughout the members of P(vg). 
 
 Now, again starting at the point of Fig. 2.1.2.1 (a), continue 
 with the modified procedure. This procedure recognizes (in step (b-2-l)) 
 that G (v. ) = can be covered by !P '(v. ) = 1. Therefore no assignment 
 
 C 1 . C K 
 
 is made to I K (vj (so it continues to have the value *), and eventually 
 c & 
 
 G (v/,) will be determined to be *. 
 c So 
 
 For this purpose, the intermediate CSPF's (the I 's) are actually 
 
 (ft ) 
 not required. The examination of I (v ) for every v to a gate v. 
 
 C K 1 
 
 during steps (b-2-2) of the modified procedure could be mimiced (though 
 
 fd ) 
 not in an efficient manner) by examining G (c v .) for every output 
 
 c KJ 
 
 connection c of every input v to a gate v. during step (2) of the 
 
 elementary procedure. However, the intermediate CSPF's are necessary 
 
 in achieving the second advantage of the modified procedure over the 
 
 elementary procedure. 
 
 This second advantage is illustrated in Fig. 2.1.2.2. Assume 
 
 that both the ordering r and r are identical and that r (v. ) >r (v.) > 
 
 & o o v i 7 o K j 
 
 r (v. ) >r (v„). Also assume that G (v.) has already been determined 
 o k o I c i 
 
 and that, due to the network configuration, G (v.) will necessarily be 
 
 c 3 
 
 0. 
 
 Fig. 2.1.2.2 (a) shows the situation just prior to executing 
 step (2) of the elementary procedure or substep (b) of the modified 
 procedure (Main Calculation Step) for v. , assuming there has been no 
 Initialization Step. It is entirely possible that at this point in 
 
15 
 
 level : 
 
 (a) Without initializa- 
 tion, situation proceding 
 calculations for gate 
 v. . 
 
 p + 2 
 
 .(a), 
 
 p + i 
 
 ir<v-* 
 
 G (d) (v.) = 
 c v i y 
 
 
 (b) With initialization, 
 situation preceding calcu- 
 lations for gate v. . 
 
 i< d) <V- 
 
 G (d) (v.) = 
 
 c__ v X 
 
 ;<%>- 
 
 (c) Eventual result by- 
 elementary procedure 
 (or modified procedure 
 without initialization). 
 
 I^ d) (v.) = 
 i d \r k )-l 3 G c d) ^i) = 
 
 *<%) = ! 
 
 G (d) (v.) = 
 
 (d) With initialization, 
 eventual result by 
 modified procedure. 
 
 G< d) (vJ=* 
 
 G (d) (v) = 
 
 C 1 
 
 G< d) (v,) = l 
 
 G (d:, (v.) = 
 
 Fig. 2.1.2.2 Determining components of CSPF vectors using initialized values 
 
16 
 
 the procedure, G^ (v.) is still undetermined (e.g., if r^v^ >r Q (v) > 
 
 r (v ) for every v€lS(v.)). Hence G^ (v ) is also unknown. By the 
 o' j 'J ex, 
 
 (d) 
 ordering r, both the elementary procedure (by the assignment G^ '(v ) = l) 
 
 c Kl 
 
 and the modified procedure without its normal Initialization Step (by 
 
 the assignment 1^ (v, ) = l) would choose the gate v, to cover G^ ( v. ) = 0. 
 D c k k c 1 
 
 ( d ) 
 But later, by assumption G^ (v.) will be found to be 0, and this will 
 
 ( d ) 
 force G ( v n ) = 1, eventually resulting in Fig. 2.1.2.2 (c). 
 c & 
 
 Had an Initialization Step been performed (as is normally done 
 
 in the modified procedure), it would have discovered the necessity of 
 
 1^ Mv.) = and I (v») = 1 (by cases (b) and (c) of the Initialization 
 c D c Ji 
 
 Step, respectively) and initialized these values. In this case, the 
 
 situation would appear as in Fig. 2.1.2.2 (b) just prior to executing 
 
 substep (b) of the Main Calculation Step of the modified procedure. 
 
 This time, due to the initialized value I (vn) = lj substep (b-2-l) 
 
 f d) 
 
 of the Main Calculation Step will choose v as a cover of G (v. ) = 0, 
 
 JO L- J- 
 
 eventually resulting in Fig. 2.1.2.2 (d). 
 
 Once again, it should be noticed that G (v, ) = 1 in Fig. 2.1.2.2 
 
 c k 
 
 (c) is not only unnecessary, but it will likely lead to further unnecessarily 
 small CSPF's for the gates in P(v.). 
 
 2.1.3 The Final Step 
 
 The Final Step is proposed to follow the Main Calculation Step 
 and attempt to further enlarge the CSPF's. This step is best applied to 
 a network from which most of the S-redundancies have already been removed. 
 
17 
 
 This is because, if given the chance, the Final Step could also perform 
 many of the duties of the Main Calculation Step. However, it generally 
 will not perform these as completely or as efficiently as would the Main 
 Calculation Step itself. So, in general, anything that can be done in 
 the Main Calculation Step should not be left for the Final Step. 
 The sub steps of the Final Step are as follows: 
 
 (a) Select the v. which is the first in the ordering r . 
 v ' i o 
 
 (b) For each G^ d ^(v.), d=l, 2,..., 2 n perform the following: 
 (b-l) If G^ d Hv. ) = and G^(v.) / 1 for every v.e IS (v. ), 
 
 C 1 ^ J J 
 
 then set G^(v. ) = 
 
 -* 
 
 (b-2) If G^(v. ) = 1 and G^(v.) = * for every v.elS (v.) 
 
 c 1 c j 
 
 then set G l ; (v.) = *. 
 c 1 
 
 ,(d) 
 
 fb-3) If G^ (v ) = 1 and if for every v. such that v.elS (v.) and 
 v ' c 1 J J x 
 
 G^ (v ) = there exists some v. such that i ^ k, v e IP (v ) , 
 
 C J K K J 
 
 and G( d )(v k ) = l, then set G^ d -\v ± ) = *. 
 
 (c) If there is a v. in IP(v. ) such that for every G K '(v.)=l there 
 
 j l c j 
 
 exists some v fc such that v^IP^), k^j, and G( d )(v k ) = l then 
 remove (i.e., prune) the connection from v to v ± and repeat 
 this step. 
 
 (d) If any connections were removed by step (c), return to Initializa- 
 tion and Main Calculation Steps. 
 
 (e) Select the next gate or external variable in the ordering r Q as the 
 
 new v and return to step (b). If none remain, terminate, 
 i 
 
 Unless pruning occurs in step (c), each of the CSPF's resulting 
 from the Final Step will include or be identical to the corresponding 
 
18 
 
 CSPF's passed to the Final Step from the Main Calculation Step. This 
 is obvious from step (b) where the only changes made to components of 
 the CSPF vectors are to change O's or l's to *'s. This can only "enlarge" 
 the CSPF's and can never "reduce" them. 
 
 If however, pruning does occur in step (c), the entire situation 
 changes. Pruning generally causes the functions realized by various gates 
 to change. This often enables a complete re-evaluation of the CSPF's 
 leading to perhaps further pruning. So immediately following the pruning, 
 it is desirable to return to the Initialization and Main Calculation 
 Steps again (after which the Final Step is also repeated). The reason 
 the unnecessary connections detected in step (c) are pruned by the Final 
 Step itself before returning to the Initialization and Main Calculation 
 Steps (rather than leaving this job for the Main Calculation Step) is 
 that it is entirely possible that the Main Calculation Step (following 
 Initialization) might not detect the unnecessary connections, leading 
 to a possible infinite loop in the algorithm. 
 
 Although the Final Step is perhaps required for the completeness 
 of the CSPF calculation, it is not felt that it is of sufficient benefit 
 in actual computation to justify its required computation time. For 
 this reason, it has not been programmed, and thus it will not be part 
 of the complete computer program discussed in Section 2.2. 
 
 2.1.U Combining the Major Steps 
 
 It has already been mentioned that the occurance of pruning 
 during one complete calculation of the CSPF's often alters the internal 
 operation of a network enough (by changing the output functions of 
 various gates) so that another calculation of CSPF's (beginning with 
 
19 
 
 the newly pruned network) is often beneficial. For example, in one 
 rather extreme case, a network (producing a 5 -variable function) 
 consisting of 33 gates and 310 connetions was reduced to a network of 
 33 gates and 15^ connections by a single application of the Initialization 
 and Main Calculation Steps. However, a second application of these steps 
 (beginning with the 33 gate, 15 U connection network) produced a network 
 of only 12 gates and 3^ connections. Certainly, such a dramatic improve- 
 ment can not be expected to occur in every case, but through actual 
 computational experience, multiple applications of the Initialization 
 and Main Calculation Steps are found to be generally quite worthwhile. 
 
 Also, as noted in the beginning of the previous section, it 
 is best to finish most of the pruning of a network before executing the 
 Final Step. 
 
 Considering both of these points, it is suggested that the 
 Initialization, Main Calculation, and Final Step should be combined 
 in the following manner. Repetitively apply the combination of the 
 Initialization Step followed by the Main Calculation Step until there 
 is no further refinement of the network configuration (i.e., until no 
 further pruning occurs). Then apply the Final Step. If pruning occurs 
 during the Final Step (in substep (c)), return to the Initialization 
 Step and repeat the whole process from the beginning. 
 
 2.2 Computer Program and Example 
 
 This section will describe the modified procedure of Section 
 2.1 as it has actually been programmed. The program to realize this 
 procedure is designated NETTRA-PG1. 
 
20 
 
 The procedure as programmed is somewhat different from the 
 procedure as it was specified in the last section, 2.1. This is due 
 to various reasons: programming convenience, consideration of computation 
 time vs. effectiveness, choosing specific methods where only general 
 methods had been specified, etc. 
 
 NETTRA-PG1 reads in the given network, applies the modified 
 pruning procedure with CSPF calculation, and prints out the resultant 
 network. The necessary details for using NETTRA-PG1 can be found in [2], 
 
 The procedure actually realized by NETTRA-PG1 will now be 
 described in detail, followed by an example of its capability in reducing 
 the cost of a network. 
 
 2.2.1 Program Realizing the Pruning Procedure with CSPF Calculation 
 In the program NETTRA.-PG1, it is the subroutine named MENI2 
 which essentially realizes the pruning procedure. The general flowchart 
 of this subroutine is shown in Fig. 2.2.1„1. 
 
 For simplicity of the explanation, it will continue to be assumed 
 that only n uncomplemented variables are avialable to the network at the 
 input terminalSo This means p=n, and let v. correspond to x. (for i = 1, 
 . . . ,n) . 
 
 Block 1 determines an ordering of gates and external variables 
 and stores it in an array G-OKDER such that for v. =G0RDER(i') and v. = 
 G0RDER(j')j i'<j' means that v. precedes v. in the ordering. The 
 ordering represented by the array GORDER satisfies the condition for an 
 ordering t q as defined in Section 2.1.1. This is done simply by storing 
 the names of the k gates of level 1 (the network output is in level l) 
 in GORDER(l), G0RDER(2), ..., G0RDER(k ) ; the names of the k 2 gates of 
 
21 
 
 ( START J — •» 
 
 FORM GORDER 
 
 (REPRESENTING 
 
 ORDERING r ). 
 o 
 
 Ik 
 
 FOR EACH d SUCH THAT 
 
 G< d) (v.) = l, 
 c i ,A 
 
 SET I£ ; (v) = 
 FOR EVERY v€lP(v j _). 
 
 
 13 
 
 MAKE 
 COVERING 
 ASSIGNMENTS . 
 
 12 
 
 REMOVE CONNECTIONS 
 
 TO v. FROM NON- 
 l 
 
 ESSENTIAL INPUTS. 
 
 11 
 
 DETERMINE ESSEN- 
 TIAL INPUTS TO 
 
 v. . 
 
 i 
 
 INITIALIZE 
 
 I 's. 
 
 c 
 
 16 
 
 UPDATE 
 ARRAYS. 
 
 10 
 
 DETERMINE ALL d 
 SUCH THAT 
 
 G (d) ( V .) = 
 c i 
 
 1 
 
 SET COUNTER: 
 GCOUNT = 0. 
 
 k 
 
 INCREMENT 
 COUNTER: 
 GCOUNT = 
 GCOUNT + 1 
 
 •f RETURN J 
 
 v. = 
 
 l 
 
 GORDER 
 (GCOUNT) 
 
 YES 
 
 Fig. 2.2.1.1 Flowchart of MENI2 
 
 REMOVE ANY c j 
 SUCH THAT 
 
 Ji 
 
 v. £lP(v.). 
 
22 
 
 level 2 in GORDER (k 1 + 1 ) , GORDER^ + 2), . .., GORDER(k 1 + k 2 ) , etc. 
 This insures that every gate will precede all of its predecessors in 
 the ordering. 
 
 Block 2 represents an initialization of the vectors I (v. ) for 
 i = 1,2, . . . ,n + R. This block corresponds to the Initialization Step 
 described in Section 2.1.1, and it is performed exactly as described 
 there. 
 
 Block 3 simply initializes a counter, the variable GCOUNT, used 
 in the program loop consisting of blocks k through l^f. 
 
 This counter is incremented in block h . The program loop 
 formed of blocks k - lh executes once for each value of GCOUNT: l,2,3,.o. 
 When GCOUNT is incremented beyond the value MR, it is detected in block 5 » 
 This is a sign that the algorithm has finished, having scanned every gate 
 in the network, and the program enters block 15. Otherwise, the program 
 proceeds to block 6. 
 
 In block 6 , v. is chosen to be the gate or input terminal whose 
 name is contained in the (GCOUNT) — position of the array GORDER; v. is 
 then the next gate or external variable to be scanned by the program. 
 
 If v. happens to be an external variable or input terminal 
 (a condition tested in block 7 ) , no action needs to be taken. So, in 
 that case, the program returns to block k to increment GCOUNT. 
 
 Otherwise, the program continues to block 8 . Here v. is tested 
 to see if it feeds any other gates in the network. If it does not, and 
 if it is not an output gate, then v. is an isolated gate. 
 
 Upon discovery of an isolated gate, its input connections 
 are removed so that other gates which feed only isolated gates can also 
 be detected and removed. This operation is performed in block 9, after 
 
23 
 
 which the program returns to block h. 
 
 However, if v was not isolated, the program proceeds to block 
 10 from block 8. It is in blocks 10 through lk where the components of 
 the CSPF vectors are actually determined (except for those determined 
 during initialization). These five blocks, as a group, correspond 
 generally, to substep (b) of the Main Calculation (Section 2.1.2). 
 
 Block 10 determines the positions of 0-components which must 
 be covered in v.'s CSPF vector. This information is used later in block 13 
 where the covering assignments are actually made. 
 
 Block 11 determines which inputs are essential to v. . 
 
 ' i 
 
 Block 12 then removes connections from the non-essential inputs 
 to v. . However, it is not true that all connections from inputs not 
 determined as essential in block 11 can be removed. The removal of 
 connections not found to be essential by block 11 must be done serially, 
 since removing any input connection to v. may cause new essential l's 
 to be created, and, hence, some formerly non-essential inputs (i.e., 
 inputs with no essential l's) of v. might suddenly become essential. 
 
 In block 13 the covering assignments are ma.de for the inputs 
 still connected to v.. This block is the counterpart of substep (b-2) 
 of the Main Calculation Step of the procedure. In fact, except for 
 substep (b-2-3), the precedure as written is identical to its implementa- 
 tion. In this substep, the program actually chooses covers as follows: 
 
 from the group v. , v. , . . . , v. e IP (v. ) such that f (v. ), ...,f V (v. ) = 1, 
 J ! J 2 J k 1 J l J k 
 
 a subset of v. is selected such that each element has the same maximum 
 J 
 
 number of output connections (among the elements of the original set). 
 From this new set, select a further subset such that each element is from 
 
2k 
 
 the lowest possible level. Finally, from this newest set, select the 
 v with the smallest index number i,. Then v. is the chosen cover for 
 
 G' d ^(v. ) = 0, and consequently 1^ '(v. ) is set to 1. 
 
 Block lU performs the assignment of required O's in the intermed- 
 iate CSPF vectors of the gates in IP(v. ). This done by the program 
 exactly in the manner specified in substep (b-l) of the Main Calculation 
 Step. 
 
 After block 1^-, the program loop for v. is completed, and the 
 program returns again to block k to examine the next gate. 
 
 After all gates have been examined, the program enters block 15 
 where a check determines whether or not there has been any improvement 
 in (the cost of) the network. If not, a return is made to the calling 
 subroutine. However, if there has been some alteration of the network, 
 various arrays which store parameters and certain lists associated with 
 feastures of the structure of the network must be updated. Then, finally, 
 a return to the calling subroutine is made. 
 
 Note that the Final Step of the procedure described in Section 
 2.1.3 has not been included in this implementation of the program. 
 
 Sometimes, although not in NETTRA-PG1, a second subroutine is 
 called immediately after the subroutine MINI2. This subroutine, named 
 SUBSTT, is quite simple; it tries to substitute the outputs of a gate, 
 GI, by the combined outputs of other gates (or external variables) in 
 the network, making use of the CSPF's just calculated by MENI2. For 
 each gate, v., in the resultant network from MENI2 , SUBSTI tries to 
 
25 
 
 find a set, T (preferably as small as possible), of v. 
 
 , wx v . such that 
 
 T n S(v.) = ft and 
 
 tJ 
 
 v 
 
 (y T f(v.)} € G (v j. 
 
 1 *- J 
 
 Then connections from the combined outputs of the elements of T are 
 
 substituted for every connetions from v., leaving v. with no output 
 
 J J 
 
 connections. Gate v may then be simply disconnected from the network 
 
 J 
 
 by disconnecting each of its input connections. 
 
 After this substitution is done, the CSPF's of the network 
 must be recalculated (e.g., by calling MINI2 again) before a second 
 substitution can be correctly performed. 
 
 Sometimes, however, when a network contains a great deal of 
 redundancy (e.g., several gates have identical sets of input connections), 
 it might be desirable to perform a less powerful substitution procedure 
 which does not require a recalculation of the CSPF's between substitutions, 
 This could be done (although it has not been programmed) by merely changing 
 the conditions for the set T used in SUBSTI: try to find a set, T, of v. 
 such that T D S(v.) - and : 
 
 „(3)/ \ r A Ja), x r .. . 
 
 G v (v.) = In 3 A-nCT '(v. )= {, , respectively, 
 
 r v.el c i l 
 
 i 
 
 ,i 
 
 where "A" is a binary operation defined by the following table 
 
 A 
 
 
 
 1 
 
 * 
 
 
 
 
 
 1 
 
 # 
 
 1 
 
 1 
 
 1 
 
 1 
 
 ■X- 
 
 * 
 
 1 
 
 * 
 
26 
 
 After the (possibly) several substitutions of this modified SUBSTI are 
 performed (without recalculating the CSPF's), the CSPF's should be 
 recalculated (e.g., by calling MINI2) before proceeding with another 
 procedure which will use the CSPF's. This is because, after a substitu- 
 tion (or substitions) of this type, restrictions may remain in the old 
 CSPF's which make them unnecessarily small in the context of the reconfigured 
 network. This differs from the case of the substitution as performed in 
 the originally described SUBSTI (i.e., in the actually programmed SUBSTl) 
 where the substitution (generally) causes the previously calculated CSPF's 
 to become incorrect. In that case, a recalculation (at least, a partial 
 recalculation) is required rather than merely suggested. 
 
 2.2.2 An Example of the Operation of the Programmed Procedure 
 
 This section will present the results of repeatedly applying the 
 procedure realized by MINI2 to a network realizing a particular function 
 for the combined purposes of pruning and calculating a set of CSPF's. 
 
 After applying the procedure of MINI2 to a somewhat redundant 
 network for the first time, generally some connections and gates have 
 been removed from the original network, causing some changes in the functions 
 f(v. ), realized by the gates. This, in turn, sometimes permits a more 
 desirable set of CSPF's to be obtained by another application of the 
 procedure realized by MTNI2. The fact is evidenced by the following 
 example . 
 
 The given network is shown in Fig. 2.2.2.1 (a). It has 5 external 
 variables, x^, x^, x , x^, x and realizes the function f (x ,Xp,x-,xr ,x_) = 
 
 (1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,1,0,1,1,1,0,0,1,1,1,0,1,0,0,0) 
 
 ( = A8AA5CE8 1 g). This network was actually obtained by a simple network 
 
27 
 
 (a) Given network of 19 gates and 76 connections 
 
 Figo 2„2 2<,1 An example of pruning procedure with CSPF calculation. 
 
\ 
 
 i 2 
 
 28 
 
 (l6 gates and 
 50 connections ) 
 
 (b) Network after first transformation by MINI2. 
 
s 
 
 2 /" 
 
 L _ 
 
 29 
 
 XI 
 
 X3 
 X5 
 
 X4 
 
 X5 
 
 X5 
 
 Xl 
 
 X5 
 
 X2 
 
 X3 
 
 X2 
 X4 
 
 X3 
 
 X4 
 
 X3 
 
 X5 
 
 X4 
 
 X5 
 
 (lA gates and 
 38 connections) 
 
 (c) Network after second transformation by MINI2. 
 
30 
 
 synthesis procedure (also implemented as a computer program called 
 N0RNET-3 LEVEL). It consists of 19 gates and 76 connections. 
 
 After pruning this network once by MINI 2 (and calculating a 
 set of CSPF's) the result is as shown in Fig. 2.2.2.1 (b). At this 
 point, 3 gates and 26 connections have been removed from the network. 
 A second pruning produces the network in Fig. 2.2.2.1 (c); 2 more gates 
 and 12 more connections have been removed, leaving a network of only 
 ik gates and 38 connections. A third pruning (results not shown) would 
 remove only 1 additional connection (from x to gate 13 ), and a fourth 
 pruning would produce no further improvement. 
 
 It is not pretended that the large number of gates and connections 
 removed from the original network is indicative of the strength of the 
 procedure since the original network was obviously quite redundant. 
 However, this example does demonstrate the effectiveness of using MINT2 
 more than once on the same network. Furthermore, the identical gates, 
 6 and 18, appearing in the network at both stages (b) and (c) indicate 
 the utility of the substitution procedure implemented as the subroutine 
 SUBSTI. If SUBTI had been used after every use of MINI2, either gate 6 
 or gate 18 ( and perhaps others) would have been removed from the network. 
 The obvious redundancy of having gates with identical sets of inputs 
 (and, hence, identical functions) in the network cannot be dealt with 
 (except in very special cases) by MINI2 alone. 
 
31 
 
 3. PRUNING PROCEDURES BASED ON NECESSARY 
 AND SUFFICIENT CONDITIONS 
 
 A pruning procedure based on CSPF's will not always produce 
 S-irredundant networks. In this section we give pruning procedures which 
 always produce S-irredundant networks. In this section we give pruning 
 procedures which always produce irredundant networks. 
 
 Procedure 3»1 (Direct procedure): 
 
 (1) Select on connection a-.! according to a particular ordering 
 which we adopt. 
 
 (2) Compare the outputs of the original network and the network 
 without Ci j . If the outputs of both networks are the same, c- ■ is removed 
 
 J 
 
 from the network. 
 
 (3) Repeat step (2) until no further pruning is possible. 
 
 This procedure is very simple but time-comsuming. The usage of 
 a O-fixed maximumset of permissible functions (OFMSPF) will reduce the 
 calculation time., 
 
 Definition 3»1 - 
 
 A OFMOSPF G^,(c.- -; ) for a connection Cn - 1 is defined to be a subset 
 OM !J ^ 
 
 of MSPF G(c. .) satisfying the following condition: 
 
 for f^ d/ (v. ) = 0, G^(c..) = holds, 
 
 v 1 OM ij 
 
 and for f (d) (v.) = l, G^ (c ) - G^ d) (c ) holds. 
 
32 
 
 Theorem 3*1 : 
 
 A connection c . . is S-redundant if and only if the OFMSPF G_ w (c. .) 
 ij OM ij 
 
 consists of only O's and *'s. 
 
 Proof : 
 
 For a NOR network, removing a connection c- . has the same effect 
 
 as replacing f (c ) by a function g such that g = for all d. Then 
 
 the "if" part of the theorem is trivial from the definition of G„(c. .) 
 * M ij 
 
 and the fact, g e G^.,(c. .) c G,,(c. .). To prove the "only if" part of 
 ' ° OM ij M xj 
 
 the theorem, let us consider the case where there is some d such that 
 
 can not be removed from the network without changing some outputs of 
 
 the network, i.e., c. . is not S-redundant. 
 
 ij 
 
 Q.E.D. 
 
 Procedure 3»2 (Pruning Procedure Based on OFMSPF): 
 
 (1) Select one connection c. . according to a particular ordering 
 which we adopt. 
 
 (2) Let D= {d} such that f (v.) and f' d >,) = for all 
 
 v eIP(v.) and v d v. . Set f; d ^(v.) = l for all deD. 
 
 K J K 1 J 
 
 (3) Update outputs JT (v ) for gates v es(v.) and for all 
 
 K K J 
 
 ( d) 
 coordinates deD, to fj, ; (v, ). 
 
 *" k 
 
 (h) Compare the updated outputs of the network fi ' (v ) with 
 
 * n+R+lr 
 
 the specified outputs z^ for l<h< m and deD. If for some deD 
 
33 
 
 some output function f), '(v _ .) £ z. , then &)../ (c ) = 1 and c. . is 
 
 * n+R+i r x ' OM v ij ij 
 
 not S-redundant ; otherwise c. . is removed from the network. 
 
 (5) Apply these steps until no further pruning is possible. 
 
 A further improvement can be obtained by using 1 - fixed maximum 
 set of permissible functions for gates. 
 
 Definition 3.2 : 
 
 A 1FMSPF G,„(v. ) for gate v. is defined to be a subset of 
 1M X 11 
 
 G M (v. ) satisfying the following condition: 
 
 for f (d) (v.) = 0, ^(vJ^G^v.), holds 
 
 and for t^\v ± ) = 1, G^(v ± ) = 1 holds. 
 
 Theorem 3»2 : 
 
 A connection c. . is S-redundant if and only if for every d such 
 that a£>( T )-0, y ip(v .) f (d) (v k ) = l holds. 
 
 k r 1 
 
 Proof : 
 
 Removing connection c . . only affects the output of gate v , so 
 
 we need only to prove that the output of v. after removing c± ., f*( v .j)> 
 
 is contained in G (v.) for the "if" part of the theorem. Observe that: 
 
 (1) fJv.) >f(v.) i.e., fi d) (v.) = l, holds for every d € f (d (v.) = l, 
 
 (2) f(v.)€Q (v.), thus if 4m )(v j ) = 1 ' 4 d) ( v . ) = 1 because of (!)> 
 and (3) for every d such that G^v..) = 1, *£ ( T j) = holds because 
 
3k 
 
 U , . f^fv, ) = 1. Therefore f (v.) eG.J v.). Since G.Jv.) is a 
 v eIP(v.) v k' * 3 1M j 1M V j 
 
 k r l 
 subset of G„(v.), f„(f.)e G..(v.). Thus c.. is S-redundant. The "only 
 if" part is proved as follows. Suppose the condition is not satisfied, 
 
 i.e., there exists a d such that gJ^v .) = but T e±P(v ) f ( v k ) = 0, 
 
 ^ k / j 
 
 Then f^ d '(v.) = l. Since g' 4 / 1 (v . ) = E 4 '(v . ) for this a aecoraing to the 
 
 definition of G M (v ), f *( v j)^ V V j^ 
 
 Since G,„(v.) is the maximum set of permissible functions for v. 
 
 M j * J 
 
 and fAv.)£ G„„(v.), connection c. . is not S-redundant. 
 
 Q.E.D. 
 
 Corollary 3.1 : 
 
 If G n „(v.) contains only l's and *'s, v. and all v, e IS (v.) 
 1M j J ' 3 k j' 
 
 are redundant. 
 
 Proof : 
 
 All input connections of v. are redundant by therorem 2, and 
 
 J 
 
 therefore v. is redundant. Next if f(v.) is replaced by a function 
 
 J J 
 
 g= {1,1,.. .,1) e G. M (v.), f(v. ) = {0,0,..., 0} for all v. £ IS (v.). There- 
 
 fore all v. € IS (v.) are redundant. 
 
 Q.E.D. 
 
 Procedure 3. 3 (Pruning Procedure Based on 1FMSPF) : 
 
 (l) Select one gate v.eV according to a particular ordering 
 which we adopt. 
 
35 
 
 (2) Let D={d r ; ( v ) = 0). If D contains all coordinates 
 
 .(d) 
 
 then v is redundant. Remove it from the network, and 
 
 •(1 
 
 i' 
 
 from to 1 for all deD. 
 
 then go to step (l). Otherwise change the value of f^ d '(v. ) 
 
 ( ci) 
 (3) Update the outputs f y (v. ) for gates v, eS(v ) and for 
 
 k k j 
 
 ( ci) 
 
 coordinates d e D to f „ (v ). 
 
 * k 
 
 (k) Compare the specified outputs of the network and the updated 
 
 ones for coordinates deD. For each deD, if f^( v )e z ' d ' 
 
 * v n+R+h h 
 
 for all 1< h < m , then set g| m (v.) = *, otherwise set 
 
 G 1M )(V J ) = ' Set G lM )(v j ) = 1 f ° r a11 d ^ D « 
 
 (&) 
 
 (5) If there is no d such that G:., ( v .) = 0; then v. and v eIS(v.) 
 
 im v j j k y 
 
 are redundant, remove them from the network and go to step (7). 
 
 (6) Select one input connection c. . of v. according to the ordering, 
 
 (ci ) 
 Check whether the condition IL-w \ f (v, ) = 1 for every 
 
 y eIP(v. ) v k 
 
 V. 3fcV. 
 
 k r i 
 
 ( d) 
 Gn>, (v.) = is satisfied or not. If it is, q.. is removed 
 
 from the network. Repeat this step until all input connections 
 are examined. 
 
 (7) Apply this procedure until no further pruning is possible. 
 
 Two computer programs NETTRA-P1 and NETTRA-P2 were written in 
 FORTRAN IV based on procedures using OFMSPF and 1FMSPF respectively. 
 The direct procedure, however, is too time-consuming and is not programmed. 
 
36 
 
 The actual computer procedures are well in line with the procedures 
 described above except that special consideration was paid to the deter- 
 mination of proper orderings and to shortening of the calculation time. 
 The ordering used in both programs is based on the levels of the gates, 
 and the order of gate labels. In NETTRA-P1 step (l), a v. € V is selected 
 
 first accordiing to the levels of gates, i.e., r(v.)>r(v. ) if L(v.)>L(v. ), 
 
 J X J _L 
 
 where L(v.) denotes the level where gate v. is. In the case when 
 
 L(v.) = L(v. ) holds, we order v. and v. in such a manner that r(v.)>r(v. ) 
 
 if j<i, c -_. is then selected by choosing v. €lP(v.) according to an 
 
 ordering that r(v. )>r(v ) if i<k. We have chosen the ordering based 
 
 on levels because it makes the calculation efficient for the following 
 reason. If a connection c . . is removed, only f(v )'s for v eS(v.) 
 
 have to be updated. The information on predecessors , successors and 
 levels of gates need not be updated until the program finishs one scan 
 on all connections by this ordering. In NETTRA-P2, the same ordering 
 
 is used in selection of v. and c. .. Since the resulting networks depend 
 
 very much on the ordering, the above ordering may not produce the best 
 
 network among all S-irredundant ones derived by pruning procedures from 
 
 the original network. . The following ordering for the selection of c. . 
 
 after v. is selected generally gives a better result although it is 
 somewhat time-consuming to determine. 
 
 (1) r(v. )>r(v ) for every v. eV and every v. £V_. 
 
 ik i (j- k I 
 
 (2) r(v.)>r(v ) if I IS(v. ) |< | IS(v, )| and both v. and v, 
 
 i k i i ' k l k 
 
 are in V or V , where | IS(v. ) | indicates the number of 
 
37 
 
 immediate successors of v . 
 
 i 
 
 (3) If there is a tie by the above rules, then r(v. ) >r(v ) 
 
 1 K. 
 
 if i <k. 
 
 We prefer a gate with less output connections because it has higher prob- 
 ability to be removed. Special consideration may be paid when an ordering 
 is determined. For example, connection c. . in Fig. 3.1 may be given higher 
 
 priority since v. and v may 
 
 J k 
 
 be merged to one gate if c . . 
 
 V h2 V hl 
 
 'ij 
 
 v. 
 
 V, 
 
 could be removed. An ordering 
 adopted by considering the 
 situation like this requires 
 more computation time than 
 the simple ordering used in 
 our program. However, when 
 Fig. j.l tn e pruning procedure is 
 
 combined with other network transformation procedures, there may emerge 
 such a case where it is desirable that a particular connection be removed 
 from the network by all means if possible. In that case, we can apply 
 the pruning procedures using necessary and sufficient condtions to check 
 whether the connection can be removed. This has the same effect as using 
 a different ordering. 
 
 The procedure based on 1FMSPF for gates is more efficient than 
 the procedure based on OFMSPF for connections since the number of gates 
 in a network is usually much less than the number of connections. The 
 later procedure, however, is more efficient when only one connection is 
 to ge checked as in the case mentioned above. 
 
38 
 
 V ^ START ) 
 
 LEV = L„ where L^ is the 
 level of the network. 
 
 Update the 
 information 
 on the top- 
 ology of the 
 
 network. 
 
 Select one gate v. such that L(v.) = LEV, 
 
 and for all k<j either L(v. ) / LEV or v 
 has been selected. 
 
 Select a connection c . . € C according to 
 
 i i 
 ascending order of i. 
 
 I 
 
 Let D= {d|f (d) (v. ) = 1, y r w w ,f (d) (v, ) = 0} 
 i i v e IP( v. )-lv. j k 
 
 K J 1 
 
 YES 
 
 Calculate fi '(v. ) for deD and v. eS(v.) with 
 (*\ * k k j 
 
 fi (v.) = 1 for deD. 
 . 3 
 
 I 
 
 ■ (d),. ttJ „ ^d- 
 
 i = 1,2,..., m. Is there any l<i<m such that 
 
 ' (d) (v )lz {r 
 
 * l n+R+i ; " Z i 
 
 For each deD compare f^ ("^ + t> + ^ with z 'for , , 
 
 YES 
 
 o=c-t^j 
 
 .(a) 
 
 (a). 
 
 f W (Tj-fi"'W 
 
 * V k' 
 
 for v € S(v.),d€D 
 k J 
 
 Fig. 3.2 Flowchart of Program NETTRA-P1 
 
39 
 
 r~\ 
 
 
 W 
 
 / cd> 
 
 
 / * 
 
 \ 
 
 H M 
 
 y 
 
 H !> 
 
 
 ,C ai 
 
 
 O H 
 
 
 2 m O 
 
 
 W O 
 
 
 Ch > 
 
 
 •r-D W 
 
 
 > -d h3 
 
 
 0) oj "^ 
 
 • 
 
 -p --- 
 
 -d 
 
 cd ~ id <D 
 
 M £^ 
 
 +3 
 
 C) 
 
 CD hh hh 
 
 <D 
 
 c II 
 
 O M h 
 
 H 
 
 a> 
 
 ^-v d) 
 
 w 
 
 -P -nC 
 
 
 o > P 
 
 G 
 
 <D -H 
 
 a) 
 
 H 1-3 <U 
 
 <D 
 
 0) 
 
 ,a 
 
 
 f s 
 
 1?° 
 
 9 
 
 
 ^ 
 
 
 TJ 
 
 
 > 
 
 CO 
 
 
 
 1 — ^ 
 
 U> 
 
 M 
 
 
 ^ -v 
 
 id 
 
 o 
 
 o 
 
 ■d 
 
 > 
 
 Ch 
 
 s 
 
 v_^ * 
 
 
 
 
 *H 
 
 •d 
 
 G 
 
 H 
 
 
 0) 
 
 cti 
 
 II 
 
 
 -P 
 
 
 y-— -v 
 
 
 d 
 
 n 
 
 .'^ 
 
 
 H 
 
 a> 
 
 1> 
 
 
 P 
 
 >d 
 
 
 
 o 
 
 .g 
 
 •— V 
 
 
 H 
 
 Sh P 
 
 Ti 
 
 
 a5 
 
 O -H 
 
 -— '* 
 
 
 
 Ch £ 
 
 ch 
 
1+0 
 
 
 o 
 
 
 
 ^ n II 
 
 
 
 M^> OtJ 
 
 
 
 > |T3 > 
 
 
 m 
 
 
 
 H 
 
 f— "N S ' v 
 
 
 >H 
 
 tS m Ti 
 
 
 
 . — :fc M) «. — 
 
 
 
 Ch JiJ <+h 
 
 
 
 II > ^ 
 
 
 
 »—N TO 
 
 
 
 M H tj > 
 
 
 
 t> H S — - 
 
 
 
 -— <> ci c6 Ph 
 
 
 
 -n H 
 
 
 
 — ' O W .ki 
 
 
 
 Ch <h XJ !> 
 
 
 
 •r-D 
 •H 
 
 o 
 I 
 
 o 
 
 II 
 
 o 
 
 -p 
 
 
 PS <Vh 
 
 
 ft o 
 
 
 -p 
 
 
 P w 
 
 
 o c 
 
 
 0) -H 
 
 
 -p -P w 
 
 
 cd O 0> 
 
 
 -d fi-P 
 
 
 B Pa3 
 
 
 £> 'PhD 
 
 
 
 
1+1 
 
 Figs. 3.2 and 3.3 show the flowcharts of NETTRA-P1 and NETTRA-P2, 
 respectively. For further detailed information on the programs, see [2], 
 
42 
 
 k. EXPERIMENTS 
 
 In order to compare the speed and effectiveness of the three 
 pruning procedures implemented as subroutines MINI2, RDTCNT, and PROCT, 
 kO single-output test networks realizing 20 different k- and 5-variable 
 functions were chosen as initial networks for the procedures. 
 
 There are 2 single-output networks to realized each of 10 
 different ^-variable functions and 10 different 5-variable functions. 
 For each function, one of the networks was obtained by a simple procedure 
 (called N0RNET-3LEVEL) for generating a 3-level network to realize a given 
 function. The other network was obtained from a "universal network" 
 (for either k- or 5-variable functions) which can realize any given 
 (k- or 5-variable) function simply by adding an extra gate as the network 
 output gate and a few connections to this gate from appropriate gates [3]. 
 
 Tables k.l and k.2 present a comparison of the results, showing 
 for each initial network and each pruning procedure the size of the pruned 
 network (i.e., the number of gates and number of connections) and the 
 corresponding computation time (in seconds). The results in Table k.l 
 are based on initial networks of the "universal" type, while the results 
 in Table k.2 are derived from networks of the "3-level" type. The programs 
 were run on IBM 360/75J, using FORTRAN compiler H(opt 2), level 20.1. 
 (The system provided timing subroutine with entry names STIMEZ and KTIMEZ 
 was used. ) 
 
^3 
 
 The three pruning procedures compared in Tables k.l and k.2 are 
 (l) the procedure based on OFMSPF' s, (2) the procedure based on lFMSPF's, 
 and (3) the procedure based on CSPF's . The first 2 of these were discussed 
 in Section 3? and the last is the modified procedure described in Section 2. 
 The pruning procedure using CSPF's was applied repetitively without the 
 Final Step, as in the example of Section 2.2 2. Analogous to this is the 
 intrinsically repetitive nature of the other 2 procedures. 
 
 All of the ^-variable functions used in this comparison are 
 known to be optimally realized by 8 NOR gates. However it is clearly 
 unreasonable to expect to obtain an optimal network from an arbitrary 
 initial network using only a pruning procedure; but for these particular 
 k- variable functions and initial networks, networks within 2 or fewer 
 gates of optimal could be obtained. Optimal networks for the 5-variable 
 functions are not known. 
 
 From the two tables it can be seen that for the large, extremely 
 redundant initial networks of the "universal" type realizing 5-variable 
 functions, the CSPF procedure obtained results comparable to those of the 
 1FMSPF procedure on the average and in usually only 1/5 to l/lO of the 
 computation time. Also the results by the CSPF procedure were generally 
 much better than those obtained by the OFMSPF procedure and were computed 
 often in 1/3 to l/k of the time. 
 
 For the smaller, though still considerably redundant, initial 
 networks of the "universal" type realizing ^-variable functions, the 
 networks obtained by all 3 pruning methods were comparable, although the 
 
 t For simplicity, let these three procedures be referred to as the 
 OFMSPF procedure, the 1FMSPF procedure and the CSPF procedure 
 respectively. 
 
44 
 
 
 FUNCTION 
 NUMBER 
 
 i 
 
 INITIAL 
 NETWORK 
 SIZE 
 
 TJEWCM DERIVED 
 BY PROCEDURE 
 
 BASED ON 
 
 OFMSPF ' s 
 
 NETWORK DERIVE 
 
 BY PROCEDURE 
 
 BASED ON 
 
 lFMSPF's 
 
 NETWORK DERIVED 
 BY PROCEDURE 
 BASED ON 
 CSPF's 
 
 
 # gates: 
 
 # connec- 
 
 # gates: 
 
 # connec- 
 
 
 # gates: 
 
 # connec- 
 
 
 # gates: 
 
 # connec- 
 
 
 
 
 tions 
 
 tions 
 
 sec. 
 
 tions 
 
 sec. 
 
 tions 
 
 sec. 
 
 
 1 
 
 33:305 
 
 19:49 
 
 1.80 
 
 15:46 
 
 6.98 
 
 15:47 
 
 .57 
 
 5 
 
 2 
 
 33:305 
 
 23:56 
 
 2.05 
 
 17:53 
 
 6.34 
 
 18:55 
 
 .62 
 
 3 
 
 33:303 
 
 15:39 
 
 1.27 
 
 13:39 
 
 3.18 
 
 13:39 
 
 .52 
 
 V 
 
 a 
 
 ^ 
 
 33:310 
 
 12:34 
 
 1.59 
 
 13:34 
 
 6.24 
 
 12:34 
 
 .54 
 
 r 
 i 
 
 5 
 
 33:301 
 
 l4:43 
 
 .92 
 
 13:43 
 
 1.80 
 
 13:43 
 
 .37 
 
 a 
 b 
 
 6 
 
 33:315 
 
 10:31 
 
 1.22 
 
 11:33 
 
 4.6l 
 
 10:32 
 
 .39 
 
 1 
 e 
 
 7 
 
 33:305 
 
 16:48 
 
 I.29 
 
 15:52 
 
 3.95 
 
 15:47 
 
 .44 
 
 
 8 
 
 33:310 
 
 15:35 
 
 1.94 
 
 12:33 
 
 6.51 
 
 13:39 
 
 .43 
 
 
 9 
 
 33:302 
 
 18:50 
 
 1.67 
 
 15:48 
 
 5.80 
 
 14:47 
 
 .47 
 
 E 
 
 10 
 
 33:307 
 
 18:^3 
 
 1.67 
 
 16: 45 
 
 5.90 
 
 16:42 
 
 .49 
 
 
 11 
 
 17:110 
 
 9:18 
 
 .27 
 
 9:18 
 
 .54 
 
 9:18 
 
 .15 
 
 1+ 
 
 12 
 
 17:110 
 
 9:20 
 
 .24 
 
 9:20 
 
 .49 ' 
 
 9:20 
 
 .14 
 
 V 
 
 13 
 
 17:109 
 
 9:24 
 
 .17 
 
 9:24 
 
 .45 
 
 9:24 
 
 .12 
 
 a 
 r 
 
 14 
 
 17:109 
 
 10:24 
 
 .35 
 
 10:24 
 
 .55 
 
 10:30 
 
 .14 
 
 i 
 a 
 b 
 1 
 
 15 
 
 17:109 
 
 9:30 
 
 .22 
 
 9:30 
 
 .44 
 
 9:30 
 
 .14 
 
 16 
 
 17:108 
 
 9:19 
 
 .25 
 
 9:19 
 
 .50 - 
 
 9:19 
 
 .15 
 
 e 
 
 17 
 
 17:108 
 
 8:17 
 
 .35 
 
 8:17. 
 
 .47 
 
 9:23 
 
 .14 
 
 
 18 
 
 17:108 
 
 9:17 
 
 .27 
 
 9:17 
 
 .59- 
 
 8:17 
 
 .10 
 
 
 19 
 
 17:107 
 
 10:21 
 
 .24 
 
 10:21 
 
 .42 
 
 10:21 
 
 .14 
 
 b 
 
 20 
 - ! 
 
 17:107 
 
 10:20 
 
 .27 
 
 9:20 
 
 .59 
 
 9:20 
 
 .14 
 
 Table 4.1 Pruning results from initial networks of the "universal" type. 
 
45 
 
 
 i 
 
 FUNCTION 
 NUMBER 
 
 INITIAL 
 
 NETWORK 
 SIZE 
 
 
 
 NETWORK DERIVED 
 BY PROCEDURE 
 BASED ON 
 OFMSPF's 
 
 NETWORK DERIVED 
 BY PROCEDURE 
 BASED ON 
 lFMSPF's 
 
 NETWORK DERIVED 
 BY PROCEDURE 
 BASED ON 
 CSPF's 
 
 
 # gates : 
 
 # gates : 
 
 
 # gates : 
 
 .... 
 
 # gates : 
 
 i 
 
 
 
 # connec- 
 
 # connec- 
 
 
 # connec- 
 
 
 # connec- 
 
 
 
 
 tions 
 
 tions 
 
 sec. 
 
 tions 
 
 sec. 
 
 tions 
 
 sec. 
 
 
 1 
 
 26:102 
 
 20:50 
 
 .57 
 
 19:49 
 
 .90 
 
 20:52 
 
 .20 
 
 5 
 
 2 
 
 25:100 
 
 22 :5k 
 
 .60 
 
 22:55 
 
 .82 
 
 21:56 
 
 .45 
 
 V 
 
 a 
 
 3 
 
 25:105 
 
 15:39 
 
 .47 
 
 15:39 
 
 • 92 
 
 16:40 
 
 .29 
 
 r 
 i 
 
 4 
 
 17:65 
 
 12: 3^ 
 
 .22 
 
 12:34 
 
 .20 
 
 12:34 
 
 .20 
 
 a 
 To 
 
 5 
 
 22:92 
 
 16:43 
 
 .45 
 
 16:43 
 
 .57 
 
 16:43 
 
 .19 
 
 1 
 
 6 
 
 18: 81 
 
 11:31 
 
 .35 
 
 11:31 
 
 .30 
 
 10:32 
 
 .12 
 
 
 7 
 
 25:100 
 
 17:48 
 
 .57 
 
 17:48 
 
 .55 
 
 17:49 
 
 .17 
 
 
 8 
 
 21:86 
 
 12:33 
 
 .39 
 
 12:33 
 
 .40 
 
 12:34 
 
 .12 
 
 
 9 
 
 22:85 
 
 20:51 
 
 M 
 
 20:51 
 
 .64 
 
 20:51 
 
 .20 
 
 
 10 
 
 26 : 106 
 
 19:50 
 
 .60 
 
 19:50 
 
 .90 
 
 19:51 
 
 .20 
 
 
 11 
 
 11:25 
 
 9: 18 
 
 .05 
 
 9: 18 
 
 .10 
 
 9:18 
 
 .07 
 
 4 
 
 12 
 
 12:31 
 
 10:23 
 
 .09 
 
 10:23 
 
 .09 
 
 10:23 
 
 .05 
 
 V 
 
 13 
 
 12:36 
 
 9:24 
 
 .09 
 
 9:24 
 
 .05 
 
 9:24 
 
 .05 
 
 a 
 
 r 
 
 14 
 
 10:31 
 
 10:24 
 
 .10 
 
 10:24 
 
 .09 
 
 10:24 
 
 .09 
 
 i 
 a 
 
 15 
 
 9:31 
 
 9:30 
 
 .09 
 
 9:30 
 
 .07 
 
 9:30 
 
 .03 
 
 b 
 
 1 
 
 16 
 
 13:36 
 
 9:19 
 
 .09 
 
 9:19 
 
 .09 
 
 9:19 
 
 .09 
 
 e 
 
 17 
 
 13:40 
 
 8:17 
 
 .09 
 
 8:17 
 
 .07 
 
 8:17 
 
 .12 
 
 
 18 
 
 13:38 
 
 9:18 
 
 .10 
 
 9:18 
 
 .15 
 
 9:18 
 
 .12 
 
 
 19 
 
 13:33 
 
 10:21 
 
 .07 
 
 10:21 
 
 .07 
 
 10:21 
 
 .07 
 
 j. 
 
 20 
 
 14:43 
 
 • 
 
 10:21 .15 
 1 
 
 10:21 
 
 .12 
 
 10:21 
 
 .15 
 
 Table 4.2 Pruning results from initial networks of the "3-level" type. 
 
1+6 
 
 O-FMSPF procedure was about twice as fast as the 1FMSPF procedure and the 
 CSPF procedure was about twice again as fast as the OFMSPF procedure. 
 
 For initial networks realizing 5-variable functions of the gener- 
 ally less redundant, "3-level" type, the resulting pruned networks were 
 generally comparable with respect to the number of gates and connections 
 involved. The CSPF procedure was often 2 to 3 times faster than the OFMSPF 
 procedure which, in turn, often needed only about 2/3 of the computation 
 time of the 1FMSPF procedure. However, in 3 cases, the OFMSPF procedure 
 required slightly more computation time than the 1FMSPF procedure. 
 
 For initial networks realizing 4-variable functions of the "3-level" 
 type, the results obtained were identical in the numbers of gates and 
 connections. In addition, the three procedures did not differ very much 
 in computation times on the average. 
 
hi 
 
 5. CONCLUSIONS 
 
 From the experiments in the preceding section, the pruning procedure 
 based on CSPF's seems to be a good choice for a general network pruning 
 problem. Relative to the other two procedures, it is fast, it produces 
 good results, and it calculates a set of CSPF's which are convenient for 
 following the pruning with certain other types of transduction procedures. 
 
 However, if an S-irredundant network is required then either the 
 procedure based on OFMSPF's or the procedure based on lFMSPF's should be 
 used. 
 
 Originally, the procedure based on lFMSPF's was just intended 
 to be an accelerated version of the procedure based on OFMSPF's, performing 
 the same sequence of connection removals in a more efficient manner. 
 However, during programming of the procedure, another apparent opportun- 
 ity to increase the speed of pruning was found as a by-product of using 
 the lFMSPF's: when the 1FMSPF of a gate includes the function written 
 in vector notation as (1,1,..., l), that gate along with all of its immed- 
 iate successors can be removed from the network. When this feature is 
 included in the procedure based on lFMSPF's (as it was for the program 
 which derived the results in Table 4.1 and Table 4.2) certain time- 
 consuming updates of arrays and variables must be made after each such 
 removal of a gate and its immediate successors. This was found to be one 
 of the causes of the long computation times for the 1FMSPF procedure in 
 Tables 4.1 and 4.2. Furthermore, the inclusion of this feature can cause 
 
kQ 
 
 connections to be removed in a different order than that of the OFMSPF 
 procedure (or, equivalently, than that of the 1FM3PF procedure without 
 the feature). Since different connection removal orderings often lead 
 to different results, the different networks in Tables k.l and k.2 
 resulting form the OFMSPF and the 1FMSPF procedures can be explained. 
 
 Based on so few examples however, it is not clear if the increased 
 computation time accompanying the inclusion of this feature outweighs 
 the apparently better ordering it provides. It is suspected that a more 
 careful programming of the updating of arrays and variables (currently, 
 this done by a general subroutine which also updates certain other 
 variables and arrays unnecessary to the pruning procedure) could increase 
 the speed of the procedure significantly without affecting the results. 
 
 Also, further experiments have confirmed that the 1FMSPF procedure 
 without this feature provides results identical to those of the OFMSPF 
 procedure in a slightly smaller computation time. This is as expected. 
 
 Thus, when both speed and effectiveness are desired or where a 
 calculated set of CSPF's is necessary, the procedure based on CSPF's 
 appears to be the best choice. However, when a guarantee of S-irredundancy 
 is needed, the 1FM3PF procedure should be used - without the gate 
 removal feature, when speed is desired, and with the gate removal feature 
 when effectiveness is preferred. 
 
 The authors are grateful to Professor S. Muroga for his discussions 
 and guidance. 
 
^9 
 
 REFERENCES 
 
 [l] Y. Kambayashi and S. Muroga, "Network Transduction by Permissible 
 Functions (General Principles of NOR Network Transduction NETTRA 
 Programs)," to appear as a report, Department of Computer Science, 
 University of Illinois, 197^. 
 
 [2] H. C. Lai and J. N. Culliney, "Program Manual: NOR Network Pruning 
 Procedures Using Permissible Functions (Reference Manual of NOR 
 Network Transduction Programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2)," 
 Report No. UIUCDCS-R-7^-686, Department of Computer Science, 
 University of Illinois, 197^. 
 
 [3] G. A. Maley and J. Earle, The Logical Design of Transistor Digital 
 Computers . The NOR network constructed in the same manner as the 
 NAND tree network in Fig. 6.U.1, page 156, is called the universal 
 network in the text. Prentice Hall, 1963. 
 
BIBLIOGRAPHIC DATA 
 SHEET 
 
 1. Report No. 
 
 uiucdcs-r-tU-G^ 
 
 pruning procedures for nor networks using permissible functions 
 
 (Principles of NOR network transduction programs NETTRA-PG1, 
 NETTRA-P1, and NETTRA-P2) 
 
 3. Recipient's Accession No. 
 
 5. Report Date 
 
 November, 197^ 
 
 7. Author(s) 
 
 J. N. Culliney, H. C. Lai, Y. Kambayashi 
 
 8. Performing Organization Rept. 
 
 No -UIUCDCS-R-7^-690 
 
 9. Performing Organization Name and Address 
 
 Department of Computer Science 
 
 University of Illinois at Urban a -Champaign 
 
 10. Project/Task/Work Unit No. 
 
 Urban a , Illinois 
 
 61801 
 
 11. Contract/Grant No. 
 
 NSF-GJ-i+0221 
 
 12. Sponsoring Organization Name and Address 
 
 National Science Foundation 
 1800 G Street, N.W. 
 Washington, D.C. 20550 
 
 13. Type of Report & Period 
 Covered 
 
 Technical 
 
 14. 
 
 15. Supplementary Notes 
 
 16. Abstracts 
 
 Three procedures of the "pruning" class of transduction procedures for NOR network 
 design by network transformation are discussed. The procedures are based, respectively, 
 on the concepts of "compatible sets of permissible functions," "0-fixed maximum sets 
 of permissible funtions" for connections, and "1-fixed maximum sets of permissible 
 functions" for gates (CSPF's, OFMSPF's, and lFMSPF's). Use of the latter two 
 guarantees single-irredundant networks. 
 
 17. Key Words and Document Analysis. 17o. Descriptors 
 
 Logic design, logic circuits, logical elements, programs (computers). 
 
 17b. Identifiers /Open-Ended Terms 
 
 Computer-aided-design, permissible functions, network transformation, network 
 transduction, pruning, redundant networks, S-irredundant networks, NOR, NAND, MSPF, 
 CSPF, 1FMSPF, OFMSPF. 
 
 17c. COSATI Field/Group 
 
 18. Availability Statement 
 
 Release Unlimited 
 
 19. Security Class (This 
 Report) 
 
 UNCLASSIFIED 
 
 20. Security Class (This 
 Page 
 
 UNCLASSIFIED 
 
 21. No. of Pages 
 
 55 
 
 22. Price 
 
 FORM NTIS-35 (10-70) 
 
 USCOMM-DC 40329-P7 
 

OCT 2,7 1975 
 
 
 rtimrrnnrrf^ 
 

 
 ^H 
 
 SB ^B 
 
 MnHlMBllBBHflMI 
 Man UOIBB