NAND Fizzbuzz: Part 1

Published on February 20, 2020

A NAND gate is a boolean function that is false if both inputs are true, and true otherwise. Since a NAND gate is functionally complete any logic function can be created by connecting together 2-input NAND gates. On digital chips NAND gates can be used for storage, making complicated state machines such as computers. Starting with a basic simulation let’s build the logic of FizzBuzz with NAND gates.

Note: Some of the diagrams in this article require monospace box drawing characters, which I’m aware some phones (and maybe some computers) don’t have. If these aren’t rending correctly you can try viewing on a desktop. Otherwise, the article should still be understandable without them.

Our simulation will consist of four devices, the first of which will be a 2-input NAND gate that will handle all logic. All our devices will have 2 functions: calculate() and flip(), and the implementation of NAND will be as follows.

class NANDDevice {
    constructor(a, b) {
        this.a = a;
        this.b = b;
        this.value = false;
        this.next = false;
    }

    calculate() {
        this.next = !(this.a.value && this.b.value);
    }

    flip() {
        this.value = this.next;
    }
}

We will keep track of our devices in an array, and every tick will call calculate on all devices, then flip on all devices.

let time = 0;
let devices = [];

function tick() {
    for (let device of devices) {
        device.calculate();
    }

    for (let device of devices) {
        device.flip();
    }

    time++;
}

Calculating the value before setting value ensures the value of a device at time t will only depend on its input’s values from time t-1.

We’ll create NAND gates via a helper function.

function mkNand2(a, b) {
    let device = new NANDDevice(a, b);
    devices.push(device);
    return device;
}

We also create two constant nodes corresponding to the two states. A node is just something with a true or false value at a given time.

const HIGH = { value: true };
const LOW  = { value: false };

And finally, a helper function to print nodes.

function printNodes(...nodes) {
    let timeStr = `${time}`;
    while (timeStr.length < 3) timeStr = "0" + timeStr;
    let nodesStr = "";
    for (let node of nodes) nodesStr += node.value ? "1" : "0";
    console.log(`${timeStr}> ${nodesStr}`);
}

With this setup let’s write a program to calculate the truth table of NAND.

let nand00 = mkNand2(LOW, LOW);
let nand01 = mkNand2(LOW, HIGH);
let nand10 = mkNand2(HIGH, LOW);
let nand11 = mkNand2(HIGH, HIGH);

tick();
printNodes(nand00, nand01, nand10, nand11);
001> 1110

Indeed this is what we expect. While we’re at it let’s also try to develop the logic for NOT, which we can do by setting one input to high. We can than put this together with a normal NAND, to get AND.

function mkNot(a) {
    return mkNand2(a, HIGH);
}

function mkAnd2(a, b) {
    return mkNot(mkNand2(a, b));
}
let and00 = mkAnd2(LOW, LOW);
let and01 = mkAnd2(LOW, HIGH);
let and10 = mkAnd2(HIGH, LOW);
let and11 = mkAnd2(HIGH, HIGH);

printNodes(and00, and01, and10, and11);
for (let i=0;i<4;i++) {
    tick();
    printNodes(and00, and01, and10, and11);
}
000> 0000
001> 1111
002> 0001
003> 0001
004> 0001

Although the correct output is 0001 we don’t get that until time 2 since we need to propagate the input through two devices. Just like real circuits these NAND gates have a propagation delay.

The propagation delay means if we connect a NOT gate to itself we should be able to get an oscillating signal.

We won’t do this directly though. Instead we’re going to introduce our second device, a buffer.

class BufferDevice {
    constructor() {
        this.source = null;
        this.value = false;
        this.next = false;
    }

    setSource(node) {
        this.source = node;
    }

    calculate() {
        this.next = this.source.value;
    }

    flip() {
        this.value = this.next;
    }
}

function mkBuffer() {
    let device = new BufferDevice();
    devices.push(device);
    return device;
}

To be clear a buffer doesn’t do any logic, it just copies the input to the output, adding a one-tick delay. This is similar to what would happen if we just chained two NOTs together but having this extra buffer device is helpful for two reasons: it only adds one tick so we can get accurate delays and it lets us set the source after it’s constructed which will help make our code cleaner.

