1
$\begingroup$

Consider the following digital logic circuit, which has multiple inputs and one output:

Digital logic circuit drawn using Logisim

The logic circuit above can be represented in tree form:

Tree drawn using Graphviz

This tree representation could then be used in a tree-based genetic programming framework to evolve the circuit. For example, this tree could be represented as a Lisp list (or (and A B) (not C)), which could then be used with the Little LISP genetic programming framework from John R. Koza's Genetic Programming textbook.

However, I now want to deal with digital logic circuits that have more than one output. For example, in the half-adder circuit below, there are two outputs $S$ and $C$, each of which is affected by both inputs $A$ and $B$.

Half adder

(Image source: SICP by Abelson et al. Section 3.3.4 A Simulator for Digital Circuits. CC BY-SA 4.0)

How do I represent and evolve such a circuit in tree-based genetic programming? How do I represent the circuit above as a tree that could then be used to evolve the circuit using a tree-based genetic programming framework?

Improve this question
$\endgroup$
5
  • $\begingroup$ Maybe you can do this with a custom function that gets $s$ and $c$ as input and that would produce the final return type, i.e. a binary vector. $\endgroup$
    – nbro
    Feb 16, 2022 at 18:56
  • $\begingroup$ @nbro Thank you for the suggestion, but how would such a tree look like exactly? With the binary vector return type, $S$ and $C$ can each be influenced by either $A$ or $B$ but not both. That is the consequence of a tree representation. Perhaps I am not fully understanding your suggestion because I don't see how it could represent things like half-adders (shown in the question) and flip-flops. $\endgroup$
    – Flux
    Feb 17, 2022 at 5:39
  • $\begingroup$ I didn't realise that you didn't want both A and B to affect both S or C, because you didn't explain this in the post. In any case, my suggestion was more about how you could possibly deal with 2 outputs. You can could create a function like id(s, a) = [s, a], and the output of the circuit/tree is of type list. Here, id is the custom function that you need to add to you function set, in addition to and, or and not. If I have some time, later, I will try to create a simple proof-of-concept that illustrates my idea. $\endgroup$
    – nbro
    Feb 17, 2022 at 9:41
  • $\begingroup$ @nbro Sorry for not making that clear. In the half-adder circuit shown in the question, The output at $S$ is affected by both inputs $A$ and $B$. Similarly for the output at $C$. $\endgroup$
    – Flux
    Feb 17, 2022 at 9:46
  • $\begingroup$ Ok, that's fine. My suggestion above still applies. $\endgroup$
    – nbro
    Feb 17, 2022 at 9:49

0

Reset to default

You must log in to answer this question.