Gate-level Synthesis of Boolean Functions using Binary Multiplexers and Genetic Programming

Arturo Hern ndez-Aguirre a Bill P. Buckles Department of Electrical Engineering and Computer Science Tulane University, New Orleans, LA, 70118, USA fhernanda,[email protected] Carlos A. Coello-Coello Laboratorio Nacional de Inform tica Avanzada a R bsamen 80, A.P. 696 e Xalapa, Veracruz, 91090, M xico e [email protected]

Abstract- This paper presents a genetic programming approach for the synthesis of logic functions by means of multiplexers. The approach uses the 1-control line multiplexer as the only design unit. Any logic function (dened by a truth table) can be produced through the replication of this single unit. Our tness function works in two stages: rst, it nds feasible solutions, and then it concentrates on the minimization of the circuit. The proposed approach does not require any knowledge from the application domain.

1 Introduction
The synthesis of logic circuits is a problem as old as the rst computer. Initial steps in this direction were given by Shannon [17], who found important mathematical properties that led to the synthesis of Boolean functions. Akers [1] proposed binary decision diagrams as the vehicle to represent and minimize Boolean functions. Bryant [3] proposed ordered binary decision diagrams (OBDD). Both approaches are based on the manipulation of the nodes of the graph, thus, the initial graph is transformed into functional equivalent subgraphs. The repetitive application of two or three simplication rules (derived from the problem domain) have proven to be sufcient to minimize these graphs. In essence, the goal is achieved by a top-down minimization strategy. That is, reduced graphs are produced from complete graphs. Several researchers have added the decision diagram simplication rules into the genetic programming environment by modifying the crossover and mutation operators [20, 7]. The added knowledge reduces the convergence time, and improves the ability to nd optimal solutions. Mechanisms of this sort do not synthesize circuits. Instead, they simplify a set of circuits (by reducing graphs) that have to be already fully functional. They also exhibit a lack of generality since the added knowledge reduces their applicability to a certain specic problem. The genetic programming (GP) approach we are to describe, follows the automatic programming capacity proclaimed by Koza [10]. That is, GP synthesizes programs or functions that reproduce a desired behavior. In our system, GP constructs Boolean functions by combining samples taken from the space of partial solutions. Once a 100% functional solution is found, our goal is turned to their minimization. Thus, the tness function is updated to reward fully functional

solutions with fewer elements. Trees (that represent circuits) are therefore trimmed, and nodes are replicated without the need of adding any heuristic other than a simple change in the tness function. The great difference between the two approaches is evident. Graph techniques apply minimization rules to the binary decision diagrams. GP with added knowledge becomes a top-down reduction method [20, 7]. Our system works with the purest form of GP. Therefore, no problem domain knowledge is included in the evolutionary process, and yet, the approach is able to produce optimal or near optimal circuits. Our approach is analog to what is called gate-level design [6]. Commonly, gate-level design using evolutionary techniques makes use of a sound and complete set of gates (AND, OR, NOT, XOR). Therefore, circuit synthesis is achieved by the correct composition (connections) of a sound set of gates [15, 9, 4, 12, 11]. Taking a radical approach to the circuit design problem, we substituted gates by binary multiplexers. Binary multiplexers are universal function generators (dened later). Thus, they form a sound basis for the synthesis of logic functions. The working hypothesis is that GP can synthesize logic circuits by means of binary multiplexers (muxes, for short) [10], and that the replication of only one element (instead of ve or six different gates) will decrease the manufacturing process cost (in this paper we address only the rst issue). We emphasized the importance of replication by allowing the use of only 1-control line multiplexers in the evolutionary process. In our approach we allow only 1s and 0s to be fed into the multiplexers. Thus, we allow the variables to be used only as control signals of the muxes. In fact, this makes a clear difference with respect to well-known tabular strategies where a variable can be fed into a multiplexer (this restriction is also valid in OBDDs). The organization of this paper is the following: rst, we will describe the problem that we wish to solve in a more detailed form. Then, we will introduce a methodology based on genetic programming to synthesize logic functions using multiplexers. We will nish with a comparison of optimal solutions found by other approaches (OBDDs) with the solutions derived by our GP system.

