LIBRARY OF THE
UNIVERSITY OF ILLINOIS
AT URBANA-CHAMPAICN
51084
UQ>r
ho. 293-300
cob.2
CENTRAL CIRCULATION AND BOOKSTACKS
The person borrowing this material is re-
sponsible for its renewal or return before
the Latest Date stamped below. You may
be charged a minimum fee of $75.00 for
each non-returned or lost item.
Theft, mutilation, or defacement of library materials can be
causes for student disciplinary action. All materials owned by
the University of Illinois Library are the property of the State
of Illinois and are protected by Article 16B of Illinois Criminal
law and Procedure.
TO RENEW, CALL (217) 333-8400.
University of Illinois Library at Urbana-Champaign
'JUM2 81999
ft 6 1 AJ1.
When renewing by phone, write new due date
below previous due date. L162
Digitized by the Internet Archive
in 2013
http://archive.org/details/optimumnetworkde293baug
J- Z-93
OPTIMUM NETWORK DESIGN USING
NOR AND NOR-AND GATES BY
INTEGER PROGRAMMING
by
C. R. Baugh
T. Ibaraki
T. K. Liu
S . Muroga
January 10, 1969
THE LIE IF THE
red 17 1969
Optimum Network Design Using
NOR and NOR-AND Gates by
Integer Programming
C. R. Baugh
T. Ibaraki
T. K. Liu
S . Muroga
January 10, 1969
S/P,ff
0SJ. 2^ Abstract
In this paper the integer programming formulations
of optimum network synthesis problems are demonstrated to be computationally-
feasible by actually obtaining all the optimum NOR gate networks and
NOR -AND gate networks for three variable switching functions. (80
representative functions of equivalent classes by permutation and negation
of variables. ) The algorithm used for solving the integer programs
is the implicit enumeration algorithm which was tailored to our problem
[91
with algorithmic and programming gimmicks. The total computation
time for these 80 functions on the IBM 360/751 was 110 minutes for NOR
gate networks and ^k minutes for NOR -AND gate networks. The algorithm
which was further modified by taking into consideration the inherent
structures of NOR gate networks showed a significant improvement of
computation time. With this second algorithm, all the optimum networks
under fan-in and fan-out restrictions for the odd parity function which
had not been computed before, were computed in 6 minutes and oq seconds.
All the optimum NOR-AND gate networks for each of 80 three
variable switching functions were also tabulated.
Optimum Network Design Using NOR and NOR-AID Gates By Integer Programming
1. Introduction
Based on the integer linear programming approach discussed in the
previous papers , optimum combinational networks of NOR gates
and those of NOR-AND gates have been synthesized. This paper presents
computational results. The integer programming algorithm used for
solving those problems is the implicit enumeration method which is
modified and it is described in detail elsewhere . The algorithm
is further tailored to our problems by making use of the particular
structures of our problems, improving the computational efficiency greatly
over the first algorithm.
In this paper all the optimal networks of three variable switching
functions with NOR gates and those with the combination of NOR-AND gates
are exhausted by integer programming approach. The computation time on
IBM 360/751 with the H level FORTRAN IV compiler for NOR networks for all
three variable switching function (80 representative functions of equivalent
classes by permutation and complementation of variables.) is 110 minutes,
and it is further improved by the factor of about 10 times by using the
above second algorithm. It takes 5^- minutes for synthesizing optimum
NOR-AND combination network for all three variable functions. This
result may suggest the computational feasibility of integer programming
approach and encourages further investigation.
2. Integer Programming and Implicit Enumeration
This section presents the outlines of the integer programming
problem and implicit enumeration algorithm for solving it. For detailed
description, see the references [6] [9] for example. The computer code
used for the network synthesis is discussed in the reference [9]. It
is a result of simplicication and modification of the original implicit
enumeration algorithm [l] [5] [6] [7] in order to improve computational
efficiency.
An integer programming problem with n unknown variables and m
constraints is in general stated as follows:
Minimize c x
(2.1)
subject to b + A x > 0,
where c is an n-dimensional vector of non-negative constants, "B" is an
m-dimensional vector of constants and A is an (m x n) matrix of given
coefficients, and x is an n-dimensional vector of variables. In our
case, all variables x are integers which assume only 1 or 0. Sometimes
this is refered to as the zero-one integer programming problem.
The implicit enumeration algorithm has been computationally
proved to be one of the most efficient methods for solving this type of
zero-one problem. It implicitly enumerates all the 2 solutions without
explicitly and exhaustively examining all of them, and picks up the
best feasible solution.
Let us start with several definitions. When all the variables in
x are assigned 1 or it will be called a solution . If a solution
satisfies the constraints A x + b > 0, it will be called a feasible solution
and if not, an infeasible solution . A feasible solution that minimizes
c x is an optimum feasible solution . A partial solution S is defined as
an assignment of "binary values to a subset of the n variables. Any
variables which are not assigned are called free variables . A completion
of a partial solution S is a binary assignment to all free variables.
Let us outline the implicit enumeration algorithm as it is shown
in figure 2.1. With a given partial solution S and the incumbent
solution (the feasible solution having the smallest value of the objective
function obtained thus far), the block entitled "CHK-IEQ" is entered. At
this point, examine whether some of the free variables must be 1 or
if each inequality is to be satisfied. Scanning through the inequalities
until no more free variables are assigned, S with these free variables
assigned becomes a new partial solution S . Next the partial solution
S is checked to determine which of the following 3 cases occurs.
(1) Feasible: The completion of S obtained by setting all
free variables to is found to be feasible. It is compared with the
incumbent and the better of the two is maintained as the incumbent. The
2
backtrack procedure is initiated to obtain a new partial solution S
by changing some of the assigned variables according to a certain rule.*
(2) Infeasible ; If at least one inequality is not satisfied by
S whatever binary values are assigned to the free variables, then S
is discarded immediately by initiating the backtrack procedure. The back-
2
track procedure forms a new partial solution S from S .
(3) Augment S : If neither of the above two cases occur, a free
2
variable is assigned to 1, forming S . The choice of this variable greatly
affects the convergence and it should be made according to the type of
problem being solved.
[7]
* The backtrack procedure was first proposed by Glover . A
detailed explanation can also be found in [6], [9] and will not be
described in this report.
2
After replacing S with S , the entire procedure is repeated by
reentering the block "CHK-IEQ".
Fig. 2.1 Implicit enumeration algorithm
(Augment S )
i_
AGMT - VAR
Augement S by
assigning a free
variable to obtain
„2
CHK - IEQ
Check inequalities
with S . Assign
free variables and
form S
(Feasible)
Keep the better solution
as the
incumbent
(infeasible)
_i
Backtrack
2
forms S
By cycling through this procedure repeatedly, the computation
results in the implicit enumeration of all possible solutions. When
the computation terminates, the incumbent is the optimum solution. The
checking procedure of each inequality such that one of cases (l), (2)
and (3) is quickly identified is explained in [9]. The implicit
enumeration algorithm converges in a finite number of steps, but the
efficiency of the algorithm heavily depends on the nature of an individual
problem. Our computational experience shows that tailoring the block
labeled AGMT-VAR in Fig. 2.1 (the subroutine which augments the partial
solution when (3) occurs) to a given particular problem speeds up
the convergence. Some aspects of our AGMT-VAR tailored to NOR gate
network synthesis will be discussed in Section k.
3. NOR Network Synthesis
All the optimum feed-forward NOR gate networks of three variable
switching functions are realized by using the formulation described in
[11]. Networks are optimum in the sense that the number of NOR gates
in the networks is minimized first and the number of interconnections
among gates and from external variables is minimized second. The same
problem was already solved by L. Hellerman by actually exhausting
all the network configurations and then finding the best network among
them for each function. When the problem is solved as an ordinary integer
program, however, the computation time for all three variable switching
functions (80 representative functions of equivalent classes by permutation
and complementation of variables) is about 110 minutes* on the IBM 360/751
with the H level FORTRAN IV compiler. This compares favorably with
Hellerman' s result consuming about 26 hours on the IBM 7090.
Now, the basic configuration for a NOR feed-forward network is
shown in Figure 3«1« Let us explain the additional inequalities, which
are introduced solely to reduce the computation time by precluding the
redundant connections or by partially precluding networks which are
equivalent by permutation of gates. The basic formulation of these
additional inequalities is the same as that of [11].
The problems we solved have three external variables x_, x p , x„.
Let the connection from x_ to the i-th gate be v_ . Let the connection
from the i-th gate to the k-th gate (i < k) be cp . Since only completely
IK
specified functions are considered, each input vectors x = (x , x p , x..)
is numbered as x J> j = 1, 2, . . ., 8 from 3T ' = (0, 0, 0) through
x = (l, 1, l). The output value of the i-th gate for the j-th input
vector 3T" 3 ' is denoted as T-?'. And let p:j*' denote cp., P: J '.
i lk lk i
* In Section k, this computation time is further reduced by designing
a sophisticated AGMT-VAR algorithm.
7
Fig. 3^1 Feed-forward network
cp,
IE
Inequalities for characterizing a feed-forward network with R NOR
gates which realizes the function f(x) is as follows.
For k - 1, 2, ..., R-l
- E v*x ( , d) - 2 P^ } > -U (1- p[ J) )
£=1 ^ l i=l 1K *
V „ k „(0') , V Jj) -. 1 TT -d(J)
(3-D
,\ *J 'i + = P ir > 1 " U P k
X>=1 1=1 = 1, 2, ..., Oj
where U is a sufficiently large positive number such that the upper
inequality is non-restrictive if p) = and the lower inequality is
non-restrictive if P, ' = 1.
k
For the last gate (the R th gate)
Z v* xft - E p^ > if f (x^ j) ) = 1
i=l l £ i=l lR "
(3.2)
z v* x ( . j) + s P ^ :> i if f (x^ j) ) = o
i=l ^ ^ i=l
j = J-^ ^- ^ • • » ) o i
And in place of the relation p.. = cp., p., we have the inequalities
IK IK 1
4 i] - *ik + <$ > - 1
p:*" + cp.. - 2 p^ > o
i T ik lk —
(3.3)
k = 2, 3, -.., R
j = 1, 2, . . ., 8.
The procedure used in this paper to obtain all optimum solutions
proceeds from R = 1 and increases R by 1 each time until the feasible
solution is reached. The objective function used is the number of
interconnections
R k-1 3 k
S ( 2 cp + Z O, (3.U)
k=l i=l 1K i=l l
and therefore its minimization results in the minimum number of
interconnections as the secondary objective. In other words, if we
find the first feasible R and then exhaust all the solutions which
minimizes the objective function (3«^)> all the optimum solutions are
obtained.
Seemingly the implicit enumeration algorithm has a tendency that
the smaller the region of all solutions, the faster the convergence.
Hence our effort was directed to preclude unnecessary solutions by adding
extra inequalities so that the solution region becomes smaller without
prohibiting any necessary optimum solutions. These additional inequalities
essentially consist of two types; one is to preclude unnecessary network
configurations and the other is to partially suppress the geometrically
equivalent networks (i.e. those with permuted gates). They are listed in
the following. Proofs are omitted.
(l) A NOR gate ( B in Fig. 3.2 (a)) which has only one input
from another gate ( A) with only one output, and which is not the
output gate is not permitted in an optimum network, because the same
7 7^^^ Fig. 3.2
& -®-d>"~@-*- -^5©""^ Cascaded
IX
(a) (b)
10
connections
function can be realized with two fewer gates, as shown in Fig. 3*2 (b).
Hence each gate except the last has at least one input from the external
variables or at least two inputs from the other gates, which is expressed
by an inequality:
3 k k-1
2 E v- + 2 cp > 2
£=1 Z i=l lk
(3-5)*
K. — J_j d % • • • « i\— J_«
Note that this condition does not hold in general when the fan-in
restriction is imposed.
(2) Consider any subnetwork which has only one gate which has outputs
to gates not in the subnetwork (Fig. 3* 3).
Fig. 3' 3 Ordering of inputs
~-»fc
(1 J
-^
~-fc
— ^
1
I
T ) — ( k \
»
r^ v-^
~-w
L>—
--^
subnetwork
Assume the subnetwork consists of 1 through k. Let the k-th gate is the
output gate of this subnetwork. Then we can order the interconnections
to the k-th gate from the other gates in the subnetwork such that
cp, < cp < . . .<
Fig. 3«^ Triangular interconnections
no other output
where the J th gate has no outputs except cp . It is easily proved that if
J K
all of cp. ., cp , cp are 1, the network is not optimum, thus introducing
ij -*-K Jk
inequalities:
*« + *ik + *dk * 2 + £ *Jt (3.7)
t=j+l
i < j < k < R .
Even if the i th gate in Fig. 3.^ is replaced by an external variable
x,, the above property is still true. Then from (3«7) we obtain:
12
v i- v i + v^ 2 +
R
E
t+k
t=j+l
•.,
(3.8)
j < k < R
I = 1. 2, 2L
(U) This condition is an extension of case (3). Consider any subnetwork
which has no outputs except those to the k th gate and where the i th gate
and the k-th gate is connected, as shown in Fig. 3' 5* Assume that the
subnetwork consists of the (i+l)st to (k l)st gates.
Fig. 3*5 Generalized triangular interconnections
no other output except
> to the k th gate
Then the interconnections from the i th gate to the subnetwork are all
redundant and therefore can be deleted. This condition is written by an
inequality:
k-1
E q>. .
k-i-1 R
< + U ( E E
^i+h i + ^ik^
h=l j=k+l 14 *' J lk
(3.9)
i = 1, 2, ..., R-2
k = i + 2 ..., R,
k-1
where U > E
cp. . for all i and k.
j=i+l
Even if the i-th gate is replaced by an external variable, the
above property is still true. In this case the inequality is:
13
k-1 . k-i-1 R
E y] <0 + U ( S E (p + (l-v*))
j=i+l * h=l j=k+l 1+n,:) ^
(3.10)
£=1, 2, 3
l = lj C. y m • • y R— £_
iv-- 1-rt j ■ • • « -^5
k-1
where U > Z v* for all i and k.
j=i+l
In the above discussion it was assumed that the subnetwork
consists of the gates of the consecutive numbers (i.e. from the (i+l)st
to (k-l)st gates) but an extension to the more general case where the
subnetwork consists of gates of non-consecutive numbers is possible.
(5) A certain geometrical symmetry is also investigated. For example,
Fig. 3' 6 shows three gates connected to the last gate.
Fig. 3» 6 Symmetry of a subnetwork
©
In this configuration, it makes no difference to which of three gates the
(R-l), (R-2), and (R-3)> the (R-if)th gate is connected. Hence we can
impose an ordering such that
Ur-1 - ^R^R-S ^ %4,R-3 (3oll)
in order to preclude part of the gate configurations which are equivalent
by permuting gates. This particular condition is represented by,
11+
VU,R-3 2 VM-2 + (1 * V 3 ,e' + (1 " "fe-2,R> + (1 - U>'
(3-12)
T'-
S-U,H-a * \4,R-! + (1 - tP R-3,E ) + (1 - \-2,R> + (1 " Vl,! 1
Similar types of symmetry conditions are extensively considered and a
number of such inequalities are employed in the actual computation.
However, the details of each type is not given here.
(6) If the interconnection between the i th and (i+l)st gates is known
to be 0, these two gates are geometrically equivalent and their output
connections can be ordered.
Hence we can first order their connections to the last gate as
%R * *i+l,B. (3 - 13)
If it turns out that cp. _ = ep. then the connections to the (R-l)th
gate can be ordered as
"i.R-l * "W-l. {3 - lk)
This argument continues until cp ^ cp. (k > i+l) eventually
holds. After that, no ordering on the connections is permitted. This
sequential condition is expressed by the inequality:
R-i . , R-i
S 2 D " ± cp. . .• Z 2 3 " 1 cp. _ . . + U cp. . _ (3-15)
i = 1, 2 } • • • j R~ 2 .
15
(7) Each gate has at least one output, because the network is assumed
to have exactly R gates. This condition is expressed by
R
2
j=k+l
% * X
(3.16)
for every k = 1, 2., . .„, R-l.
The size of the problem is given in Table 3.1, both with a selected
subset of the additional inequalities and without them.
TABLE 3.1 Size of NOR network formulation
Without additional inequalities
With additional
inequalities
R
Number of
integer programming
variables
Total number of
inequalities
% of non-zero
coefficients*
Total number of
inequalities
2
23
ko
11+.58
-
3
52
88
7.12
-
h
90
152
Ml
169
5
137
232
2.91
265
6
193
328
2.11
1+15
7
258
kko
1.60
716
* For the function f(x) = 0. For other functions, the sizes of figures
are almost equal to those in the table.
16
The formulations of the problems may be characterized by the
following properties:
(1) There are more inequalities than variables. Therefore the
solution region is usually very small. In fact, many problems were
found to be infeasible.
(2) The non-zero coefficients in the inequalities are fairly
sparse. This feature was extensively utilized in our computer program
of the implicit enumeration algorithm ^ J in order to speed up the
computation.
(3) The objective function has only coefficients of or 1.
[91
This also simplifies the algorithm and is fully utilized .
The implicit enumeration algorithm was used on the NOR synthesis
problem and the results are given in TABLE 3*2. The algorithm was set
to enumerate all optimal feasible solutions. It also assumed no fan-in
and fan-out restrictions. The computation took approximately 110 minutes
on the IBM 360/751 for a H 80 representative functions. All networks were
identical to Hellerman's.
We examined what are influential factors on the speed of our
program. The effect of additional inequalities on speed-up was remarkable.
Some problems tried for the R=5 formulation was speeded up by the factor
of 5 in computation time.
As explained in[n] many types of network restrictions such
as fan-ins and fan-outs can easily be added to the synthesis problem in
the form of inequalities, without the necessity of changing or complicating
the program. This is one of the advantages of the integer programming
formulation. When the fan-in restriction is imposed, the restrictions
17
CO
•H
CO
CO
CO
o
CO
g
S co
II
-P P>
&3
H
CO -P
H co
ft co
•H C.
-P
r-1 CO
> O -P CO
•H
<$ fe -H ft
CO
cd
CO
ch
.
d
fl
o
•H ^-v
-P M C CO
LT\
CO Cd CO O T3
c—
ON
ON
OJ
1
M-P ft-H fl
rod -P O
o
•
•
ON
•
LTN
•
1
1
h ft co o o
H
o
1
co g a g co
oo
«aj o -P ch w
t3
g
•H C!
,G
•P o
co
!>»
&S
C!
o
rd
cH
CO
J-
o
-4-
cs
•H
tj
•
•
•
-P H
-p
CO
ITN
CO
•4-
CO O
cd
■p
CO
LTN
vo
H co
H
«h CO
< O ft
d
o
•H ^-*
LT\
•P H £ co
t-
o
ON
VO
o
(0 cd co O 'd
OJ
ON
LfN
OJ
o
bO-P ft-H c!
•
•
•
•
•
cd 3 -P
oo
OJ
OJ
H ft CO O O
-d-
OO
£ s 3 s °
> -H 3 CO
ON
<; o -P chw
s
o m
•H (U W
-P H O
o -h £5
cj 3
3 o). For example, P.: is of type GC* because by setting cp = 1, F~
(2) (2)
can be covered. P.; is of type G*C* because of Pp = *. The type of
each gate is shown. Obviously the type of this partial network is G*C*
which is the type of gate 3*
Let us describe the procedure in the new AGMT-vAR. If the type of
partial network is one of ISL, COV, LTG, the current partial solution
is feasible because we use Procedure I in Section 5 of [11]. Otherwise
let us identify P. which defines the type of this partial network.
K.
In the definition of the types G*, VC*, GC*, G*C*, and NWG, free variables
are associated with P. such that if these free variables are set to 1,
k
P, is covered (e.g. in the case of VC*. P n is covered if v„ is set to
k k 11,
1, i.e if the corresponding free variable is set to 1. ). This free variable
is then specified so that p]_ is covered. For example, Fig. h.1 shows
(2) (2)
that P.: is identified according to the type of partial network. P_
is of type G*C* and can be covered by connecting gates 2 and 3? i-e by
(2) **
setting cp = 1 and specifying P^ = 1 . Other types are similarly
* The least desirable is chosen in the definition because unless
the gate having the least desirable is made to satisfy the
properties of NOR gates, the partial network is not feasible.
** In actual programming, this is done by augmenting the current
(o) (2)
partial solution by p\% - ! rather than cp = 1 and P^ ' = 1.
(2)
Subsequently cp and P^ are set to 1 when the partial solution
undergoes CHK-IEQ.
25
(3)
(J)
WG
vc*
*
vc*
■*
■*
vc*
vc*
LTG
vc^
1
vc*
-X-
,(d)
GC*
G*C*
1
G*C*
*
1
G*C*
G*C*
G*C*
cov
G*
cov
cov
1
tt
cov
cov
f
1
1
cov
1
cov
cov
1
1
cov
,(d)
Fig.
,(o)
U.l (a) Example of types of P<^ = 0, gates, and the partial network.
26
J
x l
*2
x 3
1
2
1
3
1
h
1
1
5
1
6
1
1
7
1
1
8
1
1
1
Fig. U.l (b) Assignment of values to x
^J)
27
* (i)
treated: An appropriate p in the c?se of G*, GC*, G*C* types or
an appropriate v„ in case of VC* is set to 1. However the type NWG
is treated differently. If a gate is of type NWG, the isolated gate
which has the largest gate number is identified. Let it be y. Then
p v is set to 1 where P defines the type of partial network. Setting
p , to 1 will force cp , and P JJ to 1. thus covering P, . However if
yk rk 7 k
p r_ (i.e. p ^_ is not a free variable), all solutions with anyone of
isolated gater, connected to gate k have been investigated and do not need
to be checked again. This follows from the fact that gate y and any
other isolated gate are equivalent with respect to the paritial network
(i.e. non-isolated part) since any isolated gate can be connected to
any other gate. This approach eliminates the permutation of gate labeling
which is inevitable with the feed-forward network. Of course, if we
discover that p was already set to 0, then we can simply abandon the
v K.
current partial solution and go to the backtrack procedure.
A comment is given on the case in which the type of the partial
network is VC*. If the types is VC*, sometimes more than one external
variable can be connected. In our algorithm, among all possible external
variables, the external variable which covers the largest number of
P =0 not yet covered is connected to the gate.
This new AGMT-VAR is used in place of AGMT-VAR shown in Fig. 2.1
and assigns a free variable to 1 according to the type of the partial
network. Then CHK-IEQ is applied as before. Other part of algorithm are
exactly the same as the general case discussed in the earlier sections
and in [9L except that the following objective bound check is added to
AGMT-VAR to further speed up the computation.
* Note that p:j^ = cp p;^
iK IK K
28
Given a partial solution, a lower bound of the objective function
value is estimated according to the rules based on the following properties.
If this bound exceeds the objective value of the incumbent, the current
partial solution can not give any better solution than that and accordingly
it is discarded. (The rest of computation for the current partial solution
is skipped and backtrack is immediately applied). The bound estimation
is programmed by using the following properties of the network:
(1) Exactly R gates are assumed to be used in the network. In other
words, each gate has at least one input connection and at
least one output connection.
(2) According to condition (l) of Section 3> each gate has either
at least one input connection from external variable or at
least two input connections from other gates.
(3) The number of gates each of which is solely devoted to expressing
x. (i.e. a gate has only one input which is an external variable
x.) is at most three.
1
(U) If the type of gate is GC*, G*C* or NWG, the gate needs
at least one more interconnection from another gate, as seen
from the definitions of these types.
(5) If the type of partial network is VC*, the gate whose type
defines the type of partial network needs at least one more
connection from an external variable. If this single external
variable does not cover all the P?. which are of type VC*, we
need to add at least one more external variable.
29
This bound estimation is included in AGMT-VAR and whenever it
demonstrates that the current partial solution can not give any better
Lbl e solution than the incumbent the backtrack procedure is performed
immediately.
With all these modifications added, all 15 functions which can be
realized with 6 gates were tested on the R= 6 formulation. The improvement
was remarkable. The average number of iterations per function is 136.3
and the average computation time for each function is ^.°9 seconds which
is favorably compared with the result in Table 3-2 in Section 3 run with the
general purpose AGMT-VAR, in which 95^ iterations and h-2.26 seconds on
the average were necessary for each function.
If the fan-ins and fan-outs restrictions are considered, the rules
based upon the above properties (2) and (3) must be modified. All other
rules are unchanged. For example let us assume that each gate has maximum
fan- ins and fan-outs of 3«
Let us examine Figure U.2.
Fig. k.2 Modification due to fan- in
and fan-out restrictions
30
The single input to gate j is not allowed only if
o R— 1 R— 1
S (vi + v£)+ 2 q> + E cp, , < 3 (U.U)
t=l * * t=l t:L t=l tk ""
tH tij
o R— 1 R — 1
and E (v* + v^) + E cp ti + 2 cp tk < 3 # (fc-5)
t=l t=l t=l
t+1 tt=j
t*i
Property (3) also must be modified.
Using the rules "based on these modified properties, the odd parity
function x © Xp © x_ which requires 8 NOR gates when the fan-ins and
fan-outs are limited to 3 was' solved.
Since there is only one function to be solved, the structure of
an optimum network for the function x_ © x © x is taken into consideration.
In other words, this function is symmetric in all the three variables
x_, Xp and x , and accordingly the interconnections from x. to the last
gate are ordered as follows.
7 7
and if v^ = v ' then
vl>vl>v[ (k.6)*
6 6
v ^ +1 > V £ J = 1, .2. (^.7)
* It can be easily shown that the last gate (the 8th gate) has no
external variables connected, if a given function can not be
expressed as a conjunction of the product ®f literals and a
disjunctive expression.
31
((k.'j) could "be continued to the gate numbers lower than 6. But the
continuation was not incorporated in our program. ) Also two interconnections
cjVn and cp ~ are assumed to be 1. This is guaranteed "by the fact that the
networks which are constructed by adding one gate to the output of optimum
7 NOR gate networks of x © x © x , give no better realization of
x Q, x @ x than those obtained by solving the 8 gate formulation.
The problem has 395 variables and 1012 inequalities including
additional inequalities. All optimum solutions are shown in Fig. U.3«
[13]
The network (c) of Fig. k.3 is the same as that found by Tangiguchi et al.
The computation took U822 iterations with network (a) occuring
at the 1368th iteration, network (b) at l6U7th iteration, and solution (c)
at the 3052th iteration. The total computation took less than 6 minutes
and 30 seconds on the IBM 360/751* When the program was modified so that
only one of the optimum solution is to be found, the time was reduced to
5 mil utes 15 seconds. These computation times are a considerable reduction
with respect to the results of Table 3*2 in Section 3»
The reduction of the computation is due to the desirability order
of types and the all-iterconnection formulation. The all-interconnection
network formulation appears to contribute more to the reduction than the
desirability order. The desirability order probably has to be changed
when different types of gates are to be used.
Our computation times are about the same as Davidson's, though
exact comparison is very difficult because computers used are different and
simple programming gimmicks may further make changes in computation times.
32
x 2
Xi
x 2
(a)
(b)
. (c)
Figure U.3". All optimum networks for x. @ Xp © x.
33
Probably one of the advantages of our approach is ease of programming
effort. Since we can fully use the information associated with variables
of the inequalities, the procedure to determine the types of P, , gates
and eventually the partial network is fairly straightforward and simple.
Also Property 1 of the NOR gate is automatically taken care of by the
CHK-IEQ routine, thus eliminating the procedure for checking this property.
Another advantage is the fixed amount of storage needed throughout the
computation. In Davidson's "branch and bound algorithm" the amount of
storage often grows as the computation proceeds. Thus additional programming
must be done in order to recalculate needed information or to use secondary
storage.
Because of great improvement of the all- interconnection network
formulation over the approach of Section 3* improvement in computation
time even in the case of multiple -output network design also can be
expected with the all-interconnection network formulation.
The accurate comparison of the exhaustive method, Davidson's and
ours, in terms of the program complexity, computational efficiency,
ease of programming and all other aspects, is difficult at this stage
because a number of factors should be considered for the comparison and
the data obtained so far is not sufficient. Here we tried this new
approach to show the flexibility of the implicit enumeration algorithm.
In other problems also, it is quite likely that we can achieve a great
improvement by considering the intrinsic properties of the problem and
incorporating appropriate modifications of the algorithm. Some examples
[91
of this approach will be found elsewhere
* Our integer programming approach can be extended to the logical
design of an optimum sequential network and to the diagnosis of
a network, different from Davidson's.
3^
5. NOR -AM) Network Synthesis
One of the important advantages of integer programming formulation
is that we can solve a wide variety of problems by simply changing the
set of inequalities. Networks composed of NOR and AND gates are represented
in inequalities according to the formulation in [12]. Of course the
optimum networks are also interesting in their own right. All the optimal
networks for 80 three variable switching functions are tabulated under the
same optimality criterion as NOR networks.
All the notations in this formulation are the same as NOR network
case except that we have to introduce new variables indicating whether
each gate is NOR or AND. These variables are
9 k , k=l, 2, ..., R. (5.1)
9 = 1 (0) shows that the k th gate is NOR (AND).
The basic set of inequalities describing a feed-forward network
of R gates is as follows. This formulation is found in [12].
For k = 1, 2, ..., R-l
3 k t*\ k-1 t*\ 3 k k-1 , v
= V i *i + = p ik * = v i + = *ik " U (l " P k j) " U 9 k
£=1 i=l z=l i=l
3 k (,\ k-1 , x 3 k k-1 f v
-2 v x^ ; - 2 p^ ; > -2 v - 2 cp +1-UP JJ -U0
i=l l l i=l 1K i=l Z i=l Ik k K
-2 vj xl^- 2 P^.P > - U(l-pf^r U (1-0J
i=l ^ ^ i=l lk ~ k k
S v k x (j) + 2 ~ (j) ■> " ^^
£=1 l l i=l
2 v* x^+ 2 p^ > 1 - U P k j; - U (l-0 k ) (5.2)
3 — -Lj £- j . . . > O.
35
It may be easily seen that the first twc inequalities are for an AND
gate and the others for a NOR gate, depending on the value of 6
associated with these inequalities.
For the last gate, if f(x^) = 1,
3 rj ( *\ R_ l /jN 3-n R-l
Z v x^ + Z p\^ > S v* + S p - U
i»i * * i=l ^ i=l ^ i=l lR R
ji^'^'S^- '^ 1 " 9 ^ (5 * 3)
and if f(x^) = 0,
3 R M n R-l /.x 3 R R-l
- E v*, x^ j - 2 p^ > -I v - E p + 1 - U e R
4=1 * l 1=1 4=1 * i=l
Z v ( A ( A E P ^ } > i-u(i-eJ (5.U)
4=1 * * 1=1 1R " R
for d = 1, 2, ..., 8.
The relation p.? = 1
l lk lk —
P i + ^ik " 2 p ±k - ° (5#5)
k = 2, 3, ..-, R
i = 1, 2, ..., k-1
3 = 1* ^ > • • • y o.
Additional inequalities are also incorporated to reduce the
computation time. All of those additionals inequalities which were
used in the all NOR network case are included except the geometrical
symmetry restrictions given by (5) of Section 3« In addition the following
two types of inequalities were added.
36
(l) Input interconnections
Each AND gate has at least two input interconnections. This
constraint is given by
3 k k-1
Z V £ + E p ik ^ 2 " 6 k
i=l * i=l lK *
Fig. 5-1 Triangular interconnection
(5.6)
(2) Triangular interconnections
Again consider three gates connected together as shown Fig. 5.1«
Contrary to the NOR network case, if either of the gates j and k is AND
gate, at least one of the three connections cp. ., r o , cp must be
^-3 !k jk
even if the j-th gate has outputs other than cp . This condition is
given by
cp. . + cp + cp < 2 + .
^ij jk ik - j
cd. . + cp.. + cp < 2 + 9 n
ij Y jk ik - k
(5.7)
i < j < k < R.
When the i th gate is replaced by an external variable,
v i + vv^ +
(5.8)
A + A + ^^ 2 + \
j < k < R
I = 1, 2, 3.
37
Together with these additional inequalities ( some of additional
inequalities based on the properties which have been discussed are not
incorporated because of their excessive number. ) , all the optimal
NOR-AND combination networks for each function are solved. The entire
computation took about ^k minutes on the IBM 360/751, using a program
which includes the general purpose AGMT-VAR. All functions are realized
with not more than six gates. The size of each problem and computation
time are listed in Tables 5*1 and 5.2. The computation time is
graphically given in Fig. 5*2 as well as the NOR network case.
The effect of additional inequalities was remarkable. For the
R=3 case the computation time was reduced 6 times by incorporating the
additional inequalities; and for the R=U case 18 times. Incorporation
of other additional constraints such as the constraint that each AND gate
should have at least one NOR gate connected to its output, will reduce
the computation time further, though these were not actually tried.
Also contrary to NOR gate network, no effort was made to improve
the computational efficiency of the integer programming algorithm. Of
course a significant reduction of computation time can be expected by
modifying the algorithm as discussed in Section k.
A comparison of computation time with NOR gate networks is
shown in TABLE 5«3 where the ratio of the computation time of the NOR-
AND network case to that of NOR network case discussed in Section 3
is listed.
38
o *
U ra
(U (D
N C -H
1 -H -P
C -H
O w H
£
CO
CM
H ra w
cd cd cd
-P -H rA -H
O-p Mni-p
-P -H fi fl -H
H -H O H
0)
t>
•H •->
+5 M
K (fi CD
CO +3 W
£ £1 £ ra
O -P CD CO
•H -H CQ H
+3 £
H H SZ!
bD-P 3
VD
o
UA
1
1
cd cd Ch
h h
CO
rt
1
CD CD H
>+3 d)
<'H P(
CD
H
•H
o
CO
cd
•H C
-P o
CD
Cd «H
-p -p
P o
H
ft 1
O «h
d
t~-
O -~-
•
•
•
H CO
o
co
CO
CD CD Ti
CM
bo ft a
cd O
>d
M CD O
CD g CD
> -H CO
< -Pv_-
-d
«h h
CD
O a)
-P
ft
CO
•
p
O co
cd
53 a
£\
o c
M
CD -H O
W
o
LT\
J-
_=t-
t>0-P -H
-=f
H
-=t-
co
cd cd -p
H
co
t-
h m O
00
CD CD a
> -p 3
<;-h
cd O
co
t>-
H CD O
_=r
CD S CD
> -H CO
<£ -P^--
co
CD C
H O
tH^-H
O -H -P
CO O
CO LT\ CX\
ir\
ON
-3-
\T\
• cd H
H
OJ
H
o —
R
Computation Time
Iterations
Feasible
Infeasible
Feasible
Infeasible
k
k.O
6.3
3.8
k.l
5
9.8
Ik.k
8.1
10.2
6
11.3
9.2
On the average a function can be realized by NOR-AND combination
network with O.85 fewer gates than that of the NOR network case. The
number of interconnections is also reduced by 1.5 on the average. All
the optimal networks for three variable function are tabulated in
Appendix A.
The tabulation also gives all the optimal networks by NAND-OR
combination by the following procedure: (l) take the dual of a given
function f, (2) find optimal networks for the dual function f by NOR-
AND combination and (3) replace NOR by NAND, and AND by OR. These are
optimal realizations of f by NAND-OR combination.
1+1
1000.0 -
100.0
10.0 z
1.0 _
.k -
150 200 250
Number of NOR gates
I
4
umber of NOR -AND gates
Fig. 5« 2 Average computation time per function
for NOR and NOR -AND synthesis
fe
6. Conclusion
Two logical design problems, one with NOR gates only and the
other with NOR-AND combination, formulated as integer linear programs
were solved by using the implicit enumeration algorithm. NOR gate
network synthesis is very important from an engineering view point and
has attracted much attention. Integer programming approach to this
problem is proved to be computationally feasible and is faster than
Hellerman's exhaustive method. Advantages of integer programming approach
include its versatility and simplicity to handle a variety of gate types,
a variety of network restrictions such as maximum fan-ins restriction,
and also various objectives, without changing the algorithm.
Simply changing part of the algorithm i.e. the AGMT-VAR, we can
have a program of high speed at the sacrifice of the ease of programming,
a program of simplicity and generality at the sacrifice of speed, and
a wide range of programs between these two extremes.
Due to the principle of the implicit enumeration algorithm, we can
modify and augment the algorithm so that the intrinsic properties of the
problem can be fully used. Section h explored this possibility along
with Davidson's work and obtained a improved result in NOR gate network
synthesis. Furthermore three networks for the odd parity function were
proven to be optimum.
By simply changing the inequalities, different problems can be
solved. NOR-AND gate networks were thus synthesized by using different
set of inequalities. Also we believe that this is the first tabulation
of all the optimum networks with NOR and AND gates for all three variable
functions.
U3
Reference ,
[1] E. Balas, "An additive algorithm for solving linear p rograms with
zero-one variables, " Operations Research, vol. 13, no. h pp. 517-5^9,
July-August 1965.
[2] M. A. Breuer, "Implementation of threshold nets by integer linear
Programming," IEEETEC, vol. EC-lU, no. 6, pp. 950-952, December I965.
[3] S. H. Cameron, "The generation of minimal threshold nets by an
integer program, " IEEETEC , vol. EC-13, no. 3, pp 299-302, June I96U.
[k] E. S. Davidson, "An algorithm for NAND decomposition of combinational
switching function," Ph.D. dissertation, Department of Electrical
Engineering and Coordinated Science Laboratory, University of
Illinois, 1958.
[5] B. Fleischman, "Computational experience with the algorithm of
Balas, " Oper a tions Re se arch , vol. 15, no. 1, pp. 153-155*
January - February 19^7 •
[6] A. M. Geoff rion, "Integer programming by implicit enumeration
and balas' method," SIAM Review , vol. 9 no. 2, pp I78-I9O,
April I967.
[7] F. Glover, "A multiphase-dual algorithm for the zero-one integer
programming problem, " Operations Research vol. 13, no. 6, pp 879-919*
November-December 1955*
[8] L. He Herman, "A catalog of three - variable OR- invert and AND- invert
logical circuits," IEEETEC , vol. EC-12 no. 3 pp. 193-223, June I963
[9] T. Ibaraki, T. K. Liu, C. R. Baugh, and S. Muroga, "Implicit
enumeration program for zero-one integer programming," to be
published.
[10] T. K. Liu, "A code for zero-one integer linear programming by
implicit enumeration, " Master thesis, Department of Computer
Science, University of Illinois, I968.
[11] S. Muroga and T. Ibaraki, "Logical design of an optimum network
by integer linear programming - Part I," Report No. 26k, Department
of Computer Science, University of Illinois, July I968.
[12] S. Muroga and T. Ibaraki, "Logical design of an optimum network
by Integer Linear "programming - Part II, " Report No. 289, Department
of Computer Science, University of Illinois, December 1968.
[13] K. Taniguchi, N. Tokura, T. Kasami and H. Ozaki, " Logical functions
realizable by a planar NAND network, " The Trans, of Electronics
and Commu nica tion Engineers of Japan , vol. 51-C, no. 2, pp. 59-65,
February 196 8.
kh
Appendix A: Tabulation 0:.' Optimum NOR-AND Networks
Here listed are all the optimum networks for each of all functions
of up through three variables, using NOR and/or AND gates.
The networks which have the minimum number of interconnections
and connections among the networks with the minimum number of gates are
chosen as optimal network.
The procedure for obtaining the optimum network diagram for a
given function follows that of Hellerman's [8]. A function can be
represented by a truth table as shown below, by specifying the values of
f , f p , ..., fn where f , ..., f~ show the values of the given f for
input vectors in the same rows, a, b and c denote the variables of f.
a
b
c
f l
f 2
1
f 3
1
f k
1
1
f 5
1
f 6
1
1
f 7
1
1
f 8
1
1
1
Let us write eight binary numbers f _, , .... f as follows.
1 o
f 8 f 7 f 6 f 5 f U f 3 f 2 f l
Sfc — v ' * y— ' " v '
0.
0.
Al
grouping the f.'s as shown, we obtain three octal number . This
octal number is used throughout Appendix to identify a function.
In Tables A2 and A3, only representatives of equivalence class
obtained by permutation of variables are listed, reducing 256 functions
into 80 representatives. The representative of a given function f can
be easily derived by using Table Al, which is taken from Hellerman [8].
The procedure is illustrated by an example.
Suppose that the function f has the number 321. The entry for
this number in Table Al is 5*213 • This means that f is equivalent
to function 213 hy applying permutation 5 which is (ac) as also shown
in Table Al. Table A2 shows that function 213 has optimum networks
with network numbers U9 and 56. Then Table A3 gives us the actual
optimum networks of function 213. To obtain optimum networks of 321,
we apply the inverse of permutation 5j which is also (ac), to these
networks in Table A3.
Twelve of the 80 three -variable functions listed are degenerate
in the sense that they are independent of at least one variable. The
network diagram numbers for the degenerate functions have the suffix D.
They are grouped together at the beginning of Table A3.
Table A3 shows all the optimum networks obtained for each function
without imposing fan-in restrictions. However all the networks except
that of function 026 are optimum even if the fan-in restriction that
each gate can have at most three input interconnections is imposed.
Function 026 needs one more gate if the above fan-in restriction is
imposed. Optimum networks in this case are shown in Fig. Al.
A2
Note that if a given function is symmetric in some variables,
say a and b, then, among all the optimum networks obtainable by permuting
these symetric variables, a and b, only one network is listed in Table
A2 and Table A3. The rest of networks can be obtained by simply exchanging
the connection from the external variables according to the permutation
of variables.
A3
1
2
3
1+
5
6
-1*000
1*001
1*002
-1*003
3*002
-3*003
1*006
10
1*010
1*011
-1*012
1*013
-1+*012
i+*0l3
1*016
20
2*002
-2*003
2*006
2*007
3*006
3*007
1*026
30
1*030
1*031
1*032
1*033
U*032
l+*033
1*036
1+0
2*010
2*011
-6*012
6*013
•2*030
2*031
6*032
50
1*050
1*051
1*052
1*053
1*051+
1*055
1*056
6o
-2*012
2*013
2*016
-2*017
2*032
2*033
2*036
70
6*05^
6*055
6*056
6*057
-1*071+
1*075
1*076
100
3*010
3*011
3*030
3*031
-3*012
3*013
3*032
110
3*050
3*051
i+*05i+
l+*055
3*052
3*053
l+*056
120
-5*012
5*013
5*032
5*033
3*016
-3*017
3*036
130
3*05^
3*055
-3*071+
3*075
3*056
3*057
3*076
lUo
2*050
2*051
2*051+
2*055
5*05l+
5*055
-2*07U
150
1*150
1*151
1*152
1*153
3*152
3*153
1*156
160
2*052
2*053
2*056
2*057
5*056
5*057
2*076
170
2*152
2*153
2*156
2*157
3*156
3*157
1*176
200
1*200
1*201
1*202
1*203
3*202
3*203
1*206
210
-1*210
1*211
1*212
1*213
1+*212
1+*213
1*216
220
2*202
2*203
2*206
2*207
3*206
3*207
1*226
230
1*230
-1*231
1*232
1*233
l+*232
l+*233
1*236
2 1+0
-2*210
2*211
6*212
6*213
2*230
-2*231
6*232
250
1*250
1*251
-1*252
1*253
1*251+
1*255
1*256
260
2*212
2*213
2*216
2*217
2*232
2*233
2*236
270
6*2 51+
6*255
6*256
-6*257
1*27U
1*275
1*276
300
-3*210
3*211
3*230
-3*231
3*212
3*213
3*232
310
3*<5°
3*251
l+*25l+
l+*255
-3*252
3*253
l+*256
320
5*212
5*213
5*232
5*233
3*216
3*217
3*236
330
3*251+
3*255
3*27^
3*275
3*256
-3*257
3*276
3^0
2*250
2*251
2*251+
2*255
5*25l4
5*255
2*27U
350
1*350
1*351
1*352
1*353
3*352
3*353
-1*356
360
-2*252
2*253
2*256
-2*257
5*256
-5*257
2*276
370
2*352
2*353
-2*356
2*357
-3*356
3*357
1*376
7
1*007
-1*017
1*027
1*037
6*033
1*057
2*037
-1*077
3*033
l+*057
3*037
-3*077
2*075
1*157
-2*077
1*177
1*207
1*217
1*227
1*237
6*233
-1*257
2*237
1*277
3*233
-l+*257
3*237
3*277
2*275
1*357
2*277
-1*377
Explanatory Example
Class of 321 is given by word at intersection of row 320 and column 1,
This says 321 is in class of 213 by permutation 5«
Negative permutation means the function is degenerate.
5*213
Permutation 1 is the identity
Permutation 2 is ( abc)
Permutation 3 is ( acb)
Permutation 1+ is ( be)
Permutation 5 is ( ac)
Permutation 6 is ( ab)
Table Al. Equivalent classes of functions
of three variables.
Al+
Table A2: Catalog of all the optimum NOR-AND networks
of three variable functions.
A5
Function
(octal)
000
003
012
017
07^
077
210
231
252
257
356
377
001
002
006
007
010
Oil
013
Functional expression
a'b'
a'c
a'
ab' + a'b
a' + V
be
be + b'c'
c
a' + c
b + c
1
a'b'c'
a'b'c
a'b'c + a'bc'
a'b' + a'c'
a'bc
a'bc + a'b'c'
a'b' 4- a'c
Network
number
ID
5D
8D
9D
kD
13D
10D
6d
iUd
15D
3D
11D
12D
7D
2D
1
3
7
15
8
6
5h
61
18
No« of gates
NOR
1
2
1
1
2
1
3
3
3
2
2
1
2
1
2
1
1
3
3
3
AND
1
1
1
1
1
1
1
1
1
1
1
1
1
No. of inter-
connections
and
connections
2
3
3
1
6
3
2
7
7
k
h
3
3
k
k
7
k
k
8
8
5
1
2
2
1
2
2
1
3
3
3
3
2
1
2
2
2
2
2
3
3
3
A6
Function
(octal)
Functional expression
N itwork
number
No. of gates
No. of inter-
connections
and
No. of
levels
<
NOR
AND
connections
22
2
1
5
3
)l6
a'b + a'c
k
2
k
2
)26
a'b'c + a'bc' + ab'c'
68
2
3
13
2
ff
a'b* + b'c' + a'c'
30
1
3
9
2
)30
ab'c' + a'bc
70
k
1
10
3
1 71
3
2
10
3
88
k
1
10
k
)31
a'bc + b'c'
85
k
1
9
k
)32
a'c + ab'c'
28
2
2
9
2
»33
a'c + b'c'
3k
3
1
7
3
kk
2
2
7
3
36
a'b + a'c + ab'c'
29
2
2
10
2
37
a* + b'c'
17
1
2
6
2
50
a'bc + ab'c
27
3
1
8
2
55
2
2
8
3
51
a'b'c' + a'bc + ab'c
79
3
2
11
3
52
a'c + b'c
11
2
1
5
2
26
1
2
5
3
53
a'b' + a'c + b'c
36
3
1
8
3
5k
a'b + ab'c
k7
2
2
8
3
55
a'b + a'c' + ab'c
lh
3
2
11
3
78
3
2
11
3
56
a'b + b'c
12
2
1
6
2
57
a* + b'c
33
3
1
7
3
i
h3
2
2
7
3
p
a'b + ab' + a'c'
35
3
1
8
3
U5
2
2
8
3
J6
a'b + ab' + a'c
Ik
2
1
7
2
A7
Function
(octal)
Functional expression
Network
number
No. of gates
No. of inter-
connections
and
connections
No. of
NOR
AND
levels
150
a'bc + ab'c 4- abc'
80
3
2
11
3
151
a'bc + ab'c + abc' + a'b'c'
101
3
3
Ik
3
152
a'c + b'c + abc'
62
2
2
8
' 3
153
a'c + a'b' + b'c + abc'
76
3
2
11
3
156
a'c + b'c + be'
13
2
1
7
2
157
a' + b'c + be'
37
3
1
9
3
U6
2
2
9
3
176
ab' + be' + a'c
16
2
1
8
2
177
a' + b* + c'
9
1
1
k
2
200
abc
2
1
3
1
201
abc + a'b'c'
52
3
1
9
3
202
abc + a'b'c
73
1+
1
9
3
77
h
1
9
3
82
3
2
9
k
90
3
2
9
h
203
abc + a'b'
50
3
1
8
3
206
a'b'c + a'bc' + abc
100
k
2
12
3
10^
k
2
12
k
106
k
2
12
k
109
k
2
12
k
110
k
2
12
k
111
k
2
12
h
112
k
2
12
k
207
a'b' + a'c' + abc
81
3
2
9
3
-J
A8
Functio]
(octal)
i Functional expression
Network
number
No.
of gates
No. of inter
connections
and
No. of
levels
NOR
AND
4
connections
89
3
2
9
k
9h
3
2
9
k
211
be + a'b'c*
51
3
1
8
3
212
a'c + be
31
1+
6
3
38
3
1
6
3
6k
3
1
6
It
66
2
2
6
k
213
a'b' + be
^9
3
1
7
3
56
3
1
7
3
216
a'b + a'c + be
72
k
1
9
3
86
k
1
9
k
91
3
2
9
k
95
k
1
9
k
96
k
1
9
k
217
a' + be
1+8
3
1
6
3
61
2
2
6
k
226
abc + ab'c' + a'bc' + a'b'c
105
k
2
12
k
227
a'b' + a'c' + b'c' + abc
99
k
2
12
3
102
k
2
12
k
230
ab'c' + be
8k
k
1
9
k
87
3
P
9
k
97
3
2
9
k
232
a'c + be + ab'c'
92
k
1
9
k
93
3
2
9
k
?33
a'b' + b'c' + be
57
i 1
3
1
8
,_
3
A9
No. of inter-
connections
Function
(octal)
Functional expression
Network
number
No. of gates
and
connections
No. of
NOR
AND
levels
236
a' c + be + a'b + ab'c'
98
k
2
12
3
103
k
2
12
h
107
k
2
12
k
108
k
2
12
h
237
a' + be + b'c*
69
k
1
9
3
83
3
2
9
k
250
ac + be
10
3
5
2
21
2
1
5
3
251
ac + be + a'b'c'
59
3
1
8
3
253
a'b' + c
20
3
5
3
25^
ac + a'b
32
k
7
3
39
3
1
7
3
255
ac + be + a'c'
58
3
1
8
3
256
a'b + c
63
h
6
h 1
65
3
1
6
k
27U
ab 1 + ac + a'b
Uo
3
1
8
3
275
ab' + ac + a'b + a'c'
60
3
1
9
3
276
a'b + ab' + c
kl
3
1
9
3
277
a' + b' + c
23
2
1
5
3
350
ab + ac + be
k2
3
1
8
3
351
ab + ac + be + a'b'c'
75
3
2
11
352
ab + c
25
2
1
5
3
353
ab + a'b' + c
53
3
1
8
3
357
a' + b + c
19
3
5
3
2k
2
1
5
3 :
376
a + b + c
5
2
1
1*
2
J
Table A3 List of all the optimum NOR -AND
combination networks for three variable
switching functions.
NOR
>
AND
All
o
I-
<_>
z
3
r--
O
CM
o
Q
CD
Li.
CM
in
O
CO
in
p
Z
O
u
Li.
o
CM
6
o
CM
s
o
H
U
o
o
o
o
z
§
o
A12
z
o
o
3
u.
♦
X>
o
"o
O
O
CO
u
x>
<0
m
o
<\j
10
<£>
o
O
z
3
u
"X)
CM
o
o
o
o
m
O
z
o
3
u.
u
jO
o
o
CM
o
Z
g
o
iX>
O
CVJ
z
o
o
z
U_
o
o
u
XI
*
♦
"XI
♦
"o
O
z
(J>
m
A13
o
z
=>
o
z
(XI
O
Z
o
o
z
3
If)
m
z
o
o
z
3
ro
O
o
z
a
o
z
=5
rO
O
O
z
A114
z
o
u
z
O
o
z
o
8
K
o
t-
u
z
O
z
in
ro
5
5
o
z
2
o
z
to
O
8
$
o
i-
o
3
u.
A15
8
o
z
z
3
o a o a
s
s
o
z
o
CM
o
IT)
s
z
o
CM
O A O A
€
to
Al6
Z
O
z
23
8
3
"■§
o
p
a
o
z
c\j
ID
+
on jn
CM
CM
g
IS
z
o
t-
u
z
3
O
z
ID
m
CM
s
£1 u A
8
A17
o
3
o
CM
CD
O
I-
u
3
Li.
r<->
CM
r<1
CD
CO
CO
CM
«
2
CM
o
CM
8
8
£
o
s
3
Li-
fe
o
CM
jo
o
£1
0*J
ro
ro
0>
A18
3
in
o
(VI
D
+
3
o
z
N
c\j
CM
8
Z
o
U
z
U.
ID
to
CM
8
3
O
s
s
A19
k .=r>
(1)
(2)
'=Oi
:=£>
:z C>T70R>*
-E>
(3)
(4)
dZh
c-^>
(5)
Fig. Al Optimum networks of function 026
when the fan- in is limited to three.
A20
APPENDIX B: Ordering of Interconnections
In the feed-forward network formulation gates are uniquely labeled
1, 2, ..., R. Usually there are many representations for the same
configuration of the optimal network simply by permuting the labels on
gates. For example the two networks in Fig. B.l are equivalent under
permutation of gate labels.
L 3'
In order to reduce this obvious redundancy many inequalities are formulated
to order the gates.
For an example of such inequalities a list of inequalities for the
6 gate feed-forward NOR network will be presented.
Since the inequalities were not generated systematically, the
list is not complete.
Let us denote (l - cp.) by cp. . where cp. . is 1 if there is an
interconnection from gate i to gate j and otherwise.
Note that the inequalities are for 6 gate NOR networks with
unlimited fan-ins and fan-outs. The inequalities corresponding to an
R gate NOR network with restrictions on fan-ins and fan-outs can be
written in an analogous way.
B-l
1. Order Inputs to the R-th Gate (i.e. output gate )
The ordering of connecting gates 1 through R - 1 to the output
gate R can be specified as cp > cp for all i > j. This follows from
ik — JK
that fact that any circuit with cp > cp . and k < £ can be obtained from
a circuit in which cp^ > cp for all i > j by permutation of gate labeles,
in — JK
k and I.
'26 s 1>36
2. Ordering the Outputs of All Isolated Gates
As was defined previously an isolated gate is a gate which has
none of variables, v.'s and cp ' s representing its inputs and outputs
1 jk
specified to 1. When the isolated gate is connected to the subnetwork,
the isolated gate can often be connected in several ways. Furthermore
the networks resulting from these different ways of connecting the gate
are often equivalent with respect to permutation of the gate labels.
In Fig. B.2 networks (b) and (c) give an example of two different ways
of connecting the isolated gate 3*
Fie;. B.2
B-2
By examining Fig. B.2 we can see that gates k and 5 of the subnetwork
consisting of gates k, 5, and 6 are equivalent with respect to permutation
of gate lables and the connection of gate 3 to gate k or 5 (i.e. network
(b) is equivalent to network (c) if gate labels k and 5 are permuted).
Thus we can restrict cp , < cp for the given subnetwork consisting of
gates k,$ and 6 to prohibit network (c).
The subnetwork (a) in Fig. B.2 can be specified as
^36 + \6 + * 5 6 (1)
for the following reason. The sum in expression (l) assumes the value
zero if and only if the gate U,5 and 6 are connected as shown in Fig. B.2
fa) and otherwise it is 1 or greater. Thus we can order the pair of
interconnections cp„_ and cp„, under the assumption that the subnetwork
3? 3*+
of Fig. 3' 2 (a) exists. This conditional ordering of gate output inter-
connections can be expressed by the following inequality
^<^ 35 +* 3 6 + \6 + V (2)
Because if the subnetwork exists, the last three terms of (2) becomes
and (2) becomes cp , < cp . Let us call cp , < cp of expression
(2) as the ordering portion and + cp ^ + cp, ^ + cp /- as the subnetwork
specification portion. Note that the subnetwork specification portion
will be positive and expression (2) will be non-restrictive if the
subnetwork described by cp , + -cp, ^ + "cp ^ does not exists.
All the following inequalities in this section can be similarly
interpreted by first examining the subnetwork specification portion
B-3
of the inequality and then observing the ordering required on the pair
of cp. . variables.
a)
5 W 6 **(*)
This subnetwork is denoted by cp,-,- + 9^6 * Assuming this subnetwork
we can get the following inequalities in terms of isolated gates, according
to the above discussion.
Ordering Subnetwork
^35 - % + ^56 + \6
^25 - *35 + *56 + \6
^15 - *25 + ^56 + ^6
^23 - ^h + ^35 + H + \6
^13 * 'lU + % + V + ^6
^!2< 6 + 2cp 2 5 + ^ ^ Ucp 3 6 + 2C °35 + ^ +8CP 2 3 (3)
The subnetwork specification portion of expression (3) is 8cp . The
ordering portion is i+cp g + 2cp + cp , < i+q? g + 2cp + cp . which expresses
the restrictions
B-6
"26 * V