Circuit Simulator in Java

October 3, 2007 9:15 PM

Can you help me solve this (not homework) computer science problem?

A friend of mine (who is a physics professor) asked me to write a program for him that would implement this:

http://yellowbkpk.com/algebra%20circuits.pdf

To do this, I wrote a Java program with a data model that looks somewhat like this:

• Addition, Negation, Reciprocal, Opposite, Input, and Output are all concrete implementations of a "circuit element" abstract class.


• A circuit element has an array of inputs, each of which is a reference to another circuit element.


• A circuit element has an abstract getValue() method. For example, the Addition circuit element returns input[0].getValue() + input[1].getValue().


• The output for the circuit is computed when the Output circuit element calls its input's getValue() (which initiates the recursion).

The problem with this design is that it only works for combinatoric circuits (like the "subtraction" example in the PDF). When I try something like the bottom three examples, I get infinite recursion.

Can you suggest a better way to implement this?

posted by yellowbkpk to computers & internet (21 comments total)

Sorry about the bad formatting and PDF link...
posted by yellowbkpk at 9:15 PM on October 3, 2007

I don't quite understand the SQRT one. If the multiplier takes a 5 as one input and the other input is the reciprical of the output of the multiplier, how is this supposed to be initialized?

Another way of asking, I think, is what is the output of a multiplier when only one input is connected?
posted by jeffamaphone at 9:35 PM on October 3, 2007

Simillarly, I don't see how you get 13 out of the bottom one.
posted by jeffamaphone at 9:38 PM on October 3, 2007

Being able to have feedback (cycles in the graph) means that the user can specify pretty much arbitrary systems of equations. I think the best thing to do would be to convert the circuit into a traditional algebraic form and then hand it off to a symbolic mathematics package— Mathenatica, MACSYMA, etc.. Or you could look into the kinds of manipulations that those packages use to manipulate polynomials, and perform equivalent manipulations on your circuit graph. But this starts getting hairy surprisingly quickly.

