nand2tetris

My repo for the “nand2tetris” project. The corresponding MOOC, “Build a Modern Computer from First Principles: From Nand to Tetris”, is available on Coursera.

The goal is to build a computer from the ground up, starting from the =Nand= gate for combinational logic and the =D flip-flop= for sequential logic, to the OS itself.

Progress

Part 1

• [X] Week 1: Boolean Functions and Gate Logic
• [X] Week 2: Boolean Arithmetic and the ALU
• [X] Week 3: Memory
• [X] Week 4: Machine Language
• [X] Week 5: Computer Architecture
• [X] Week 6: Assembler

Part 2

• [ ] Week 1: Machine Language & Virtual Machine I: Stack Arithmetic
• [ ] Week 2: Virtual Machine II: Program Control
• [ ] Week 3: High-Level Language
• [ ] Week 4: Compiler I: Syntax Analysis
• [ ] Week 5: Compiler II: Code Generation
• [ ] Week 6: Operating System
• [ ] Week 7: Postscript: More Fun to Go

Logisim files

Although not required by the course, my goal is to implement most chips with Logisim (.circ files). I might give a try to Digital later.

When I already implemented a chip before, then I use the corresponding Logisim’s built-in chip when it’s available.

Here is an example for sequential logic, starting from RAM64 (a RAM with 64 16-bit registers) and going all the way to the D flip-flop:

RAM64

The RAM64: 8 ✕ RAM8 + combinational gates (DMux8Way, Mux8Way16)

Logisim representation

HDL representation

CHIP RAM64 {
    IN in[16], load, address[6];
    OUT out[16];

    PARTS:
    DMux8Way (in=load, sel=address[3..5], a=load1, b=load2, c=load3, d=load4, e=load5, f=load6, g=load7, h=load8);
    RAM8 (in=in, load=load1, address=address[0..2], out=out1);
    RAM8 (in=in, load=load2, address=address[0..2], out=out2);
    RAM8 (in=in, load=load3, address=address[0..2], out=out3);
    RAM8 (in=in, load=load4, address=address[0..2], out=out4);
    RAM8 (in=in, load=load5, address=address[0..2], out=out5);
    RAM8 (in=in, load=load6, address=address[0..2], out=out6);
    RAM8 (in=in, load=load7, address=address[0..2], out=out7);
    RAM8 (in=in, load=load8, address=address[0..2], out=out8);
    Mux8Way16 (a=out1, b=out2, c=out3, d=out4, e=out5, f=out6, g=out7, h=out8, sel=address[3..5], out=out);
}

RAM8

The RAM8: 8 ✕ Register + combinational gates (DMux8Way, Mux8Way16)

Logisim representation

HDL representation

CHIP RAM8 {
    IN in[16], load, address[3];
    OUT out[16];

    PARTS:
    DMux8Way (in=load, sel=address, a=load1, b=load2, c=load3, d=load4, e=load5, f=load6, g=load7, h=load8);
    Register (in=in, load=load1, out=out1);
    Register (in=in, load=load2, out=out2);
    Register (in=in, load=load3, out=out3);
    Register (in=in, load=load4, out=out4);
    Register (in=in, load=load5, out=out5);
    Register (in=in, load=load6, out=out6);
    Register (in=in, load=load7, out=out7);
    Register (in=in, load=load8, out=out8);
    Mux8Way16 (a=out1, b=out2, c=out3, d=out4, e=out5, f=out6, g=out7, h=out8, sel=address, out=out);
}

Register

The Register (16-bit register): 16 ✕ Bit.

Logisim representation

HDL representation

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:
    Bit (in=in[0], load=load, out=out[0]);
    Bit (in=in[1], load=load, out=out[1]);
    Bit (in=in[2], load=load, out=out[2]);
    Bit (in=in[3], load=load, out=out[3]);
    Bit (in=in[4], load=load, out=out[4]);
    Bit (in=in[5], load=load, out=out[5]);
    Bit (in=in[6], load=load, out=out[6]);
    Bit (in=in[7], load=load, out=out[7]);
    Bit (in=in[8], load=load, out=out[8]);
    Bit (in=in[9], load=load, out=out[9]);
    Bit (in=in[10], load=load, out=out[10]);
    Bit (in=in[11], load=load, out=out[11]);
    Bit (in=in[12], load=load, out=out[12]);
    Bit (in=in[13], load=load, out=out[13]);
    Bit (in=in[14], load=load, out=out[14]);
    Bit (in=in[15], load=load, out=out[15]);
}

Bit

The Bit (1-bit register): DFF (D flip-flop) + combinational gate (Mux)

Logisim representation

HDL representation

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    Mux (a=feedback, b=in, sel=load, out=muxout);
    DFF (in=muxout, out=feedback, out=out);
}

DFF

The DFF (D flip-flop) can be implemented from Nand gates. In the course, it is already provided in order to separate clearly the combinational logic from the sequential logic.