Package ca.ryerson.kclowes.digsim

This package contains the core of a digital circuit simulation engine.

See:
Description

Interface Summary

Block	A Block is connected to at least one input Node and a one or more output Nodes.
NodeChangeListener	A NodeChangeListener is used to listen for chnages in a Node value.

Class Summary

AbstractBlock	An AbstractBlock is a prototype implementation of a Block interface for single-output Blocks..
Event	An Event is a simple immutable data structure containing the relevant information about an Event.
EventTest	Basic test on the Event class.
Nand	Nand is an n-input nand gate.
NandTest
Node	The Node object keeps track of its value and informs any dependent Blocks of any changes.
NodeChangeEvent	The NodeChangeEvent class description.
NodeTest
OutDamnSpotOut	Eliminates glitches.
OutDamnSpotOutTest
SimulateSimpleCircuitTest	Various tests of simulator.
Simulator	The Simulator performs the actual simulation of a digital system composed of Blocks and Nodes.
SimulatorTest	Basic tests of the Simulator class.

Package ca.ryerson.kclowes.digsim Description

This package contains the core of a digital circuit simulation engine. The simulation engine was designed as a teaching tool in Object Oriented software design.

Overview

The digsim package provides the core classes/interfaces to implement a simple event-driven digital circuit simulator. The primary objective in designing this package was to give electrical engineering students a reasonably small example of object-oriented design and implementation.

Problem statement

We wish to simulate the behavior of digital circuits. For example, the boolean equation Z = AB + BC could be implemented using 2-input nand gates with the circuit shown below:

The initial value of the input vector (A, B, C) is (1, 0, 1); the output of each gate is shown (and the initial values have been chosen so that the behavior of the circuit is consistent and stable.)

The goal of the simulator is to predict what will happen to various signals if one (or more) inputs change. Suppose, for example, that the input vector becomes (1, 1, 1). Basic boolean logic tells us that the output Z is now 1; i.e.:

Z = AB + BC = 1*1 + 1*1 = 1

The simulator should be able to handle arbitrarily complex circuits (including feedback loops). The simulator should also explicitly take into account gate delays and determine the time of any signal change.

For example, in the example above let us first assume that the gate delays for the three Nand gates are 10, 20 and 30 ns and that input B changes from 0 to 1 at time 0. The first visible effect will be the output of Nand1 which will change from 1 to 0 at time 10 ns. The next effect will be the Nand2 output changing from 1 to 0 at time 20 ns. The final effect (after which the circuit will be stable barring additional input changes) will the the Nand3 output changing from 0 to 1 at time 40 ns.

Event-driven Simulation

The event-driven simulation model only does something when a signal changes. (Henceforth, we will use the word Node instead of signal.) These changes are scheduled and are called Events. An Event indicates a new value for some Node scheduled to occur at some specific time.

All pending Events are maintained in a priority queue. The simulation procedes by removing one Event at a time from the queue and computing its consequences which may include the generation of additional Events. This procedure continues until there are no more pending Events.

Example (Simple Combinational Logic without feedback)

Let's start with the previous circuit where the intial input vector (A, B, C) is(1, 0, 1) and all other Nodes have been initialized to consistent values. How does the event-driven model behave when the input vector becomes (1, 1, 1)?

From the point of view of the simulator, the input vector itself is of no interest; rather, the changes in any of the Nodes is very much of interest. Here, the change in the B Node: it is scheduled to become 1 at time 0. Hence we add an Event (node:B, value:1, time:0) to the queue

The queue now has one Event in it. The simulator now removes this single Event and computes its consequences.

In this case, since the B Node is an input to both Nand1 and Nand 2, the outputs of these gates needs to be re-computed. Both outputs will become 0, but at different times. Consquently, two new Events are added to the priority queue:

1. node:Nand1-output, value:0, time:10;
2. node:Nand2-output, value:0, time:20;

Once the Nand1-output event is handled, a new Event is added to the queue which now contains:

1. node:Nand2-output, value:0, time:20;
2. node:Z, value:0, time:40;