For instance, this is what our NOT oscillator looks like.

          │╲
          │ ╲
        ┌─┤  │()┐ not
        │ │ ╱   │
        │ │╱    │
        │       │
        │       │
        │   ╱│  │
        │  ╱ │  │
 buffer └─┤  │──┘
           ╲ │
            ╲│
let buffer = mkBuffer();
let not = mkNot(buffer);
buffer.setSource(not);
printNodes(buffer, not);
000> 00
001> 01
002> 11
003> 10
004> 00
005> 01
006> 11
007> 10
008> 00
009> 01

As we might imagine it create something of a loop: 00, 01, 11, 10, 00, etc. Since it takes two ticks for the not’s output to get back to its input the period is four. Either node looked at by itself acts as a clock with the same period.

As promised, our buffer allows us to add arbitrarily long delays, which means we can make arbitrarily long clocks.

function mkDelay(input, ticks) {
    let output = input;
    for (let i=0;i<ticks;i++) {
        let buffer = mkBuffer();
        buffer.setSource(output);
        output = buffer;
    }
    return output;
}

function mkClock(duty) {
    let buffer = mkBuffer();
    let not = mkNot(buffer);
    buffer.setSource(mkDelay(not, duty - 2));
    return not;
}

The duty parameter of mkClock refers to the time the clock stays high for, which is half the entire cycle. Since all nodes initially start at 0 (except the HIGH constant) the clock will be low at time 0 and immediately jump to high at time 1.

let clk = mkClock(3);
printNodes(clk);
000> 0
001> 1
002> 1
003> 1
004> 0
005> 0
006> 0
007> 1
008> 1
009> 1

I said earlier we can also use NANDs to store data. If we connect two NOTs back to back we get a bistable circuit such that there are two stable states, and once it’s in one of those states it’ll stay there forever.

  |\
/-||()\ B
| |/  |
\-----|-\
      | |
/-----/ |
| |\    |
\-||()--/ A
  |/

In the above image if A is high B will be low, and if B is low A will be high. The opposite is true if A is low.

Unfortunately, this isn’t that useful because we have no way to control the current state. But recall we build NOT gates by just setting one NAND input high. From the perspective of the other input, the NAND becomes a NOT gate. If we were to permanently set one input low instead, the output would be a constant high.

       |--\
NR ----|   \
       |    |()*---- Q
     /-|   /   |
     | |--/    |
     \-----------\
               | |
     /---------/ |
     | |--\      |
     \-|   \     |
       |    |()--/
NS ----|   /
       |--/

If we expose these as inputs, we successfully create a latch. When both inputs are high the latch simply stores its previous value. Bring one input low and depending on which one the output goes low or high. Specifically this is called an SR latch, since NS can be used to set (bring high) and NR can be used to reset (bring low) the output. Since these inputs are active low, for instance we set when NS is low and do nothing when NS and NR are high, we call the inputs NS and NR instead of simply S and R.

function mkSRLatch(ns, nr) {
    let q = mkBuffer();
    let rNand = mkNand2(q, nr);
    let sNand = mkNand2(rNand, ns);
    q.setSource(sNand);
    return q;
}

We can test our latch by consecutively giving it the four possible inputs. We’ll generate these inputs with two clocks.

let ns = mkClock(5);
let nr = mkClock(10);
let q = mkSRLatch(ns, nr);
printNodes(ns, nr, q);
000> 000     010> 011
001> 110     011> 101
002> 111     012> 101
003> 110     013> 101
004> 110     014> 100
005> 111     015> 100
006> 010     016> 000
007> 010     017> 000
008> 011     018> 001
009> 011     019> 001

We can ignore the output at the beginning (we’ll get back to that), and just focus on the times when only nr or ns are high. At time 6, ns is low and nr is high meaning we want to set q. A couple ticks later at time 8 we get our wish. Then at time 11 ns goes high and nr goes low, causing q to dutifully go low again at time 14. The time discrepancy, a 2 versus 3 tick delay has to do with how we positioned the buffer.

