## Introduction

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).

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.

## Chapter 1: Boolean Logic

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.

### NAND (1-bit)

 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. ### NOT (1-bit)

 Inputs in Outputs out Function If in = 0 then out = 1, else out = 0 ### AND (1-bit)

 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. ### OR (1-bit)

 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. ### XOR (1-bit)

 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. ### MUX (1-bit)

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 ### DMUX (1-bit)

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 } ### Multi-bit gates

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]).

### Multi-way gates

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.

### Multi-way OR (8-way)

 Inputs in Outputs out Function out = Or(in, in, in, …, in)

Is there a version that uses less gates? ### 4-way 16-bit MUX

 Inputs a, b, c, d, sel Outputs out 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 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). ### 8-way 16-bit MUX

 Inputs a, b, c, d, e, f, g, h, sel Outputs out 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. ### 4-way 1-bit DMUX

 Inputs in, sel 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} ### 8-way 1-bit DMUX

 Inputs in, sel 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} ## Chapter 2: Boolean Arithmetic

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:  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. ### Arithmetic logic unit (ALU)

There’s a lot to explain here. This has been the most interesting exercise in the book so far. ## Chapter 3: Sequential Logic

### 1-bit register

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. ### 16-bit register

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

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. ### Program counter 