Two’s Complement

Two’s complement is a way of representing signed binary numbers that makes signed addition use the same logic as unsigned addition. The most significant bit now represents $-2^n$ instead of $2^n$. For example, 1011 in two’s complement represents -8 + 2 + 1 = -5.

An easy way to convert a number to two’s complement is to flip all the bits and add 1.

Adders

We look at three different adders:

The Half-adder, which adds two bits together, producing a sum and a carry.
The Full-adder, which adds three bits together, producing a sum and a carry.
The Adder, which adds two n-bit numbers together.

A Ripple Carry Adder is an Adder that is build from multiple Full-adders chained together. This is simple, but inefficient as for an n-bit number you have a delay of n cycles as you wait for the carry bit to propegate.

A Carry-lookahead Adder is more efficient, but more complicated.

The Arithmetic Logic Unit

Our ALU will compute a set of functions on two 16 bit numbers. The chosen function will depend on six control bits - leading to $2^6 = 64$ possible different functions, although there are probably only about 18 interesting ones.

Control bit:
zx - zero the x input
nx - negate the x input (after zeroing if requested)
zy - zero the y input
ny - negate the y input (after zeroing if requested)
f  - function, 1: Add, 0: And
no - negate the output

For example, if zx, nx and f were 1, we would:

Zero the x input, giving 0000000000000000.
Negative it, giving 1111111111111111 = -1.
Add y and x, giving y - 1.

This was designed manually, thinking backwards from the list of functions the authors wished to support.

Exercises

Half Adder

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

sum = XOR(a, b)
carry = AND(a, b)

Full Adder

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

0 0 |   1     0
0 1 |   0     1
1 0 |   0     1
1 1 |   1     1

sum = XOR(XOR(a, b), c)
carry = OR(AND(a, b), AND(b, c), AND(a, c))

Looking at answers on the internet, most people combined two Half-adders here. Wikipedia on the other hand has the same logic for the sum, but uses one fewer AND gates on the carry by ANDing with XOR(a, b) instead (src).

Adder

For the adder I implemented a Ripple Carry Adder:

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

    PARTS:
    HalfAdder(a=a[0], b=b[0], carry=c0, sum=out[0]);
    FullAdder(a=a[1], b=b[1], c=c0, carry=c1, sum=out[1]);
    FullAdder(a=a[2], b=b[2], c=c1, carry=c2, sum=out[2]);
    // ...
    FullAdder(a=a[15], b=b[15], c=c14, carry=c15, sum=out[15]);
}

And for the Incrementer (saving mostly so I remember the syntax):

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

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

The ALU

For the ALU it seems wise to create a new block that applies the “maybe zero, maybe negate” logic.

A chip can have multiple out wires (which is useful for the “is result zero” and “is result negative” flags).

Extend turns 0 into 0000000000000000 and 1 into 1111111111111111:

CHIP Extend {
    IN  in;      // bit to extend
    OUT out[16]; // 16-bit output

    PARTS:
    Mux16(a=false, b=true, sel=in, out=out);
}

CondZero conditionally zeroes a value:

CHIP CondZero {
    IN  
        in[16],  // 16-bit input       
        z;      // zero the input?

    OUT 
        out[16]; // 16-bit output

    PARTS:
    Not(in=z, out=notz);
    Extend(in=notz, out=notz16);
    And16(a=in, b=notz16, out=out);
}

Actually thinking about it, I could get rid of Extend and just do:

    Mux16(a=true, b=false, sel=z, out=mask);
    And16(a=in, b=mask, out=out);

CondNeg conditionally negates a value:

CHIP CondNeg {
    IN  
        in[16],  // 16-bit input       
        n;      // negate the input?

    OUT 
        out[16]; // 16-bit output

    PARTS:
    Not16(in=in, out=notin);
    Mux16(a=in, b=notin, sel=n, out=out);
}

IsZero checks if a value is zero:

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

    PARTS:
    Or(a=in[0], b=in[1], out=a);
    Or(a=in[2], b=in[3], out=b);
    Or(a=in[4], b=in[5], out=c);
    Or(a=in[6], b=in[7], out=d);
    Or(a=in[8], b=in[9], out=e);
    Or(a=in[10], b=in[11], out=f);
    Or(a=in[12], b=in[13], out=g);
    Or(a=in[14], b=in[15], out=h);

    Or(a=a, b=b, out=i);
    Or(a=c, b=d, out=j);
    Or(a=e, b=f, out=k);
    Or(a=g, b=h, out=l);

    Or(a=i, b=j, out=m);
    Or(a=l, b=l, out=n);

    Or(a=m, b=n, out=o);
    Not(in=o, out=out);
}

And putting this all together we can construct our ALU:

// 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

CHIP ALU {
    IN  
        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 
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:
    CondZero(in=x, z=zx, out=x1);
    CondZero(in=y, z=zy, out=y1);

    CondNeg(in=x1, n=nx, out=x2);
    CondNeg(in=y1, n=ny, out=y2);

    And16(a=x2, b=y2, out=and);
    Add16(a=x2, b=y2, out=add);

    Mux16(a=and, b=add, sel=f, out=res);
    CondNeg(in=res, n=no, out=out, out=out2, out[15]=ng);

    IsZero(in=out2, out=zr);
}