NAND Fizzbuzz: Part 2

Published on November 27, 2020

In Part 1 we built a discrete time simulation of NAND gates and “Buffer” devices and were able to get as far as printing the alphabet. I promised at the end we’d introduce input devices, but this post will instead set a more modest goal of printing Hello World.

Before we get back to the action there’s going to be some changes for anyone who’s following along, so I need to take some time to explain these changes and why they’re necessary.

Moving to Deno

To continue following along you’re going to need to install Deno, “A secure runtime for Javascript and Typescript”. Although I never explicitly said it, Part 1 was meant to be run in NodeJS but there’s some limitations on NodeJS that I think warrant Deno’s use instead.

First, there’s no easy way (that I can find) to synchronously get input in node. In Deno I can do,

const buffer = new Int8Array(1);
while (!Deno.stdin.readSync(buffer));

and this will block until we get input. I had already developed an asynchronous solution to this problem with Node but it added too much complexity for what’s just a fun series of blog posts.

Next, being able to write some things in Typescript is nice. These posts will still be in Javascript exclusively but I can write the imported code in Typescript and everything just works as it should.

And last, it’s easier to follow along. Before, I was linking to which is a great service to painlessly follow along in your browser. But since my last post they implemented some changes that force you to create an account which adds some friction where I think it’s now easier to just download deno. The mix of “secure by default” and allowing HTTP imports means I can show you a code snippet like this,

import { go } from "";

and you don’t have to manually download additional files or worry that hello.ts is doing anything besides console I/O.

I still recommend if you don’t want to download anything. They have Deno support in beta, you just have to create an account.

Other Changes

With the move to Deno some sloppy choices made in Part 1 are coming back to bite. Instead of trudging along with them I decided it’s worth making changes to what was developed in part 1.

First, since things are now being spread out across multiple files, the device array will no longer be a global. All our mk functions now take the device array as their first argument.

