# Evolving Multi-Output Digital Circuits Using Multi-Genome Grammatical Evolution
## 3 Proposed Approach: Multi-Genome GE
### Cyclic Dependency Checking Algorithm
The upper section of the grammar contains the rules that need to be expanded. The lower section contains rules that define the fixed part of the circuit problem, such as the circuit interface. An expanded form of the grammar for the 5-bit + 5-bit Adder with Output and No-Output sharing are shown in Listings A1 and A2 respectively in the Appendix A. ``` <stmts>::= {<tr1-sum-i><tr1-cout-i>}=5 {<tr1-sum-i+1><tr1-cout-i+1>}... {<tr1-sum-i=n><tr1-cout-i=n>} <tr1-sum-i>=[1,n] ::= sum[i] \"=\" <expr-i>; <nextline> <tr1-cout-i>=[1,n] ::= in_cout[i] \"=\" <expr-i>; <nextline> <expr-i>=[1,n] ::= a[i] | b[i] | c_in (<expr-i><bitwise-op><expr-i>) | <expr-i> <bitwise-op> <expr-i> <expr-i> || <tv1-input> <bitwise-op> ::=\"s\" | \"|\" \"=\" | \"=\" \"=\" <tv1-input> ::= {sum[i=1] | in_cout[i=1]} | {sum[i=i+1] | in_cout[i=i+1]} |... | {sum[i=n] | in_cout[i=n]}=5 <output-stm> ::= codeword \" = {dataword,parity_bit};\"<nextline> <nextline> ::= \"\
\"  
Figure 6: Mean average best across 30 independent runs for Hamming Code (7,4) using MG-GE and standard GE. Figure 7: Mean average best across 30 independent runs for Hamming Code (15,11) using MG-GE and standard GE. Figure 8: Mean average best across 30 independent runs for 5-bit + 5-bit Adder using MG-GE and standard GE. Figure 9: Mean average best across 30 independent runs for 10-bit + 10-bit Adder using MG-GE and standard GE. The benefits of the new genome representation can be observed from Figures 6-9. The experimental setups using MG-GE outperform GE when the same grammar variants are used except for the 5-bit + 5-bit adder in Figure 8, where both MG-GE and GE using Grammar with No-Output Variable Sharing converge to similar final mean best fitness. However, MG-GE Grammar with No-Output Variable Sharing attains the final mean best fitness after a few generations. We also observe both MG-GE setups for the Hamming Code (\(7A\)) Encoder in Figure 6 attain their final mean best fitness after a few generations. This suggests evolution can perform quite well on relatively easier problems with no inter-output dependencies when the least appropriate grammar is used (Grammar with Output Variable Sharing). Furthermore, MG-GE outperforms GE on all problems using the most appropriate grammar variant. We observe the experimental setup for MG-GE using the Grammar with Output-Variable Sharing for the 5-bit + 5-bit and 10-bit + 10-bit adders recorded a success rate of 16/30 and 21/30, respectively, while all other setups recorded zero successful runs. This is because the ripple-carry adder, which operates like elementary addition, propagates the carry bits from the previous bit addition stages to the last stage of bit addition. Hence, designing the grammar to allow output variable sharing while ensuring no cyclic dependency between output variables is formed ensures correct carry outputs are available for the summation stages to use. As a result, the Grammars without Output Variable Sharing will require evolution to evolve the carry-out bit from the previous summation stage for the current summation stage, rendering the problem more challenging to deal with. On the Hamming Code (\(7A\)) and Hamming Code (\(15\),\(11\)) Encoder problems, MG-GE with the Grammar with No-Output Variable Sharing obtained a success rate of 30/30 and 27/30, respectively. Using the Grammar with Output Variable Sharing, MG-GE obtained zero successful runs. This is due to the fact that for the hamming code encoders, there exist no dependencies between the output variables. Therefore, using the grammar with Output Variable Sharing for a problem with non-existing inter-output dependencies impedes evolutionary performance.