2 Problem Statement
The problem of interest to us is the design of a logic circuit that performs a desired Boolean function using the least possible number of 1-control line multiplexers. It is well known that logic functions of n variables can easily be implemented by 2n ? 1 1-control line multiplexers. Likewise, what is widely unknown is the degree of redundancy of the solution. We address this problem in the rst set of experiments. Further comparison is provided by contrasting our circuits against those created using OBDD techniques. In the last set of experiments we report an important circuit design problem: partially specied Boolean functions.

device as an universal logic unit is known as residues of a function. Denition 1. The residue of a Boolean function f (x1; x2 ; : : : ; xn ) with respect to a variable xj is the value of the function for a specic value of xj . It is denoted by fxj , for xj = 1 and by fxj for xj = 0. Any Boolean function can then be expressed in terms of these residues in the form of an expansion known as Shannons decomposition [17]:

f = xj f jx + xj f jx (1) The logic function y that represents the mapping of two

j j

3 Previous Work
It is possible to nd in the literature several reports concerning the design of combinational logic circuits using GAs. Louis [14] was one of the rst researchers who reported this class of work. Further work has been reported by Koza 1 [10], Coello et al. [4, 5], Iba et al. [9], and Miller et al. [15]. However, none of these approaches has concentrated on the exclusive use of multiplexers to design combinational circuits using evolutionary techniques. Several strategies for the design of combinational circuits using multiplexers have been reported after the concept of universal logic modules [21]. Chart techniques [13], graphical methods for up to 6 variables [19], and other algorithms more suitable for programming have been proposed [16, 8, 2, 18]. The aim of these approaches (muxes in cascade or tree, or a combination of both), is either to minimize the number of multiplexers, or to nd p control variables such that a Boolean function is realizable by a multiplexer with p?control signals. A popular approach named Ordered Binary Decision Diagrams (OBDDs) makes use of node transformations to reduce the size of the initial tree. Akers [1] also shows a suitable transformation of trees into logic functions implemented by means of multiplexers. Thus, multiplexers are only the implementation device (never seen during the design) while binary decision diagrams encode a Boolean function. Yanagiya [20] is credited as being the rst to use OBDDs to learn the 20-multiplexer. After him, several researchers have included the OBDD minimization rules in the form of crossover and mutation operations into a GP based system (e.g., Droste [7]). These systems perform circuit design through tree simplication and reduction.

inputs A and B onto the output port of a multiplexer with one selector line s is: y = sA + sB . This output function quickly takes the Shannons expansion form if the same function is used in both input ports. Say f = A = B is any logic function, then y = sf + sf . If we pick xj as the selector and the inputs are the residues fxj and fxj , the output becomes y = xj fxj + xj fxj . Further expansion of the residues into selector-residue pairs leads to an expansion as shown in Figure 1. As can be observed, every n-control signals multiplexer can be synthesized by 2n ? 1 1-control signal multiplexers. Notice that the number of layers or depth of the array is equal to n. Multiplexers can be active low or active high devices, a quality that we simply name class A and class B. For a class A multiplexer, when the control is set to one the input labeled as 1 is copied to the output, and vice-versa, the input labeled as 0 is copied to the output when the control is zero. For a class B multiplexer the logic is exactly the opposite: copy the input labeled 0 when the control line is one, and copy the input labeled 1 when the control is zero. In order to differentiate this property, class A muxes have the control signal on the right hand side and class B on the left, as can be seen in Figure 1. Therefore, the control signal is located on the side of the input to be propagated when the control is in active state. The active state will be 1 for all the examples presented in this paper. It is possible to use both classes of multiplexers simultaneously in a circuit, or during the circuit synthesis process. Two characteristic properties of circuits of this nature should be taken into consideration during the design process: Class Transformation Property: Class A and class B multiplexers can be converted freely from one class into the other, by just switching their inputs, thus input labeled 1 goes to input 0 and input labeled 0 now goes into 1 (see Figure 1). Complement Function Property: For every logic function F , its complement F 0 is derivable from the very same circuit that implements F by just negating the inputs, that is, by changing 0s to 1s and 1s to 0s. Circuits can also be sinthesized using only one class of multiplexers.

