NAND Fizzbuzz: Part 2
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 repl.it 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 "https://www.ericproberts.dev/extra/2020/hello.ts";
go();
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 repl.it 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);
ds.push(device);
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 "https://www.ericproberts.dev/extra/2020/nand_helpers_part2.ts";
const ds = [];
const clk = mkClock(ds, 5);
mkOutputDevice(
ds,
{ clk, enb: HIGH, mode: LOW,
outs: num2Bus("y".charCodeAt(0), 8) }
)
for (;;) runDevices(ds);
$ deno run https://www.ericproberts.dev/extra/2020/nand_yes.js | head -c100
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
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.
Reset
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 "https://www.ericproberts.dev/extra/2020/nand_helpers_part2.ts";
const ds = [];
const clk = mkClock(ds, 10);
const buffer = mkBuffer(ds)
const ff = mkDFlipFlop(ds, buffer, clk);
buffer.setSource(ff);
for (let i=0;i<30;i++) {
printNodes(i, ff);
runDevices(ds);
}
$ deno run https://www.ericproberts.dev/extra/2020/nand_test_ff_initial.js
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 "https://www.ericproberts.dev/extra/2020/nand_helpers_part2.ts";
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(
ds,
mkAnd2(ds, nrst, flipflops[i-1]),
clk
);
}
for (let i=0;i<50*16;i++) {
if (i%50 === 0)
printNodes(i, nrst, ...flipflops);
runDevices(ds);
}
$ deno run https://www.ericproberts.dev/extra/2020/nand_hotstate.js
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, nodes.map(n => 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]) {
trueNodes.push(inp[j]);
}
}
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 "https://www.ericproberts.dev/extra/2020/nand_helpers_part2.ts";
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
messageData.push(value);
}
// Exit with code 0
messageData.push([
...num2Bus(0, 8).map(n => n.value),
true,
]);
const flipflops = [];
flipflops[0] = mkDFlipFlop(ds, mkNot(ds, nrst), clk);
for (let i=1;i<messageData.length;i++) {
flipflops[i] = mkDFlipFlop(
ds,
mkAnd2(ds, nrst, flipflops[i-1]),
clk
);
}
const rom = mkRom(ds, messageData, flipflops);
mkOutputDevice(
ds,
{
outs: rom.slice(0, 8),
clk,
enb: nrst,
mode: rom[8]
}
)
for (;;) runDevices(ds);
$ deno run https://www.ericproberts.dev/extra/2020/nand_hello.js
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 hi@ericproberts.dev.