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
    CommentedFeb 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
    CommentedFeb 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
    CommentedFeb 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
    CommentedFeb 17, 2022 at 9:46
  • $\begingroup$Ok, that's fine. My suggestion above still applies.$\endgroup$
    – nbro
    CommentedFeb 17, 2022 at 9:49

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.