4 Multiplexers as Function Generators

A binary multiplexer with n selection lines is a combinational circuit that selects data from 2n input lines and directs it to a single output line. The concept that supports the use of this
1 Kozas approach to the design of combinational circuits has only concentrated on the generation of fully functional circuits and not in their optimization.

f(000) f(100) f(010) f(110) f(001) f(101) f(011) f(111)

0 1 0 1 0 1 0 1 0 1 0 1 0 1 f(X2X1X0) 0

Ao

Bo

Ao

Bo

X Y

X Y

X Y

CLASS "A"

CLASS "B"

CLASS "A"

CLASS "B"

X2

X1

X0

Implementation

Muxes class A and class B

Functional equivalence between Muxes class A and class B

Figure 1: Implementation of a multiplexer of 3-control signals by means of 7 1-control signal muxes. Muxes class A and class B. Functional equivalence between both classes

5 The Genetic Programming Environment

In the following we describe genetic programming issues that should help to fully understand the approach. We also discussed briey the representation and the evolutionary operators adopted (i.e., selection, crossover, and mutation). Representation: Binary trees encoding the population are represented by means of lists. Essentially each element of the list is the triplet (mux; left child; right child) that encodes subtrees as nested lists. The tree captures the essence of the circuit topology allowing only children to feed their parent node. In other words, a multiplexer takes only inputs from the previous level. This is shown in Figure 2. Both classes of binary multiplexers are implemented. Since multiplexers A0 and B 0 are controlled by C 0, the former is depicted with the control signal on its right side, and the latter with the signal on its left side. Selection operator: The mating pool is created by ternary selection, thus, three individuals are randomly chosen from the entire population and the one with highest tness is placed into the pool. The overall effect is the increment of the selection pressure that should decrease the convergence time. Crossover operator: The exchange of genetic information between two trees is accomplished by exchanging subtrees. Our implementation does not impose any kind of restriction on the selection of subtrees or crossover points. Node-node, node-leaf, and leaf-leaf exchanges are allowed. The particular case when the root node is selected to be exchanged with a leaf is disallowed, so that no leaf may be mistakenly converted into a node. This avoids the generation of invalid trees (in such cases the valid children are replicated twice). Mutation operator: Mutation is implemented in a simple way: rst a mutation point is randomly cho-

sen among the nodes and leaves. When a node (multiplexer) is selected, its control input is changed as follows (assuming n control signals): a0 ! a1 , a1 ! a2 , an?1 ! an , an ! a0 . Similarly simple is the mutation of a leaf: 0 ! 1, 1 ! 0. Fitness function: Our goal is to produce a fully functional design (i.e., one that produces the expected behavior stated by its truth table) which minimizes the number of multiplexers used. Therefore, we decided to use a two-stages tness function. At the beginning of the search, only compliance with the truth table is taken into account, and the evolutionary approach is basically exploring the search space. Once the rst functional solution appears, we switch to a second tness function in which fully functional circuits that use less multiplexers are rewarded. The tness function is switched regardless of individuals that are not fully functional. The tness function is the only agent responsible for the life span of the individuals. Initial population: The depth of the trees randomly created for the initial population is set to a maximum value equal to the number n of variables of the logic function. This is a fair limit because for complete binary trees with n variables, 2n ? 1 is the upper bound on the number of nodes required. However, we found in our experiments that in the initial population trees of shorter depth were created in larger numbers than trees of greater depth. This led us to allow the trees to grow without any particular boundaries as to allow a rich phenotypic variation in the population.

6 Further Renement of the Solutions

Our two-stage tness function does not take into account the redundancy of the terminal nodes. It simply rewards shorter trees with higher credit. Nonetheless, terminal nodes are usually replicated in vast numbers. Indirectly, this property

( A2, ( B1, ( A0, 0, 1 ), 0 ), ( B0, ( B1, 0, 1 ), ( B1, 1, 0 ) ) ) C2 C1 C0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 F 0 0 0 1 0 1 1 0

0 0 F

C2

C1

1 0

C0

1 1

C0

C1

0 0

1 1

C1

0 1

1 0

