3

I'm writing cycle based logic simulation in C#. I want to simulate both combinational and sequential circuits. Combinational circuits are straightforward but sequential circuits give me trouble.

I want to detect oscillations and display appropriate warning message. Is there a simple way to check how many times a single gate can change its state and still leave the circuit stable?

I thought about 'minimum feedback arc set algorithm' but it seems to be an overkill. Many desktop applications does this fast so I doubt they're using it.

I also found paper advising the use of ternary logic (0, 1, unknown), and splitting algorithm in two parts - one initializing the circuit and one doing actual computations - but it was saying something like 'if algorithm A does not terminate the circuit has oscillations' which gives me nothing since there is no way to stop the clock cycle and warn the user.

Any ideas how applications like "Logisim" or "digital works" detect oscillations ?

Morfidon
  • 1,469
  • 1
  • 18
  • 34
  • I can think of a simple algorithm: calculate all logic levels over the entire network *twice*. If (at least) one of the values changes, then you have oscillation. –  Oct 27 '13 at 22:04
  • A gate in simple RS flip flop can change its state twice and leave circuit stable (third evaluation can tell if there's an oscillation) - if computed in proper order. By proper order I mean the order a human use to solve circuit by hand. If I use simple DFS algorithm the same gate can change its state MANY times. http://tinyurl.com/py4z7ol I am not absolutely sure but i suspect that if gate is inside more feedback cycles it needs to be computed three, fours, five times - i will be very thankful if someone can confirm this. – Morfidon Oct 27 '13 at 22:21
  • Right, I didn't think about that. Yes, a third round would help. As to the correct order: isn't that as simple as starting at the inputs? –  Oct 27 '13 at 22:22
  • Sadly, no. If gate A is connected to gate C and to gate B wich is connected to gate C the order is: A then B then C. Cannot go straight to C or you must recompute it later. – Morfidon Oct 27 '13 at 22:38
  • in my read, "input" is an input of the entire circuit; a junction where only inputs of gates connect. –  Oct 27 '13 at 22:47
  • Yes, i got that. You start at the circuit input, then got gate A, then junction to C and B. And you not compute C until B is ready. I can get that by using sorted list. The truble begins when there are loops. – Morfidon Oct 27 '13 at 22:59
  • http://ozark.hendrix.edu/~burch/logisim/qanda.html#source Logism is open source. – Kastor Oct 28 '13 at 22:14

1 Answers1

1

Verilator is a logic simulator that works by compiling synthesizable Verilog into C code.

It tries to construct an order of logic that will be guaranteed to be stable, but if it fails it emits some UNOPT and UNOPTFLAT warnings and simply repeats the simulation a number of times until nothing changes.

By default, 100 rounds are used before it reports a failure to converge, but this can be changed using argument converge-limit.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • This is nice when checking if circuit is stable. But on desktop application I want to let user build both ungated rs flip flop and simple cpu that computes sin(x). I'm afraid I can't check whole circuit 100 times every clock cycle. – Morfidon Oct 27 '13 at 23:05