Efficient computer method for ExOR

logic design
P h . W . Besslich, D r . - l n g . , F.I.E.T.E.. F . I . E . ( l n d ) . [Link].

Indexing terms: Logic, Computer-aided design, Reed-Muller expansions

Abstract: Application of exclusive-OR logic design suffers from a lack of straightforward design methods.
Recently a procedure using generalised Reed-Muller (GRM) coefficient maps has been proposed. Based on this
approach, an efficient computer method is developed for the generation of all 2" sets of GRM coefficients of an
n-variable Boolean function. Along with the coefficients a metric may be calculated from which the minimum
cost set according to some criterion may be selected. The method requires a storage of 2" bits and an average of
2"" 1 + n/2 ExOR single-bit operations per set of GRM coefficients.

Zusammenfassung: Die ExOR-Logik wird wenig angewandt, da es an geeigneten Entwurfsmethoden fehlt.

Kiirzlich wurde ein Verfahren vorgeschlagen, das Diagramme von verallgemeinerten Reed-Muller-Koeffizienten
(GRM) verwendet. Auf der Grundlage dieses Verfahrens wird hier eine effiziente Computer-Methode zur
Erzeugung aller 2" Satze von GRM-Koeffizienten einer Funktion von n Variablen vorgestellt. Gemeinsam mit
den Koeffizienten kann eine Kostenfunktion berechnet werden, mit deren Hilfe man die giinstigste Realisierung
ermitteln kann. Die Methode erfordert einen Speicherraum von 2" Bits und im Mittel 2"~l + n/2 (Einzel-Bit-)
ExOR-Operationen je Realisierung.

1 Introduction map operations (foldings) in order to get the various sets of

GRM coefficient becomes troublesome if the number n of
Logic design using exclusive-OR gates offers two advan- variables exceeds four. It is the purpose of this paper to
tages when compared to conventional Boolean realisations suggest a fast computer method for the generation of all
using AND/OR/NAND/NOR gates. Firstly, in certain possible sets of GRM coefficients from which the optimum
cases more economic realisations in terms of the number of may then be selected.
gates and/or interconnections may be obtained. Secondly, The method we are proposing here is based on a fast
the testability of circuits is significantly improved [1]. The in-place transform method. The Boolean function is
gains from this second advantage may even exceed pos- assumed to be given in the form of a truth table. The 2"
sible disadvantages in such cases where the ExOR realis- values of the function are stored in memory. The algorithm
ation is more costly than the equivalent vertex form. then sequentially generates the 2" sets of the 2" GRM coef-
Applications have so far not become very popular because ficients in the very same memory locations. The algorithm
of the practical difficulties in the design procedure. In par- is fast, and hence an exhaustive search for the minimum
ticular, there are no easy to handle algorithms available to becomes feasible.
find minimum solutions, as there are in the case of
Boolean vertex networks. For the case of ExOR, sums of
products the Reed-Muller expansion [2] may be put to an
efficient use. However, the fixed positive (true) 'polarity' of 2 Generation of RM coefficients
the variables in the Reed-Muller expansion proves to be a
To generate the positive canonic RM expansion from the
major confinement. Actually the minumum form may
truth table let
require different polarities of the variables in its various
terms. f(x) = b0 0 bl x 0 0 b2
In a recent paper [3] Wu, Chen and Hurst have sug-
gested a map method for a generalised Reed-Muller ®b2n_lxox1
xn_ 0)
(GRM) expansion in which the variables may be true or where the GRM coefficients b{ are allocated in the order of
complemented. There are 2" sets of GRM coefficients for the decimal equivalent of the x, product terms, x 0 being
an n-variable function, which represent the function for all the least significant bit.
possible combinations of true or complemented variables, The positive canonic RM coefficients bj can take the
fixed for all terms. The 2" expansions of a function require values 0 or 1 only. Hence, they indicate which products of
different numbers of product terms. Let the presence or the variables are present in the expansion. In the case of
absence of a GRM term be represented by a 1 or 0, respec- n = 3 the eight possible products are:
tively. Then the number of ones is to be minimised by
complementing (suitable) variables. In Reference 3 it is 1, XQ , X 1 } X o X l5 X 2 , X o X 2 , X 1 X 2 , X o Xj X 2
shown how this can be pursued by map (folding and In order to relate the bj to the minterms, let the function
ExOR) operations. The penalty to be paid for the fixed be given as
polarities is a sub-optimum number of product terms,
while the number of input variables or the number of f(x) = como + clm1 c2n_1m2n-1 (2)
inverters required is generally less than for the minimum where the m, are the minterms and the c, e {0, 1} indicate
form. whether the functional value is zero or one for the related
Mapping of the RM coefficients and performing the input. As all the minterms in eqn. 2 are disjoint, it is per-
missible to change the inclusive-OR operators to exclusive-
Paper 2701E, first received 28th May 1982 and in revised form 23rd June 1983 OR operators:
The author is with the Department of Electrical Engineering, University of Bremen,
PO Box 330440, D-28OO Bremen 33, Federal Republic of Germany f(x) = como®clml ® •••®c2n_1m2n_1 (3)
IEE PROCEEDINGS, Vol. 130, Pt. E, No. 6, NOVEMBER 1983 203
 Equating eqns. 1 and 3: similar problems [4]. In this paper we are using signal-