Figure 2: Truth table for logic function specication, circuit generated, and its coding
RULE 2 Z RULE 1 Z Z Am Am An An Z Z Z

An

Bn

An

An

An

Figure 3: Further renement. Node equivalence and subtree equivalence introduces further minimization because duplicated terminal nodes are pruned away from the solution. Terminal nodes are deleted according to the rules shown in Figure 3. Similar rules derived from the problem domain are given in [1]. Rule 1 is applied for transforming one multiplexer class into the other, aiming to maximize redundant nodes that can be deleted and the entire set replaced by just one of them. Subtrees as shown in rule 2 have been observed occasionally.

F 1(a; b; c) = (1; 2; 4) P F 2(a; b; c; d) = (0; 4; 5; 6; 7; 8; 9; 10; 13; 15) P F 3(a; b; c; d; e) = (0; 1; 3; 6; 7; 8; 10; 13; 15; 18; 20; 21; 25; 26; 28; 30; 31) P F 4(a; b; c; d; e; f ) = (0; 1; 3; 6; 7; 8; 10; 13; 15 18; 20; 21; 25; 27; 28; 30; 31; 32; 33; 35; 38; 39; 42; 42; 45; 47; 50; 52; 53; 57; 59; 60; 62; 63)
Table 1 summarizes the results of these experiments. In the rst column, we have the function implemented (itemized above); next to it, we have the number of variables of that function, and after that, we have the number of muxes required by the standard implementation (SI), and then the number of muxes required by our GP system. The last column shows the savings in the number of muxes, thus the difference between SI and GP. 7.2 GP vs. OBDDs In the second set of experiments we contrast the evolved solutions against solutions delivered by OBDDs. It is widely known that OBDDs are very sensitive to node ordering. As a consequence, circuit design in this case is mostly reduced to the computation of the variable ordering that minimizes the size of the circuit. Since our interest is the reduction of the

7 Experiments
The design metric in the following experiments is the number of elements. We contrast solutions against the standard implementation, ordered binary decision diagrams, and the design of partially specied Boolean functions. 7.1 GP vs. Standard Implementation Using standard implementations (SI), Boolean functions with n variables can be implemented using 2n ? 1 binary multiplexers. A considerable reduction in the number of elements is achieved by our system. We ran these experiments with a population size of 600 individuals. Maximum number of iterations is 100 for F 1, 200 for F 2 & F 3, and 700 for F 4. These functions can be found elsewhere. Functions implemented

F 1 2 3 4

Vars 3 4 5 6

SI 7 15 31 63

GP 5 7 15 21

Saved 2 8 16 42

Table 1: Comparison of the results produced by our genetic programming system (GP) against standard implementations (SI). number of nodes, some circuits are found to have less elements than in their optimal OBDD version. Functions implemented Input 0000 0001 0010 0100 1000 0111 1011 1101 1110 1111 F 0 1 1 1 1 1 1 1 1 0

Function F5. The OBDD of any function similar to F 5 with n variables has n nodes. The optimal order of the variables is 1; 2; 3; 4; 5; 6; : : : ; n. [3]. We have found optimal solutions to functions of this sort with 4, 6, 8 and 10 variables. In Figure 4 the OBDD tree is depicted along with its evolved solution. The subtree b5 is repeated on both branches. Furthermore, b5 can be minimized even more. Careful count indicates that the evolved tree shown is optimal. The genetic programming system found the optimal solution at generation 300, using a population size of 990 individuals, a probability of crossover of 0.35, and probability of mutation per individual of 0.65 (the probability of mutation per gene is therefore 0.65/L, where L is the total number of terminals plus non-terminals in the tree). Function F6. The next design is the synthesis of a similar function with 6 variables. The optimal solution found by OBDDs to this problem has 14 non-terminal nodes with variable ordering 1; 2; 3; 4; 5; 6. Thus, no other variable ordering will nd a better solution using OBDD techniques [3]. In Figure 5 we show the evolved optimal solution delivered by the genetic programming system. It is implemented with only 10 nodes. The genetic programming system found the optimal solution at generation 219, using the same parameters indicated before. Function F7. The odd parity function is a very hard problem to solve using multiplexers and genetic programming. In fact we have only found optimal solutions for up to 4 variables. Its hardness is due in part to the fact that there exists an ideal solution using xor gates. Therefore, any other approach will have more elements that the number of xor gates. Using OBDDs, the solution for n variables has at most 2n ? 1 non-terminal nodes. In Figure 6, we show the OBDD solution, and the evolved optimal solution delivered by the genetic programming system which has 7 nodes that can be reduced to 5. The genetic programming system found the optimal solution at generation 26, using a population size of 510 individ-

