My home page
Back to my software experience page
Back to my portfolio

Circuit Simulation Package

The CIRCUIT-SIM package implements a relatively simple digital circuit simulator similar to that described in Abelson & Sussman's Structure and Interpretation of Computer Programs ("SICP").


circuit-sim-20111019.tar.gz

Component files

Example Files

Foundation: Agenda and Actions

The variable CIRCUIT-SIM:*AGENDA* contains a queue of time-stamped events. The functions CIRCUIT-SIM:PROPAGATE and CIRCUIT-SIM:PROPAGATE-UNTIL process the events in that queue, either until the queue is empty or the specified time has been reached, respectively.

The basic signals are carried on circuit elements created by CIRCUIT-SIM:MAKE-WIRE and CIRCUIT-SIM:MAKE-BUS. Wires have arbitrary values, but only 0/1 or NIL/T have definite logical values. (The idea is that values such as :invalid or :floating might be used to represent states that result from missing a setup time requirement, or floating connections, or other unusual states. These values could be propagated through gates, representing indeterminate circuit behavior.) Busses can be parsed into separate wires using CIRCUIT-SIM:NTH-WIRE, or interpreted as integers, one bit from each wire.

Wires also have a list of "actions"; functions called when the state of the wire changes. These are the basic mechanism for circuit behavior to be represented.

Circuit Components

Interesting circuit components such as CIRCUIT-SIM:INVERTER, CIRCUIT-SIM:MAKE-ROM, etc., act by placing "actions" on the input wires which calculate the effect (usually at a slightly later time) of the changed input, and place those resulting actions on the output wires.

Circuit Probes and External Events

CIRCUIT-SIM:PROBE and other assorted functions place actions on wires that result in printing information about events on the wire.

CIRCUIT-SIM:AT-TIME is a macro allowing for arbitrary code, usually representing external system inputs, to be executed at specific times in the simulation.

Adder example

The simple example from SICP is that of a single-bit half-adder circuit.

It consists of two AND gates, an OR gate, and an inverter.

D = IN1 OR IN2
Carry = IN1 AND IN2
E = NOT Carry
Sum = D AND E

This is implemented in circuit-components.lisp
(defun half-adder (in1 in2 s c or-prop-delay and-prop-delay inv-prop-delay)
  (let ((d (make-wire))
        (e (make-wire)))
     (or-gate in1 in2 d or-prop-delay)
     (and-gate in1 in2 c and-prop-delay)
     (inverter c e inv-prop-delay)
     (and-gate d e s and-prop-delay)))

(in-package "CIRCUIT")

(defun sicp-example ()
  (let ((inv-delay 2)
        (and-delay 3)
        (or-delay 5)
        (in1 (make-wire))
        (in2 (make-wire))
        (sum (make-wire))
        (carry (make-wire)))
     (setf *agenda* (make-agenda 0))
     (probe sum "sum")
     (probe carry "carry")
     (half-adder in1 in2 sum carry or-delay and-delay inv-delay)
     (set-signal in1 1)
     (propagate)
     (set-signal in2 1)
     (propagate)))

(sicp-example)

sum Time: 0 New Value: 0
carry Time: 0 New Value: 0
[the initial values]
carry Time: 3 New Value: NIL [in1 = 1 propagates through carry]
sum Time: 3 New Value: NIL [initial value of wire E has propagated]
sum Time: 8 New Value: T [in1 = 1 has propagated through OR and AND gates]
[ at this point, the first propagate has finished; in2 is set to 1]
carry Time: 11 New Value: T [in2 = 1 propagates through carry]
sum Time: 16 New Value: NIL [in2 = 1 has propagated through OR and AND gates.]
DONE

This demonstrates that the sum line has a propagation delay of 8 time units (OR+AND and AND+INV+AND are both 8), and the carry has a delay of 3.

Integrated Woz Machine

The "Woz Machine" is the state-machine floppy-disk controller designed by Steve Wozniak for the Apple II microcomputer. It was a brilliant and classic design, much simpler and lower cost than the standard floppy controller. The introduction of low-cost floppy storage into the microcomputer market was possibly the most important event that made these machines practical tools for home and business, as opposed to toys for tinkerers and hobbyists.

Basic sequencer operation

The Disk II controller is actually quite subtle in several places. The reader is not expected to understand this fully from my description. Truly interested readers should find a copy of Jim Sather's Understanding the Apple IIe for a full treatment.

For reading, the sequencer assembles disk pulses into complete bytes, where a byte always starts with a most-significant-bit of 1. Because the disk reading process can begin at any point in a circular track, the disk data must be written with self-synchronizing patterns and distinct markers at appropriate places to allow the CPU to reliably locate data. Then, the CPU must read data without interruption until a complete sector has been read; if more than a dozen microseconds or so are missed, data will be lost, although in a properly formatted disk, the controller will maintain byte synchronization.