processing (flow-graph) methods based on the matrix nota-
b0 © by x 0 © b2 Xj © b3 x0 © tion to obtain efficient algorithms.
e f c 2 - 1 * 0 * 1 •••
Let
= coxox1 • • x ^ ^
(4) and (8)
we find the relations between the c{ and bj. For this
purpose we allow the variables in the minterms to assume be column vectors. Then
all possible combinations of zeros and ones.
For the sake of simplicity let us confine ourselves to the b=RA®c (9)
case of n = 3. From eqn. 4 we obtain:
where R is a constant matrix and the operation A ©
x 0 = 0, Xy = 0, x 2 = 0: c 0 = b0 stands for a matrix multiplication in which multiplication
and addition are replaced by conjunction (A) and ExOR,
x 0 = 1, Xy = 0, x 2 = 0: Cy = b0 © by respectively. This operation may be considered a matrix
x0 = 0, Xy = 1, x 3 = 0: c2 = b0 © b2 V (5) multiplication in GF(2). The matrix R can be iteratively
built up from

x 0 = 1, Xy = 1, x 2 = 1: c7 = b0 © by © • • • © b7 (10)
Resolving these equations we obtain the bj expressed in
Eqns. 9 and 10 are special cases of a more general iterative
terms of the c,-: scheme [5].
^o — c 0 Example:
by =CQ®Cy
b2 = c 0 © c 2
b0 1 0 0 0 0 0 0 0 c0
b2 = c 0 © cy ®c2® c3
> (6) 1 1 0 0 0 0 0 0 cI
bA = c0 © c 4 b2 1 0 1 0 0 0 0 0 c2
1 1 1 1 0 0 0 0 c3
b5 = c0 © Cy ® c 4 © c 5 A©
bl 1 0 0 0 1 0 0 0 c4
b6 = c 0 © c 2 © c 4 © c 6 b5 1 1 0 0 1 1 0 0 c5
be 1 0 1 0 1 0 1 0 c6
67 = C0 © Cy ® C2 © C3 © C4 © C5 © C6 © C7 1 1 1 1 1 1 1 1 c7
Hence, the RM expansion of/(x) in terms of the c, is c0
f(x) = c 0 © (c0 © Cy) x0 ® (c0 © c2) x t ) c1
c 0 )c 2

© (c0 © c4) x 2 © (c0 ®Cy®c4® c5) x 0 x 2

