OEBOBHflHWBQONiBSJ n&o BBfBfi ■MHHBOBH SmSfiHBBH ■k ■HHIfNnnC tfu- Mill HHh ■■§■■ HflHE flflHHHDflHeB .J9HwMIwCCyw?WctG DBMfi IBBhHHHEBHB waSsa HB&w? ■MmMK HSMf IK at 8& Ws* mH EWE mKflKfttt ■I Raw ■■■■■ Hh ■uuHWafMm DBS CKSH8B ■HaflvBBSIiBeH ■ 903 ■ Empkb ■ Bwa E hhshkt ■ ■ 9b S3? ■BAnHMnHV idHq BO Mrrrn'iflliffKWWrr ■OMDOMMOnQRIN RM9oaaSim^e«u^&aBffi< 4HSS KICPWOflWOggmBgCHi LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 5IO. 84 lifer ho. 800 - 80*3 cop. 2i Digitized by the Internet Archive in 2013 http://archive.org/details/networktransduct804kamb J?Cr/V ' Report No. UIUCDCS-R-76-80I+ Attf Network Transduction Based on Permissible Functions (General Principles of NOR Network Transduction NETTRA Programs) by Yahiko Kambayashi Saburo Muroga June 1976 UIUCDCS-R-76-80U Network Transduction Based on Permissible Functions (General Principles of NOR Network Transduction NETTRA Programs) by Yahiko Kambayashi Saburo Muroga June 1976 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 618OI This work was supported in part by the National Science Foundation under Grant No. DCR 73-03^21. 1. Introduction Logic design of networks with NOR or NAND gates is important since basic logic gates of many integrated circuits (for example, RTL (Register-Transistor Logic), DTL (Diode-Transistor Logic), TTL (Transistor-Transistor Logic), ECL (Emitter- Coupled Logic), ILL (integrated- Injection Logic) and VMOS) realize NOR or NAND. Many papers were published on the problem of synthesizing networks with NOR or NAND gates. These are classified into the following four groups. (1) Switching algebraic method [6], [8], [12], [19]. (2) Map- factoring method [20], [23], [29]. (3) Exhaustive method [7]. (k) Integer programming method including branch- and -bound method [3], [21], [22], [2k] ~ [27]. (5) Network transformations [k] , [5], [H], [17], [27]. (Transformations of net- works in order to comply fan- in/ fan- out restrictions such as those in [28] are of different nature, so they are not discussed in this paper but will be elsewhere. ) Each method has different advantages and disadvantages. The switching algebraic methods are relatively easy to use but the results are not neces- sarily optimal networks except the cases under very specific constraints (such as two level networks without fan- in, fan-out restrictions). The ex- haustive method can be applied only to networks with very few gates though it gives optimal networks. The integer programming method and the branch-and- bound method yield optimal networks by much shorter calculation time than the exhaustive method. These methods are, however, too time-consuming if the number of gates exceeds 10. When we need a synthesis procedure which can treat a logic network with many gates, the network transformation methods seem promising, which transform networks designed by some methods such as the switching algebraic method into simpler networks. Some NOR (or NAND) network transformations were discussed by [k] , [5], [20] . Recently more general trans- formations were studied by T. Nakagawa, H.C. Lai and S. Muroga (the trans- formations are combined with the branch- and -bound method in order to improve the efficiency of the branch- and -bound method) [27], H. Lee and E.S. Davidson [17] and Y. Kambayashi, H.C. Lai and S. Muroga [11] . In this paper new network transformation methods based on the concept of permissible functions are presented. These methods are called the network transduction methods (Transformation and Re duction ). Any network designed by some known method is transformed and reduced into a simpler network by the transduction method. A function f is called a permissible function for a gate if specified components of each of the network outputs (each network output is completely or incompletely specified functions) do change their values by replacing the function i realized at the output of that gate by the function f. Then two concepts of specia sets of permissible functions, i.e., a maximum set of permissible functions (MSPF) and a compatible set of permissible functions (CSPF), are introduced. Properties and calculation procedures for these sets are discussed. If we use MSPF's in some network transduction, we may have a better resul than the use of CSPF's, but the calculation of MSPF's takes much longer time. Pro- cedures to remove redundant connections and gates in a given network, using MSPF's and CSPF's, are described in this paper. Using the concept of permissible function; some network transformations which are known already can be generalized. Several such transformations are shown along with examples. A new network transduction method based on error compensation is also discussed briefly. If an output function is incompletely specified, unspecified components may change by the replacement. Even in such a case, the network output is regarded as "not changed." In other words, this definition of a permissible function is not concerned with unspecified components. 2. Basic Definitions In this paper we consider only a loop-free combinational network which has p input terminals, R NOR gates and m output terminals. Let X = {x 1 , x g , ..., x n ), Z = {z 1 , z 2 , ..., zj , V ] . = {y ± , Vg, . .., v )j V_ = (v _ , v _, . . . , v _) and V~ = {v _,,. v _ _. . . . , v _ } be p ' G p+1' p+2' » p+R p+Rfl' p+R+2' ' p+R-Hn the set of n external variables, the set of m output functions, the set of p input terminals, the set of R NOR gates, and the set of m output terminals, respectively. If x , x , ..., x , x , x , ..., x (x. means the compliment of x. ) are fed to p input terminals, then we set p = 2n. For simplicity in this paper we assume only uncomplemented external variables (x . 's) are available as input functions, so we set p = n and x . is assumed to be connected to v . for i = 1, 2, . . . , n. In other words, "input terminals" essentially mean external variables, i.e., V = X . Let C = {c. .} be the set of connections, where c. . denotes a connection fed from v. e V T U V rt to v. e V A U V„. V is defined ij i I G j G by Each output function z. may not be completely specified. We assume that z. for each i is realized at the output of NOR gate v . which is con - nected to output terminal v „ . . Thus connection c „ . exists for i = p+R+i p+i , p+R+i 1, 2, . . . , m. We also assume that there exists no direct connection from any input terminal to output terminals, that is, no z. is identical to any x.. If there exists a connection c. . from v. to v., v. is called an imm ediate predecessor of v. and v. is called an immediate successor of v., where v. , v. € V. Let IP(v. ) and IS(v. ) denote the set of all immediate prede- 1* j i i £ cessors of v. and the set of all immediate successors of v., respectively. If there exists a sequence of gates v , v , . .., v between v. and v. with a non-negative integer t such that v _ e IS(v. ), v, e IS(v, , ) for q = 2, kl i ' kq k,q-l / ^ ' 3, ..., t and v. e IS(v , ), then v. is a predecessor of v. and v. is a succes- sor of v.. Let P(v. ) and S(v. ) denote the set of all predecessors of v. and — l v l v l - i the set of all successors of v. , respectively. A vector which contains the notation * in its component denotes the set of all vectors which are formed by assigning or 1 to * in all pos- sible combinations. For example, F = (1,0,*,*,) = {(1,0,0,0), (1,0,0,1), (1,0,1,0,), (1,0,1,1)}. vector F, Let F^' denote the j-th component of the vector F. For the above F^ - 1, F (2) = 0, F (3) = *, Y (k) - *. Union U and intersection fl are used to mean ordinary set operations, e.g., (1,0,1,1) U (1,0,0,1) = (1,0,*,1). (i,o,*,i) n (1,0,1,*) = {(1,0,0,1), (1,0,1,1)} n {(1,0,1,0), (1,0,1,1)} = (1,0,1,1). A function realized at v. is represented by f(v. ). By the definition, f (v. ) = x. for i =1, . . . , n, 11 f(v .) = f(v „ .) = z. for i = 1, ..., m. v n+i v n+R+i' 1 ' ' A function f. (completely or incompletely specified) .n at an input terminal, a gate, or a connection, is represented by a 2 dimen- sional vector where ' (^ x 2 , ..., xj =0, = if f '(5) ._ * 1 if f.(x n , x Q , ..., x ) = d ( don,t> \ i v 1' 2' ' n J \care / for j - 1 = 2 n ~ x_ + 2 "'" x + ... + x . ° 1 2 n Based on the previous definition of *, an incompletely specified function in its vector representation thus expresses the set of all completely specified functions by assigning and 1 to * in all possible ways. External variables are accordingly represented by x, = { ^J • 9 • • • ••• i -J y y y * • * * * • 3 -*- / » V .. „ / V J ,n-l n-1 x„ = Ji-2 Ji-2 Ji-2 ,n-2 x x n _ 1 = (0, 0, 1, 1, ..., ..., 0, 0, 1, 1), = (0, 1, 0, 1, ...,..., 0, 1, 0, 1). n Definition 2.1: If no specified components of the network output functions change "by replacing the function realized at input terminal v., gate v. or connection c. ., by a function f, then function f is called a permissible -*- J function for input terminal v., gate v. or connection c. ., respectively. This is illustrated in Fig. 2.1. Suppose we want to find a permissible function for connection c. . in network in (a). When we replace c. . by a function f of variables x_,...,x as shown in (b), f is a permissible function for c. . if specified components of z.,,...,z in (b) are not different from those in (a). Usually there is more than one permissible function for c. .. Notice that permissible functions for a connection c. . are separately defined from those for a gate v. with the same i. Therefore, when gate v. 1 ' ° 1 has more than one fan-out connection, there may be generally some permissible functions of v. which are not permissible functions of c. .; and there may be generally some permissible functions of c. . which are not permissible functions of g.. Bat when gate has only one connection c. ., every permissible function -^ -*- J of g. is a permissible function of c. . and vice versa. Also note that changes in unspecified components * of the network output functions are irrelevant to this definition. x. n (a) m x n x V. 1 V. • V "^\ \ \. • • > n y « • L— ^/ L S « • • • f m (b) Fig. 2.1 Permissible function for connection c ij Definition 2.2: The binary operation # is defined as follows, o#o = 0, 1 # 1 = 1, 0#1 = 1 # o = *, 1 #* = *, # 1 = *, o # * = * # =: *, *#* = *. This relation is summarized in Table 2.1 # 1 * -x- * 1 * 1 * * -* * *- Table 2.1 Operation # For vectors f l " ( V V •••' a 2 n^ where components are 0, 1, or *, f # f is defined by f l #f 2 = (a i # V a 2 # V ••- a 2 n #b 2 n ) * Note that this operation is different from U (union). For example, (10 11)1(1110) =(1*1*) = (1 1 0) U (1 1 1) U (1 1 1 0) U (1 1 1 1) => (1 1 1) U (1 1 1 0). X => y means that set X contains all the elements contained in Y and furthermore X contains some elements not contained in Y. X => Y means that X => Y or X = Y. If f and f p are two different permissible functions for a certain input terminal, gate, or connection, then the set f- # f p is a set of permis- sible functions for the same input terminal, gate, or connection, because the specified components of the network outputs are identical for both f and f ™ ^ for every j no matter whether t™ ' = f ™ ' = 1; t™' = t£ = 0; f ™ ' = 0, fg' = 1; or f£^ = 1, ?£* = 0. Since the associative law holds with the operation #, we can generalize this statement as follows. Lemma 2.1 ; Let F , F , ..., F„ .. and F» be single vectors whose components are 0's, l's and *'s and each of them represents a set of permissible func- tions for a certain input terminal, gate, or connection. Then the set F. # F, # ... # Fp is also expressed by a single vector representing a set of permissib^ a functions for the same input terminal, gate, or connection, respectively. As F # F # ... # F, can be represented by a single vector and F 1 #F 2 # ... #F £ ^ &!' F 2' "•*' V' we can obtain the following two properties. (1) If a set G of permissible functions is given which may not be expressed by a single vector, we can obtain a set G' of permissible functions such that G 1 can be expressed by a single vector and G' ^ G. (2) The set of all permissible functions for any input terminal, gate, or connection can be consequently expressed by a single vector. This set is called the maximum set of permissible functions , abbreviated as MSFF. Let G„,(v. ) and G„,(c.) denote maximum sets of permissible functions for v. and c. ., respectively. We use G(v. ) and G(c. .) to denote arbitrary subsets of G„(v. ) and G„,(c..), respectively. As seen from the second paragraph after Ml M lj ' Since p = n is assumed, an input terminal is an external variable as mentioned in Section 2. 10 Definition 2.1, G„„(v. ) is not necessarily identical to G.,(c.) when gate 'Ml M 10 v. has two or more fan-out connections but G,,(v. ) = G„(c. .) holds when gate l M l M 10 v. has only one fan-out connection c. .. Because of the above property (l), J- X J we use only sets of permissible functions represented by a single vector (i.e., if there are permissible functions F , F , . .., F», we consider F # F p # . . . # F» by combining them with # instead of considering {F , F , . .., FJ). This restriction is useful to reduce memory space and calculation time when procedures based on permissible functions are to be implemented by computer programs. A gate or a connection is said to be S- redundant (implying single- redundant) if no specified components of the network outputs change by re- moving the gate or the connection. In some networks, no specified components of the network outputs change if two or more gates and/or connections are re- moved while the outputs change if a single gate or a connection is removed. In contrast to "S-redundant, " it is called M- redundant (implying multiple-redundant;. A network without any S-redundant gates or connections is called S-irredundant . S-irredundant networks are important for fault location. If a network is not S-irredundant it is called an S-redundant network . A network with S- or M-re- dundant gates or connections is called a redundant network and a network which is not redundant is called an ir redundant network . Notice that an- irredundant network does not necessarily have a minimum number of gates or connections. Lemma 2.2 : If a set of permissible functions for an input terminal, a gate, or a connection is represented by a single vector whose components are O's and *'s only, then the input terminal, the gate, or the connection is S-re- dundant, respectively. In other words, even if it is removed from the net- work, the specified components of the network outputs do not change. If the set of permissible functions is maximum, the condition becomes a necessary and 11 sufficient condition for S-redundancy of the input terminal, the gate, or the connection. Proof ; When the components consist of only O's and *'s, (0, 0, . .., 0) is contained in the set. Thus, even if the function realized at the input ter- minal, the gate, or the connection is replaced by the function which is identically 0, the network outputs do not change, so we can remove it. The second statement is obvious. When the set is not maximum, there may be a permissible function with some components of 1 such that a gate or a connection can be removed. But even in this case, if the maximum set is obtained, its components must be or * only. Q.E.D. 12 3. Maximum Sets of Permissible Functions In this section we will give a procedure to calculate maximum sets of permissible functions (abbreviated as MSPF). This procedure will be used to obtai S-irredundant networks. Especially for tree networks (i.e., networks where each gate has exactly one fan-out connection) the procedure is effective. Let us introduce the following definition to be used in Theorem 3«1« Definition 3.1 : The binary operation □ is defined as follows: *uo = *ni = oni = *, □ = 1, 1 □ = 0. Operations for other combinations are not defined. Note that the operation □ is nether commutative nor associative. The relation is summarized in Table 3.1, where "-" denotes "undefined." First Element Second Element □ 1 * 1 * - 1 * * * _ Table 3-1 Operation G For vectors f l = ( W , " ,a 2 n ) f 2 = (b 1 ,b 2 ,...,b n ) , whose components are 0, 1, or *, f^ □ f g is defined by f l Qf 2 = ( a l Gb l' a 2 Gb 2^-^ a 2 n :]b 2n ) * Theorem 3.1: If the MSPF G..(v. ) for gate v and f(v) for every v 6 IP(v ) M v k k k' are given, the MSPF G (c ) for an input connection c, of v is given by M v jk jk 13 G M (c ik } =G M ( V °( v f(v)) (3-D J where if IP(v ) = {v.}, \y f(v) is regarded as the function of * J v€IP(v. ) k r J constant 0. (See Fig. 3'1 where all v € IP(v ) except v. are collectively k J shown as a single input line. ) Proof : Fig. 3.1 shows the relation among G (v, ), v f where (d) denotes the M ^ v€lP( Vl ) l x k 7 J d-th component of the vector. There are three cases as follows. ( d) (a) G^ ( v k.) = *• Since this means that the network outputs are not influenced by the output of v, , all inputs of v are arbitrary (see Fig. 3.1(h)). For v. € IP(v, ) M jk ( c\ ) (b) G/. (v ) = 1. As the output of v is required to be 1, all inputs should be 0's since v is a NOR gate (see Fig. 3.1(c)). For v. € IP(v, ), k j k G (d) (c.J =0. M v jk y (=) G< d) (v k ) . 0. (c-l) If \s f K (v) = 1, then the output of v, is always independent v€lP(v ) K I k 3 ( d) of the value realized at c, (see Fig. 3.1(d)), that is, G„ (c ., ) = *. jk 7 ' M jk (c-2) If v ft \v) = 0, then the input from v. must be 1 since f' (v. ) = v€!P(v. ) ° k j_ • k y VfcV. 3 (d) (it is obvious from G^\\) = 0. See Fig. 3.1(e)). Thus G M (^=1 . These relations are represented by Eq. (3.1). Q.E.D. M jk f (a) M veIP(v n ) I k k 4 a) K) M k (a) Ik or 1 (b) (c) (e) Fig. 3-1 Relation among G^ d) (v k ), v, f (d) (v) and G^ d) (c ) veIP(v k ) vk. 15 If a given set G(v ) of permissible functions is not maximum, the following equation gives a set G(c., ) of permissible functions for c ., , Jk Jk which is not necessarily maximum G(c., ) = G(v. ) D ( v f(v)) (3.2) Jk k v€lP(v k ) vtv. For output connections the following lemma yields an MSPF. Lemma 3*1 : For any connection connected to output terminal realizing z., J the MSPF is given by z . . , .... H^) H (d) = * if z (d) =>z! (a) for all 1, 1—1 ' 1 < i < m, H (d) = f (d)/ j if z (d) ig not # and algo 3 i zf d) 1= z! (d) holds for i l some i(l< i < m) where z! is the i-th output function realized by the network which is obtained from the original network (the i-th output is z.) by replacing connections from v. by f(v.) realized by the new gate in Fig. 3»5« Here f(v.) is the complement of f(v.), the function at v., and "z) M above is used as ordinary set implication, i.e., * - °> * - 1 » 1 - ^ 0^0- Proof : (l) Suppose z. ' => z! holds for all 1=1, . .., m for the com- bination of external variables such that d - 1 = 2 x_ + . . . + x . Even 1 n if we change the output of v. from f (v.) to its complement f (v.), the J J J network still realizes the required output functions. So we can assign * to (&) H . (2) Suppose the above condition is not satisfied. If we change the output of v. from f^ (v.) to f^ (v.), then at least one output z. changes (i.e., z . r z! ). So we can not use f^ (v.) for the output of v.. ii J we can obtain the following procedure to calculate the MSPF's for a network. Procedure MSPF (Procedure to calculate the MSPF's) (1) Calculate f (v. ) for each gate v. in the network for every combination of x l' X 2* " * " ' X n* (2) There exists at least one gate v. connected to only an output terminal (loop- free condition) which realizes output function z.. For such gate v. the MSPF is given by G.,(v. ) = z.. l e * M l j (3) Select a gate v. whose MSPF is already known. The MSPF for each input con- nection c.. of v. is calculated by using Eq. (3«l) of Theorem 3»1« o J- * (k) Let us calculate the MSPF for input terminal or gate v . (U-l) When the MSPF G (c . ) for every v.e IS(v ) is given and for every pair v. and v. in IS(v ) i-L i 2 k S(v, ) n S(v ) = x l x 2 holds, G (v ) is given by Eq. (3«*0 in Lemma 3.3. (J+-2) When the above condition (^--l) is not satisfied, we calculate the MSPF for v using Lemma 3»^« K. (5) Repeat steps (3) and (h) until we obtain the MSPF's for all gates, input ter- minals, and connections. Lemma 2.2 gives a necessary and sufficient condition for the S-redundancy of a gate, an input terminal, or connection, using MSPF's. A procedure to calculate an S-irredundant network is obtained by combining Procedure MSPF and Lemma 2.2. 2k Procedure SINM : (Procedure to obtain an S-Irredundant Network based on the MSPF's) (1) Calculate the MSPF's for all gates and connections, starting from the network output and moving toward input terminals using Procedure MSPF. Usually in a network every external variable is assumed to be necessary, so we need not calculate the MSPF's for input terminals. (2) During the calculation of step (l), we can remove connections and gates as follows. (2-1) Connections. The MSPF's for input connections of v, are calculated by Eq. (3-1) • If there exists an input connection of v whose MSPF consists of O's and *'s only, remove such a connection. (2-2) Gates. As a result of removing connections, there may exist gates without any output connections, and then remove such gates. (3) If some connnections or gates are removed in step (2), a network which is different from the original network may be obtained ^although the net- work outputs still represent the same functions. If so, return to step (l) with the new network. Otherwise go to step (k) . (h) Terminate the procedure and we have obtained an S-irredundant network. This procedure does not necessarily yield a network with a minimum number of gates or connections, since an S-irredundant network does not nec- essarily have a minimum number of gates or connections. But the procedure is useful in many cases since every network with a minimum number of gates or connections must be S-irredundant. The procedure is greatly simplified and speeded up if it is applied to a network in which all gates satisfy the condition of Lemma 3.3, because 25 the application of Lemma 3.1+ is time-consuming. Since a tree network is the case, Lemma 5 is applicable. Let us give a simple example of a tree network here. Example 3»1 : Consider the tree network shown in Fig. 3.6(a). We get easily the following: f(v 1 ) = (0 1 1 1 1), f(v 2 ) = (0 1 1 1 1), f(v 3 ) = (0 1 1 1 1), f(V = (0 1 1 1 1 1 1), f(v 5 ) = (0 1 0), f(T 6 ) = (1 0), f(v ? ) = (1 1 1 1 0). MSPFs are obtained as follows because all gates have single outputs, G M ( V " f ( V ■ W = G M ( V ° f (V 6 } = (* 1 0), G M (v 6 } = W D f ^ (a) 2 T^*-^ :^_ -Lly^ T^^- Vi Vi 2 — : q _ Z^kjp iiA (b) L 3— -t V (c) Fig. 3»6 Example for Procedure SIM 27 f(V = (01110111), f(v 5 ) = (10 10 0), f(Vg) = (10 0), W = (01110111), G M ( V = (*0001000), G„(v,) = (*00 0*00 0), By Lemma 2.2 we can remove gate V/- and the network in Fig. 3»6(c) is obtained. By the following approach we can obtain an S-irredundant network from any type of network, without using Lemma 3*^ which is time-consuming. (1) By duplicating gates appropriately, obtain an equivalent network in which every gate is connected to at most one gate (accordingly a gate which is connected to an output terminal may have two outputs). (2) Since in the network obtained in step (l) every gate satisfies the con- dition of Lemma 3*3, Procedure INM can be applied without using Lemma 3»^- The resultant network after the above procedure may have more gates than the resultant network obtained by Procedure SINM only, although both net- works are S-irredundant. 28 h. Compatible Sets of Permissible Functions The procedure for simplifying a network discussed in the previous section has the following disadvantages, since it is based on the MSPF's. (A-l) If there exists a gate which does not satisfy the condition of Lemma 3.3, we need to use a time-consuming calculation of Lemma 3«^- (A-2) In Procedure SINM each time an S-redundant connection is removed, the re- calculation of MSPFs for the entire new network is required. Two or more S-redundant connections cannot be in general removed at the same time, since the network outputs may change. Reduction of calculation time is very important in order to develop a practical procedure. For this purpose we introduce the concept of a com- patible set of permissible functions (abbreviated as CSPF) which is a subset of an MSPF. Procedures based on CSPFs have the following advantages and dis- advantages . (B-l) For the calculation of CSPFs we do not need to use a time-consuming process like Lemma 3«^» (B-2) Even if an S-redundant connection is removed we need not recalculate CSPFs for the new network. (B-3) The property (B-2) above is useful for developing network transduction procedures based on CSPFs, which will be discussed in [2], [9], [l6] for a simple one, see Section 5). (B-k) Since CSPFs are subsets of MSPFs, the network obtained by the use of CSPFs is not necessarily S-irredundant. For the above reasons there is a trade-off between the calculation time and the effectiveness of procedures. 29 Let us illustrate disadvantage (A-2) with a simple example. Let N and N be subnetworks consisting of gate v. and its predecessors, i P(v. ) U (v.}, and gate v. and its predecessors, P(v.) U {v.}, respectively. For simplicity we assume that P(v. ) fl P(v.) = and IS(v.) = IS(v.) = {v } 1 J X J k (see Fig. U.l(a)). We can remove connection c , in N (or c in N ) J if the output function f (v. ) of N (or f(v.) of N ) is contained in G.,(c„ ) * v l v. j v. M lk i 3 (or G M (c ., ))after the removal of the connection. We may not, however, be able to simultaneously remove both connections c and c because the simul- taneous removal of both connections may change both functions realized at v. and v. such that f(v, ) is no longer in G M (v ), as the following functions show. More concretely, we assume the following functions are realized at v . , v . and v n . f(v.) =(01100010), f(v.) = (00110001), J f(v k ) =(10001100), as shown in Fig. ^-.1 (a). Suppose the MSPF for v G (v ) = (* 1 * *) M k 7 v ' be given. Then the MSFF's for connections c. and c ., are calculated by lk jk Theorem 3*1, G M (c ik } = ( * 1 * * ° * * *^ G M (c jk } - (* * * 1 * * 1), as shown in Fig. ^t-.l(b). Let f., and f_ be arbitrary functions in G,„(c, ) ° 12 * M ik 30 f(v.) = (0 1100010) v. f(v k ) =(10001101 f(v.) =(0 011000 1) (a) v V. G M K ) =(*1** ***) v. G m( v J = (* 1 * * M v k G u(°j]J = (***io**i) (b) (0 100000 0) € G ■ (c.. ) M lk (10 10 1110) £ G M (v. M k (0 001000 1) € GJc, ) M jk (*ll*0***)c G ( c ) " M ik (c) (***!()**!) C G M (c jk ) (d) Fig. 4.1 Disadvantage (A-2) of MSPF's 31 and G (c, ), respectively. By the definition of MSFFs, the output function M Jk of v is in G..(v. ) if f_ and f(v.) or f (v. ) and f_ are connected to v as K M £ X J 1 d K. inputs instead of the original f (v. ) and f(v.)« We cannot, however, replace both inputs f (v. ) and f(v.) simultaneously by f and f p , respectively. For example, if f and f p such that f = (01000000), f = (0 1 1), are simultaneously connected to v , the output of v, becomes (10 10 1110) which is not contained in G M ( v k ),as shown in Fig. k.l. (c). If we can find subsets G(c. n ) and G(c ., ) of G„(c. ) and G^c, ), v ik y v jk y M v lk' M ok 7 ' respectively, such that the output of v corresponding to simultaneous con- nection of any two inputs f e G(c, ) and f £ G(c ) is always in G (v ), then we can remove two connections c , and c , at the same time when f (v. ) ab cd l and f(v.) are contained in G(c, ) and G(c ) after the removal of c , and c , j Ik. jk ab cd respectively. For example, in Fig. k.l. (d) the following G(c ik ) and G(c . ) have such a property. G(c ik ) =(*11*0***), G(c v ) = (* * * 1 * * 1). This is one of the motivations of defining CSFFs in Definition k.2. 32 Definition 4.1 : A tied subnetwork of a given network is defined as part of the given network satisfying the following conditions, where U is the set of input terminals, gates, connections and output terminals, contained in this subnetwork. (1) If v. € U, then S(v. ) 5 U, (2) If c. . e U, then v. e U and S(v.) c U, (3) If v. e U, v. e U and v. e IS(v. ),then c. . e U. Definition 4.2 : Let U be the set of input terminals, gates, connections and out- put terminals in a tied subnetwork N of a given network. All the sets of permissible functions, G(v. ) and G(c. .) (v. € U, c . . e U), are said to be com- patible with respect to this tied subnetwork if the following property holds with every subset W of U. (1) Replace the function at each element w in W by a function in G(w). (2) In the resultant new network each element u in U, which is not contained in W realizes some function contained in G(u). (3) The above condition (2) holds, no matter which function in G(w) is chosen for each w in condition (l) (i.e., condition (2) holds for every different choice of functions in G(w)'s for all the w's of W). As a special case, a tied subnetwork can be a given network itself. In this case if sets of permissible functions satisfy the above conditions, they are simply called compatible sets of permissible functions (CSFFs) . A CSFF for an element u (€ V U C) is denoted by Gp(u). There is a procedure to calculate CSFFs, which will be explained later. Definition 4.3 : The following arrangement of v. 's in V- U V is called ordering r : denoting the ordering number of v. with r(v.), 33 1 < r(v. ) < R for v. € V — 1 — l G R + 1 < r(v. ) < R + n for v. € \L. — i — l I Theorem k.l : Consider a tied subnetwork N which contains gate v. but none of its input connections. Let U be the set of input terminals, gates, connections, and output terminals in this tied subnetwork. Let B be the set of all sets of permis- sible functions for elements in U such that these sets are compatible with respect to subnetwork N. Let subnetwork N' be a tied subnetwork which consists of all elements in U and all input connections of v . Then the union of B and the sets of permissible functions calculated by Eq. (4.1) is a set of permissible functions which are compatible with respect to subnetwork N 1 . For y. e IP(v k ), 0(0-) = (G(v ) □ ( ^ f(v))} # f(v.) (k.l) 3K k r(v)>r(v.) J v€lP(v k ) J If there exists no v satisfying r(v) > r(v.) and v 6 IP(v ), \/ f(v) ' J K ' r(v)>r(v.) veiP(v k ) :) is regarded as the function of constant 0. Proof : Table 4.1 shows the relation for the d-th components based on Definitions 2.2 and 3»1« In the following let us explain why we must de- termine the entries as shown in the last column in Table k.l. (d) (1) If G v (v. ) is *, the output of v is either or 1. If it is 0, its input is 1 or 0. If it is 1, its input is 0. Since we have and 1, (d ) G (c ., ) = *. Thus we have the first row of Table k.l. (ci) (2) G (v ) = 1. Because v is a NOR gate, all inputs of v must be 0, i.e., G (c . ) s 0. Thus we get the second row of Table 3.1. 3^ G (d) (v k ) V f (<3) (v) r(v)>r(v. ) velP(v. ) J k f (d, (v.) G (d) (c. k ) * or 1 or 1 # 1 1 1 or 1 #■ -* 1 1 Table 4.1 (3) G (v ) = 0. In this case at least one input of v, must be 1 and others K. K. are arbitrary. (3-1) If v f (v) = 1, then the input from v. is arbitrary, i.e., r(v)>r(v.) v€lP(v. ) J G^ (c, ) = *. Thus we get the third row of Table 4.1. <]k (d) (3-2) If v f (v) = 0, then there are two cases. r(v)>r(v. ) v£lP(v n ) J k (3-2-1) f (v.) = 0. In this case we must have f (v.) = 1 for v. such J -Li. that r(v. ) > r(v.), so the input from v. is arbitrary, i.e., » (a, v ■ *• 3 35 (3-2-2) f (d) (v.) = 1. Then G (d) (c,, ) = 1. Even if we change one or more input functions of v, each of which is K. contained in a set of permissible functions G(c ) for that input c obtained J-K Ok by Eq. (k.l), the output of v remains in G(v, ), because Table k.l is prepared such that the relationship between G(c ) and G(v, ) is maintained. Since B is the set of sets of permissible functions which are compatible with respect to subnetwork N, the union of B and all sets of permissible functions for the inputs of v, (calculated by Eq. (^.l))is also the set of sets of of permissible functions which are compatible with respect to subnetwork N'. Q.E.D. Theorem k.2 : Consider a tied subnetwork N which contains all output connections of input terminal or gate v, but not v, itself. Let U be the set of input terminals, gates, connections, and output terminals in this subnetwork. Let B be the set of all sets of permissible functions for elements in U suoh that these sets are compat- ible with respect to subnetwork N. Let tied subnetwork ¥ be a subnetwork which con- sists of all elements in U and v . Then the union of B and the set of permis- ■ sible function for v calculated by Eq. (U.2) is the set of sets of permis- sible functions which are compatible with respect to subnetwork W. G(v ) = 17 G(c ). {k.2) k v.GlS(v k ) kj Proof ; As B is the set of sets of permissible functions which are compatible with respect to tied subnetwork N, all specified components of the network outputs do not change by replacing one or more functions of c .(v.£LS(v )) by kj j k functions contained in their respective sets of permissible functions in B. If a function in G(v ) in Eq. (^.2) is chosen as the output function of v , all the functions of fan-out connections of v remain in their respective 36 G(c, .)• By "the definition of compatibility, it can be shown easily that the union of B and G(v ) defined by Eq. (k.2) is the set of sets of K. permissible functions which are compatible with respect to tied subnetwork W. Q.E.D. Let us outline a calculation procedure of CSPFs based on Theorems k.l and k.2. (its details will be described as Procedure RSCS. ) Obviously, MSPFs for any connections connected to output terminals obtained by Lemma 3.1 are compatible with respect to a tied subnetwork consisting of all these out- put terminals and connections connected to them. Starting with the fan-out connections as a tied subnetwork calculated above, we gradually increase the size of the tied subnetwork while calculating CSPF's for all input terminals, gates, output terminals and connections in each tied subnetwork, based on Theorems k.l and k.2 (notice that only a single tied subnetwork which contains the output terminals is being considered throughout the entire network). When the tied sub-j network coincides with the entire network, we have calculated CSPFs for all the input terminals, gates, connections, and output terminals. During the cal- culation, each set of permissible functions does not change, once calculated. Thus, although the notation G (u) as a CSPF for element u is defined for the entire network, use of G (u) even for a tied subnetwork would not cause any confusion. In Procedure SIWM each time we find an S-redundant connection we have to recalculate MSPFs, but if we use CSPFs such a recalculation is un- necessary. Lemma 2.2 gives a condition for an input terminal, gate, output terminal or connection being S-redundant. If, however, we use CSPFs instead of MSPFs, we may not be able to remove connections by Lemma 2.2 because of the dependency of CSPFs on ordering r. For example, consider a three-input gate 37 v^ shown in Fig. k.2. Assume G c (v ), f(v ), f(v ) and f(v ) are given as follows 1 . V ' V ' ^3 G c (v k ) =(100001**), f(v ) = (0 1 1 1 1), q l f(v ) = (0 1 1 0), f(v n ) q 3 (00011001). If r(v ) < r(v ) < r(v ), then G c (c ) = (0 * * * * * *), On ** G c (c ) = (011**0* *), G C (c a k } = (° * * 1 10 * *)> by Theorem 4.1 (see Table k.l). v % V V. Fig. k.2 Three-input NOR gate 38 So we can find c is redundant by Lemma 2.2. But if r(v ) < r(v ) < q l k q 2 q l r(v ), then q 3 ' G C (c q k)^ 01 *" *^ G C (c q k ) = ( ° * 1 * * ° * * } > G c (c q fc ) = (0 * * 1 1 * *). We cannot find redundancy of c in this case. This dependency on ordering q-J£ can be avoided sometimes by the following lemma. Lemma k.l: If for gate v n we can find a set E c IP(v n ) which satisfies k — k v€{lP(y )-E) ' (d) (v) =1 for all d satisfying gA (v ) - 0, then input connections to v from input terminals and gates in E are S- redundant. The proof is obvious. In the case of Fig. k.2, as f^ (q 2 ) v f (q-,) (a) is 1 for all d satisfying G^, (v ) = 0, c is S-redundant. L> K. q, k Combining Lemma k.l with a calculation procedure of CSPFs based on Theorems k.l and k.2 and Lemma 3.1, the following procedure is obtained. Procedure RSCS : (A Procedure to Remove S-redundant Connections and Calculate CSPFs) (1) Calculate f (v. ) for each gate v. in a given network. (2) For each output connection c. . which realizes an output function z , G c (c )' is given by G c (c )= z R . (3) As the network is loop-free, there exists at least one gate v. whose out- put is connected only to an output terminal and realizes z . For such 39 gate v. , G c (v.) =G c (c..) = V This is a special case of Theorem k.2. (k) When a set G c (v , ) of permissible function is given, first we remove S-redundant inputs, and then calculate CSPFs for all .inputs of v . (k-l) Calculate a set E satisfying E cr IP(v k ) , f (d) (v) =1 v€{lP(v k )-E} ( c\ ^ for all d such that GA. (v, )= 1. No good procedure to find a maximum set E has been known so far. The following method is one approach to find an E, although the result may not be maximum. In IP(v, ) select one element with the smallest number by the ordering r and check whether it is removable or not by Lemma k.l (E consists of only one element). If it is S-redundant, remove it and apply this process to other elements with higher numbers in IP(v, ) until all the elements are selected. {k-2) Calculate CSPFs for all the inputs of v using Eq. (k.l) (see Theorem k.l). (5) When connections are removed in step (k) , we can remove some input terminals or gates if they are not connected to any other gates. If CSPFs for all fan-out connections of v, have been already calculated, a CSPF for v, is given by Eq. (k.2). (6) Repeat steps (k) and (5) until CSPFs for all input terminals, gates output terminals, gates and connections in the network are calculated. The reason why an ordering number for any input terminal is chosen to be higher than those for gates is that we want to remove gates rather than input terminals to reduce the cost of the network. 1+0 The result of Procedure RSCS may vary if we use different ordering r. Normally a gate with many fan-out connections is hard to remove, so it may be desir- able to add the following conditon in determining the ordering r. If | IS (v.) | > |lS(v.)|, then r(v. ) >r(v.) where |lS(v.)| denotes the number of fan-out connections from gate v. . 1 Example 4.1 : We apply Procedure RSCS to the network in Fig. 4.3(a) which shows a full adder realized by a universal network [20] (in [20] this is called a tree network) where two outputs z and z are given by 'l = x i © x 2 © x 3 (sum), z 2 = x.^ ^ x g x sy x x 1 (carry). Ordering r is determined as follows: for gate v., r(v. ) = i -3; for input terminal v., r(v-) = i + 9* In the network shown in Fig. 4.3(a), functions realized by ex- ternal variables and gates are as follows External variables Gates f f f f f f f f f f(v f(v f(v v l } = ( V 2 } = ( V 3 } = ( V V = ( v 6 } V Vg) V = ( icr = ( hj/ — ( TO' (0 (0 1 (0 10 (0 11 (0 (0 (0 (0 (0 (0 1 (0 10 (10 11 1 1), 10 1 1); 10 1 1), 10 1), 10 1 1 1), 1 0), 1 0), 10 o o), 10 0), 0), o o), 0). kl Zp= X-. Xp \s XpX._ \/ X, 3 X 1 Z l = X l© X 2© X 3 ( a ) ( b ) ( c ) Fig. k.3 Full adder k2 For the output gates, v. and v , we can obtain sets of permissible functions as follows: G c (v^) = (01101001), G p (v c ) = (00010111). From G c (v i< _), f(v^), f(v ) and f(v ),we obtain G c (v^), G (v„) and G (v q ), since these gates are single-output gates. G c (v 6 ) = (* * * 1 0), G c (v 7 ) =(*00*01*0), G c (v ) = (* 1 * * 0). From Gp(v^), f(vn), f(v_ ) and f(v ) we have (1) c, p /r is redundant (Lemma ^.l), (2) G c (c 8>6 ) = (* * * * 1 * *), G c (c io,6 )= (* * 1 * * * ° *)• Similarly we can remove c- , and we get G c (c 8 ? ) = (* * * * 1 * *), G C (c ll 7 ) = ( * 1 * * * ° * *)' We can remove c.„ Q , and get G c (c io,9 ) = (" 10 "")' G c (c n J = (* i * o * * * *). k3 Also: for inputs of v^, G c (c g ) = (* * * 1 0), G (c ) = (* * 1 * O). C ■ LU ' 5 g c (c 11 5 ) = (n*o*ooo), G c (c 12 ^) = (1**0*000). Thus g c (v 8 ) = g c (c 8 ^) n g c (c 8 ^ 6 ) n g c (c 8 ^ 7 ) = (* * * 1 0), G c (v 1Q ) = (* * 1 * 0), g c (v i:l ) = (*1*0*0 0). From the above results, G c (c 12 Q ) = (* * * * * * *), G C^ C 12 10 ^ = (* * ° * * * * *)» ' G c (c 12 ) = (* * * * * * *). So we can remove connections c 12 Q , c ±2 1Q , and c 11 . Finally, G C (c 12,i+ } =(100*0**0), G C^ C 12,5) =(1**0*0 0). G c (v 12 ) =(10000000). The network obtained is shown in Fig. ^.3(b). If we apply Procedure RSCS to the network in Fig. ^.3(h), further reduction is possible. kk G c (v ) = (00010111), f (v Q ) =(10001000), f(v 1Q ) = (10100000), f(v u ) = (11000000), f(v 12 ) = (10000000). We can eliminate connection c.„ _ (Lemma i +.l).The resulting network is shown 12,5 in Fig. k.3(c) . This network is known as the minimum 3-level full adder using NOR gates as proved by the integer programming design procedure [18]. h5 5. Network Transductions Using Permissible Functions In sections 3 and k we discussed procedures to calculate MSFP's and CSPF's and their applications to simplifying networks by removing redundant connections and gates. For further network simplifications more powerful network transductions are desired. Some of known transformations [11], [17],[27] can be generalized using the concept of permissible functions. Several such transductions are presented here while detailed discussions are given in [2], [9], [l6], A more powerful trans- duction based on error compensation will be briefly discussed. The transduction procedure can also treat a multiple-redundancy, as the discussion in [10] shows. Theorem 5.1 : If there exist two gates and/or input terminals, v. and v., satisfying the following conditions, all fan-out connections from v. can be J replaced by fan-out connections from v.. Thus v. is removable. 1 j (1) f(v.) e G(v.), where G(v.) is a set of permissible functions of v. which can be an MSPF or a CSPF. (2) v t S(v ). Proof ; By the definition of permissible functions if (l) is satisfied, the output function of v. can be replaced by f(v.). (2) guarantees a loop-free J network after this transformation. Q.E.D. Use of MSPF's in Theorem 5*1 may give a better chance for removal since G (v.) 3 G(v.)(G(v.) can be a CSPF), but the calculation of MSPF's is normally time-consuming. This theorem is a generalization of the primitive "gate merging" which is an inverse of a "parallel duplication" or a "serial duplication" [11]. Fig. 5.1 shows an example of a gate merging. In Fig. 5.1(a) v. and v. realize k6 (a) (b) Fig. 5.1 Gate merging hi the same function, so the network in Fig. 5«l(b) is obtained. Let us give an example for Theorem 5.1. Example 5.1; The network shown in Fig. 5«2(a) realizes the function f = X X s, X X s/ xx Functions realized at input terminals and gates are as follows, f(v 1 ) = (o 1 111) f(v 2 ) = (o 1 1 Oil) f(T 3 ) = (o 1 1 10 1) = (01**00**), w = (10***** *). ^8 Since f(vo) e G (v ), the network in Fig. 5.2(b) is obtained by sub- stituting Co/ for c . (2) Transformation by MSPFs In this case the calculation of MSPFs is very easy, since the net- work in Fig. 5' 2(a) is a tree. MSPFs for gates are as follows. W ■ W ■ W ■ w = w - (0 1110001 (* 000**10 (1000*1*0 (#*]_-*-*-*0* (01***0** (10****** Here, G (v ) = G (v ) and we get the same result (Fig. 5 • 2(b)) M f Of The result cannot be obtained by the gate merging. x. X. (a) Fig. 5.2 Example of Theorem 5«1 ^9 The following transformation is given in [11]. "if f(v.) = J v f(v. ) and v. , . .., v. f S(v.), then each output connection of k=l,...,h X k x l X h J v. can be replaced by the connections from v. , .,.., v. ." The next theorem J x l x h generalizes this. Theorem 5.2 : If there exist h gates and/or input terminals v. , v. , . .., X l X 2 v. and a gate v. satisfying the following conditions, each fan-out connection X h J of v. can be replaced by the outputs of v. , . .., v. . Thus v. is removable. (1) v f(v. ) € G(v.), k=l,2,...,h k J where G(v.) is a set of permissible functions for v. which can be an MSFF or a CSPF. (2) For every f(y. ) where k - 1, . .., h, there exists at least one d satisfying x k f (d) (v. ) =1, v f (d) (v. ) =0, G (d) (v.) = 1 k t=l,...,h t J (3) v , v , . .., v £ S(v ). x l x 2 x h J Proof : If the outputs of v. , v. , . .., v. are connected to one NOR gate, X l X 2 x h it is equivalent to connecting one input function, f(v. ) \/ f(v. ) ss ... v f(v. ), X l X 2 X h If (l) is satisfied, the outputs from v. , v. , ..., v. can replace each fan- x l x 2 x h out connection of v.. If there exists f(v. ) (k = l,...,h) which does not 3 X k satisfy (2), the following relation holds and each output of v. can be replaced J without v. : \ 50 v f(c. ) € G(v.). t=l,...,h t J Again (3) guarantees a loop-free network after this transformation. Another well known transformation is as follows [5l, [20]. Q.E.D. "if all immediate successors of v. have input x., x. can be fed to v. as a r e dund ant i nput . ' ' A simple application of this transformation is shown in Fig. 5»3- In Fig. 5«3(a) x (or x ) can be fed to v^ (or v ) since its immediate successor v. (or v,-) has input x p (or x , respectively). By merging two iden- tical gates after the transformation the network in Fig. 5' 3(b) is obtained. (a) x. (b) Fig. 5-3 Use of redundant inputs 51 Generalized versions of this transformation are given in [171 and [27]. Using permissible functions, a further generalization is possible as follows . Theorem 5»3 : Let G(v.) be a set of permissible functions for gate v. which can be an MSPF or a CSPF. We can add a connection from input terminal or gate v. to v. if the following conditions are satisfied. (1) f^(v.) = for all d such that G^(v.) = 1. (2) v. t S(v.). Proof: If there exists d such that f (v.) =1 and G (v.) = 1, a connection from v. to v. changes the output of v from 1 to 0. So we can not connect v. to v.. For all other combinations of values of f^ (v.) and G (v.) a connection from v. to v. keeps the output of v. in G(v.)« (2) guarantees J- j J J a loop-free network after adding a connection from v. to v.. Q.E.D. We can derive network transduction procedures based on Theorem 5«3> as follows. T-I. Add one or more connections by Theorem 5*3 in order to get two gates with identical input sets. If it is possible, merge the two gates and we get a network with a less number of gates. T-II. Add one or more connections by Theorem 5»3» We may be able to remove other connections or gates by this addition. If it is possible, we can get a network with different configuration. T-II can be used to change network configurations. If we cannot apply any known transformations [11], [17], [27] to a given network, we apply T-II in order to change the network configuration. For the resultant network we 52 may be able to further apply the known transformations. If we want to reduce the necessary calculation time, we need to develop more systematic network transduction procedures. The following example illustrates one of such procedures based on permissible functions. In order to simplify a given network, we first remove an appropriate gate from it. Then we try to compensate for the errors in the network outputs caused by the removal, by changing the configuration of the resultant network. Example 5.2 : Fig. 5.k(a) shows a network realizing (100000000010110 1). In order to simplify the network let us remove Vn. Then we get the network in Fig. 5«*+(b) whose output is (100001000010110 1). Note that the outputs of the two networks differ only in the 6-th components. We want to compensate for the erroneous component value of the latter network by adding connections. Functions realized at the input terminals and gates in the original network in Fig. 5«M a ) are as follows. f (v x ) = f (v 2 ) = f (V3) = f (V = f (v 5 ) = f (v 6 ) = (0 000000011111111 (0 000111100001111 (0 011001100110011 (0 101010101010101 (1000000000101101 (0 000101000000010 53 f (v ? ) (0 101000011010000 : (0 101111100000000 (0 011001100000000 (1010000000100000 (0 000000011001100 (1100110000000000 * (V f(v 1Q ) f(v n ) f(v 12 ) The values of the 6-th component for input combination x = x = and Xp = Xjl = 1 are shown in Fig. J.k (a) and (b). Components of vectors representing CSEF's can be calculated independently, so we calculate CSFF's for all components except the 6-th of the network in Fig. 5.U(b). G C ( V = G C < v 6> ' G c (v ? ) = G c ( V = G c ( V = G c (v n ) = G c (v 12 ) = (10 (0***1 (01*1* (0 * 1 * * (10*00 (0***0 (1*0*1 0000101101 1***0*0010 **110100*0 #i#*o*oo*o 0*0010**0* 0*1*0*1*0* *oo***o*** If we can change the 6-th component of f(v/-), f(v_) or f(v q ) from to 1, the error of the network output can be compensated. The value in the 6-th component of the output at gate V/- (also v„, and v ) is due to Xi = 1 (x = 1 and f(v..p) = 1, respectively). If we want to change the output of v Q from to 1, the 6-th component of f(v_ p ) must be 0. If we can change the output of v ip to any function in the set of permissible functions H= (1*0*10*00***0***) (it is the same as G (v_ p ) except the 6-th component), the error will be C v 12 X. 5h X. V 12 1 I V. 12 k -*— 6 V, V (b) x, V x 2 ■■rl V X V (c) W 9 1 V V Fig. 5.1+ Example of a transduction based on error compensation (The values shown at the gates are for the 6-th component of the external variables, i.e., x = x = and x^ = x^ = l) 55 compensated. We can generate such a function by adding x. to v p and con- sequently by changing the output of v 1p into (100010000000000 0) which is contained in H. The network obtained is shown in Fig. 5.k(c). Let us describe the network transduction procedure illustrated by Example 5«2. T-III. (l) Remove a gate or a connection from a given network N. Let N' be the obtained network. (2) Calculate the components of errors in the outputs of N*. (3) Calculate components of vectors representing MSFF's or CSPF's (for remaining gates and connections ) corresponding to all error- free component positions of the outputs of N' . (h) Compensate for errors by adding or removing connections. T-III is a more systematic network transduction procedure than the transductions discussed previously. It can be also used to treat multiple- redundancy. Assume that two connections c , and c are multiple-redundant and neither of them is single -redundant. Let N' be a network without c , . ab By compensating for errors of N'.,c . could be removed. ' cd Further discussions based on such error compensation will be given in [10] . 56 6. Conclusion In this paper the concept of permissible functions is introduced and procedures to calculate maximum sets of permissible functions (MSFF's) and compatible sets of permissible functions (CSEF's) are given. Several network transduction methods which are network simplification procedures based on permissible functions are also shown. More general network transduction procedures along with computer experiments are discussed elsewhere [l], [2], [9], [10], [131 ~ [16]. Network transduction procedures which are discussed with respect to NOR networks in this paper can be easily generalized to networks of other types of gates, such as NAND, OR, or AND gate networks (or a mixture of two or more types of gates, including NOR gates). 57 7« Acknowledgement The authors wish to express their thanks to Messrs. H.C. Lai, J.N. Culliney and K. Hohulin for valuable discussions and comments. 58 References [l] J.N. Culliney, "Program manual: NOR network transduction based on connectable and disconnectable conditions (Reference manual of NOR network transduction programs NETTRA-G1 and NETTRA-G2)," UIUCDCS-R-75-698, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Feb. 1975. [2] J.N. Culliney, H.C. Lai, and Y. Kambayashi, "Pruning procedures for NOR networks using permissible functions (Principles of NOR network transduction programs NETTRA-PG1, NETTRA-P1, and NETTRA-P2), UIUCDCS-R-7^-690 Dept. of Computer Science, Univ. of 111., Urbana, 111., Nov. 197^. [3] E.S. Davidson, "An algorithm for NAND decomposition under network constraints ' IEEE Trans., vol. EC-18, pp. IO98-IIO9, Dec. I969, [k~\ D.L. Dietmeyer and P. R. Schneider, "A computer-oriented factoring algorithm for NOR logic design," IEEE Trans., vol. EC-1^, pp. 868-87^, Dec. I965. [5] D.T. Ellis, "A synthesis of combinational logic with NAND or NOR elements," IEEE Trans., vol. EC-llj-, pp. 7OI-7O5, Oct. I965. [6] J.F. Gimpel, "The minimization of TANT networks," IEEE Trans., vol. EC-16, pp. I8-36, Feb. I967. [7] L. Hellerman, "A catalog of three-variable OR- INVERT and AND- INVERT logical circuits," IEEE Trans., vol. EC-12, pp. 198-223, June I963. [8] K. R. Hohulin and S. Muroga, "Alternative methods for solving the c-c table in Gimpel' s algorithm for synthesizing optimal three level NAND networks," UIUCDCS-R-75-72O, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., April 1975. [9] 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)," to appear as a report, Dept. of Computer Science, Univ. of Illinois, Urbana, 111. [10] Y. Kambayashi, H.C. Lai, J.N. Culliney and S. Muroga, "NOR network transduction by error compensation (Principles of NOR network transduction programs NETTRA-E1, NETTRA-E2, and NETTRA-E3)," to appear as a report, Dept. of Computer Science, Univ. of Illinois, Urbana, 111. [11] Y. Kambayashi, H.C. Lai and S. Muroga, "Transformations of NOR networks," to appear as a report, Dept. of Computer Science, Univ. of Illinois, Urbana, 111. [12] K.S. Koh, "A minimization technique for TANT networks," IEEE Trans., Jan. 1971, pp. IO5-IO7. Discussion on this paper, pp. U07-^08, April 1972. 59 [13] H. C. Lai, "Program manual: NOR network transduction by generalized gate merging and substitution (Reference manual of NOR network transduction programs NETTRA-G3 and NETTRA-G4)," UIUCDCS-R-75-71^, Dept. of Computer Science, Univ. of Illinois , Urbana, 111., April 1975. [Ik] 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), UIUCDCS-R- 7^-686, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Nov. 197*1. [15] H.C. Lai and J.N. Culliney, "Program manual: NOR network transduction by error compensation (Reference manual of NOR network transduction programs NETTRA-E1, NETTRA-E2, and NETTRA-E3)," to appear as a report, Dept. of Computer Science, Univ. of Illinois, Urbana, 111. [l6] H.C. Lai and Y. Kambayashi, "NOR network transduction by generalized gate merging and substitution (Principles of NOR network transduction programs NETTRA-G3 and NETTRA-G^)," UIUCDCS-R-75-728, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., June 1975. [17] H. Lee and E.S. Davidson, "A transform for NAND network design," IEEE Trans., vol. C-21, pp. 12-20, Jan. 1972. [18] T.K. Liu, K. Hohulin, L.E. Shiau and S. Muroga, "Optimal one-bit full adders with different types of gates," IEEE Trans., vol. C-23, pp. 63-7O, Jan. 197^. [19] E.J. McCluskey, "Logical design theory of NOR gate networks with no- complemented inputs," Proc. 1+th Ann . Symp . on Switching Circuit Theory and Logical Design , pp. 137-1^, I963. [20] G.A. Maley and J. Earle, The Logical Pes ign of Transistor Digital Computers , Englewood Cliffs, N.J. : Prentice-Hall, 1963. [21] S. Muroga, "Logical design of optimal digital networks by integer programming," Chapter 5 in Advances in Information Systems Science , vol. 3, edited by J.T. Tou, Plenum Press, pp. 2b'3-34b, 1970. [22] S. Muroga, Threshold Logic and Its Applications , Chapter Ik, Wiley- Interscience, 1971. [23] S. Muroga, Logic design and switching theory, class notes, Dept. of Computer Science, Univ. of Illinois, Urbana, 111. [2k] S. Muroga and T. Ibaraki, "Logical design of an optimum network by integer linear programming - Part I," Report No. 26k, Dept. of Computer Science, Univ. of Illinois, July 1968. 6o [25] S. Muroga and T. Ibaraki, "Logical design of an optimum network by- integer linear programming - Part II," Report No. 289, Dept. of Computer Science, Univ. of Illinois, Dec. 1968. [26] S. Muroga and T. Ibaraki, "Design of optimum switching networks by integer programming," IEEE Trans., vol. C-21, pp. 573-582, June 1972. [27] T. Nakagawa, H.C. Lai and S. Muroga, "Pruning and branching methods for designing optimal networks by the branch-and-bound method," Report No. k'Jl, Dept. of Computer Science, Univ. of Illinois, Urbana, 111., Aug. 1971* Also International Journal of Computer and Information Sciences, Sept. 197^« [28] Y.H. Su and C.W. Nam, "Computer-aided synthesis of multiple -output multi-level NAND networks with fan- in and fan-out constraints, " IEEE Trans., vol. C-20, pp. lM+5-1^55, Dec. 1971. [29] H.C. Torng, Theory and Logic Design , Addison-Wesley, pp. 112-126, 1972. 3IBLI0GRAPHIC DATA IHEET 1. Report No. . _ . UTUCDCS-R-76-80^ 2. 3. Recipient's Accession No. 'network transduction based on permissible functions (general principles of nor network transduction nettra programs) 5. Report Date June 1976 6. . Author(s) Yahiko Kambayashi and Saburo Muroga 8. Performing Organization Rept. No -UTUCDCS-R- 76-8OI+ . Performing Organization Name and Address University of Illinois at Arbana- Champaign Department of Computer Science Urbana, Illinois 6l801 10. Project/Task/Work Unit No. 11. Contract /Grant No. NSF Grant No. DCR 73-03^21 2. Sponsoring Organization Name and Address National Science Foundation Washington, D.C. 13. Type of Report & Period Covered Technical 14. 5. Supplementary Notes 6. Abstracts When a switching function requires many gates in its implementation, it is usually difficult to design a network with a fewest possible number of gates (not necessarily a minimum number) by any known methods (optimal networks by the integer programming design approach or suboptimal networks by other known design methods). In this paper, the concept of permissible functions is introduced. Networks designed by some known design methods can be simplified by network transformation and reduction based on permissible functions. This transformation and reduction is called network transduction. This paper developed several network transduction methods along with examples . '. Key Words and Document Analysis. 17a. Descriptors Network transduction, network transformation, permissible function, logical design, NOR gates, maximum set of permissible functions, MSPF, Compatible set of permissible functions, CSPF. 'b. Identifiers/Open-Ended Terms 'c. COSATI Field/Group '•Availability Statement RELEASE UNLIMITED 19. Security Class (This Report) UNCLASSIFIED 21. No. of Pages 63 20. Security Class (This Page UNCLASSIFIED 22. Price >RM NTIS-35 (10-70) USCOMM-DC 40329-P7I IU1 \*>\m JUN 2 1 RECO