Chapter 2 -- Arithmetic Logical Unit

This is the workflow problems of Chapter 2 of the "The Elements of Computing Systems" by Noam Nisan and Shimon Schocken. These are my own solutions for my own reference.

As the NAND gate is considered primitive we build all our logical gates around this gate following order of the book. The Elements of Computing Systems.

halfAdder

The Half adder adds two bits, let us call the least significant bit of the addition sum and the most significant bit the carry. The expected behaviour is below

a b carry sum
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

sum = LSB of a + b, carry = MSB of a + b;

CHIP HalfAdder {
    IN a, b;
    OUT sum, carry;

    PARTS:
    And(a=a, b=b, out=carry);
    Xor(a=a, b=b, out=sum);
}

Full-Adder

Full adder adds three bits, like the half-adder case, the full adder chip produces two outputs, the least significant bit of the addition and the carry bit.

a b c carry sum
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

sum = LSB of a + b + c, carry = MSB of a + b + c;

CHIP FullAdder {
    IN a, b, c;
    OUT sum, carry;

    PARTS:
    HalfAdder(a=a, b=b, sum=s1, carry=c1);
    HalfAdder(a=s1, b=c, sum=sum, carry=c2);
    Or(a=c1, b=c2, out=carry);
}

Add16

16 bit add, integer 2's complement addition, overflow is neither detected nor handled.

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

    PARTS:
    FullAdder(a=false, b=a[0],  c=b[0],  sum=out[0],  carry=c0);
    FullAdder(a=c0,    b=a[1],  c=b[1],  sum=out[1],  carry=c1);
    FullAdder(a=c1,    b=a[2],  c=b[2],  sum=out[2],  carry=c2);
    FullAdder(a=c2,    b=a[3],  c=b[3],  sum=out[3],  carry=c3);
    FullAdder(a=c3,    b=a[4],  c=b[4],  sum=out[4],  carry=c4);
    FullAdder(a=c4,    b=a[5],  c=b[5],  sum=out[5],  carry=c5);
    FullAdder(a=c5,    b=a[6],  c=b[6],  sum=out[6],  carry=c6);
    FullAdder(a=c6,    b=a[7],  c=b[7],  sum=out[7],  carry=c7);
    FullAdder(a=c7,    b=a[8],  c=b[8],  sum=out[8],  carry=c8);
    FullAdder(a=c8,    b=a[9],  c=b[9],  sum=out[9],  carry=c9);
    FullAdder(a=c9,    b=a[10], c=b[10], sum=out[10], carry=c10);
    FullAdder(a=c10,   b=a[11], c=b[11], sum=out[11], carry=c11);
    FullAdder(a=c11,   b=a[12], c=b[12], sum=out[12], carry=c12);
    FullAdder(a=c12,   b=a[13], c=b[13], sum=out[13], carry=c13);
    FullAdder(a=c13,   b=a[14], c=b[14], sum=out[14], carry=c14);
    FullAdder(a=c14,   b=a[15], c=b[15], sum=out[15], carry=c15);
}

Incrementer 16 bit

16 bit Incrementer, special purpose chip dedicated to adding the constant 1 to a given number.

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

    PARTS:
    Add16(a[0]=true, b=in, out=out);
}