Neither of these Events has any further consequences and the simulation terminates once they have been removed from the queue.

Package architecture

The fundamental classes in the package are:

Node:

A class containing the Node's current value; it also knows about all the Blocks that use the Node as an input.

Block:

An interface for all concrete circuit elements. The evaluate() method is invoked when an input Node changes value; an Event on the output Node may be added to the event priority queue.

Event:

An immutable class containing the time, affected Node and new Node value of an event.

Simulator:

This singleton class manages the event priority queue and simulation progress (e.g. stepping through the queue). In principle, a user interface should only interact with this class (i.e. the class acts as a facade to the simulation engine).

Bugs and Limitations

Limitations

Glitches

Glitches: The Problem

Consider the simple circuit with the indicated stable and consistent initial Node values.

Suppose that both inputs A and B change simultaneously. The inputs to the Nand gate will still have one input at 0 and the other at 1; the output should remain at 1. This will be the case if the Event changing A to 0 is handled before the Event that sets B to 1. However, Events that occur at the same time may be handled in any order. If the B event is handled first, the current algorithm will set the output Z to 0 and, as soon as it handles the A event (which will occur at the same “time”), it will set Z back to its correct value of 1.

In short, there will be a zero-time pulse at the Nand output: we call this a “glitch”.

Glitches: Possible solutions

There are many possible ways that the simulation algorithm could be modified to eliminate these glitches. For example, the Simulator could check if there was a previous Event for the same Node at the same time and delete one or both of them. (This approach would eliminate a glitch after the Events generated had been produced but before the offending glitch Events were processed.)

The recommended solution, however, is:

• Split the removal of Events from the priority queue into two phases.
• First, delete all Events in the priority queue that occur at the same time and set the Node values for each. In addition, remember all of the Blocks that use any of these Nodes as inputs.
• Next, once all the Nodes have been changed to their new values, send an evaluate message to each Block that uses any of the changed Nodes.

Note that this approach would eliminate the generation of glitch Events.

Glitches: The work-around

This version of the simulation engine does not solve the glitch problem in the “correct” way. Rather, we find a work-around (or kludge) solution.

The work-around solution involves no changes to the Simulation engine or any of its classes. Rather, we exploit the basic functionality of the engine with a new concrete Block whose sole purpose is to eliminate glitches.

This new class is called OutDamnSpotOut (with apologies to W. Shakespeare and Lady Macbeth). You can insert this Block (which has zero delay) at the output of any Block that may produce undesireable glitches.

Refer to the OutDamnSpotOut documentation for more information.

Glitches: Why a work-around, not a solution?

My reasons for the work-around:

• The current architecture is reasonably simple; there are (and will always be) various reasons to improve it. However, it is important to keep it small for pedagogical reasons. At a certain point, a choice must be made between elegance vs. complexity (and size).
• A “work-around” is a time-honoured solution to problems with existing classes/packages that don't behave precisely the way one might want.
• This particular work-around also illustrates the power of having both an interface (Block) and an abstract template implementation (AbstractBlock). The Block interface does not require a single output while the AbstractBlock template only applies to blocks with a single output. Unlike most ordinary concrete Blocks (such as Nand) which are subclassed from AbstractBlock, the OutDamnSpotOut work-around class implements the Block interface directly. (Among other reasons, this is done in order to have a block that has two outputs from the point of view of the simulation algorithm but only a single output from the point of view of the user of the class.)
• Finally, the design pattern used in OutDamnSpotOut is similar to the one suggested for implementing an inertial delay model within an engine that only supports ballistic delays.

Only Boolean Node values

Having only Boolean Node values (1 and 0) limits the usfulness of the simulator. For example, devices with tri-state or open-drain (collector) outputs cannot be simulated directly. Other Node values such as hi-Z, weak-0 and weak-1 could solve this problem. Additional values such as unknown, rising and falling could also be useful.

