Summary

In my last post I described a logic circuit simulator that I was working on.  I have continued to work on this simulator source code and have discovered a difficulty in simulating a flip-flop.  While researching for a creative solution to my dilemma I stumbled across a circuit called a Falstad circuit.  This circuit demonstrates the output glitch that I discovered in my last article in a rather interesting way.

The Circuit

So the circuit is extremely simple.  One AND gate with two inputs and an inverter:

If you remember your digital logic circuitry, you’ll recognize that an AND gate is only true when both inputs are true.  Since there is an inverter between the two inputs of the AND gate, then any input will produce a true and false or a false and true input to the AND gate.  So the output will always be false.

That’s exactly how this circuit behaves in a perfect world:

Great circuit.  It basically does nothing.  That would be a perfect circuit with no delays.  However, in the real world there are delays.  The inverter will have a delay and the output of the inverter will be true for a few nanoseconds before the input of true is transmitted out as a false.  That means that the AND gate will get a short duration true output.  So let’s change the delay to a standard TTL gate delay for this circuit and re-run the simulation:

The output of the AND gate is also delayed, so it appears in the graph above that the true for the AND gate occurs right after the red line goes red.

Latches

Latches were designed to avoid the delay problem that I’m demonstrating with the Falstad circuit above.  The idea of a latch is that it will only accept the input and latch it in place.  The simplest latch is the Set-Reset or SR latch:

What this circuit does is hold the output when the inputs are both true.  If the S input receives a false pulse, then Q will go high and Q-bar will go low and the configuration will hold this value until R receives a pulse.  So the circuit should behave something like this:

I’m only showing the S input and assuming the R input stays true or high for the entire signal above.  I’m also only showing the Q output since Q-bar will be the opposite.

I had to make a couple of changes to my circuit simulator to make this work.  First, I changed the RunCircuit() method to run the whole circuit for sample 0, then run the circuit for the next sample until all samples were completed.  My previous algorithm ran all the samples for an output, then did the next output until the circuit was complete.  The second change involved the computation for the output of the circuit for one sample.  I had to check and see if the number of samples available on an input was one less than the sample being worked on.  If that was the case, then I just take the previous sample since the output of one of NAND gates will not arrive at the input of the other until the circuit completes.  Therefore, I just lookup the previous level.  This is my output from the simulator (with a perfect circuit):

As you can see Q goes high when S goes low.  Q then remains high no matter what S does afterward.

Before I figured out how to make my simulator work, I was unsure of my results so I dragged out the breadboard and dug around in my bag of chips (oh, you think I’m kidding):

Anyway, I needed a TTL 7400 NAND gate and I knew there was at least one in this bag.  So I found one and stuck it in my breadboard and wired a SR latch:

Yup, it worked as I remembered it working.

Next, I changed my TTL logic to use normal logic with delays.  Yikes.  That was not so pretty.  I tweaked the algorithm a little to read the last input that was sampled when there are not enough input samples.  That helped, but I still get a bounce issue and apparently, that’s a problem in real flip-flops.

Once the SR latch is triggered by S going low, then the arrangement becomes stable.  The width of that oscillation is the delay time of one NAND gate.  This is occurring when both S and R are high at the same time.   This is supposed to be the “invalid” condition according to the truth table:

Apparently, the simulator is correct.  My next project will be the JK Flip-Flop.  If you’re hungry for more information on the subject this is a very nice article about Latches: http://www.electronics-tutorials.ws/sequential/seq_1.html.

Where to get the Code

You can go to my GitHub account and download the full source code by clicking here.  This is a work in progress, so expect changes in the future.

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:

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:

There 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:

The truth table looks like this:

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

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:

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:

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:

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.

I’m moving my blog from Google Blogspot to my own domain.   Almost any person who has used blogspot knows the problems.  Google does not maintain their blog engine.  I’ve been using Blogspot since April of 2012 and I’ve seen little change.  The javascript for the theme I used to use doesn’t work as well as it used to.  Clicking on a picture and then closing the picture using an iPad causing the blog to snap to the top.  Code highlighting is not an easy add-on.  Available themes are limited.  Blog customization is difficult.  So I finally reached my pain point and decided to look for another blog engine.  I stumbled across Ghost and I really like their blogging site, but their prices are high and I have two blogs.  I don’t make any money from my blogging, so there’s no real justification to move from a fee blog site to a site that costs money.  I do, however, have a website that I am already paying for.  That website is hosted by Godaddy.  Fortunately, Godaddy has WordPress and there was a Casper theme, which is the same default theme that Ghost uses.  Therefore, I can get the same quality of output as Casper and not pay a dime more for services that I already pay.  Sweet!

WordPress has been around since the stone-age and they have come a long way since the last time I installed and configured it.  First, it was a click of the button to activate (after I setup a blog subdomain to my frankdecaire.com domain).  Then I added some plug-ins to do code highlighting.  Next, I scraped a blog post from Blogspot and tweaked the appearance.  The WordPress editor interface is a pleasure to use.  Blogspot has a bug involving inserted images.  Sometimes you can’t get the cursor to occur after the image.  Another bug in Blogspot that drives me insane is when I add carriage returns and nothing happens.  Hitting the publish or save and then re-editing the post shows the extra lines I added but couldn’t see.  I no longer have to deal with all that mess.

My next task is to move all my old articles over from Blogspot.  Maybe I’ll just put a forwarding link there and just continue here… Decisions.  Decisions.