Digital Circuit Structure Design via Evolutionary Algorithm Method

INTRODUCTION

Digital system plays a major role in the recent electronic technology due to many advantages. The main component to form a digital system is the combination of various types of logic gates. Many general applications such as binary adder and subtractor have been fabricated into a single Integrated Circuit (IC). The level of integration becomes complicated when the number of bit per IC getting increases. Subsequently, the number of gates used per single substrate will be increased as well as the power consumption.

Mano (2002) commented that the conventional digital circuit design is a very complex task which required much knowledge in domain-specific rules. The design procedures involve the process such as choosing the suitable gate types to match the logical specification, minimizing and optimizing the boolean representation with respect to the user defined constraints.

Besides conventional method, Evolutionary Algorithm (EA), have been widely applied to complex optimization problems as reported by Zebulum et al. (2002). One of the applications can be presented the nation of structure design for the digital circuit. The EA was used to conceive arrangements of digital gates that could solve a specific problem, such as the parity function. This ideal was highly original, since the evolutionary algorithm performed thorough automatic circuit design from scratch; no human knowledge was needed.

GA search technique is found by Holland (1992) and extensively applied into optimization tasks by Goldberg (1989). GA is a stochastic search method that mimic the metaphor of natural biological evolution. Evolutionary algorithms operate on a population of potential solutions applying the principle of survival of the fittest to produce better and better approximations to a solution. At each generation, a new set of approximations is created by the process of selecting individuals according to their level of fitness in the problem domain and breeding them together using operators borrowed from natural genetics. This process leads to the evolution of populations of individuals that are better suited to their environment than the individuals that they were created from, just as in the natural adaptation.

The application of GA in combination logic design is firstly proposed by Louis (1993). In his research, he combines GA with knowledge-based systems and uses masked crossover operator to solve the combination logic circuit. His method can solve the functional output for the combination logic but not emphasize on the optimization of the gate usage.

Sadiq et al. (2002) were implemented Fuzzified Simulation Evolution (SimE) Algorithm for combination digital logic design. They proposed two fitness operator for functional fitness and objective fitness. The functional fitness called Multilevel Logic Based Goodness Measure which is based on the assumption that the higher the level of a gate in a multilevel logic circuit, the more minterms are covered at the output of that gate. Therefore, the goodness of a gate is affected by the number of minterms covered at its output and the level where the gate is located. The objective fitness targeting the optimization in term of area, delay and power consumption.

Nilagupta and Ou-Thong (2003) proposed an approach to enhance the designing process by minimizing the number of transistors used in designing a combinational logic circuit by using GA. The chromosome representation is based on Louis method which is a bi-dimensional matrix. Each cell in the matrix is logic gates; includes NULL, NOT, NAND, NOR and XOR. The fitness function works in two stages. The validity of the circuit outputs or the functional output is taken into account in the initial stage. GA uses to optimize the number of transistor count after the functional solution appeared. This research is mainly focused on the optimization of transistor used in the digital circuit but not the number of gate.

In this study, we proposed a method to design the structure of the combination logic circuit using EA. This approach is able to optimize the usage of logic gate compare to the conventional method. The main objective of this research is to design a digital circuit which can produce the desired output function with the most minimum usage of logic gates. The types of gate used can be a combination of Wire, NOT, XOR, XNOR, NAND, NOR, AND and OR. The structure of the digital circuit is encoded into one-dimensional genotype as represented by a finite string of bits. The design process then be done by the Genetic Algorithm (GA) operator such as crossover, mutation and selection. The best solution found is decoded back to the digital circuit structure.

APPROACH AND METHODS

In this study a selected optimization method is based on a genetic algorithm. Genetic Algorithms (GA) are adaptive heuristic search algorithm premised on the evolutionary ideal of natural selection and genetic. The basic concept of GA is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Darwin of survival of the fittest.

The GA works by creating many random solutions to the problem at hand. This solutions will be subjected to an imitation of the evolution of species. All these solution are coded as genetic chromosomes and it will be made to mate by hybridization, also throwing in the occasional spontaneous mutation. The offspring generated will include some solutions that are better than the original.

The proposed approach represented the solution inside the block in Fig. 1, i represents the number of the original input signals and o are the desired outputs signals. The detail solutions inside the block are encoded into a string of chromosomes and subjected to the process of evolutionary algorithms.

The architecture of the proposed system is shown in Fig. 2. We use an encoding system to represent the structure of combination logic circuit. The two-dimension phenotype is encoded into one-dimension genotype as represented by a finite string of bits. A group of bits string used to represent 10 types of possible logic gates, Wire 1, Wire 2, XOR, XNOR, NAND, NOR, AND and OR, which listed in Table 1. Every logic gate has two inputs and one output.

The structures of gates are arranged in G_x,y matrix form which x is represented the gate in row and y is represented the gate in the column. The m inputs is connected to y column of the logic gates. The possible input combination is based on 2^m. The output constraint signal is obtained at y+n column of the logic gates; n is the number of column.

(1)

Table 1:	Logic gates representation

Fig. 1:	Block representation of combination digital circuit structure

Fig. 2:	Block diagram of the proposed system

