# Boolean Arithmetic

The Elements of Computing Systems

Thu 26th Dec 2019

Table of Contents

1. Two’s Complement
2. Adders
3. The Arithmetic Logic Unit
4. Exercises

# 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:

1. Zero the x input, giving 0000000000000000.
2. Negative it, giving 1111111111111111 = -1.
3. 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
0 0 1 |   1     0
0 1 0 |   1     0
0 1 1 |   0     1

1 0 0 |   1     0
1 0 1 |   0     1
1 1 0 |   0     1
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);
}