F 5(a; b; c; d; e; f ) = ab + cd + ef F 6(a; b; c; d; e; f ) = ad + be + ef F 7(a; b; c) = a b c odd-parity

Table 2: Partial function of 4 variables k 2 3 4 vars 4 8 16 size 7 15 31 aver 60 200 700

Table 3: Convergence to the optimum uals. The rest of the parameters were the same as before. 7.3 Partially specied functions We want to address the ability of the system to synthesize circuits of optimal size for Boolean functions with a large number of variables. The following property allows us to verify our GP system. Boolean functions with 2k variables (where k = 1; 2; : : : ), are implemented with exactly (2 2k )?1 binary muxes. For example, for k = 2, a Boolean function of 22 = 4 variables is implemented with exactly 7 muxes when the truth table is specied as shown in Table 2. A similar technique has been used by Droste to specify the 11-multiplexer [7]. For greater k (i.e., the number of variables), we specify the table in a similar way. There are exactly 2 2k + 2 entries in the table. Table 3 shows the high rate of convergence of the GP system to the optimum. We ran 100 experiments for each function (each k ). The column called vars shows the number of variables for some integer k , size refers to the optimum number of binary muxes needed to implement the partial Boolean function, and aver indicates the average number of iterations needed to nd the optimum. In all cases, we found optimum size circuits in more than 90% of the iterations.

1 2 3 4 b4 5 6 0 0 1 0 a1 1 1 a0 0 0 a0 b5 1 a3 1

b2 b5 b4 0 a0 0 a1 1 0 a1 1 0 a1 1 a0

OBDD

EVOLUTIONARY DESIGN
Figure 4: Synthesis of problem design 1

b2 b5 1 a4 0 a3 0 a0 0 1 0 a0 0 1 1 a3 1 b1 1 b1 0 a4 0 b1 0 a4 a0 1 a3

Figure 5: Synthesis of problem design 2

0 2 0 3 0 1 1

1 2 1 3 1 0 0 1 a1 0 1 b0 b1 0

a2 a0 a1 1 0 1 b1 0

EVOLUTIONARY DESIGN
n 0 0 1 1 1 n 0

OBDD
Figure 6: Synthesis of problem design 3

8 Final remarks
We have shown a genetic programming approach for the synthesis of logic functions and minimization of their number of elements. The system generates smaller circuits than the standard implementation approach. Solutions produced by our GP system are also quite similar in size to the solutions generated by OBDDs. More experimentation is needed in this respect. The ability to generate large partial functions has been veried to be optimal (in most cases) for functions with up to 16 variables. Some specic problems, as the oddparity turned to be very hard to solve. We are aware of the fact that in several cases, optimal solutions are not achievable through the exclusive use of multiplexers, but through the use of xor gates.