(If there were no "reciprocal" box then you might be able to boil this down to inverting a matrix. But with reciprocals and feedback I think you've bitten off a hard problem.)

If the graphs are representing some physical system, then they might be restricted to some form that can be solved by, e.g., successive approximation. (The square-root circuit, for example.) But in the general case you'll have to deal with graphs with multiple solutions, graphs with no solution, and graphs whose solutions are difficult to find (this is probably an NP-complete problem).
posted by hattifattener at 9:44 PM on October 3, 2007

s/Mathenatica/Mathematica/
posted by hattifattener at 9:44 PM on October 3, 2007

Explain how the feedback works. When is it calculated?
posted by jeffamaphone at 9:52 PM on October 3, 2007

Think in terms of systems of equations. The Square Root box is actually:

25 * A = B
1/B = A

25 * 1/B = B

25 = B*B

5 = B

===

Mean:
13 + A = B
-7 = C
C + B = -A

13 + A = B
-7 + B = -A

13 + A = B
A = 7 - B

13 + 7 - B = B

20 - B = B

20 = 2 * B

10 = B
posted by b1tr0t at 9:52 PM on October 3, 2007

Ah, I see. That does make it harder.
posted by jeffamaphone at 9:56 PM on October 3, 2007

You might try:
1. Build a graph of the circuit elements
2. Traverse the graph, extracting equations and inserting variables where unknown quantities exist
3. If you have N equations with N or fewer unknowns, send your system of equations to an equation solver, else fail
posted by b1tr0t at 9:56 PM on October 3, 2007

I suggest you check out Numerical Recipies in C, chapter 2.

Oh, you want Java I guess. Lucky you, 3rd edition exists.
posted by jeffamaphone at 9:59 PM on October 3, 2007

It's feedback. Much of electronics is based upon these sort of things - it's interesting seeing it with an entirely different type of "circuit elements."

This is not too much help, but to illustrate the problem I shall explain that the answers can be found by noting that the elements impose constraints upon the values at the nodes where they are connected. This is what's called a "system of equations." The square root has three nodes - the two inputs to the multiplier and the output of the multiplier. Everything is connected to at least one of these points.

Let's call the multiplier's inputs i and j and the output o. We can find the value of any of these given one of them.

The system imposes these constraints.

o = i * j
j = 1/o

That's two equations. With no more information there are three unknowns and while we could write all sorts of different relationships between them but we cannot solve them for numbers.

We can prove that this is a square root machine by algebraic manipulation to the two equations. Simply replace j in the first equation with the value from the second equation:

o = i * 1/o

o = i/o

o^2 = i

o = +/- square root (i)

But look, even this example actually has two correct answers. The output could be 5 or -5.

So you need to write an engine to solve systems of equations. But they're not even systems of linear equations. Even I know how to solve systems of linear equations, but non-linear is harder.

You're probably best off looking at what, if any, sort of pre-existing math package can do this best for you and then figuring out a program that parses these schematics into equations.
posted by TheOnlyCoolTim at 10:07 PM on October 3, 2007

Your friend is a physics professor--does he have access to LabVIEW? It's a block-diagram-based environment that already has all of the addition/subtraction/etc. elements already available as blocks. These circuits would be very easy to make and wire up--it's drag and drop--and would be easy for the students to change the values being input. Feedback in LabVIEW is not a problem.

Note: He may have access through his school; if not, it's probably too expensive. Worth asking, though--it might be easier to implement an existing program than to build a new one.
posted by Upton O'Good at 10:12 PM on October 3, 2007

The usual way to solve this kind of thing is with iteration rather than recursion. The simulator starts with values on each wire and calculates what each operational box should yield based on its inputs. That changes the value on most of the wires.

Then you do it again using the new wire values. And again. And again. If you think the system will settle, you write your iterative simulation so that it monitors "this" value and "the previous" value for some wire until the amount of change on it per iteration is below a certain threshold, after which the simulation stops automatically. Expect it to take 50 or 500 cycles to settle if it's at all complex.

If you're not sure if the system settles (and not all systems with feedback do) then you make your iteration dump all the wire values on each iteration, so that you can go back and look at them (perhaps by plotting them against iteration number e.g. "time").
posted by Steven C. Den Beste at 11:30 PM on October 3, 2007

If what you're simulating is a circuit that can contain feedbacks, you really need to include some notion of time in your simulation.

Instead of having each circuit element immediately perform an internal calculation when it's asked for an output value, each element needs its current output value stored. You need to make some provision for giving each circuit element a default (initial) output value. 1 is good, if you can't think of a reason not to use it.

Next, you run what is effectively a two-phase clock to all circuit elements. During phase 0, each element queries each of its inputs for their currently stored output values; during phase 1, each element recomputes its own output value based on the inputs it collected in phase 0.

That way, all the outputs change in sync, and there's no infinite recursion.

Stop the simulator when its output value has been within epsilon percent of its previous value for M clocks, or fails to stabilize after N clocks.
posted by flabdablet at 11:35 PM on October 3, 2007

Jinx!
posted by flabdablet at 11:36 PM on October 3, 2007

The multiply box becomes 25 * A = N;
the divide box becomes A = 1 / N.
So, you have something like 25 * 1 / N = N, or
(25 / N) - N = 0.

So, then try Newton's Method to find N?
posted by blenderfish at 11:55 PM on October 3, 2007

I went in and labeled your diagram with green numbers and purple letters for reference purposes. Please see this.

You can create the program so that it's table driven. Each entry in the table describes one operational element in the circuit, and the table taken as a whole is a wiring list for the system.

The table is an array of structures. Each structure contains an enum telling which type it is (value, measurement, addition, negation, multiplication, reciprocal), two input wire numbers, and an output wire numbers. Not every type uses all three wires, so we define UNUSED as 0 for a placeholder for unneeded wires.

So looking at my version of the last circuit we get this (label, type, input1, input2, output):

A: value, 7, UNUSED, 5 // for a "value", input1 is its constant value
B: value, 13, UNUSED, 1
C: negation, 5, UNUSED, 6 // for a "negation", input2 is unused
D: negation, 4, UNUSED, 3
E: addition, 6, 2, 4
F: addition, 3, 1, 2
G: measurement, 2, .1, UNUSED // for a "measurement", input2 is the settling threshold

If you do that, then the rest of the program is completely generic, and you can change circuits just by altering how that array is initialized.
posted by Steven C. Den Beste at 12:03 AM on October 4, 2007

You'll probably get convergence more often if, instead of simply replacing its output value by a new value based on its inputs, a circuit element yields an output that's the average of the newly-computed result and its previous output value.

For example, without averaging, the square-root circuit would yield:

clock, reciprocal, multiplier
0, 1, 1
1, (1/1)=1, (25*1)=25
2, (1/25)=0.04, (25*1)=25
3, (1/25)=0.04, (25*0.04)=1
4, (1/1)=1, (25*0.04)=1
...

Not a lot of convergence going on there. But with averaging, you'd get

clock, reciprocal, multiplier
0, 1, 1
1, (1/1+1)/2=1, (25*1+1)/2=13
2, (1/13+1)/2=0.53846154, (25*1+13)/2=19
3, 0.29554656, 16.23076923
4, 0.17857897, 11.80971660
5, 0.13162750, 8.13709538
6, 0.12726074, 5.71389146
7, 0.15113641, 4.44770496
8, 0.18798573, 4.11305757
9, 0.21555693, 4.40635043
10, 0.22125106, 4.89763686
11, 0.21271558, 5.21445664
12, 0.20224506, 5.26617307
13, 0.19606814, 5.16114976
14, 0.19491171, 5.03142658
15, 0.19683125, 4.95210962
16, 0.19938269, 4.93644540
17, 0.20097880, 4.96050638
18, 0.20128556, 4.99248823
19, 0.20079324, 5.01231365
20, 0.20015095, 5.01607236
...

which is clearly heading in the right direction.
posted by flabdablet at 12:56 AM on October 4, 2007

Here's Gerry Sussman doing a lecture from SICP featuring circuit simulators in Scheme. Could help you get on the right track (although I suspect trying to do functional programming in Java may be a fool's errand).
posted by letourneau at 4:41 AM on October 4, 2007

