Automatic design of digital circuits using grammatical evolution and SystemVerilog

Digital circuit design is a very complex and time-consuming task which requires a great deal of skill. Evolutionary Algorithms have been applied to circuit design problems and have been demonstrated to be better and more creative at exploring the circuit design search space than humans.

In industry, digital circuit design is greatly aided by the use of Hard-ware Description Languages (HDLs) and powerful logic simulators. HDLs permit circuit designers to design circuits at a very abstract level. These are then tested and synthesised before being committed to hardware.

We present Automatic Design of Digital Circuits (ADDC), a system which uses Grammatical Evolution (GE) to design digital circuits using an HDL and a logic simulator. First, we investigate the applicability of ADDC to circuit design and how best to configure it, with a focus on grammar design and selection operators. Grammar design is a key aspect of GE since grammars define the boundaries, size and topology of the problem search space. We observed from the results that experimental setups with grammars designed with domain knowledge recorded a higher success rate compared to grammars designed with no domain knowledge.

Secondly, we investigate the capability of ADDC to evolve more complex circuits by exploiting the use of higher-level language constructs such as if-else, always block, switch-case, and generate for-loop in SystemVerilog (an HDL). With the incorporation of these higher-level constructs, to date, ADDC has evolved the most complex selective parity, adder, and multiplier circuits in the relevant literature.

Finally, there are many digital circuits characterised by multiple outputs. However, both single and multiple output problems are typically represented using a single genome. We propose a new multi-genome GE, together with associated genetic operators, to help mitigate the ripple effect GE suffers from. The ripple effect in GE is a phenomenon whereby a small change (such as a mutation event) in an individual’s genotype, usually in the beginning regions, results in a drastic change in its phenotype after the mapping process. This issue can be very problematic when solving multi-output problems using standard GE, as there is no mechanism to stop searching for an output once it has been solved and, instead, direct the search operators to regions of the genome coding for the unsolved outputs. Hence, due to the destructive effect of GE’s search operators, solving such problems is challenging. A genome per output representation for a multi-output problem ensures ripple effects are localised. Results demonstrate the multi-genome GE outperforms standard GE on multi-output circuit benchmark problems.