Building own Computer with Nand2Tetris: Project II

21 March 2022

This week's project includes creating an adder circuit, an increment circuit, and combining all the things into an arithmetic logic unit that we have created so far.

The ones whose interested in with Nand2Tetris-HDL, please check the manual.

Half Adder

From the truth table, we can easily recognize that $\text{sum} = A \oplus B$ and $\text{carry} = AB$ for inputs A and B. Creation of such circuit will be very easy for us in HDL.

 * Computes the sum of two bits.

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b
        carry;  // Left bit of a + b

    And (a=a, b=b, out=carry);
    Xor (a=a, b=b, out=sum);
Nand2Tetris-HDL implementation of Half Adder.

Full Adder

Half adder can only add two bits, and give us the sum and the carry. To create a circuit which can add more than one bit, we will need a three-input adder circuit, since we also need to add previous carry.

Think about this: 28 + 94. Adding of less significant character (8 and 4) can be done with half adder. It'll give us a sum of 2, and a carry of 1. To add second characters, we have to add three different numbers now: 2 + 9 + 1 (carry). That's the reason we require full adder.

A full adder can be implemented using two half adders, and a OR  gate for combination of carries.

 * Computes the sum of three bits.

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    HalfAdder (a=a, b=b, sum=sumAB, carry=carAB);
    HalfAdder (a=sumAB, b=c, sum=sum, carry=carSC);
    Or (a=carAB, b=carSC, out=carry);
Nand2Tetris-HDL implementation of Full Adder.

It is time to create a 16-bit adder, then!

16-bit Adder

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    HalfAdder (a=a[0], b=b[0], sum=out[0], carry=carr0);
    FullAdder (a=a[1], b=b[1], c=carr0, sum=out[1], carry=carr1);
    FullAdder (a=a[2], b=b[2], c=carr1, sum=out[2], carry=carr2);
    FullAdder (a=a[3], b=b[3], c=carr2, sum=out[3], carry=carr3);
    FullAdder (a=a[4], b=b[4], c=carr3, sum=out[4], carry=carr4);
    FullAdder (a=a[5], b=b[5], c=carr4, sum=out[5], carry=carr5);
    FullAdder (a=a[6], b=b[6], c=carr5, sum=out[6], carry=carr6);
    FullAdder (a=a[7], b=b[7], c=carr6, sum=out[7], carry=carr7);
    FullAdder (a=a[8], b=b[8], c=carr7, sum=out[8], carry=carr8);
    FullAdder (a=a[9], b=b[9], c=carr8, sum=out[9], carry=carr9);
    FullAdder (a=a[10], b=b[10], c=carr9, sum=out[10], carry=carr10);
    FullAdder (a=a[11], b=b[11], c=carr10, sum=out[11], carry=carr11);
    FullAdder (a=a[12], b=b[12], c=carr11, sum=out[12], carry=carr12);
    FullAdder (a=a[13], b=b[13], c=carr12, sum=out[13], carry=carr13);
    FullAdder (a=a[14], b=b[14], c=carr13, sum=out[14], carry=carr14);
    FullAdder (a=a[15], b=b[15], c=carr14, sum=out[15], carry=carr15);
Nand2Tetris-HDL implementation of 16-bit Adder.


The line you see on the Add16 part written as b[0]=true means that make the input's first bit equal to 1, and we are sure b will be a 16-bit value because of the implementation of it.

 * 16-bit incrementer:
 * out = in + 1 (arithmetic addition)

CHIP Inc16 {
    IN in[16];
    OUT out[16];

    Add16 (a=in, b[0]=true, out=out);    
Nand2Tetris-HDL implementation of Incrementer.

Arithmetic Logic Unit

In the course, we are asked to implement a ALU which can do these functions within given inputs:

One can create an ALU which is capable of processing 18 different functions with only doing negotiation, AND operation, and addition.

Here's the HDL I have created.

 // This file is part of
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/ALU.hdl

 * The ALU (Arithmetic Logic Unit).
 * Computes one of the following functions:
 * x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
 * x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs, 
 * according to 6 input bits denoted zx,nx,zy,ny,f,no.
 * In addition, the ALU computes two 1-bit outputs:
 * if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
 * if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.

// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0        // 16-bit constant
// if (nx == 1) set x = !x       // bitwise not
// if (zy == 1) set y = 0        // 16-bit constant
// if (ny == 1) set y = !y       // bitwise not
// if (f == 1)  set out = x + y  // integer 2's complement addition
// if (f == 0)  set out = x & y  // bitwise and
// if (no == 1) set out = !out   // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

        x[16], y[16],  // 16-bit inputs
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute out = x + y (if 1) or x & y (if 0)
        no; // negate the out output?

        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    Mux16 (a=x, b=false, sel=zx, out=Xzx);
    Mux16 (a=y, b=false, sel=zy, out=Yzy);

    Not16 (in=Xzx, out=NotXzx);
    Not16 (in=Yzy, out=NotYzy);
    Mux16 (a=Xzx, b=NotXzx, sel=nx, out=Xnx);
    Mux16 (a=Yzy, b=NotYzy, sel=ny, out=Yny);

    Add16 (a=Xnx, b=Yny, out=outAdd);
    And16 (a=Xnx, b=Yny, out=outAnd);
    Mux16 (a=outAnd, b=outAdd, sel=f, out=outF);

    Not16 (in=outF, out=NotOutF);
    Mux16 (a=outF, b=NotOutF, sel=no, out=outTemp, out=out);

    // ZR
    ZeroCheck16 (input=outTemp, output=zr);

    // NG
    NegativeCheck16 (input=outTemp, output=ng);
Nand2Tetris-HDL implementation of ALU.

The file also calls for two chips that we haven't introduced before. I have created them because the Nand2Tetris-HDL does not allow us to use an internal pin's sub-bits-array. Therefore, I used a method to avoid "internal pin" behavior. You can see these chips' HDL files below.

CHIP NegativeCheck16 {
        IN input[16];
        OUT output;

                And (a=input[15], b=input[15], out=output);
Nand2Tetris-HDL implementation of NegativeCheck16 that gives us if the output is negative, or not.
CHIP ZeroCheck16 {
        IN input[16];
        OUT output;

                Or8Way (in=input[0..7], out=tOut1);
                Or8Way (in=input[8..15], out=tOut2);
                Or (a=tOut1, b=tOut2, out=NotZC);
                Not (in=NotZC, out=output);
Nand2Tetris-HDL implementation of ZeroCheck16 that gives us if the output is zero, or not.