[7] Stefan Droste. Efcient genetic programming for nding good generalizing boolean functios. In John R. Koza, K. Deb, M. Dorigo, and D. Fogel, editors, Proceedings of the Second Anual Conference on Genetic Programming, pages 8287, San Francisco, California, July 1997. Morgan Kaufmann. [8] R.K. Gorai and A. Pal. Automated synthesis of combinational circuits by cascade networks of multiplexers. IEE Procedings Pt E, 137(2):164170, March 1990. [9] Hitoshi Iba, Masaya Iwata, and Tetsuya Higuchi. Gate-Level Evolvable Hardware: Empirical Study and Application. In Dipankar Dasgupta and Zbigniew Michalewicz, editors, Evolutionary Algorithms in Engineering Applications, pages 260275. Springer-Verlag, Berlin, 1997. [10] John R. Koza. Genetic Programming. On the Programming of Computers by Means of Natural Selection. The MIT Press, 1992. [11] John R. Koza, David Andre, III Forrest H. Bennett, and Martin A. Keane. Use of automatically dened functions and architecture-altering operations in automated circuit synthesis with genetic programming. In John R. Koza, David E. Goldberg, David B. Fogel, and Rick L. Riolo, editors, Proceedings of the First Annual Conference on Genetic Programming, pages 132140, Cambridge, Masachussetts, jul 1996. Stanford University, The MIT Press. [12] John R. Koza, III Forrest H. Bennett, David Andre, and Martin A. Keane. Automated WYWIWYG design of both the topology and component values of electrical circuits using genetic programming. In John R. Koza, David E. Goldberg, David B. Fogel, and Rick L. Riolo, editors, Proceedings of the First Annual Conference on Genetic Programming, pages 123131, Cambridge, Masachussetts, jul 1996. Stanford University, The MIT Press. [13] Glen G. Langdon. A decomposition chart technique to aid in realizations with multiplexers. IEEE Transactions on Computers, C-27(2):157159, February 1978. [14] Sushil J. Louis. Genetic Algorithms as a Computational Tool for Design. PhD thesis, Department of Computer Science, Indiana University, aug 1993. [15] J. F. Miller, P. Thomson, and T. Fogarty. Designing Electronic Circuits Using Evolutionary Algorithms. Arithmetic Circuits: A Case Study. In D. Quagliarella, J. P riaux, C. Poloni, and G. Winter, editors, Genetic e Algorithms and Evolution Strategy in Engineering and Computer Science, pages 105131. Morgan Kaufmann, Chichester, England, 1998.

9 Acknowledgments
This paper describes research done in the Department of Electrical Engineering and Computer Science at Tulane University. Support for this work was provided in part by DoD EPSCoR and the Board of Regents of the State of Louisiana under grant F49620-98-1-0351. The third author acknowledges partial support from REDII-CONACyT, and from CONACyT project number I-29870 A.

Bibliography
[1] S. B. Akers. Binary decision diagrams. IEEE Transactions on Computers, C-27(6):509516, June 1978. [2] A. E.A. Almaini, J.F. Miller, and L. Xu. Automated synthesis of digital multiplexer networks. IEE Proceedings Pt E, 139(4):329334, July 1992. [3] R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transaction on Computers, C35(8):677691, August 1986. [4] Carlos A. Coello, Alan D. Christiansen, and Arturo Hern ndez Aguirre. Automated Design of Coma binational Logic Circuits using Genetic Algorithms. In D. G. Smith, N. C. Steele, and R. F. Albrecht, editors, Proceedings of the International Conference on Articial Neural Nets and Genetic Algorithms, pages 335 338. Springer-Verlag, University of East Anglia, England, April 1997. [5] Carlos A. Coello, Alan D. Christiansen, and Arturo Hern ndez Aguirre. Use of Evolutionary Techa niques to Automate the Design of Combinational Circuits. International Journal of Smart Engineering System Design, 2(4), 2000. [6] M. Davio, J. P. Deschamps, and A. Thayse. Digital systems, with algorithm implementation. Wiley, New York, USA, 1983.

[16] Ajit Pal. An algorithmic optimal logic design using multiplexers. IEEE Transactions on Computers, C35(8):755757, August 1986. [17] C. E. Shannon. The synthesis of two-terminal switching circuits. Bell System Technical Journal, 28(1), 1949. [18] Sajjan G. Shiva. Introduction to Logic Design. Scott, Foresman and Company, 1988. [19] A.J. Tosser and D. Aoulad-Syad. Cascade networks of logic functions built in multiplexer units. IEE Proceedings Pt E, 127(2):6468, March 1980. [20] Masayuki Yanagiya. Efcient genetic programming based on binary decision disgrams. In Toshio Fukuda and Takeshi Furuhashi, editors, Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, pages 234239, Nagoya, Japan, 1995. IEEE, IEEE. [21] Stephen S. Yau and Calvin K. Tang. Universal logic modules and their application. IEEE Transactions on Computers, C-19(2):141149, February 1970.