© (CO ®C2®C4,® C6) XXX2
© (CO ®Cy@C2®C3® C4 © C5
©c6©c7)xox1x2 (7) The corresponding signal-flow diagram is shown in Fig. 1.
After the RM coefficients bj have been related to the truth The (relative) addresses of the c, are chosen according to
table entries, we will now devise an iterative in-place algo- the binary numbers of the minterms to which they are
rithm for computing the bj from the c,. This procedure will associated or, in other words, in the sequence of
be explained for n = 3. Karnaugh-map cells or truth table lines.
Table 1 shows how the 2" (binary) bj can be calculated The number of ExOR operations required for pro-
iteratively in 2" memory locations originally containing the cessing the ct is n2"~ 1 . The signal-flow diagram according
2" (binary) c{. The procedure requires exactly n iterations.
The processing of the c, may alternatively be expressed
in matrix form. Matrices have already been applied to

Table 1 : Iterative generation of the bt

Relative Initial After After After
location content 1st iteration 2nd iteration 3rd iteration

000 Co Co CQ CQ

001 q q CQ © I
010 c2 °2 Cb©C 2 CQ® i
011 °3 C,®C3 Co® i^ 2 ^^ 1 ^^ 3
100 c4 Co® C4 CQ © Ca Co® c' 4
101 c5 q ©c 5 q © c5 CQ ® ^
i 4 © ^ ©c 5
110 c6 C2®CG CQ®C^®C2®C6 CO©'C4 Q7 C 2 Op C g
111 c7 C3®C1 CI®C5®C3®C-, CQ ®c,! ©• • - 0 c 7
Fig. 1 Signal-flow diagram for generation of A3 from c3

204 IEE PROCEEDINGS, Vol. 130, Pt. E, No. 6, NOVEMBER 1983

to Fig. 1 may be extended for any n. Note that the memory the negation of the variable x 2 , and Figs. 2b and c show
locations need to store only bits, and the n2"~1 operations the negation of xx and x 0 , respectively. From the corre-
are single-bit operations From eqns. 5 and 6 it is discern- sponding signal-flow diagrams (Figs. 3a, b and c) we see
ible that applying the iterative operation to the vector b
reverses the operation to yield c. C Ci C

3 Generation of all sets of GRM coefficients b

s ".
b
1 b
1 b
5 b. e b
5

The procedure outlined in the previous Section generates

the fixed (positive) polarity RM coefficients from a given b
7
b
3 b
3 b
7 b
*
b
7
truth table. In Reference 3 it has been shown how, from
the RM-coefficient map 2"" 1 , other sets of RM coefficients
X
can be obtained, in which one or several variables are used 2 *2 X X,

in complemented form (generalised RM coefficients,

GRM). The purpose of generating different GRM expan-
sions is that they contain different numbers of ones, i.e.
different numbers of product terms. Hence, a minimal form
may be selected from them.
Unfortunately no algorithm is known from which we
could deduce information as to which variables to negate
in order to ensure a minimum realisation. The only way
conceivable with the present knowledge is an exhaustive
generation of all possible GRM coefficient sets. Fig. 3 Signal-flow diagrams for generation of GRM coefficients (n = 3)
The major problem is to find an efficient method to a Negation of x2 b Negation of .v, c Negation of .v0
generate the 2" — 1 other sets, namely with no additional
storage and with a minimum of operations. In this Section
we will show how all the 2" sets of GRM coefficients can that each folding is equivalent to one iteration of a radix-
sequentially be generated 'in-place' requiring only 2""1 two fast transformation, in which, compared to the trans-
ExOR operations per set. formation used in Section 2, the butterfly is 'upside-down'.
It has been shown [3] that the negation of a variable x,- In order to obtain all possible GRM expansions with a
in the RM expansion is equivalent to a folding of the minimum of operations, use is made of the following facts:
by-map along the x,/x,- interface. Although the map entries
on the x, side remain unchanged, the x, side is modified so (a) To obtain a GMR expansion in which two or more
that the new entries are the ExOR sums of associated cells variables are negated, the sequence of 'folding' operations
of the x, and the x, side. For simplicity we confine the is of no influence on the result [1].
demonstration of the method to n = 3. Fig. 2a illustrates {b) The transform operations are of the ExOR type
only. Consequently, performing the same iteration twice,
leaves the data unchanged.
-o b (j)
The 'polarities' in the 2" GRM expansions may be
expressed by the 2" possible 0/1 combinations of the n
variables, where 0 and 1 stand for complemented and true
•° b- variables, respectively. In order to generate all possible sets
of GRM coefficients, each one with only one iteration
(folding), the polarities of the variables are to follow a
U) Gray code pattern. Table 2 illustrates this procedure for
the case n = 3. As can be seen from Table 2, only one
iteration with 2"" 1 single-bit operations is required to gen-
erate another set of GRM coefficients.