function mkNand2(ds, a, b) {
    const device = new NANDDevice(a, b);
    return device;

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

function mkAnd2(ds, a, b) {
    return mkNot(ds, mkNand2(ds, a, b));

OutputDevice is also different now. It outputs raw bytes instead of the lower 256 characters of unicode, and takes two extra inputs for enb (if it should output anything, regardless of clk) and mode (if it should exit).

Here’s how you could implement a simpler version of yes.

import {
    HIGH, LOW,
    mkClock, mkOutputDevice, num2Bus, runDevices,
} from "";

const ds = [];
const clk = mkClock(ds, 5);

    { clk, enb: HIGH, mode: LOW,
      outs: num2Bus("y".charCodeAt(0), 8) }

for (;;) runDevices(ds);
$ deno run | head -c100
error: Uncaught BrokenPipe: Broken pipe (os error 32) 
    at unwrapResponse (deno:cli/rt/10_dispatch_minimal.js:59:13)
    at sendSync (deno:cli/rt/10_dispatch_minimal.js:106:12)
    at writeSync (deno:cli/rt/12_io.js:108:20)
    at Stdout.writeSync (deno:cli/rt/30_files.js:144:14)
    at OutputDevice.flip (devices.ts:101:29)
    at runDevices (helpers.ts:24:16)
    at yes.ts:20:10

Since we’re not trying to create a fully-fledged interface for streams the fact that this is able to produce something half-useful is pretty cool. If you change mode to HIGH this will become a program that immediately exits with the return code specified by outs.


We’ll get back into continuing the simulation by asking a question: what’s the initial output of a flip flop? We can test this by connecting its input to its output and seeing where it ends up.

 import {
    mkBuffer, mkClock, mkDFlipFlop,
    printNodes, runDevices,
} from "";

 const ds = [];
 const clk = mkClock(ds, 10);

 const buffer = mkBuffer(ds)
 const ff = mkDFlipFlop(ds, buffer, clk);

 for (let i=0;i<30;i++) {
     printNodes(i, ff);
$ deno run
000> 0   010> 0   020> 0
001> 0   011> 0   021> 0
002> 1   012> 0   022> 0
003> 0   013> 0   023> 0
004> 0   014> 0   024> 0
005> 1   015> 0   025> 0
006> 0   016> 0   026> 0
007> 0   017> 0   027> 0
008> 0   018> 0   028> 0
009> 0   019> 0   029> 0

This shouldn’t be surprising since all our NANDs are initialized to zero. But this is actually more of a trick question. Real flip flops don’t have an “initial” state unless we place some additional logic on it. Instead we need to have some sort of signal to tell it we’re “initializing”. So we aren’t going to rely on this behaviour. Instead, we’ll create a node, which we’ll call nrst in our circuit, that remains low until the end of the first clock cycle.

function mkNReset(ds, delay) {
    return mkDelay(ds, delay, HIGH);

Like our initially low flip flops this also exploits the fact all our nodes except HIGH are initially low. And it’s worth reiterating our BufferDevice is really a fiction that we’ve been using to create devices we’d otherwise need to create different simulated devices for. For example, accurate clocks usually require crystal oscillators (although “ring oscillators” exist they aren’t that accurate), and real buffers are usually two NOT gates back to back, which would have very different behaviour than BufferDevice. In the spirit of approximating how actual circuits work we’ll hew towards what would be synthesizable.

Hot State Encoding

We’re going to model our message printing system as a state machine, where a bank of flip flops will represent the current state. From that we can calculate the output.

To print Hello World!, we’ll need to iterate through 13 states: one for each character and another for exiting. At minimum this requires 4 bits which we could connect to an adder and count up for each state. But this would make calculating the 9 output bits (8 outs and 1 mode which will be high in the last state to exit) challenging.

Instead, we’re going to use “Hot State Encoding”, which just means that every state gets its own flip flop. We’re only in a valid state when exactly one flip flop is high, and when doing calculations we can ignore invalid states. This makes calculating the next state trivial: if flip flop corresponding to the previous state is high then we should be high (unless nrst is low, in which case we either want to be low or high depending on if we represent the first state).

import {
    mkAnd2, mkClock, mkDFlipFlop, mkNot, mkNReset,
    printNodes, runDevices
} from "";

const ds = [];
const clk = mkClock(ds, 25);
const nrst = mkNReset(ds, 55);

const flipflops = [];
flipflops[0] = mkDFlipFlop(ds, mkNot(ds, nrst), clk);
for (let i=1;i<13;i++) {
    flipflops[i] = mkDFlipFlop(
        mkAnd2(ds, nrst, flipflops[i-1]),

for (let i=0;i<50*16;i++) {
    if (i%50 === 0)
        printNodes(i, nrst, ...flipflops);
$ deno run
000> 00000000000000
050> 00000000000000
100> 11000000000000
150> 10100000000000
200> 10010000000000
250> 10001000000000
300> 10000100000000
350> 10000010000000
400> 10000001000000
450> 10000000100000
500> 10000000010000
550> 10000000001000
600> 10000000000100
650> 10000000000010
700> 10000000000001
750> 10000000000000

This also makes our job generating the output very easy: for each output bit we just need to check if we’re in any of the states that should be high. Since each state is a flip flop this becomes an OR gate.

Creating a ROM

We need to create some circuit capable of storing and giving back what to output. Put another way, we need to convert the state into an arbitrary pre-defined output of our choosing. Put another way, we need some sort of Read Only Memory, or ROM, of what we want to output that’s compatible with how we encoded the state.

For our Hello World! output we need the output to be 9 bits wide, and there’s 13 possible outputs. To be compatible with hot state encoding, we have 13 lines as input and don’t make guarantees about the output if more than one input line is high.

We’re going to write a more general mkRom, but let’s first try an example with trying to design the boolean equation for OUT0 given I0...I12. For this bit, the outputs for each state in order need to be 0100101100010.

The easy way to generate the output is to just ask: are we in any states where we should be HIGH? So our equation just becomes OUT0 = I1+I4+I6+I7+I11 (where + means OR).

We can write a mkRom that generalizes this process for any data, but first we need to take a detour and develop multi-input gates.

Multi-Input Gates

Since NANDs form the base of all our logic, we’ll start with them.

This isn’t too bad as long as we rely on our good friend recursion. The base cases are easy: 2 inputs just use a 2-input gate, 1-input is the equivalent of not (the and in not and disappears). The NAND of nothing is a little more tricky: AND of nothing is vacuously true so NAND of nothing must be false.

When we recurse we make use of the associativity of AND by combining their NOTs. Note NAND is not associative: NAND(1, NAND(1,0)) = 0 != NAND(NAND(1,1), 0) = 1, and NAND(A, B, C, ...) = NOT(AND(A, B, C, ...)) = NOT(AND(A, AND(B, AND(C, ...)))) != NAND(A, NAND(B, NAND(C, ...))).

function mkNand(ds, nodes) {
    if (nodes.length === 0) {
        return LOW;
    } else if (nodes.length === 1) {
        return mkNot(ds, nodes[0]);
    } else if (nodes.length === 2) {
        return mkNand2(ds, nodes[0], nodes[1]);
    } else {
        const middle = Math.floor(nodes.length / 2);
        const left = mkNand(ds, nodes.slice(0, middle));
        const right = mkNand(ds, nodes.slice(middle));
        return mkNand2(ds, mkNot(ds, left), mkNot(ds, right));

It also helps to think of a multi-input NAND in terms of a multi-input AND, and where we just NOT the outputs. Since AND is associative, it’s easier to reason about.

Here’s mkAnd and mkOr, the latter of which uses De Morgan’s law. If you have paper and pencil you should be able to convince yourself these are correct.

function mkAnd(ds, nodes) {
    if (nodes.length === 0) {
        return HIGH;
    } else if (nodes.length === 1) {
        return nodes[0];
    } else {
        return mkNot(ds, mkNand(ds, nodes));

function mkOr(ds, nodes) {
    return mkNand(ds, => mkNot(ds, n)));

Back to ROM

Our mkRom is going to take it’s data a 2D array of booleans, where array[i][j] is the data to output when line i is high on output j.

function mkRom(ds, data, inp) {
    const outputs = [];
    for (let i=0;i<data[0].length;i++) {
        const trueNodes = [];
        for (let j=0;j<data.length;data++) {
            if (data[j][i]) {
        outputs.push(mkOr(ds, trueNodes));
    return outputs;

As promised we just have to build up the the array of nodes that are true for each input and let mkOr do the rest of the work.

Hello, World!

We can test our ROM by putting everything together and seeing if we can print Hello World!

import {
    mkAnd2, mkClock, mkDFlipFlop, mkNot, mkNReset, mkRom, mkOutputDevice,
    runDevices, num2Bus, printNodes,
} from "";

const ds = [];
const clk = mkClock(ds, 25);
const nrst = mkNReset(ds, 55);

const message = "Hello World!";
const messageData = [];
for (let i=0;i<message.length;i++) {
    // Since num2Bus returns constant nodes, we need to grab `.value`
    // to convert it to booleans
    const value = num2Bus(message.charCodeAt(i), 8).map(n => n.value);
    value.push(0); // MODE
// Exit with code 0
    ...num2Bus(0, 8).map(n => n.value),

const flipflops = [];
flipflops[0] = mkDFlipFlop(ds, mkNot(ds, nrst), clk);
for (let i=1;i<messageData.length;i++) {
    flipflops[i] = mkDFlipFlop(
        mkAnd2(ds, nrst, flipflops[i-1]),

const rom = mkRom(ds, messageData, flipflops);

        outs: rom.slice(0, 8),
        enb: nrst,
        mode: rom[8]

for (;;) runDevices(ds);
$ deno run
Hello World!

I won’t promise anything for next time, since I still haven’t introduced InputDevice which I promised in part 1! If you’ve been reading along and enjoying the series, I don’t keep user comments on this blog, but feel free to shoot me an email at