Although it may look like q changes back to high when both are low, if kept running the simulation we’d find q actually oscillates when this is the case. In general we want to avoid ns and nr both going low. We can fix this by adding more gates to convert the SR latch into a D latch.

A D latch has two inputs: d and enb (enable). When enable is low we maintain the same output, regardless of the value of d. If enable is high, we set the output to the current value of d. We can create this with the introduction of three gates.

function mkDLatch(d, enb) {
    let ns = mkNand2(d, enb);
    let nr = mkNand2(mkNot(d), enb);
    return mkSRLatch(ns, nr);
}
let enb = mkClock(8);
let d = mkClock(16);
let q = mkDLatch(d, enb);
printNodes(enb, d, q);
00> 000  08> 111  16> 011  24> 100
01> 110  09> 011  17> 101  25> 000
02> 111  10> 011  18> 101  26> 000
03> 110  11> 011  19> 101  27> 000
04> 111  12> 011  20> 101  28> 000
05> 111  13> 011  21> 101  29> 000
06> 111  14> 011  22> 100  30> 000
07> 111  15> 011  23> 100  31> 000

Now that we have storage and logic we should be able to start making state machines. For instance, let’s try to create an 8-bit counter.

In order to make a counter we need to switch gears a little and make an adder. For simplicity we’ll stick with the ripple carry adder. A ripple carry adder is formed by chaining together full adders, which adds 3 1-bit inputs into a 2-bit sum. Chaining the high bit of the output (Cout) into the next Cin input lets us carry as though we were carrying digits in paper addition.

ABC│CS
╶──┼─╴
000│00
001│01
010│01
011│10
100│01
101│10
110│10
111│11
function mkFullAdder(a, b, cin) {
    // I'll leave showing this matches the
    // truth table as an excercise to the
    // reader
    let nand1 = mkNand2(a, b);
    let nand2 = mkNand2(a, nand1);
    let nand3 = mkNand2(nand1, b);
    let nand4 = mkNand2(nand2, nand3);
    let nand5 = mkNand2(nand4, cin);
    let nand6 = mkNand2(nand4, nand5);
    let nand7 = mkNand2(nand5, cin);
    let sum = mkNand2(nand6, nand7);
    let cout = mkNand2(nand5, nand1);
    return { sum, cout };
}

function mkAdder(as, bs, cin) {
    let ss = [];
    let cout = cin;
    for (let i=0;i<as.length;i++) {
        let adder = mkFullAdder(as[i], bs[i], cout);
        ss.push(adder.sum);
        cout = adder.cout;
    }
    return { ss, cout };
}

As a convention I’ll call arrays of nodes busses and make their variable names plural by appending an s. Because it makes calculations simple, any bus that represents a number will be treated as big endian, so a[0] will always be the 1’s place for a. For an 8-bit bus a[7] will be the 128’s place.

let adder = mkAdder(
    [HIGH, HIGH, HIGH, LOW,  LOW, LOW],
    [LOW,  HIGH, LOW,  HIGH, LOW, LOW],
    LOW
);
printNodes(...adder.ss)
00000> 000000
00001> 111111
00002> 000000
00003> 111111
00004> 000000
00005> 101111
00006> 100000
00007> 100110
00008> 100000
00009> 100010
00010> 100010

Before continuing I’m going to introduce two helper functions. The first connects an array of buffers to a bus, and the second creates a constant bus representing the given number.

function connectBus(buffers, bus) {
    for (let i=0;i<buffers.length;i++) {
        buffers[i].setSource(bus[i]);
    }
}

function num2Bus(num, width) {
    let neg = num < 0 ? 1 : 0;
    if (neg) {
        num = -num - 1;
    }

    let out = [];
    for (let i=0;i<width;i++) {
        out.push( ((num&1)^neg) ? HIGH : LOW );
        num >>= 1;
    }

    return out;
}

Since we have the ability to create an adder and to store data we should be able to create a counter. Essentially we want a set of latches that every set period of time will have a value one more than the previous time.

