Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 57 ยท Projects

Project: A Logic Circuit Simulator

Build a gate-level logic simulator in Python. Store a circuit as a netlist, evaluate it in topological order, print truth tables and simulate a full adder.

Throughout this course you have written small Python functions to imitate gates and adders. Real design tools do something more general: they read a description of any circuit and compute its behavior. In this project you will build a tiny version of such a tool, a gate-level logic simulator. You describe a circuit as a list of gates and wires, and the program works out the outputs for any inputs, prints a truth table, and even rejects circuits that are broken.

The project teaches two ideas that reach far beyond digital logic: representing a design as data (a netlist), and evaluating a dependency graph in topological order. By the end you will have simulated a full adder, checked it against ordinary addition, built an n-bit ripple-carry adder automatically, and measured its longest path.

Step 1: represent the circuit as a netlist

A circuit is a set of gates connected by named wires. The simplest data structure is a table with one row per gate: which wire does it drive, what kind of gate is it, and which wires does it read? That table is called a netlist.

What the simulator needs

Gate library AND, OR, NOT, NAND, NOR, XOR, XNOR.
Netlist One row per gate, naming its wires.
Ordering Evaluate a gate after its inputs.
Reporting Print results as a truth table.

Four small pieces make a complete simulator.

1 / 2

Every wire is driven by exactly one source: either a primary input or the output of one gate. So we can store the netlist as a dictionary keyed by the driven wire, with the gate type and its input wires as the value. The gate library is another dictionary that maps each gate name to a Python function. Gates like AND, OR and XOR accept any number of inputs.

Step 2: evaluate in the right order

You cannot compute a gate until its inputs are known. In a full adder, the final sum gate needs the result of an earlier XOR, which in turn needs the primary inputs. If we evaluate gates in the order they were written, a netlist that lists them out of order will break.

The fix is a topological sort: order the gates so that every gate comes after the gates that feed it. The code uses a depth-first search. To order a wire, first order all its sources, then add the wire itself. The search also detects two kinds of mistakes:

  • A wire that nobody drives (a typo in a name) is reported as having no driver.
  • A feedback loop, where a gate depends on itself through other gates, is reported as an error. Circuits with feedback, like the SR latch, need a different, iterative simulation. Our simple simulator is for purely combinational circuits.

The first program defines the simulator and builds a full adder. The gates are added in a deliberately shuffled order, and the simulator sorts them out.

Python A netlist simulator and a full adder

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The evaluation order starts with the gates that read only primary inputs (ab and x), then the gate that needs x and cin (xc), then the outputs. The truth table is the familiar one from Half Adders and Full Adders: for example the row 1 1 1 gives sum 1 and carry-out 1, because 1 + 1 + 1 = 3 = 11 in binary.

Step 3: read netlists from text

Hand-written Python calls are tedious. Real tools read a text file. The next version adds a small parser: one gate per line, in the form output GATE input input ..., with # starting a comment. Because the netlist is now just text, you can paste, edit and share it. The program also checks the adder automatically against Python's integer addition, and shows three kinds of broken input.

Python Parsing netlist text and catching errors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking a circuit against a trusted reference model, as the program does here, is the main way real hardware is verified. If you had wired one gate wrongly, ok would be False. The three broken examples show why a simulator should validate the design before running it: a typo or a loop is far easier to understand as a clear message than as a strange output.

Step 4: generate big circuits with code

Because circuits are data, a program can build them. The function below creates an n-bit ripple-carry adder by repeating the full-adder pattern for each bit and chaining the carries. It then does two things no hand-drawn diagram could do quickly: test all 256 input pairs of the 4-bit version, and measure the depth of each circuit, the number of gates on the longest path from an input to an output. Depth is a rough measure of delay, since each gate adds time.

Python An n-bit adder built by code and timed by depth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 4-bit adder uses 20 gates (5 per bit), passes all 256 checks, and has a longest path of 9 gates. The depth grows by 2 for every extra bit: 3, 5, 9, 17 for 1, 2, 4 and 8 bits. That is the weakness of ripple-carry design: the carry must pass through one AND and one OR per bit, so doubling the width doubles the delay. It is exactly the problem that carry-lookahead adders solve.

Ideas to extend the project

  • Gate delays. Give each gate type its own delay and compute the arrival time of each wire, not just the depth. This is the beginning of static timing analysis.
  • Fan-out count. Count how many gates read each wire. High fan-out slows a real signal down.
  • Logic optimization. Add a pass that finds duplicate gates (same type and same inputs) and merges them.
  • Equivalence checking. Write a function that tests two circuits against every input and reports a counterexample. Use it to prove that your NAND-only adder equals your normal one.
  • Sequential circuits. Add a D flip-flop element and a clock loop. The combinational evaluation stays the same, and registers update between rounds, just like the clocked models in earlier lessons.
  • Exporting. Print the netlist as Verilog (see Hardware Description Languages): each row becomes an assign statement.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a netlist describe?

    A netlist lists the components (here, gates) and the named wires connecting their inputs and outputs. It carries the structure of the circuit and nothing physical.
  2. 2. Why must the simulator sort gates in topological order?

    Each gate reads the values of its input wires. If any of them are not computed yet, the gate cannot produce a correct output, so every gate must come after its sources.
  3. 3. What does the simulator report for a gate whose output feeds back to its own input chain?

    A purely combinational evaluation order does not exist when a gate depends on itself. Memory circuits need an iterative approach that repeats until the outputs settle.
  4. 4. In the n-bit ripple adder, why does the depth grow by 2 gates per added bit?

    The carry chain c(i+1) = g(i) OR (x(i) AND c(i)) passes through an AND and an OR per bit, so the longest path lengthens by two gates each time the width grows by one.

Summary

  • A netlist stores a circuit as data: for each wire, the gate that drives it and the wires that gate reads.
  • A topological sort orders the gates so each one is evaluated after its inputs, and a depth-first search also finds missing drivers and feedback loops.
  • Reading the netlist from plain text makes circuits easy to write, share and generate by code.
  • Simulating every input row and comparing with a reference model (here, integer addition) is how a design is verified.
  • Depth (longest path in gates) is a first estimate of delay, and it shows why ripple-carry adders get slow as they grow.

Next: Project: Vending Machine Controller.