For hobbyist reasons I wrote a program which takes the equations of the logic gates of a digital circuit as input, does some analysis, outputs the analysis results and generates program code for doing logic simulation.

Combinational logic is not a problem but sequential logic is:

Currently my program requires you to specify manually that a certain gate's output has a "state" (*) which must be stored in a variable.

I made the attempt to let the program detect such states automatically but the algorithm I developed often recognized too many gates as "having a state".

(For more complex circuits both gates of a flip-flop were detected as "having a state" for example although for a flip-flop the state of only one of the gates must be stored.)

My question:

Is there an algorithm that allows you to detect states in such a circuit (given by the gates' equations) automatically?

I'm planning to simulate circuits with ~20000 gates so simply trying out all combinations will not work.

(*) Please excuse me if I use the word "state" with a wrong meaning. In circuit development the word has a slightly different meaning than in computer science.

About D.W.'s comment:

Let's say I want to simulate a digital circuit which has some inputs, some outputs and n bits of RAM memory.

For simulating the circuit it is obvious that I have to store the values of the n bits of RAM memory somewhere in a variable.

The RAM memory is modeled by the equations of the logic gates the RAM memory is built of - so it's not easy to see/detect that these logic gates represent RAM memory.

So my problem is to find out which n bits represent the data stored in the RAM so I have to store these bits in variables.

I'm going to treat every gate as having a state

This would be possible. However I fear that the simulation will cause wrong results if the variables contain contradictory information when I store more than n bits (e.g. if one variable says: "the bit in RAM has the value 0" and the other one says: "the bit in RAM has the value 1").

  • $\begingroup$ This sounds like a problem that is NP hard in general. $\endgroup$ – adrianN Sep 11 '17 at 7:41
  • $\begingroup$ @adrianN OK. Thanks. In this case I would definitely have to specify the states manually. $\endgroup$ – Martin Rosenau Sep 11 '17 at 10:25
  • $\begingroup$ What do you mean by "has a state"? What criteria would determine which gates should be detected as "having a state"? Is my algorithm allowed to output "I'm going to treat every gate as having a state" or output "I'm going to treat none of the gates as having a state"? Basically, you need to give us a self-contained specification of which outputs are permissible: you say you want the fewest possible number of gates to be labelled as having a state, but the way to achieve that is to label none of them as having a state. I suspect there's more context we're missing. $\endgroup$ – D.W. Sep 11 '17 at 12:07
  • $\begingroup$ @D.W. I added some clarification $\endgroup$ – Martin Rosenau Sep 11 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.