The book *The Elements of Computing Systems* by Noam Nisan and Shimon Schocken explains the design of a modern computer starting at the level of the most basic logic gates and working up to high level programming languages and operating systems.

Each chapter of the book contains a project to be completed, such as designing a CPU, building an assembler and implementing an operating system. Each chapters and project builds on the knowledge and work in the previous chapters (though they could also be completed out of order as independent exercises).

You can find more information about the book here: From Nand to Tetris.

These are my notes as I work through the book. I’m sure there are much better solutions than mine to many of the problems.

The project for this chapter is to implement a series of logic gates using only NAND gates as a primitive building block (plus any other gates once you have implemented them). For this chapter, I’ve shown them all using the NAND gates.

I simulated these using a tool called Logisim, which is a lot of fun to tinker with. The circuit images for the gates are screenshots from Logisim.

Inputs | a, b |

Outputs | out |

Function | If a = b = 1 then out = 0, else out = 1 |

This logic gate outputs a true value (1) except when both inputs are true. Don’t need to implement this one - it’s the building block for all the rest.

Inputs | in |

Outputs | out |

Function | If in = 0 then out = 1, else out = 0 |

Inputs | a, b |

Outputs | out |

Function | If a = b = 1 then out = 1, else out = 0 |

NAND is really NOT+AND, so another NAND gate will turn NAND back into AND.

Inputs | a, b |

Outputs | out |

Function | If a = b = 0 then out = 0, else out = 1 |

Negating the two inputs before they pass through a NAND gate makes an OR gate.

Inputs | a, b |

Outputs | out |

Function | If a ≠ b then out = 1, else out = 0 |

XOR only outputs true when one of the inputs is true, not both. This was the first tricky one for me. I’ve marked in the gate functions being performed by clusters of NANDs.

Multiplexer, can control which input passes through to the output by using a *select* input.

Inputs | a, b, sel |

Outputs | out |

Function | If sel = 0 then out = a, else out = b |

Demultiplexer, controls which output the input passes through to.

Inputs | in, sel |

Outputs | a, b |

Function | If sel = 0 then { a = in, b = 0 } else { a = 0, b = in } |

These are simply arrays of the above gates, e.g. an 8-bit OR gate applies an OR function to 8 separate pairs of input bits (a[0 to 7] and b[0 to 7]).

For multi-way gates, the logic applies to all of the inputs at once, not separately. For example, a multi-way OR gate with 8 input bits would have a single output bit that would be true if any of the 8 input bits were true.

Inputs | in[8] |

Outputs | out |

Function | out = Or(in[0], in[1], in[2], …, in[7]) |

Is there a version that uses less gates?

Inputs | a[16], b[16], c[16], d[16], sel[2] |

Outputs | out[16] |

Function | If sel = 00 then out = a, else if sel = 01 then out = b, else if sel = 10 then out = c else if sel = 11 then out = d |

A 4-way multiplexer is essentially two multiplexers mashed together. It has two select bits: sel[0] selects between a/b and c/d. The second bit selects between the two ‘winners’ of the first multiplexer.

I’ve substituted 16-bit gates for most of this diagram to keep it comprehensible. The *extenders* are turning a 1-bit input into a 16-bit output (all bits are the same as the input).

Inputs | a[16], b[16], c[16], d[16], e[16], f[16], g[16], h[16], sel[3] |

Outputs | out[16] |

Function | If sel = 000 then out = a, else if sel = 001 then out = b, else if sel = 010 then out = c … else if sel = 111 then out = h |

Have simplified the diagram for this one by showing 16-bit versions of the gates.

Inputs | in, sel[2] |

Outputs | a, b, c, d |

Function | If sel = 00 then {a = in, b = c = d = 0}, else if sel = 01 then {b = in, a = c = d = 0}, else if sel = 10 then {c = in, a = b = d = 0}, else if sel = 11 then {d = in, a = b = c = 0} |

Inputs | in, sel[3] |

Outputs | a, b, c, d, e, f, g, h |

Function | If sel = 000 then {a = in, b = c = d = e = f = g = h = 0}, else if sel = 001 then {b = in, a = c = d = e = f = g = h = 0}, else if sel = 010 … else if sel = 111 then {h = in, a = b = c = d = e = f = g = 0} |

The project for this chapter is to implement adder chips, then use these as part of an arithmetic logic unit (ALU).

My first attempt worked but was a little redundant:

Improved:

*h/a* indicates half-adders.

This is a chain of full adders, each passing their carry bit to the next adder.

I can’t get this to work in Logisim unless I put a constant 0 bit in to the carry pin of the first full adder (see centre top of diagram). Might come back to this.

There’s a lot to explain here. This has been the most interesting exercise in the book so far.

The square block is a data flip flop (another fundamental piece used as a primitive for the textbook). It has a clock signal feeding into it, and outputs whatever was fed in one clock cycle ago.

Feeding its output back in means it will store the value permanently. I have added a multiplexer however, so we can choose between feeding in the currently stored value (default), or when the load bit is set, storing a new value.

Just many 1-bit registers linked together and sharing a load bit and clock signal.

This is 8 x 16-bit registers linked together. The address input will determine which 16-bit register is selected (by the demultiplexers) to load and to output.