As a first attempt, let’s hook a clock up to the enable inputs of some latches and loop the outputs through a counter.

let clk = mkClock(50);

let buffers = [];
let latches = [];
for (let i=0;i<8;i++) {
    buffers[i] = mkBuffer();
    latches[i] = mkDLatch(buffers[i], clk);
}

connectBus(
    buffers,
    mkAdder(
        latches,
        num2Bus(1, 8),
        LOW
    ).ss
);
printNodes(...latches);
00000> 00000000
00050> 00011000
00100> 00001100
00150> 11110110
00200> 11011111
00250> 00001111
00300> 01000111
00350> 11010011
00400> 11110011
00450> 01001111

There’s a few reasons we might suspect this doesn’t work. First, is it because we’re looking at the wrong times? The clock period is 100 ticks (we’re showing every 50). If we think about how we built the clock, these times correspond to just before the clock goes high and just before the clock goes low, which is reasonable to suspect which be the correct times to look at the output. You can try inspecting the latches at different times, but that’s not the problem.

Another concern we might have is if the clock is too slow to support the adder. It’s not exactly clear how fast the adder is from the code, but it’s certainly a lot of NAND gates. In fact, the worst case for the slowest output to show the correct value is 48 ticks. That’s slow, and even slower when you consider it needs to pass through the buffer and all the NANDs in each latch. But that’s still well within our 100 tick lock cycle and not the issue.

If you haven’t figure it out and are actively following along, I’d urge you to think a little more before continuing.

The problem is the adder is too fast for the latches. Because the latches are active for a full 50 ticks, we need to maintain the output from the adder until at least the end of the duty cycle. And while the slowest output takes 48 ticks, the fastest output, ss[0], only takes 4. Otherwise the next state goes straight through the latches, back into the adder and by the time the duty cycle ends we have the incomplete value of two states ahead, which is gibberish.

A (bad) solution is to add a 50 tick delay to the adder. This causes the latch to read the output 50 ticks in the past, back when the output of the latch was stable (ie enb low).

let clk = mkClock(50);

let buffers = [];
let latches = [];
for (let i=0;i<8;i++) {
    buffers[i] = mkBuffer();
    latches[i] = mkDelay(
        mkDLatch(buffers[i], clk),
        50
    );
}

connectBus(
    buffers,
    mkAdder(
        latches,
        num2Bus(1, 8),
        LOW
    ).ss
);
printNodes(...latches)
00000> 00000000
00050> 00000000
00100> 10000000
00150> 10000000
00200> 01000000
00250> 01000000
00300> 11000000
00350> 11000000
00400> 00100000
00450> 00100000

This works, but out solution leaves something to be desired. The adding of arbitrary delays in our circuit is error prone, wasteful (time-wise and gate-wise) and would be pretty difficult to fabricate if you ever wanted to turn this into a real circuit. Another solution is generate a clock with a smaller duty cycle, but this also has some of the same problems.

Our solution instead will be to replace the D latches with D flip flops.

          ┏━━━━━━━━━━━━┓      ┏━━━━━━━━━━━━┓ 
    ┌─────┨D           ┃  ┌───┨D           ┃
D ──┘     ┃      D    Q┠──┘   ┃      D    Q┠───── Q
          ┃    Latch   ┃      ┃    Latch   ┃   
CLK ─┬╴▶●─┨CLK         ┃   ┌──┨CLK         ┃
     │    ┗━━━━━━━━━━━━┛   │  ┗━━━━━━━━━━━━┛
     └─────────────────────┘

Note: ▶● is a NOT gate
function mkDFlipFlop(d, clk) {
    let nclk = mkNot(clk);
    let master = mkDLatch(d, nclk);
    let slave = mkDLatch(master, clk);
    return slave;
}

What we’ve built is two D latches with the slave latch input hooked up to the master output, and given inverted clocks. On both a high or low clk at least one of the latches isn’t enabled, so the output is generally stable. On a falling edge, when clk goes high to low, the master latch becomes enabled and the slave latch disabled, while reading the output from the master. On a rising edge the master reads the input and becomes disabled.