-o u (j)
Table 2: Example for generation of the 2" sets of GRM
coefficients
GRMC Polarity Difference Iteration
k = (x2 x d = (x 2 x, X Fig.
b(0) 1 1 1
0 0 1 3c
£,(1) 1 1 0
1 0 0 3a
fc(5) 0 1 0
0 0 1 3c
fc<4) 0 1 1
0 1 0 3b
fc<6) 0 0 1
0 0 1 3c
£,(7) 0 0 0
1 0 0 3a
£,(3) 1 0 0
0 0 1 3c
Fig. 2 Operations to obtain GRM coefficients (n = 3) £,(2) 1 0 1
u Negation of x2 b Negation of x, c Negation of x 0

IEE PROCEEDINGS, Vol. 130, Pt. E, No. 6, NOVEMBER 1983 205

4 Example and concluding remarks ExOR operation. To determine the number of AND gates
or the total number of inputs, an assessment of the nature
In the previous two Sections it has been shown how the of the product terms is necessary. There are product terms
method given by Wu, Chen and Hurst [3] can efficiently consisting of a variable or the constant b0 = 1 only. They
be implemented on a computer. Depending on the are those having one 1 or no 1 at all in the binary rep-
throughput of the computer, the CPU time for an iteration resentation of their relative address a. They do not require
to generate a new set of GRM coefficients for a 4-8 vari- an AND gate, but an input for the ExOR gate, or only an
able problem is of the order of 1-100 ms. The method may inverter at the output in the case of the constant b0 = 1.
even be programmed on a programmable pocket calcu- All other product terms require an AND gate of | a \ inputs.
lator. A 5-variable problem takes about 20 s per iteration In our example the set A(14) is optimum: It requires 7
on a TI-59 calculator. ExOR inputs, 6 AND gates or a total of 24 gate inputs.
As an example we consider the 5-variable problem as In this paper a computer method is proposed to effi-
was used in Reference 3: ciently execute the mapping and folding procedures that
f(x) = £ 8, 10, 11, 16, 17, 19, 23, 24, 26, 27 were developed in Reference 3. These procedures generate
fixed-polarity GRM expansions only. It should be noted
From this truth-table representation we enter the c, (10 that mixed-polarity GRM expansions may still give fewer
ones) into the cleared (relative) memory locations 0 to 31, terms than fixed-polarity expansions. However, as no
as illustrated in Table 3 second column. Application of the general minimisation algorithm is available, an exhaustive
search for minimal mixed-polarity expansions would raise
Table 3: Example the computational effort significantly. On the other hand,
Memory c, b(0> b0) £,(31) mixed-polarity expansions may require more than n input
location signals (x, and 3c,, i = 0, 1, ..., n — 1), whereas fixed
0 0 0 1 0 0 polarity has a maximum of n inputs. Should integrated
1 0 0 0 0 0 circuit layout be involved, the number of inputs of a
2 0 0 1 0 0 network may be even more critical than absolute mini-
3 0 0 1 0 0 misation.
4 0 0 1 1 1
5 0 0 0 0 0 The method outlined here can work with only 2" bits of
6 0 0 1 0 1 storage and an average of 2"" 1 + n/2 single-bit operations
7 0 0 0 1 1 for the generation of a set of GRM coefficients. For each
8 1 1 0 0 1 set a cost function may easily be calculated and outputed
9 0 1 1 0 1
10 1 0 1 0 1
along with the coefficients.
11 1 1 0 0 1
12 0 1 1 1 1 References
13 0 1 0 0 0
14 0 0 1 0 0 1 REDDY, S.M.: 'Easily testable realisations for logic functions', IEEE
15 0 1 1 1 1 Trans., 1972, C-21, pp. 1083-1088
16 1 1 1 0 0 2 MULLER, D.E.: 'Application of Boolean algebra to switching circuit
17 1 0 0 0 0 design and error detection', IRE Trans. 1954, 1, pp. 6-12
18 0 1 1 0 0 3 WU, X., CHEN, X., and HURST, S.L.: 'Mapping of Reed-Muller coef-
19 1 1 1 0 0 ficients and the minimisation of exclusive OR-switching functions',
20 0 1 1 0 0 IEE Proc. E, Comput. & Digital Tech., 1982, 129, (1), pp. 15-20
21 0 0 0 0 0 4 GREEN, D.H., and TAYLOR, I.S.: 'Multiple-valued switching circuit
22 0 1 1 0 0 design by means of generalised Reed-Muller expansions', Digital Pro-
23 1 0 0 0 0 cesses, 1976, 2, pp. 63-81
24 1 1 1 0 1 5 BESSLICH, Ph.W.: 'A Method for the generation and processing of
25 0 0 0 1 1 dyadic indexed data', IEEE Trans., 1983, C-32, pp. 487-493
26 1 1 1 0 1
27 1 1 1 1 1
28 0 1 1 0 0
29 0 0 0 0 0
30 0 1 1 1 1
31 0 0 0 0 0