The sequencer similarly shifts out write data, one bit per 4 microsecond interval; MSB first. A `1' bit results in a write pulse, a `0' in no pulse. The CPU must provide data on 32-microsecond intervals or extra zeros will result. (These are deliberately introduced for writing self-synchronizing patterns.) One tricky point is that the write pulse is generated by the high-bit of the sequencer address, not by an opcode.

The basic control of the sequencer is through two bits controlled by the CPU (READ/WRITE, SHIFT/LOAD) the read pulse from the disk head (after being fed through a circuit synchronizing the transitions to the 2 MHz sequencer clock), and the high bit of the data register (QA).

Sequencer Listing

The file woz-machine-hw-sim.lisp simulates the sequencer ROM, the data latch, the control latch, and some glue logic on the chip. It only partially implements the analog timer the Disk II controller uses to control the disk motor, and ignores the ROM containing bootstrap code, which is used only by the CPU.

The function LIST-P6-SEQUENCER walks the address lines on the P6 ROM and formats the output opcodes in a table

(asdf:oos 'asdf:load-op "woz-machine")
(woz-machine:list-p6-sequencer)


Data Dump of Woz Machine Floppy Disk Controller Sequence P6 ROM
Byte format: <next SEQ><opcode nibble>-<opcode symbol>

Opcodes:
  NOP no-operation
  CLR: clear data latch to zero
  SL0: shift 0 bit left into data latch
  SL1: shift 1 bit left into data latch
  LD:  load data latch from Apple II data bus
  SR:  shift state of write-protect bit right into data latch

READ PULSE=RP represents flux transition for 1 bit
SHIFT, LOAD, QA, READ/WRITE MODE are control bits

WRITE MODE

    *-----------READ PULSE-------------*-----------NO READ PULSE----------*
    *-----SHIFT------*------LOAD-------*------SHIFT------*------LOAD------*
SEQ *--QA'--*---QA---*--QA'---*---QA---*--QA'---*---QA---*--QA'---*---QA--*

0-   18-NOP   18-NOP   18-NOP   18-NOP   18-NOP   18-NOP   18-NOP   18-NOP   
1-   28-NOP   28-NOP   28-NOP   28-NOP   28-NOP   28-NOP   28-NOP   28-NOP   
2-   39-SL0   39-SL0   3B-LD    3B-LD    39-SL0   39-SL0   3B-LD    3B-LD     
3-   48-NOP   48-NOP   48-NOP   48-NOP   48-NOP   48-NOP   48-NOP   48-NOP   
4-   58-NOP   58-NOP   58-NOP   58-NOP   58-NOP   58-NOP   58-NOP   58-NOP   
5-   68-NOP   68-NOP   68-NOP   68-NOP   68-NOP   68-NOP   68-NOP   68-NOP   
6-   78-NOP   78-NOP   78-NOP   78-NOP   78-NOP   78-NOP   78-NOP   78-NOP   
7-   08-NOP   88-NOP   08-NOP   88-NOP   08-NOP   88-NOP   08-NOP   88-NOP   
8-   98-NOP   98-NOP   98-NOP   98-NOP   98-NOP   98-NOP   98-NOP   98-NOP   
9-   A8-NOP   A8-NOP   A8-NOP   A8-NOP   A8-NOP   A8-NOP   A8-NOP   A8-NOP   
A-   B9-SL0   B9-SL0   BB-LD    BB-LD    B9-SL0   B9-SL0   BB-LD    BB-LD     
B-   C8-NOP   C8-NOP   C8-NOP   C8-NOP   C8-NOP   C8-NOP   C8-NOP   C8-NOP   
C-   D8-NOP   D8-NOP   D8-NOP   D8-NOP   D8-NOP   D8-NOP   D8-NOP   D8-NOP   
D-   E8-NOP   E8-NOP   E8-NOP   E8-NOP   E8-NOP   E8-NOP   E8-NOP   E8-NOP   
E-   F8-NOP   F8-NOP   F8-NOP   F8-NOP   F8-NOP   F8-NOP   F8-NOP   F8-NOP   
F-   88-NOP   08-NOP   88-NOP   08-NOP   88-NOP   08-NOP   88-NOP   08-NOP   


READ MODE

    *--------------SHIFT---------------*----------------LOAD--------------*
    *------QA'-------*-------QA--------*-------QA'-------*-------QA-------*
SEQ *---RP--*-NO RP--*---RP---*-NO RP--*---RP---*-NO RP--*---RP---*-NO RP-*

0-   18-NOP   18-NOP   18-NOP   18-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
1-   2D-SL1   2D-SL1   38-NOP   38-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
2-   D8-NOP   38-NOP   08-NOP   28-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
3-   D8-NOP   48-NOP   48-NOP   48-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
4-   D8-NOP   58-NOP   D8-NOP   58-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
5-   D8-NOP   68-NOP   D8-NOP   68-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
6-   D8-NOP   78-NOP   D8-NOP   78-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
7-   D8-NOP   88-NOP   D8-NOP   88-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
8-   D8-NOP   98-NOP   D8-NOP   98-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
9-   D8-NOP   29-SL0   D8-NOP   A8-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
A-   CD-SL1   BD-SL1   D8-NOP   B8-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
B-   D9-SL0   59-SL0   D8-NOP   C8-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
C-   D9-SL0   D9-SL0   D8-NOP   A0-CLR   0A-SR    0A-SR    0A-SR    0A-SR    
D-   D8-NOP   08-NOP   E8-NOP   E8-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
E-   FD-SL1   FD-SL1   F8-NOP   F8-NOP   0A-SR    0A-SR    0A-SR    0A-SR    
F-   DD-SL1   4D-SL1   E0-CLR   E0-CLR   0A-SR    0A-SR    0A-SR    0A-SR    
CIRCUIT::DONE

The function WOZ-MACHINE:READ-DISK-BIT-STREAM demonstrates the action of the read sequencer on a series of read data pulses. (Which can be used, for instance, to demonstrate the effect of certain copy protection schemes which use unusually formatted bit streams to defeat ordinary read algorithms.)

The following example demonstrates the self-synchronizing sequence of eight 1's followed by two 0's, followed by the standard address header (hex) D5 AA 96. The times are in nsec, and represent the times when the CPU may be reading the data bus. In real code, of course, the CPU is reading the assembler code from memory; only one cycle in 7 can actually be read by the CPU in the usual read loop which polls for a 1 to appear in the MSB of the data. Many lines of output have been omitted. Note the beginning of the bit stream is only seven ones out of eight, representing the reader being out of sync by one bit.

(woz-machine:read-disk-bit-stream #b1111111001111111100111111110011111111001111111100110101011010101010010110)
;; truncated FF sync, 4 full FF sync, D5 AA, 96

6502 read Time: 0 New Value: 00000000
6502 read Time: 980 New Value: 00000001
6502 read Time: 1960 New Value: 00000001
6502 read Time: 2940 New Value: 00000001
6502 read Time: 3920 New Value: 00000001
6502 read Time: 4900 New Value: 00000010
6502 read Time: 5880 New Value: 00000010
6502 read Time: 6860 New Value: 00000010
6502 read Time: 7840 New Value: 00000010
6502 read Time: 8820 New Value: 00000101
6502 read Time: 9800 New Value: 00000101
(Note the interesting start-up transient here.)
6502 read Time: 10780 New Value: 00000101
6502 read Time: 11760 New Value: 00000101
6502 read Time: 12740 New Value: 00001011
6502 read Time: 13720 New Value: 00001011
6502 read Time: 14700 New Value: 00001011
6502 read Time: 15680 New Value: 00001011
6502 read Time: 16660 New Value: 00010111

...finally, the first one bit gets to the MSB, and the sequencer tries to hold that byte for as long as possible, so the CPU will have a chance to read it. Unfortunately, being out of sync, this byte is garbage.

6502 read Time: 28420 New Value: 10111111
6502 read Time: 29400 New Value: 10111111
6502 read Time: 30380 New Value: 10111111
6502 read Time: 31360 New Value: 10111111
6502 read Time: 32340 New Value: 10111111
6502 read Time: 33320 New Value: 10111111
6502 read Time: 34300 New Value: 10111111
6502 read Time: 35280 New Value: 10111111
6502 read Time: 36260 New Value: 10111111
6502 read Time: 37240 New Value: 00000001

Now, the register is cleared, and shifts in the next byte.

6502 read Time: 38220 New Value: 00000010
...
6502 read Time: 59780 New Value: 01001111
6502 read Time: 60760 New Value: 10011111
...
6502 read Time: 91140 New Value: 01110011
6502 read Time: 92120 New Value: 11100111
...
6502 read Time: 123480 New Value: 01111100
6502 read Time: 124460 New Value: 11111001
...
6502 read Time: 155820 New Value: 01111111
6502 read Time: 156800 New Value: 11111110
...
6502 read Time: 192080 New Value: 01111111
6502 read Time: 193060 New Value: 11111111

Finally, the machine is in sync.

6502 read Time: 194040 New Value: 11111111
...
6502 read Time: 207760 New Value: 11111111
6502 read Time: 208740 New Value: 00000001
...
6502 read Time: 231280 New Value: 01101010
6502 read Time: 232260 New Value: 11010101

Hex D5, which is held in the register for 9 cycles of the 6502.

...
6502 read Time: 240100 New Value: 11010101
6502 read Time: 241080 New Value: 00000001
...
6502 read Time: 263620 New Value: 01010101
6502 read Time: 264600 New Value: 10101010

Hex AA

6502 read Time: 272440 New Value: 10101010
6502 read Time: 273420 New Value: 00000001
...
6502 read Time: 295960 New Value: 01001011
6502 read Time: 296940 New Value: 10010110

Hex 96.