Department of Electronics and Telecommunications – “Dunarea de Jos” University in Galati, Romania
Received date: January 06, 2015; Accepted date: January 07, 2015; Published date: January 17, 2015
Citation: Rustem P (2015) Toward EHW 2.0 – Some Ideas in HDL-Based Evolution of Digital Circuits. Glob J Tech Opt 6:174. doi: 2229-8711.1000174
Copyright: © 2015 Rustem Popa. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Global Journal of Technology and Optimization
Evolvable Hardware (EHW) is a field of Evolutionary Computation (EC) started in the early 1990’s that includes a subfield of Evolvable Hardware Design and a subfield of Adaptive Hardware. Two methods of evolvable hardware design of a one-bit full adder are analyzed in this paper: first method is based on the well-known idea of gate-level design using a network of programmable gates, and the second method uses Verilog instructions coded in chromosomes represented as binary strings. Eventually, the two solutions were compared in terms of hardware resources and propagation times.
Evolvable hardware; Genetic algorithms; FPGA; Digital electronics; Verilog HDL
The conventional design process in electronics, either analog or digital, is top-down and begins with a precise specification. EHW design may be used when no hardware specification is known before. Its structure is adaptively searched using a Genetic Algorithm (GA) in a bottom-up way. EHW design combines knowledge of both GA and electronic design to evolve electronic circuits. It can offer new design solutions, which differ from the patterns typically used by humans.
In this paper we deal only with extrinsic evolution, which uses a model of the hardware and evaluates this model by simulation in software. Although  deals only with intrinsic evolution, which uses a real hardware programmable device, it is a very good up to date critical review of the field. It compares the current state of the field to that described in , a famous paper published by Yao and Higuchi 15 years ago.
Taking into account the progress of this research field in the 1990’s, the two authors discussed the promises and possible advantages of EHW, and pointed on the challenges meet in order to develop real large-scale EHW. Unfortunately,  considers that the field is in a critical stage today. In its early stages, the field was developed with small steps forward. But the hope of bigger steps in the near future has not been confirmed by the passage of time. One of the main challenges remains scalability, which is representation of evolved complex circuits in terms of chromosomes [1,3,4]. Other challenge is measurement, that is fitness evaluation, or the metric used to evaluate the viability of an evolved circuit, and, on the other hand, the ability to compare traditional and evolved designs [1,5].
One of the first ideas for the use of Hardware Description Languages (HDLs) in the field of EHW was introduced in . In order to improve the scalability, and taking into account that only structural HDL is synthesizable, while behavioral HDL is not, it was proposed, as a promising research direction, evolutionary-based compilation of behavioral HDL to structural HDL. A method of EHW design using Grammatical Evolution (GE) has been proposed in . GE allows evolution in any programmable language, including Verilog HDL. As we can see in , there are a lot of functional HDLs, but Verilog HDL is the Industry Standard HDL.
The remainder of the paper is structured as follows: next section describes the two implementations of a one-bit full adder, the following section discuss some experimental results by comparing the two solutions in terms of hardware resources and propagation times in a FPGA circuit, and the last section contains conclusions.
Genetic implementation using a network of logic gates
The main stages of evolutionary design in electronics, both analog and digital, are illustrated in Figure 1. First, a population of chromosomes is randomly generated. Then, these chromosomes are converted into circuit models and circuit responses are compared with design specifications. Those chromosomes that generate the best circuits receive the best evaluations or the best fitness. They are selected as parents for a new generation of chromosomes.
If evolutionary algorithm is a GA, then new chromosomes are generated using genetic operators such as crossover and mutation. Through crossover, chromosomes are chosen two at a time, as parents, and their off springs are generated by exchanging parts of their structure. So, each offspring inherits a combination of features from both parents. Mutation means a small change in a new generated chromosome, with a small probability. In this way the algorithm can explore new features that are not yet in the population, in order to avoid premature convergence, when the diversity in population is lost. It makes the entire search space reachable despite the finite population size. The whole process is repeated for several generations, until is generated the best chromosome which represents a valid solution for our design.
Our problem is to design a circuit that performs a desired binary function, specified by a truth table, using a certain specified set of available logic gates. Based on the ideas presented in  and , we have used a network of programmable logic gates for each binary function in the circuit.
The proposed digital circuit is a one-bit full adder, which is in fact a system of two binary functions, each of them with three Boolean variables. Each function is implemented in a network of four gates, using a standard GA. Each gate has maximum two inputs and may be one of the following 8 types of logic gates: AND, NAND, OR, NOR, NOT taking into account the first input, NOT taking into account the second input, XOR, and the complement of XOR. An example with only 4 types of gates is given in Figure 2.
The first interesting aspect of this problem is the encoding of solutions as strings of bits, each string being a chromosome that the GA can evolve. Figure 2 explains the main idea used for this purpose. Each chromosome contains the whole information about the connections between inputs and outputs of the gates. Each gate contain three fields: the two first fields refer to each of the inputs used, and the third is the type of the gate .
If we want to implement the output si of the full adder of rank i, which has the boolean equation:
then, as we can see in Figure 2, we need only two XOR gates, corresponding to the positions III and IV. The gates numbered with I and II are not used to implement this function, so, it doesn’t matter how they are connected, and this part of the chromosome may be considered as beeing in fact “junk DNA”. This evolved function is represented in Figure 3.
The other function of the adder, ci, was implemented on another similar network of four programmable gates, and Figure 3 presents the whole circuit.
The optimal equation of the carry output of the adder, ci, is:
because the XOR gate is shared by both functions of the adder. One of the potential evolved equations is represented in Figure 3:
Equation (3) gives the same function as that represented in equation (2), and it’s not optimal because the two function of the adder have evolved separately.
In order to represent the chromosomes that describe a binary function using circuit representation in Figure 2, we may choose the following codes to inputs and outputs of the gates: 1 – 000 or 110, 2 – 001 or 111, 3 – 010, 4 – 011, 5 – 100, and 6 – 101. Double codes could be used for constants 0 and 1. The gates may have the following codes: AND – 000, NAND – 001, OR – 010, NOR – 011, NOT1 – 100, NOT2 – 101, XOR – 110, and the complement of XOR – 111.
Thus, the length of a chromosome is 36 bits, and the best chromosomes that describe the functions si and ci are :
As we can see, the first half of the chromosome given in (4) does not encode anything because two of the gates are not connected in circuit. So, half of the genetic information in first chromosome is rather “junk DNA”.
Genetic implementation using Verilog HDL
Probably one of the first papers that proposes the use of HDL languages in EHW design is . Taking into account that only structural VHDL (Verilog) is synthesizable, while behavioral VHDL is not (because structural VHDL offers a problem decomposition), the following two research directions are proposed:
a) Evolutionary-based compilation of behavioral HDL to structural HDL. Force specifications to be in a standard behavioral language. b) Evolutionary-based synthesis of structural AHDL. AHDL is the acronym from Analog HDL. Structural AHDL may be the required first step to automatic analog synthesis.
Verilog HDL is an Industry Standard HDL and its syntax is simpler than that of VHDL. In this paper we deal with the synthesis of digital circuits, but the method may be also used for the synthesis of analog circuits. The building blocks may be sufficiently small to allow evolution toward optimal solution [6,12].
Verilog code for the one-bit full adder is given in Figure 4. It is a behavioral code, because Boolean functions are defined with instruction assign and there is no reference to the circuit structure, that is we don’t care how the logic gates are interconnected. The only instructions that change in the evolutionary process are the two instructions assign, one for each of the two binary functions.
First instruction assign describes function si, which is given in equation (1). If we represent this instruction in a binary coded chromosome, and we guess that our function follows a pattern like the one given in (6), where in1, in2, and in3 are any of the three inputs, and op1 and op2 are any of the valid logic operators, then the chromosome may be the one from (7).
We have generated this chromosome using the following rules: in1 – 00, in2 – 01, in3 – 10, and logic operators are the same used for the circuit representation in Figure 2 (XOR – 110). This representation uses only 12 bits instead of 36 bits and the search space is much smaller in this case.
Function ci has another pattern. Instruction assign in Figure 4 (for function Carry_out) has three product terms written in a disjunctive form. If in is any of the three inputs, and op is any of the valid operators, then the pattern could be:
and the chromosome will have only 27 bits. If we use distributive for the last 2 product terms, then will remain only 4 operations, and the length of the chromosome will be only 24 bits. We can further reduce the length of the chromosome to only 22 bits, if we consider only AND, OR and NOT operators. This last pattern may be used also for si function, due to the idempotency theorem.
It is obvious that when we evaluate a chromosome as a solution of the problem, we must take into account the precedence of the operations. All these potential solutions are evaluated using a fitness function. In our case, for a single Boolean function, fitness is the ratio between the number of the correct values of the function and the number of all possible values (which is 2n, if the Boolean function has n input variables). A well-designed circuit will be obtained only when the value of fitness is 100%. An approximately value of the fitness is unacceptable in our case.
Another structure of an evolved one-bit full adder using a network of gates is given in Figure 5. This time, useful part of the first chromosome is the same, but the second chromosome is completely different, as we can see in (10) and (11):
Both methods described above used a standard GA with the following parameters: population size was 128 chromosomes (a tournament type selection was used), 40 or 80 of them have been changed each generation, crossover probability 1 or 0.8, mutation probability 10%, and number of generations, 500 for the first method and only 100 for the second method.
GA was implemented in Matlab environment on an Intel Core 2 Duo CPU, 2,4 GHz, and, using the first method, the average time in 10 runs for si function was 5,487s, and for ci function was 14,269s.
Using the second method, based on Verilog HDL, the average time in 10 runs, for si function was only 0,506s, and for ci function was 0,694s.
We have tried also to implement this circuit in a real FPGA, in order to compare the resources used and the times of propagation. We have synthesized the circuit in a Spartan 3 FPGA from Xilinx, using the development integrated environment ISE 14.1. We found that there is no difference between the analyzed solutions. Both solutions implemented with gates, the conventional and the evolutionary, use 2 LUTs, each of them with 4 inputs, and 1 slice, time delay being between 5,479 and 5,882 seconds. Implementation with Verilog HDL, in structural and behavioral versions, use also 2 LUTs with 4 inputs and 1 slice, and global time propagation is between 5,481 and 5,853 seconds.
So, in conclusion, there is no advantage in FPGA implementation, because ISE environment optimizes the internal resources used to implement our functions, regardless of the form of representation. However, as we claimed from the beginning, EHW can provide surprising solutions in some cases, especially at a certain level of complexity, when a favorable pattern can provide a gain compared to conventional solutions. And the use of HDL languages seems to be a promising solution for the future.
The field of EHW has been developed for almost 20 years without having a uniform rate of growth. Current results are much more limited than previous expectations. We are confident that using of HDL languages can provide another significant development of this interesting area of research.
We fully agree with the authors of , who write that: “One thing is for certain, if we want to keep the field of evolvable hardware progressing for another 15 years we need to take a fresh look at the way we think about evolvable hardware: about which applications we should be applying it to; about where it will actually be of real use; about where it might finally be accepted as a valid way of creating systems and about what medium it should be based in.
We wish us all luck in this, the second generation of evolvable hardware.”