How to simulate digital logic circuits with feedback loops?

Question

I learning how to simulate digital logic circuits . I am presenting the source code of my first attempt here. It is small program for simulating circuits consisting of AND,OR and NOT gates.

This code works well for circuits without loops. When circuit loops are introduced it causes a stack overflow because of endless recursion. Please help me to remove this bug.

Please note that this is a hobby project and any help will be appreciated.

Source code :

#include <cstdlib>
#include <iostream>
using namespace std;

class LogicGate
{
    int type;//gate type: 0 for NOT, 1 for OR, 2 for AND
  //pins 
  bool ina;//input a
  bool inb;//input b::this pin is not used for NOT gate
  bool outc;//output

  //fan-in
  LogicGate* ga;//gate connected to input a
  LogicGate* gb;//gate connected to input b

  //fan-out
  LogicGate* gc;//gate connected to output 
  int gctarget;//target input to which the gate "gc" is connected, 0 for input a, 1 for input c 



public:
    char* name;
    LogicGate()
    { 
        ina = inb = outc = false;
        ga = gb = gc = (LogicGate*)0;
        type = 0;
    }
    LogicGate(bool a, bool b)
    { 
        ina = a; inb = b; outc = false;
        ga = gb = gc = (LogicGate*)0;
        type = 0;
    }

    //set logic
    void settype(int t){if(t>=0&&t<3)type=t;else type=0;}

    //set input
    void seta(bool a){ ina = a; }
    void setb(bool b){ inb = b; }
    void setab(bool a, bool b){ina = a; inb = b; }

    //connect gate
    void cona(LogicGate* cga){ ga = cga; }
    void conb(LogicGate* cgb){ gb = cgb; }
    void conab(LogicGate* cga, LogicGate* cgb){ ga = cga; gb = cgb; }

    //connect the output of this gate to another gate's input
    void chainc(LogicGate* cgc, int target)
    { 
        gc = cgc; 
        gctarget = target;
        if(target==0) cgc->cona(this); else cgc->conb(this);
    }

    //calculate output
    bool calcout()
    {
        //if the input is not available make it available by forcing the connected gates to calculate
        if(ga){ ina = ga->calcout(); } //BUG:this may cause Stack overflow for circuits with loops
        if(gb){ inb = gb->calcout(); }//BUG:this may cause Stack overflow for circuits with loops

        //do the logic when inputs are available
        switch(type)
        {
        case 0:
            outc = !ina; break;
        case 1:
            outc = ina || inb; break;
        case 2:
            outc = ina && inb; break;
        }

        //if a gate is connected to output pin transfer the output value to the target input pin of the gate 
        if(gc){
            if(gctarget==0){
                gc->seta(outc);
            }else{
                gc->setb(outc);
            }
        }

        //for debugging only
        cout<<name<<" outputs "<<outc<<endl;
        return outc;
    }


};
int main(int argc, char *argv[])
{   
    LogicGate x,z;

    //AND gate
    z.settype(2);
    z.seta(false);
    z.setb(true);
    z.name = "ZZZ";


    //OR gate
    x.settype(1);
    x.cona(&z); // take one input from AND gate's output
    x.setb(true);
    x.name = "XXX";

    //z.cona(&x);// take one input from OR gate's output to make a loop:: results in stack overflow
    x.chainc(&z,0);//connect the output to AND gate's input "a" to form loop:: results in stack overflow 

    cout<<"final output"<<x.calcout()<<endl;

    return 0;
}

Answer 1

The Problem here is that you are Looping infinitely. A program behaves somehow different than real logic gates. I see two possibilities here:

1) Implement cycles

You can implement it like a cpu works. a call to calcout only calculates to Output of one gate and iterates to the next one. You could create a Container class for your gates:

class GateContainer
{
    //Contains all gates of your "circuit"
    std::vector<LogicalGate> allGates;

    //Contains all current gates to be processed
    std::queue<LogicalGate*> currentGates;

    void nextStep();
}

The nextStep function could look like this:

void GateContainer::nextStep()
{
    //Get first gate from queue
    LogicalGate *current = currentGates.front();
    currentGates.pop();

    //Do all the calculations with th current gate

    //Push the gate connected to the Output to the list
    currentGates.push(current->gc);
}

Please not that this code is untested and may also Need some error checks

2) Try to catch Loops

You can also try to catch Loops in calcout. You could achieve this by creating a flag in LogicalGate and reset it every time before calling calcout:

class LogicalGate
{
    ...
    bool calculated;
    ...
}

Now before calling calcout() You Need to set calculated to false for every gate. Then, calcout could look something like this:

bool calcout()
{
    calculated = true;

    if(ga && !ga->calculated){ ina = ga->calcout(); }
    if(gb && !ga->calculated){ inb = gb->calcout(); }

    ...
}