ExOR transformation (see Section 2) yields the third I Ph. W. Besslich was born in 1929 at Berlin,
column which represents the b{0) RM coefficients. For each Germany. Dr. Ph. W. Besslich is a recipient
ExOR iteration, according to Section 3, we obtain another of the Medal for Excellent Performance
from the Technical University of West
set of the GRM coefficients b(k) in the same memory loca- Berlin, where he was awarded Dipl.-Ing.
tions. Note that due to the linearity of the ExOR operation (M. Tech.) and Dr.-Ing. (Ph. D.) degrees in
each step could be reversed if the operation is executed a 1957 and 1963, respectively. He worked for
second time. However, no reversing is required if the iter- ten years in the research and development
ations are performed in the sequence according to Section wings of AEG-Telefunken and Philips in
3. From the 32 sets of GRM coefficients only b{0), b(i\ b{14) Germany, in the fields of communication
and A(31) have been included in Table 3. 'and data processing, and became the head
At this point the question of a suitable minimisation of a development department. From 1968-1974 he was seconded
to the Indian Institute of Technology, as professor and Head of
criterion arises. Depending on the realisation, different cri-
the Electronics & Communications Department, under the Indo-
teria may be applied: one is to minimise the number of German Agreement on Technical Co-operation. At present he is
AND gates, another one to minimise the number of inputs Professor of Electrical Engineering at the University of Bremen,
of the ExOR gate, or to minimise the overall number of Federal Republic of Germany. He is the author of many pub-
inputs. The choice of a criterion will be made according to lications and holds patents in the above mentioned fields.
a cost function to be applied. The number of ones in a set He is a Fellow of the IETE (New Delhi) and of the Institution
of GRM coefficients tells the number of inputs for the of Engineers (India). He is also a Senior Member of the IEEE.

206 IEE PROCEEDINGS, Vol. 130, Pt. E, No. 6, NOVEMBER 1983