Summary
In this post I’m going to talk more about creating simulation software and the difficulties of inventing something new.
Writing Software is Like Working in a Sausage Factory
Writing new software is more of an art than a science. Sure, we call ourselves scientists and we have methods and proven algorithms for getting things done “right.” At the end of the day, it’s a bit of trial and error. Sometimes a software development project contains a lot of unknowns. As an advanced software engineer, my daily routine consists of mostly “unknowns.” I’m the guy who has to “figure it out.” That’s my job and that’s what I enjoy doing. When I create software for my hobbies, I run into the same problem.
I start a project with all kinds of great ideas about how the software will work, what algorithms I’ll use and all I need to do is type in the code. Then I have to troubleshoot. First I’ll find some simple bugs. Then I’ll dig into deeper bugs and hopefully, what I’ve built works as expected. Otherwise, I might spend an enormous amount of time trying to find a bug that turns out to be a flaw in my initial assumptions. This will be followed by a re-design and a lot of refactoring. On really rare occasions, I’ll throw out my code and start over. Actually, I don’t throw anything away these days. There’s version control, unlimited cheap storage, etc. No need to throw it out, just archive for future review (if I need to).
Once the program works, then I have to do some cleanup work. There is usually some dead-code that needs to be removed. Also, code formatting might take a back-seat when I’m trying to figure out an algorithm. That needs to get cleaned up. Then there are “TODO:” notes littered all over the place. I’m really bad about getting back to those. They can be handy, but they can multiply quickly.
My development process usually goes like this:
- Create a library to contain my code.
- Create a test project to unit test my library code.
- Create a shell of the first object and create one or more empty unit tests (with Assert.Fail() or something similar in the body of the test method) of features that I’ll need.
- Create code for the first feature, add code to the unit test that applies.
- Make the unit test pass.
- Repeat
Sometimes I create a console application so I can use logging to do my troubleshooting. This occurs when things get more complicated and I need to integrate pieces together. If I want web output, I’ll create a website project and if I want a windows graphical screen output, I’ll just create a Windows Application project (all in the same solution). I can switch which project is the startup project, so I just keep all the projects together where I know they are related.
Of course, this is the Sausage Factory. It get messy inside and it’s not for the faint of heart (aka, non-technical). For those who have never written a program, it just appears that I’m a zombie at a keyboard typing in strange words and characters. For those who have written more than an introduction-level program, they’ll just nod and smile.
The Digital Logic Simulator
One type of program that usually starts with the most unknowns is the simulator program. A simulator program is an abstract representation of something in the real world. The Digital Logic simulator just simulates physical logic circuits that can be built with TTL (Transistor-Transistor Logic) circuits. This simulator is not intended to be electrically accurate, only accurate in the sense that I can simulate the timing of real circuits. There are already software packages on the market that are electrically accurate and some are extremely good (and they have the price tag to go with them). I’m doing this as a hobby, so I expect to gain some knowledge and I’m also doing this as a blogging subject so I can pass along my knowledge to anyone who wants to learn more about digital logic and simulators.
When I setup this simulator, I created arrays (or lists) of voltages that are applied to inputs and outputs. Each array cell represents a voltage sample for 1 nanosecond of time. So far I’ve kept the voltages to 5 volts and zero volts and assumed that there are no voltages in-between. Will I exploit the capability of setting any sample to any voltage? I’m not sure yet. My current concern is the timing aspect of it all.
To simulate the operation of a circuit, I have to translate inputs into outputs. So input voltages are copied to the outputs of simulated wires (since a wire just conducts the voltage to the other end). Logic gates can require anywhere from 1 to dozens of inputs in order to determine what the output voltage is. So I have written objects and methods to represent how a gate will handle inputs. Then I have setup special connection objects that can translate from one gate output to other gate inputs. In order to make it all work I have created a circuit object that begins with the input data and attempts to propagate the voltages from the inputs through all the wires and gates until the outputs are known. This algorithm works…. to a point.
One of the first problems I ran into using the input to output algorithm is that there could be unknown inputs to gates. This happens because two different input signals to a gate might travel through different numbers of other gates. Like this:
As you can see the signal from input “A” will arrive at gate 1 before the result of gate 0 arrives (because inputs B and C need to be processed through gate 0 first). So if the circuit algorithm tries to process gate 1 before gate 0, then one of the inputs is still unknown. My solution (for now) is to mark all outputs as “unknown”, then attempt to process each gate. If the inputs to a gate are all known, then process the gate and translate the output. Then I run through the circuit again to see if I can determine more gate solutions. This can continue up to 10 times, in which I assume the circuit cannot be solved.
The next big problem was the flip-flop. This was a very difficult problem because the flip-flop is a chicken-and-the-egg problem. The outputs are fed back into the inputs of the opposite NAND gate. So the inputs are always unknown. As I mentioned in one of my earlier blog posts, I can get around this type of problem by being able to compute the output of a gate with some unknown inputs as long as I have one or more inputs that can determine the output. In other words, if an AND gate contains one input that is a zero, then it doesn’t matter what the other inputs equal, the output will always be zero. With this assumption, I can determine outputs with minimal inputs and get around the flip-flop issue.
Next, I discovered that one of my virtual circuits contained a missing input connection. I decided to create some test methods that I can use in my unit tests to determine if the circuit is valid to start with. First, I need to make sure there are no open inputs on any gates. So I have a method to test this. Then I needed to make sure there are no two or more outputs connected together. That would be a short circuit. Last, I needed to determine if, at the end of a circuit run, there were any wires that contained voltages at the source end that were different from the termination end. This would be an invalid circuit configuration and cannot happen in the real world. So after running a circuit, I check the wires and if that passes, then I’m on to unit testing the known inputs with the outputs to determine if the circuit is correct.
I can create very complicated circuits out of gates. My next trick will be to create circuits of circuits. I’ve tried a couple of algorithms to make this work. I’m hoping to come up with a plan that would allow me to connect circuits together and treat the whole thing the same way I treat a circuit. Unfortunately, this is not as easy as I had hoped. One of the problems is that I have to run a circuit in order to get the outputs. So I connected two Full Adder circuits together into a two-bit adder like this:I know what the logic table looks like, so I created the unit test for this circuit before I built it. Then I built the circuit and I ran into a problem. The bottom adder requires the carry out from the top adder in order to perform its calculations. In addition to the sequence of operations problem, there is also the fact that the output of the first adder has a connector object that must copy the voltage from one end of the wire to the other. Before anything starts though, the inputs must all be copied to the circuit inputs. Fun times.
The program is rather slow already. I’m OK with the simulation running slow, I’m not looking to run this in real-time or to produce a lot of data in a short amount of time. However, the slowness is going to compound when I get to the circuit of circuit level (and beyond). So I’m re-thinking my algorithm.
New Circuit Algorithm Ideas
One algorithm I’ve been thinking about involves starting with an output and working backwards recursively to find enough inputs to satisfy a known signal. In the case of the two-bit adder, I can start with the output S0. This output will require Cin (which is hard-wired to zero volts), A0 and B0. For S1, I’ll need Cin, which requires the result of Cout of the other adder circuit. Then I’d need to find out that output first and so on. This algorithm will work except for one tiny problem. The timing of it all.
To obtain the timing, I’ll need to go forward through the circuit. There are a few ways I can implement this. First, I can just run my recursive backward seeking algorithm until I get to the inputs and just unroll my recursions and fill in the arrays as I go.
Another idea I have in my head involves the same algorithm, trace from output to input recursively, but just store the paths that the electrical signal must follow. Then trace the signals from inputs to outputs using the order setup by the recorded paths from the recursive algorithm. This would be a two-step algorithm. Find the paths then translate the signals.
Some pitfalls to watch for:
- These circuits could become really large and recursion can get slow. If recursion becomes a problem, I’ll be forced to use a stack.
- Another issue will involve infinite recursion. This I know will happen in situations like the Flip-Flop. I’ll need to design in a safety cut-off before I start using recursion for anything. I’ll also have to see what I can use for a cut-off in a Flip-Flop circuit.
- Testing recursion can be difficult. I’ll need to think about how I’m going to test this thing.
Fortunately, I already have a few circuits in the solution that I know work. So I can setup my new algorithm and run some existing unit tests to verify that the new algorithm works properly. I can also retain my circuit verification methods since that will not need to change.
One other assumption that my circuits make is that wires are perfect. There is no delay calculated for wires. Wires are represented by the wire object and the connection object so I can add delay time to these. However, the delay time for a wire depends on it’s diameter and length. Both of these are not normally known until a physical design is determined. For now, I’m going to continue to assume a delay of zero, but anyone using this code to simulate a circuit should be aware of this limitation.
I guess it’s time for me to get to work…