We define that G_x,y+1 gate always obtain one signal from the output of G_x,y, gate and another signal from G_x+1,y gate, while G_x+m,y+1 obtain the signals from the output of G_x+m,y and G_x,y. The system process is started with the random generation of initial population. The length of the chromosomes is depend on the size of the entire structure. The number of bit in the chromosomes represents type of gate. The collection of all individuals of the cell represents a solution.

The algorithm for the proposed system is as follows:

The design has fitness of 1 if it output value satisfies the constraint specification. Otherwise the structure design is deviated from the performance specification. The structure design modification is done by crossover and mutation operator. Crossover is the technique of exploring new regions of the search space to produce design other than the random population which generated in the initial stage. Crossover is a randomized approach to exchange information between two chromosomes. The new population is produced by crossover. The process of crossover can creates new structures from the existing structures. Crossover operation creates a variation in the population by producing offerings that combine characteristics from the two parents but are different from either of the parents. After the crossover operation, when the new chromosome achieved fitness percentage of 30%, the particular individual from the present generation moves to the mutation process.

Mutation is an approach to prevent the solutions in the population falling into a local optimum of the solved problem. Mutation operation randomly changes the offspring resulted from crossover.

The fitness of the process is the correctness of the obtained logic circuit in matching the truth table of the required function. In this study, we proposed a fitness functional called constraint fitness. The constraint fitness is based on the comparison of circuit output with the constraint output. The formula for Constraint Fitness (CF) is:

(2)

(3)

F_C is achieved 1 when x is equal to 1. c_o is constraint output set by the user and f_o is functional output generated from the circuit. When the functional output is exactly equal to the constraint output, this will cause the magnitude of the summation |c_o – f_o| equal to 0. Consequently, F_C will equal to 1 due to x is 1. It is possible to get more that one constraint fitness in a random generated population. In order to determine the global optimum of the design, we accumulated all the population with the constraint fitness equal to 1 for further evaluation.

In this research, we are targeting the optimization of number of gates used in the structure design. After obtained the constraint fitness, the second objective is to get the fitness of gate optimization used in the circuit design. The population for this Gate Optimization Fitness (GOF) evaluation is base on the chromosome with the constraint fitness of 1. Each string of chromosome is evaluated for the gate optimization fitness. The algorithm for this fitness is:

(4)

(5)

The numerator of [5] is the summation of the gates which can produces the constraint fitness equal to 1. The denominator part is the summation of the gate per structure. The fitness of GOF should in between 0 and 1. The global optimal is achieved when met the smaller fitness of GOF.

IMPLEMENTATION AND RESULTS

The proposed system was written in MATLAB language. Experiments have been conducted using the system to investigate its effectiveness in constraint-directed logic synthesis. The results produced by the proposed approach were compared with those generated by K-Map method.

For all the experiments, population size N = 1000, percentage of crossover reproduction C = 60, percentage of mutation reproduction M = 40. Combination logic gates boolean function of the designs are illustrated in the different table. These results show that the proposed system is able to produce quite effective solution of constraint-directed logic synthesis.

Example 1: The minterm for the output of the first example is as following:

F(a,b,c,d) = Σ(2,3,5,6,8,9,12,15)

Table 2 shows the first example result. Convergence to the optimum was achieved in generation 69. If this circuit developed by human, the proposed approach produces less number of gate counts by 80% compare with the other method as shows in Table 2.

Figure 3 shows the digital circuit schematic for Example 1 which was designed by the proposed method. The design just needs 1 AND and 2 XOR gates to generate the required output. Meanwhile, the solution for Example 1 that designed by convention K-Map method is illustrated in Fig. 4. The circuit needs 4 NOT gates, 6 AND gates and 5 OR gates to produce the necessary output. Obviously, the circuit designed by the proposed method needs lesser gate if compared to the conventional method.

Table 2:	Comparison result between the proposed method and human design method of Example 1

Table 3:	Comparison result between the proposed method and human design method of Example 2

Fig. 3:	Circuit of Example 1 which was designed by the proposed method

Fig. 4:	Circuit of Example 1 which was designed by K-Map

Example 2: The minterm of the second example is as following:

F(a,b,c,d) = Σ(7,10,11,13,14,15)

Table 3 shows the second example results. Convergence to the optimum was achieved in generation 175. The proposed approach produces less number of gate counts by 28.57% compare with the other method.

For example 2, the digital circuit schematics of both designs are shown in Fig. 5 and 6, respectively. The design done by proposed method just needs 3 AND and 2 OR gates to generate the required output. While, the design done by convention K-Map method needs 5 AND gates and 2 OR gates to produce the necessary output. Clearly, the circuit design implemented by the proposed method requires smaller number of gate if compared to the conventional design.

Table 4 shows the result of 5 Constraint Fitnesses (CF) for Example 1. Each CF achieved value of 1 in different population. CF 1 reached fitness at population of 60, CF 2 at population of 39, CF 3 at population of 31, CF 4 at population of 69 and CF 5 at population of 44.

Table 4:	The constraint fitnesses for CF 1 to CF 5

Fig. 5:	Circuit of Example 2 which was designed by proposed method

Fig. 6:	Circuit of Example 2 which was designed by K-Map

Table 5:	Gate optimization fitness for Example 1 and Example 2

The Gate Optimization Fitness (GOF) for Example 1 and Example 2 is shown in Table 5. The lowest GOF for Example 1 is 0.6 whereas 0.3 for Example 2.