Tree Representation of Logic Circuits

• posted

Hello Everyone I am now trying to simulate gate level evolution in software. I was unsure about the formation of my chromosome string. I would be using an evolutionary approach to design a circuit. I have read documents on Multi Expression Programming(MEP) and Gene Expression Programming(GEP). The examples are quite good but still i feel its a challenege getting a valid equation from a random generated string like - "(a&b))|c!d(b)" I am currently generating a random string for the initial population of the chromosomes. but major problem is how can i make it valid. Someone suggested that i should use the concept of lexical analysis used with compiler design. I am really confused regarding what approach to adopt. It would be great if someone could guide me. I have read the MEP gate evolution example from C#corner I feel its very complicated. Ankit Parikh Manukau Institute of Technoogy

• posted

Ankit,

to be honest, i have not the slightest idea about MEP or GEP or the like. But at my university days i wrote a Pascal program that would take a input string like the one that you present and reduce it to a simpler form. The aim of the program was to find out whether a expression was a "Tautologie" (Always true, independand of the values of the input variables) or not. The program did this not by trying out all input variables settings but instead by symbolical manipulation according to rules like "a|!a may be reduced to TRUE" or "a&!a may be reduced to FALSE".

I guess from that experience i have a certain understanding of what you are gaining for. And i guess the people who told you about parsing, lexical analysis and compiler design were quite right! If you have a totally random expression you will most probably need to perform lexical analysis to find out whether it is a valid expression.

However, if i understand your question right it is not your true aim to make a random expression a valid expression. Instead it seems what you need is a valid random logic expression. I suggest, then that this is what you should do: Not use a random generator to generate character sequences but use a random generator to generate complicated logic expressions from simple logic expressions. This will need some programming stuff too but could be easier than analyzing a existing string.

Best regards Ulrich Bangert