If it's not necessarily important that you solve this problem in Java, I'd strongly second LabVIEW. In addition to what Upton mentioned, LabVIEW also makes it easy step through and debug complicated simulations by progressively showing you the outputs of each node. You can also build redistributable EXEs if he wants to give something to his students.

We used it a lot in university EE/CompE labs -- I reckon that your physics prof friend can get access to it through someone in those departments, if not through his own.
posted by JohnFredra at 10:27 AM on October 4, 2007

The gist of the machine described in the Sussman lecture, stripped of all the LISP-specific stuff and detailed data structure descriptions, is this:

1. Every wire in the circuit has a current value, a procedure for setting that value, and a list of notification procedures to call when the value is actually changed to something different. These procedures belong to the inputs of circuit elements, and get added to the wire's notification list when the wire is connected to an input.

2. There is an agenda, or work queue, that tells the entire simulated machine what to do next. Each agenda item consists of a time, a set-value procedure, and a value to set. The work queue is maintained in time-sorted order.

3. Each circuit element is designed to respond to notification of a change in any of its inputs, by:

(a) fetching the current value of that input
(b) computing a new output value based on all inputs
(c) inserting the set-value procedure for all wires connected to the output into the work queue, along with the new output value and a time that's the sum of the current system time and the element's propagation delay

4. There are some special circuit elements that are responsible for getting the whole thing started, presumably by spontaneously doing 3(b) and 3(c) for time 0 as soon as their outputs are connected to anything. This is glossed over in the lecture.

5. There are some other special circuit elements (probes) that have just a single input connection and no output connections, whose input-change notification procedure just makes them fetch the new input value and print it on the console.

6. Running the simulation involves:

(a) removing the first item from the work queue
(b) setting the current system time to that item's time
(c) calling the specified set-value procedure with the specified value

until the work queue is empty. The reason that the work queue can possibly get empty is that wires won't call their notification procedures if their set-value procedure sets their value to the same one they already have.

The whole thing is designed for logic, rather than analog signal levels; there's an underlying assumption that outputs will only change once per change of input(s). If you were going to use this architecture for your "analog computer" circuits, you'd need to invent a mechanism for gradual output change, or you probably wouldn't get convergence.

One way that I think would work, just off the top of my head, is to give each of your circuit elements a (possibly implict) internal wire connecting its output to a (possibly hidden) extra input. That way, you could get the kind of averaging behavior I described above if you wanted it.
posted by flabdablet at 9:36 PM on October 5, 2007