Overview.  Write an interactive digital circuit simulator for combinational and sequential circuits. Your simulator will first read in the description of a circuit (using the format described below). Then, it will prompt the user to enter the values for the circuit inputs. Next, it will calculate the circuit output values using event-driven simulation. Finally, it will prompt the user to enter new values for the circuit inputs, and repeat the whole process.

Event-driven simulation.  The simulator will compute the output value of a logic gate only if an input value of that gate has changed (this change is called the event). One way to do this is to maintain a FIFO (first-in first-out) queue of gates that need to be processed. Each gate in the queue has one or more inputs that have changed. The algorithm removes a gate from the queue, looks up its input values, and computes its output value. If this computed output value is different from the old output value, the algorithm determines which gates use this output value as an input, and adds those gates to the queue; otherwise if the computed output value is the same as the old output value, no new gates are added to the queue.

The simulation begins by initializing all outputs to UNKNOWN. Then, all of the gates connected to a circuit input are put onto the queue. Next, the above procedure is repeated until the queue is empty, at which the simulation for the user's set of circuit input values is complete, and the circuit output values are known. Note that a circuit output can change several times before it "settles" to a final value. This phenomenon is normal for sequential circuits. In fact, there are some pathological circuits that will oscillate, and never "settle" down, so you must be prepared to type Ctrl-c to stop the simulation.

Circuit description.  For simplicity, we will consider only circuits composed of AND, OR, and NOT gates. Each gate has at most two inputs, but it can have many outputs. Circuit inputs and outputs will be treated like gates, and when we say "gates" (versus "logic gates") below, we include circuit inputs and outputs. We use the following format to describe a circuit. The 0th line contains the number of gates n. The remaining lines contain information for one circuit input, logic gate, or circuit output as described below. All gates are identified by their line number in this file. Each line consists of the following fields:

6 1: I 0 0 5 0 2: I 0 0 3 0 3: N 2 0 4 0 4: A 3 5 5 0 5: O 1 4 4 6 0 6: Q 5 0 0

Running the simulator.  The user reads the circuit description directly from a file that is specified by a single command-line argument:

arizona.Princeton.EDU% a.out rsflipflop.txt

To handle sequential circuits, the simulator then prompts the user to continue or quit. If the user types 'q' and then Enter, the program terminates; otherwise, the simulator prompts the user to enter a value for each input, and continues as above. After the first simulation for a circuit, if the user does not quit, you should re-simulate the circuit with the new circuit input values, but you should not re-initialize all gate outputs to UNKNOWN. The simulator cannot simulate sequential circuits unless it stores the logical gate outputs from one simulation to the next.

Boolean logic.  You will need three (not two) values for each gate output: 0 (FALSE), 1 (TRUE), or 2 (UNKNOWN). Recall that all gate outputs are initialized to UNKNOWN. Boolean logic is extended to handle the value UNKNOWN in the natural way as follows.

The assignment.  Write a circuit simulator whose behavior is as described above. Your first task will be to read in the circuit description and store it in an appropriate data structure. The consecutive numbering of gates makes using an array a viable approach, since a gate can be uniquely identified (indexed) by its line number in the file. Advice: keep your design modular, and test modules individually.

The checklist contains significant advice on which modules and data types to create, and even provides code to read in the circuit and display it. If you haven't programmed before this semester, we strongly recommend using these hints.

Submission.  The main() function should be in a file named simulator.c. We will compile your program with the command "gcc126 *.c", so be sure to submit all the appropriate source and header files, and a readme file as usual. If you follow the checklist hints, you will submit the following files: readme, QUEUE.h, BOOLEAN.h, CIRCUIT.h, queuearray.c boolean.c, circuit.c, and simulator.c.