Note that there is a work-around for tri-state devices: for a set of tristate outputs connected to the same Node, treat each as an ordinary output and connect each output to a multiplexor input. Use the tri-state control signals to select the multiplexor input and connect the its output to the original Node driven by the tri-state devices.

Limited delay model

The current delay model is very simple (and this is done on purpose to achieve simplicity). The model assumes:

• The delay is “ballistic”—i.e all changes at the delay input are passed to the output no matter how short an input pulse may be.
• There is only one delay parameter for an AbstractBlock. Real circuit elements may have different delay times between the change on a specific input and its effect on the output.
• The delay is symmetric: i.e. a 1 to 0 or 0 to 1 transition on the input is assumed (in AbstractBlock) to have the same delay time. Real circuit elements often have different delays for the two possible transitions.

Note: inertial vs. ballistic delays

We use the term “ballistic delay” to describe a delay element whose input is copied to its output exactly delay-time later. For example, if a 10 ns delay element has an input pulse of 0.00001 ns, that extremely short pulse will be echoed at the output 10 ns later.

Real circuits do not work like that. (Suppose you build a real inverter with real devices such as transistors and real wires/capacitors/inductors/resistors and measure the delay between an input change and an output change. If your oscilloscope indicates a 10 ns delay, you can reasonably deduce that a 0.00001 ns pulse at the input will be swallowed by the various capacitances in the circuit and never appear at the output.)

In the “inertial delay” model, an input pulse whose duration is less than some specified time (usually some percentage of the delay time) is simply ignored. This model is a better approximation of how real devices behave. (Note that it also includes the ballistic model as a special case: i.e. when the minimum pulse duration to ignore is zero.)

There are possible work-arounds for these limitations using specialized concrete Blocks to emulate the inertial delay model or asymmetric delays using the existing built-in ballistic delay model. The techniques used in the OutDamnSpotOut Block could be used to do this.

Limited timing parameters (and edge detection)

Not only do real circuit elements usually work using an inertial delay model, they also have additional timing specifications such as setup, hold, rise and fall times.

While all of these could be accomodated (at least in principle) within the current model (by using various specialized Blocks), it may well be better to incorporate some of these parameters directly into the simulation engine.

These issues are particularly important when a Block has an input that is edge sensitive.

Bugs

Output cross-connection

Nothing prevents two outputs being connected together.

Ill-defined and unverified Node names

The current specification for valid Node names is too general.

Future Plans

The bug involving Node naming conventions should be fixed.

The most important limitation is the restriction of Node values to pure Boolean values. Adding additional possibilities to support tri-state outputs has the highest priority. This would also be the time to address the “output cross-connection” bug.

Many of the remaining limitations can be addressed at the user interface level and by creating special blocks based on the current ballistic delay model to emulate other delay models.

It would be very nice if the simulator (either the engine itself or the user-interface or some combination of the two) could throw an Exception when some constraint (such as hold/setup time violation or short-cicuiting active outputs) were violated.

The user interface

Despite the bugs and limitations of the current simulation engine, the bigger problem at the present time is the poor quality of the user interface(s).

The simulator itself (the digsim package) is meant to provide the necessary mechanisms to implement any user-interface policy. It is important to retain this division between mechanism and policy; in particular, care should be taken when adding features to the simulation engine that could be dealt with at the user-interface level.

History

The simulator core was designed and implemented in 1997. This initial core was used as a demonstration in a course that year (and never used again). In 1999, I re-wrote the core design in C using various Abstract Data Type conventions appropriate to that non-object-oriented language. The C version has been used in lab projects at the second-year level (a basic course on data stuctures and algorithms) since then.

In February 2004 I was teaching a third-year course on object-oriented design (with Java as the primary language) when I remembered that I had written a prototypical digital circuit simulator using Java in the distant past. After digging through archives, I found the original source code and design documentation

I was not too embarassed by the quality of the design/analysis/implementation and used the old code as a starting point for lab projects. I also cleaned up the old design and started work on a user-interface package.

This is the result.

Version:

1.0 (20 March 2004)

Author:

Ken Clowes (kclowes@ryerson.ca)