Digital Logic Simulator

Summary

One of my favorite college courses was computer simulation.  This was a 400 level course that required calculus-based statistics.  Our projects included a project to simulate real-world queuing problems like a McDonalds drive-through line and an airport with one runway.  The answers that we were required to ask were things like: How many cars can the drive-through handle in an hour, or how long would it be before cars would be backed up to the street.  In the case of the airport simulator the results should answer questions like how many aircraft can land per hour or what is the maximum number of aircraft that the airport can handle before aircraft must circle around.

There are a lot of simulations in the world.  Traffic simulations, weather, factory simulations, even financial simulations.  One of the simulators that I am currently interested in is a digital  logic circuit simulator.

Any time I start a new project I start by going to Google (or Bing) and doing some research.  So I dug around and there are a lot of people who have written digital logic simulators and there are a lot of software packages that perform the simulation.  I’m writing this simulator for my own purposes and I have a specific need in mind.  Primarily, I’m trying to simulate a circuit and determine what the fastest timing will be for the circuit.  So my logic gate objects are going to be a lot more complicated than the typical True or False type of inputs and outputs.

Timing

Simulating timing problems makes the entire task much more complicated.  One issue is that I want to create an object for each gate type and then type in the delay time expected between the inputs and outputs.  I also want to simulate voltage levels (eventually), so I need to account for voltage thresholds.  Voltage thresholds can be boiled down to a voltage range to represent a “1” and a voltage range to represent a “0”.  The “All About Circuits” website has a very nice diagram showing the voltage levels for a typical TTL circuit:

I have currently set the input threshold to 2.7 volts and above to be a “1” and anything below to be a zero.  Eventually, I’m going to fix that to be 2-5 volts to be a “1”, 0.8-0 volts to be a “0” and then randomize anything between 0.8-2 volts to be either a “0” or “1” (and log the input as an error).  This voltage level transition logic will play into fan-out limits and other circuitry later on.  For now, I’m just going to fake it at 2.7 volts.

Ah, but the timing.  OK, this is where things can get nasty.  First of all, I need to account for all the inputs of a gate before I can get the output.  If there is a delay, like 18ns for the 7408 AND gate, then I need to know what the two input signals were 18ns ago before I can get an output.  So I decided to use an array (or technically “Systems.Collections.Generic.List” objects) to hold samples for each nanosecond of signal.  Therefore, I can just fill the AND gate inputs with 100 or so nanoseconds of samples, and then the output will react to sample 0-82 starting 18ns into the output to represent 18ns of delay time.  Here’s an example:

and_gate_timing

The above logic is for an AND gate with an 18ns delay from input to output.  The 5 represents 5 volts and 0 represents 0 volts, which is the typical voltage levels of TTL Logic.  The delay times for TTL logic can be found by searching for the datasheet.  It’s easier to find if you know the chip numbers, which you can look up using this chart here.  Once you know the package number, you can search for “7408 datasheet” and get a PDF like this one.

Next, you’ll need to search down the datasheet to find the the switching characteristics, like this NAND gate:

switching_characteristicsThere are two switching times.  The top timing is called tPLH and represents the time delay when the input signal goes from low to high.  This is typically (TYP) 11 nanoseconds.  The maximum time would be 22ns.  The bottom timing is called tPHL and represents the time delay when the input signal goes from high to low.  You’ll notice that this time is only 7ns with a max of 15ns.  Most TTL circuits switch faster on the trailing edge or high to low input.  For my first iteration of this simulator, I’m going to ignore the MAX timing and just assume all Integrated Circuits are created equal and use the TYP speed.

All the timings above are for the 7400 and 5400 packages.  There are other TTL packages that you can buy including 74LS00, 74S00, 74HC00, etc.  These all have different timing, power consumption, etc.  For my NAND gate, I created a switch statement like this:

GateName = "74";
switch (gateType)
{
	case TTLGateTypeEnum.Normal:
		SignalDelayLowToHigh = 11;
		SignalDelayHighToLow = 7;
		break;
	case TTLGateTypeEnum.LS:
		SignalDelayLowToHigh = 9;
		SignalDelayHighToLow = 10;
		GateName += "LS";
		break;
	case TTLGateTypeEnum.S:
		SignalDelayLowToHigh = 3;
 		SignalDelayHighToLow = 3;
		GateName += "S";
		break;
	case TTLGateTypeEnum.Perfect:
		SignalDelayLowToHigh = 0;
		SignalDelayHighToLow = 0;
		GateName += "PERFECT";
		break;
}
GateName += "00";