The way we characterize the function of the device is to say Q takes on the value of D any time there’s a rising clock edge and remains constant any other time. Of course there’s still some timing issues at play (these devices have setup an hold times just like real devices), but our clock cycle is comfortably long enough where we can ignore these.

let clk = mkClock(50);

let buffers = [];
let flipflops = [];
for (let i=0;i<8;i++) {
    buffers[i] = mkBuffer();
    flipflops[i] = mkDFlipFlop(buffers[i], clk);
}

connectBus(
    buffers,
    mkAdder(
        flipflops,
        num2Bus(1, 8),
        LOW
    ).ss
);
printNodes(...flipflops);
00000> 00000000
00050> 00000000
00100> 00000000
00150> 10000000
00200> 10000000
00250> 01000000
00300> 01000000
00350> 11000000
00400> 11000000
00450> 00100000

Although all we’ve done so far is create a counter we’ve shown NAND gates are enough to not only create arbitrary logic functions like addition, but to store data and change it in a synchronized way.

But we’re missing an important component in order to create FizzBuzz: output. Right now all our state is locked inside the circuit we’re just using a print function to peer inside. What we need to do is create some sort of interface to actually allow the circuit to print arbitrary characters. This interface will take the form of a new device.

class OutputDevice {
    constructor(outs, clk) {
        this.clkPrev = true;
        this.clk = clk;
        this.outs = outs;
        this.read = 0;
        this.put = false;
    }

    calculate() {
        this.put = this.clk.value && !this.clkPrev;
        this.read = 0;
        for (let i=0;i<8;i++) {
            if (this.outs[i].value) {
                this.read += 1 << i;
            }
        }
        this.clkPrev = this.clk.value;
    }

    flip() {
        if (this.put) {
            let c = String.fromCharCode(this.read);
            if (c === "\u0004") { // EOT
                process.exit();
            } else if (c !== "\0") {
                process.stdout.write(c);
            }
        }
    }
}

function mkOutputDevice(outs, clk) {
    let device = new OutputDevice(outs, clk);
    devices.push(device);
    return device;
}

Our OutputDevice works like so: if we’re at a positive clock edge and the value of the outs input is not all 0’s, print that unicode character. With the special case that if the character is EOT we print nothing and immediately exit.

(Note: specifically it can output the first 256 characters of unicode. The character encoding is a superset of ASCII, since they share the same first 128 characters.)

A simple example would be to try and exit the program as quickly as possible.

let clk = mkClock(2);
mkOutputDevice(
    num2Bus(4, 8),
    clk
);
printNodes(clk)
00000> 0
00001> 1
(program terminates)

A more complicated example would be to print the alphabet and exit.

let clk = mkClock(50);

let buffers = [];
let flipflops = [];
for (let i=0;i<5;i++) {
    buffers[i] = mkBuffer();
    flipflops[i] = mkDFlipFlop(buffers[i], clk);
}

connectBus(
    buffers,
    mkAdder(
        flipflops,
        num2Bus(1, 5),
        LOW
    ).ss
);

let print = mkNand2(
    mkAnd2(flipflops[0], flipflops[1]),
    mkAnd2(flipflops[3], flipflops[4])
);

mkOutputDevice(
    [
        mkAnd2(flipflops[0], print),
        mkAnd2(flipflops[1], print),
        mkNand2(mkNot(flipflops[2]), print),
        mkAnd2(flipflops[3], print),
        mkAnd2(flipflops[4], print),
        LOW,
        print,
        LOW
    ],
    clk
);
_@ABCDEFGHIJKLMNOPQRSTUVWXYZ

Close enough! In the next part I’ll use hot state encoding to print known strings in simpler way than just counting, and create an input device, which we’ll use to ask the user how many lines of FizzBuzz they want.

If you haven’t been following along and want to run the code I’ve posted everything on Repl.it where you can modify and run all these examples. All the helper functions are there, just copy and paste the last code block of each example into the // circuit section, and add the printNodes statement to the for loop.