I love computers. When I recently discovered that the Nand2Tetris guys, Noam Nisan and Shimon Schocken, had just packaged their famous course into a neat 12 week Coursera package, I couldn’t resist studying it any longer.
In this course you will build a modern computer system, from the ground up. We’ll take you from constructing elementary logic gates all the way through creating a fully functioning general purpose computer. In the process, you will learn how really computers work, and how they are designed.
I also picked up a copy of their excellent textbook The Elements of Computing Systems.
Fundamental chips with truth tables.
Perhaps the most useful, an AND gate’s output is on (true/high) if and only if both inputs are on.
| a | b | out | | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |
The NOT gate’s output is the opposite of the input.
| in | out | | 0 | 1 | | 1 | 0 |
On when either (including both) input is on.
| a | b | out | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |
An input selector. Three inputs
sel, and a single output
out. On when either
sel is off and input
a is on, or
sel is on and input
b is on. Can be assembled using
Incredibly powerful. For example, enables the concept of programmable chips, such as an AndMuxOr chip, which in essence wires a single
AND gate, and a single
OR gate through a multiplexor, allowing the chip consumer to select the mode of operation.
In communications, the
MUX is the backbone for encoding many discrete messages on a single communications line, by using an oscilator as the selection input. Decoding of the stream of bits can similarly occur, by applying an oscilator with a
| a | b | sel | out | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |
Or in abbreviated form:
| sel | out | | 0 | a | | 1 | b |
An output selector. Two inputs
sel, and two outputs
sel is on, will routes
a, otherwise route
| in | sel | a | b | | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 |
(x AND y) = (y AND x) (x OR y) = (y OR x)
(x AND (y AND z)) = ((x AND y) AND z) (x OR (y OR z)) = ((x OR y) OR z)
(x AND (y OR z)) = (x AND y) OR (x AND z) (x OR (y AND z)) = (x OR y) AND (x OR z)
De Morgan Laws
NOT(x AND y) = NOT(x) OR NOT(y) NOT(x OR y) = NOT(x) AND NOT(y)
Boolean Function Synthesis is the premise that by reviewing the truth table for a particular function, that a series of boolean algebra statement can be assembled for only the so called “truth” conditions,
OR‘ing them all together. By applying various laws (e.g. distributive, De Morgan etc) you can often decompose the algebra into a much simplier form. Practically making the implementation simpler, more efficient and cheaper to physically implement. Unforunately this is not a straight forward procedure (NP-hard problem).
A remarkable mathematical property of the above primitives, thanks to the narrow and finite world of boolean algebra (unlike that of integers for example), is that any, yes any, boolean function can be represented using an expression containing just
A premise that the world of digital computers completely hinges on.
This can be incredibly taken even further. Given that the humble
OR gate alone is versatile enough of representing any function (that is, it is capable of producing a signal of 0 or 1, based on all variations of input signal, unlike an
AND gate which has the property that if you only feed it zeroes it will always have zero as output), and thanks to De Morgan, we know that an
OR gate can be represented as a combination of
(x OR y) = NOT(NOT(x) AND NOT(y))
OR as a primitive, can be dumped. Sorry
OR. Leaving us with just
NOT as the primitive operations on which everything else in the Boolean world can be built. There is another atomic function, that by alone, like
OR, can compute everything. Enter
NAND truth table:
| a | b | out | | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 |
NAND can effortlessly represent:
NOTby feeding both inputs the same value, that is,
NOT(x) = (x NAND x)
NANDitself, that is,
(x AND y) = NOT(x NAND y)
And with that, we can see how
NAND provides the fundamental Boolean building block upon which everything in a digital computer can be built with.
Yes, mind blowingly cool.
A bus put simply, is a unit of bits. In HDL,
mybus is a bus of 8 bits, which is commonly referred to as a byte).
Sub-buses are useful for composing and/or breaking down buses.
A composition example in HDL. Here the 16 input pins to
Add16, are formed by combining two smaller 8-bit buses,
msb, to form an overall 16-bit representation.
IN lsb, msb; Add16(a[0..7]=lsb, a[8..15]=msb, b=..., out=...);
The Hack chip-set API
Below is a list of all the chip interfaces in the Hack chip-set, prepared by Warren Toomey. If you need to use a chip-part, you can copy-paste the chip interface and proceed to fill in the missing data. This is a very useful list to have bookmarked or printed.
Add16(a= ,b= ,out= ); ALU(x= ,y= ,zx= ,nx= ,zy= ,ny= ,f= ,no= ,out= ,zr= ,ng= ); And16(a= ,b= ,out= ); And(a= ,b= ,out= ); ARegister(in= ,load= ,out= ); Bit(in= ,load= ,out= ); CPU(inM= ,instruction= ,reset= ,outM= ,writeM= ,addressM= ,pc= ); DFF(in= ,out= ); DMux4Way(in= ,sel= ,a= ,b= ,c= ,d= ); DMux8Way(in= ,sel= ,a= ,b= ,c= ,d= ,e= ,f= ,g= ,h= ); DMux(in= ,sel= ,a= ,b= ); DRegister(in= ,load= ,out= ); FullAdder(a= ,b= ,c= ,sum= ,carry= ); HalfAdder(a= ,b= ,sum= , carry= ); Inc16(in= ,out= ); Keyboard(out= ); Memory(in= ,load= ,address= ,out= ); Mux16(a= ,b= ,sel= ,out= ); Mux4Way16(a= ,b= ,c= ,d= ,sel= ,out= ); Mux8Way16(a= ,b= ,c= ,d= ,e= ,f= ,g= ,h= ,sel= ,out= ); Mux(a= ,b= ,sel= ,out= ); Nand(a= ,b= ,out= ); Not16(in= ,out= ); Not(in= ,out= ); Or16(a= ,b= ,out= ); Or8Way(in= ,out= ); Or(a= ,b= ,out= ); PC(in= ,load= ,inc= ,reset= ,out= ); RAM16K(in= ,load= ,address= ,out= ); RAM4K(in= ,load= ,address= ,out= ); RAM512(in= ,load= ,address= ,out= ); RAM64(in= ,load= ,address= ,out= ); RAM8(in= ,load= ,address= ,out= ); Register(in= ,load= ,out= ); ROM32K(address= ,out= ); Screen(in= ,load= ,address= ,out= ); Xor(a= ,b= ,out= );
Using a electronics breadboard, and old raspberry pi with a breakout kit, and a bunch of commodity NAND chips from my local electronics store, I plan to mess around with physically constructing the following composite gates (as per nand2tetris project 1) all based on NAND’s.
- NOT gate
- AND gate
- OR gate
- XOR gate
- MUX gate
- DMUX gate
- 16-bit NOT
- 16-bit AND
- 16-bit OR
- 16-bit MUX
- 16-bit OR
- 16-bit/4-way MUX
- 16-bit/8-way MUX
- 4-way DMUX
- 8-way DMUX
Source: Jaycar Electronics the 74HC132 Quad 2 in NAND Gate IC
If interested, see follow up post DIY Computer Part 2 The ALU.