You can see that the normal gate is 11ns and 7ns.  The “PERFECT” NAND gate assumes no delay and is used only for testing simulator software or bypassing the delay for theoretical circuits (you can test the basic feasibility of a circuit before introducing a time delay).  One other short-cut I performed is that the timing on some spec sheets show decimal nanoseconds.  The timing is continuous so it could be any number in real-life, but TYP is the average of signals that the gate was tested under.  Therefore I just rounded up to the nearest unit and my entire simulator is limited to 1ns minimum sample size.  Technically, this could be altered in a future version to increase the sample size, but be aware that the array size of each input and output will increase accordingly.

Running a Circuit

Each gate is a separate object.  I created an abstract super class so I could promote any similar code up to that class.  It’s called LogicGate.  Some of the code inside each gate is becoming repetitive and I will be promoting more of the duplicate code into this super class.

To make the circuit run, the basic algorithm is as follows:

  1. Copy an array of voltage levels into each starting input.
  2. If all inputs are filled, then copy the output samples into an array of the next connected input.
  3. If all outputs have been computed, then the circuit is complete.

My next task was to develop a connection object.  The connection object tells which output is connected to which input.  The connection object has a method called “TransmitSignal()” that will copy the output of the “Source” to the input (stored as Termination).  

You might notice that there is a wire object as well.  This was setup to be used as an input connection to a complete circuit.  I’m still trying to merge the wire and connection objects together to perform the correct function for both instances.  This is part of the sausage-making that occurs when developing something from the ground up.  First, try one or two objects and connect them.  Then refactor.

The circuit object has a RunCircuit() method that will go through all the connections in a circuit and copy the sample data from the inputs to the outputs until all signals have been copied.  My goal is to be able to connect circuits together and perform the same logic between circuits, recursively.  As of this blog post there is a circuit for a half adder and a full adder.

Showing the Circuit Run

I added a dumb-and-dirty windows forms application that has one main form.  The form will display the waveforms of all inputs and outputs for a full-adder.  The full-adder circuit is based on this diagram:

full_adder_circuit

The truth table looks like this:

full_adder_truth_table

When I run a perfect circuit (all gates set to perfect), I get the following:

half_adder_ttl_perfect

As you can see the above signals match the truth table.  For instance, on the left, before the first transitions occur, all three inputs (A, B, Cin) are zero and the S and Cout are zero.  Next, after the first transition, the Cin switches to a “1”, you can see that “S” is also a “1” and the Cout remains zero, just like the truth table.  If you continue to follow the signal transitions from left to right, you can see the truth table matches up exactly.

Now it’s time to see if the circuit works when there is a delay.  Here’s the output of a full adder using LS logic gates:

ttl_ls_logic

You can visually see the delay from the first Cin transition to the S output.  The signals do not transition at exactly the same time.  This part seems to be working. 

It appears that there is a bug in the logic someplace.  The S or sum output seems to go low for a short period of time while the Cin transitions to zero, the B input transitions to high and the A input remains as a low signal (see red circle above). When I look at the logic gate there is a longer delay from the A and B inputs to S than the Cin input due to the extra XOR gate at the input.  That means that the B input transition is delayed to the input of the second XOR gate.  Therefore B is still low when Cin transitions to high.  I’m betting that the real circuit behaves the same and there is no real bug.  My simulator is providing valuable data already.

Verification Time

I ran out to DoCircuits and started up a full-adder circuit.  The output from that circuit shows this:

docircuits_full_adder

I like how they indicated “unknown” for the outputs S and Cout during the delay.  When Cin and B transition at the same time, after a delay, the sum goes to low.  That’s a head-scratcher.  Unfortunately, the input signals are limited and I can’t replicate my exact scenario.

OK, here’s a more detailed study on circuit delays: Propagation Delay, Circuit Timing and Adder Design.  If you scroll down to page 49,  you can see the same problem occurring in real life:

timing_simulation

The bottom line is that I learned something today.  Had I plugged some chips into my breadboard and flipped a few switches I would not have seen this nanosecond transition issue.  If I had built a signal generator and pumped the three signals into this circuit I could have caught it on an oscilloscope, but more than likely, I would have built some giant circuit containing this small piece and would be pulling my hair out trying to figure out what is going on.  Obviously, my simulation and the fact that I wrote it myself, showed me a few things that I did not expect.

Where to Get the Code

As always, I have posted the code on my GitHub account and you can download it by clicking here.  Feel free to expand this into anything you’d like.  Check back in the future and see if there are any updates.

 

Leave a Reply