Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 67 ยท Projects

Project: A Gate-Level Logic Simulator

Write a netlist simulator that uses only NAND gates, then build NOT, AND, OR, XOR, a ripple-carry adder, latches, a register and a counter from it.

Every processor you have studied in this track, however complicated, is made of gates wired together. This last project goes to the bottom of the stack. You will write a small gate-level logic simulator, then use only one kind of gate, the NAND, to build everything above it: the other logic gates, an adder, memory, a register, and a counter that counts clock cycles.

It uses ideas from Logic Gates and Boolean Algebra, Combinational Circuits, Latches, Flip-Flops and Registers and Building an ALU. Because NAND is a universal gate, nothing else is needed: you will see with your own eyes that a computer can be made from a single gate type.

The design

A circuit is a netlist: a list of gates and the named wires, called nets, that connect them. Our simulator has exactly one kind of gate, out = NAND(a, b), and a few rules:

  • A net that no gate drives is an input. You set its value (0 or 1) from the outside.
  • Every gate has two input nets and one output net. Its output is 0 only when both inputs are 1.
  • To simulate, sweep over all gates, recompute each output from the current values of its inputs, and repeat until a whole sweep changes nothing. At that point the circuit has settled. A circuit that never settles is oscillating, and the simulator raises an error.
  • A net may be used as a gate input before the gate that drives it is created. That is how feedback loops are written, and feedback is what makes memory possible.

This is a zero-delay model: it computes the stable state and ignores how long signals take to travel. Real timing analysis, glitches and propagation delay are beyond it, but the settled values are exactly what a real circuit would show once its signals have stopped changing.

flowchart TD
  N["NAND gate"] --> G["NOT, AND, OR, XOR"]
  G --> HA["Half adder"]
  HA --> FA["Full adder"]
  FA --> RA["Ripple-carry adder"]
  N --> SR["SR latch<br/>(feedback)"]
  SR --> DL["D latch"]
  DL --> FF["D flip-flop"]
  FF --> REG["Register"]
  REG --> CNT["Counter<br/>(register + adder)"]
  RA -.->|"same ideas"| CNT

Everything in this project is stacked on the single NAND gate; the left branch computes, the right branch remembers.

Step 1: the simulator and the other gates

The Circuit class holds the gate list and the value of every net. The method nand adds a gate (creating a fresh output net name if you do not give one), set assigns input values, and settle runs the sweeps. The last helper, depth, measures the longest chain of gates leading to a net; you will use it to compare adder speeds.

Then come the building blocks, each a small function that adds gates to a circuit and returns its output net:

  • NOT a: NAND(a, a), one gate. With both inputs equal, the NAND is simply an inverter.
  • AND: a NAND followed by a NOT, two gates.
  • OR: by De Morgan's law, a OR b = NAND(NOT a, NOT b), three gates.
  • XOR: four NAND gates, using the first NAND's output twice.

The program builds each one, runs its truth table, and verifies the results against Python's own &, | and ^ operators. It also checks De Morgan's law on actual gates.

Python Every gate from NAND alone

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 gate counts (1, 2, 3 and 4) show the real price of the universality of NAND. A hardware designer who has AND, OR and XOR cells would use them; the simulator is stricter on purpose. The XOR is the clever one: the first gate computes m = NAND(a, b), and the two middle gates each compare one input with m. When a and b are equal, both middle gates output 1 and the final NAND outputs 0; when they differ, exactly one middle gate outputs 0 and the final NAND outputs 1.

Step 2: build an adder

Arithmetic is the first thing a computer needs. A half adder adds two bits: the sum is the XOR of the inputs and the carry is the AND. A full adder adds three bits (two operands and an incoming carry) by chaining two half adders and ORing their carries. A ripple-carry adder chains one full adder per bit, passing the carry from the least significant bit to the next, exactly as you add numbers by hand.

The program below builds a 4-bit adder (inputs a0..a3, b0..b3 and cin) and tests it three ways: three sample sums, an exhaustive test of all 256 pairs of 4-bit numbers against Python's +, and a scaling table that builds adders of 1 to 32 bits and reports their gate count and the number of gates on the longest path.

Python A ripple-carry adder from 60 NAND gates

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 60 NAND gates and agrees with Python for every one of the 256 input pairs, so it is not merely "probably right": it was tested on its entire input space. That is a luxury of small hardware.

The scaling table shows the key weakness of the ripple design. The gate count grows linearly (15 per bit), but so does the longest path: 7 gates for one bit, then 4 more for every additional bit, reaching 131 gate delays at 32 bits. The carry has to ripple through every stage before the top sum bit is correct, so a wider adder is a slower adder. This is why real ALUs use carry-lookahead logic that computes carries in parallel, as discussed in Building an ALU. It is also why the clock period of a CPU is set by its longest path.

Our full adder uses 15 gates because we built it mechanically from AND, OR and XOR. A hand-optimized NAND full adder needs only 9. Finding the smaller design is a good exercise.

Step 3: memory from feedback

All the circuits so far are combinational: the output depends only on the current inputs. Memory needs the opposite, an output that depends on history. The trick is feedback: wire gate outputs back into gate inputs.

Two cross-coupled NAND gates form an SR latch. Each gate's output feeds the other's input. With both inputs inactive (1), the loop keeps whatever state it has: that is the stored bit. Pulling the set input to 0 forces q to 1; pulling reset to 0 forces it to 0. (The inputs are active low, because a NAND is only influenced by a 0.)

Two more gates in front of the latch gate its inputs with an enable signal and give a D latch: while the enable is 1 the latch follows the data input d, and while it is 0 the latch holds its value. A latch that follows its input is called transparent, and that is a problem for building processors: a value could race around a loop several times in one clock phase. The fix is the master-slave D flip-flop: two latches in series with opposite enables. The master is transparent while the clock is low and the slave while the clock is high, so the output can only change just after the clock rises, and it takes whatever d was at that moment.

flowchart LR
  D["d"] --> M["Master latch<br/>transparent when clk = 0"]
  M --> S["Slave latch<br/>transparent when clk = 1"]
  S --> Q["q"]
  C["clk"] --> NC["NOT"]
  NC --> M
  C --> S

A master-slave flip-flop: while the clock is low the master collects d; when it rises the master freezes and the slave passes that value to q.

The next program builds all of these. It shows the SR latch being set, held, reset and held. It then builds a 4-bit register from four flip-flops sharing one clock and tests the key property: the output changes at the clock edge, and later changes of d while the clock is high have no effect. Finally it combines a register with an incrementer made from XOR and AND gates (the half-adder chain from before, with a carry-in of 1) plus a synchronous clear, creating a 4-bit counter, and runs 18 clock cycles.

Python Latches, a register and a counter

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 SR latch table shows memory in action: after "set" the output is 1, and it stays 1 when the inputs return to the hold state. After "reset" it stays 0. The same inputs (s_n=1 r_n=1) give different outputs depending on the past; that is what makes it sequential.

The register's first "before edge" value is 15, which is an arbitrary power-on state. In the simulator it depends on how the loop happened to settle from all-zero starting values, and in real hardware it depends on tiny electrical differences. Flip-flops start in unknown states, which is why real circuits have a reset signal. The counter handles it with a synchronous clear input that forces zero on the first clock edge. After that the counter prints 1, 2, 3, ... up to 15 and wraps to 0, exactly like a 4-bit register. The whole counter is only 72 NAND gates.

Because every flip-flop here is edge-triggered, the counter can feed its own output back into its own input, through the incrementer, without chaos. The flip-flop reads d at the clock edge and then ignores it until the next edge. With plain latches the same loop would race.

What you have built, and where to go next

In roughly 100 lines you have a working digital logic lab. Compare it with the rest of the track: the ALU's adder is Step 2, the registers of the CPU are Step 3, and the counter is the heart of a program counter. A complete CPU adds multiplexers, a decoder for opcodes and a larger memory, all expressible with the same gates. Ideas for extending the project:

  1. Build a multiplexer and decoder from NAND gates and use them for a register file with a write-enable.
  2. Add a subtractor and flags: invert b, set cin to 1 (two's complement), and compute the zero, negative and overflow flags.
  3. Optimize the full adder down to 9 NAND gates and compare the depth with depth().
  4. Add carry-lookahead and measure how much shorter the longest path becomes.
  5. Write a netlist parser so that circuits can be described as text like w3 = NAND a b and loaded from a string.
  6. Join the projects: connect the counter to a small ROM as a program counter and drive the mini CPU from it.

When a circuit misbehaves, test its pieces separately with the exhaustive approach used here. Combinational blocks with a few inputs can be checked on all inputs; sequential blocks can be checked by printing the state after every clock edge.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can a computer be built from NAND gates alone?

    Any Boolean function can be built from NAND gates alone, which is why the simulator needs only one gate type.
  2. 2. How is a NOT gate built from a NAND gate?

    NAND(a, a) is 0 when a is 1 and 1 when a is 0, which is NOT a.
  3. 3. What gives the SR latch the ability to remember a bit?

    The cross-coupled loop has two stable states, so it keeps its value even when the inputs return to the inactive state.
  4. 4. Why does a ripple-carry adder get slower as it gets wider?

    In the simulator the longest path grows by 4 gates per bit, since the top sum bit is valid only after the carry has rippled through all lower bits.
  5. 5. Why is a master-slave flip-flop used instead of a single D latch in a register?

    A transparent latch lets changes race through; two latches with opposite enables make a value change only just after the clock rises.

Summary

  • A gate-level simulator needs only a netlist, a value for each net, and a loop that recomputes gates until nothing changes.
  • NAND is universal: NOT, AND, OR and XOR cost 1, 2, 3 and 4 NAND gates here, and De Morgan's law can be checked directly on them.
  • Half adders, full adders and a ripple-carry adder follow directly; the 4-bit adder was verified exhaustively against Python.
  • Ripple-carry gate count and delay both grow linearly with width, which motivates carry-lookahead.
  • Feedback creates memory: two cross-coupled NAND gates are an SR latch, and a pair of gated latches is an edge-triggered D flip-flop.
  • A register is flip-flops with a shared clock, a counter is a register plus an incrementer, and real hardware needs a reset because flip-flops power on in an unknown state.

You have now built the stack from gate to program. Test your skills with Practice: Data Representation and Digital Logic.