Boolean arithmetic
Binary system
The arithmetic logic unit (ALU) is the centerpiece chip that executes all the arithmetic and logic operations performed by the computer. Most of the operations performed by digital computers can be reduced to elementary additions of binary numbers.
Let \(x = x_n x_{n-1} \ldots x_0\) be a string of digits. The value of \(x\) in base \(b\), denoted as \((x)_ b\), is defined the following way:
$$ \begin{align} (x_n x_{n-1} \ldots x_0) b = \sum{i=0}^n x_i \cdot b^i \tag{1} \end{align} $$
Computer hardware for binary addition of two \(n\)-bit numbers can be built from logic gates designed to calculate the sum of three bits (pair of bits plus carry bit).
In order to represent signed numbers in binary code, we can split the set of all allowable integers into two equal subsets. We will use two's complement method, also known as radix complement to represent signed integers. Two's complement is defined as follows:
$$ \bar x = \begin{cases} 2^n - x, & \text{if} \quad x \ne 0 \\ 0, & \text{otherwise} \tag{2} \end{cases} $$
Properties of an \(n\)-bit binary system with two's complement representation:
- There is a total of \(2^n\) signed numbers.
- The largest positive number is \(2^{n-1}-1\).
- The largest negative number is \(-2^{n-1}\).
- The codes of all positive numbers begin with 0.
- The codes of all negative numbers begin with 1.
- To obtain the code of \(-x\) from the code of \(x\), flip all the bits of \(x\) and add 1 to the result.
The benefit of this system is that addition of any two signed numbers is exactly the same as addition of positive numbers.
Half adder
/**
* 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
PARTS:
Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);
}
Half adder output
| a | b | sum | carry |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Full adder
/**
* 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
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);
}
Full adder output
| 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 |
Adder
/**
* Adds two 16-bit values.
* The most significant carry bit is ignored.
*/
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
HalfAdder(a=a[0], b=b[0], sum=out[0], carry=c0);
FullAdder(a=a[1], b=b[1], c=c0, sum=out[1], carry=c1);
FullAdder(a=a[2], b=b[2], c=c1, sum=out[2], carry=c2);
FullAdder(a=a[3], b=b[3], c=c2, sum=out[3], carry=c3);
FullAdder(a=a[4], b=b[4], c=c3, sum=out[4], carry=c4);
FullAdder(a=a[5], b=b[5], c=c4, sum=out[5], carry=c5);
FullAdder(a=a[6], b=b[6], c=c5, sum=out[6], carry=c6);
FullAdder(a=a[7], b=b[7], c=c6, sum=out[7], carry=c7);
FullAdder(a=a[8], b=b[8], c=c7, sum=out[8], carry=c8);
FullAdder(a=a[9], b=b[9], c=c8, sum=out[9], carry=c9);
FullAdder(a=a[10], b=b[10], c=c9, sum=out[10], carry=c10);
FullAdder(a=a[11], b=b[11], c=c10, sum=out[11], carry=c11);
FullAdder(a=a[12], b=b[12], c=c11, sum=out[12], carry=c12);
FullAdder(a=a[13], b=b[13], c=c12, sum=out[13], carry=c13);
FullAdder(a=a[14], b=b[14], c=c13, sum=out[14], carry=c14);
FullAdder(a=a[15], b=b[15], c=c14, sum=out[15]);
}
Adder output
| a | b | out |
| 0000000000000000 | 0000000000000000 | 0000000000000000 |
| 0000000000000000 | 1111111111111111 | 1111111111111111 |
| 1111111111111111 | 1111111111111111 | 1111111111111110 |
| 1010101010101010 | 0101010101010101 | 1111111111111111 |
| 0011110011000011 | 0000111111110000 | 0100110010110011 |
| 0001001000110100 | 1001100001110110 | 1010101010101010 |
Incrementer
/**
* 16-bit incrementer:
* out = in + 1 (arithmetic addition)
*/
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
HalfAdder(a=in[0], b=true, sum=out[0], carry=c0);
FullAdder(a=in[1], b=false, c=c0, sum=out[1], carry=c1);
FullAdder(a=in[2], b=false, c=c1, sum=out[2], carry=c2);
FullAdder(a=in[3], b=false, c=c2, sum=out[3], carry=c3);
FullAdder(a=in[4], b=false, c=c3, sum=out[4], carry=c4);
FullAdder(a=in[5], b=false, c=c4, sum=out[5], carry=c5);
FullAdder(a=in[6], b=false, c=c5, sum=out[6], carry=c6);
FullAdder(a=in[7], b=false, c=c6, sum=out[7], carry=c7);
FullAdder(a=in[8], b=false, c=c7, sum=out[8], carry=c8);
FullAdder(a=in[9], b=false, c=c8, sum=out[9], carry=c9);
FullAdder(a=in[10], b=false, c=c9, sum=out[10], carry=c10);
FullAdder(a=in[11], b=false, c=c10, sum=out[11], carry=c11);
FullAdder(a=in[12], b=false, c=c11, sum=out[12], carry=c12);
FullAdder(a=in[13], b=false, c=c12, sum=out[13], carry=c13);
FullAdder(a=in[14], b=false, c=c13, sum=out[14], carry=c14);
FullAdder(a=in[15], b=false, c=c14, sum=out[15]);
}
Incrementer output
| in | out |
| 0000000000000000 | 0000000000000001 |
| 1111111111111111 | 0000000000000000 |
| 0000000000000101 | 0000000000000110 |
| 1111111111111011 | 1111111111111100 |
Arithmetic logic unit
Our ALU computes a fixed set of functions \(\text{out} = f_i (x, y)\) where \(x\) and \(y\) are two 16-bit inputs. We instruct the ALU which function to compute by setting six control bits to selected binary values. The overall functionality of the hardware and software is delivered jointly by the ALU and the operating system that runs on top of it.
/**
* 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
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:
Not16(in=x, out=notx);
And16(a=x, b=notx, out=z);
Mux16(a=x, b=z, sel=zx, out=zxout);
Not16(in=zxout, out=notzxout);
Mux16(a=zxout, b=notzxout, sel=nx, out=nxout);
Mux16(a=y, b=z, sel=zy, out=zyout);
Not16(in=zyout, out=notzyout);
Mux16(a=zyout, b=notzyout, sel=ny, out=nyout);
And16(a=nxout, b=nyout, out=andxy);
Add16(a=nxout, b=nyout, out=addxy);
Mux16(a=andxy, b=addxy, sel=f, out=fout);
Not16(in=fout, out=nfout);
Mux16(a=fout, b=nfout, sel=no, out[0..7]=out1, out[8..15]=out2, out[15]=ng, out=out);
Or8Way(in=out1, out=or1);
Or8Way(in=out2, out=or2);
Or(a=or1, b=or2, out=nz);
Not(in=nz, out=zr);
}
Arithmetic logic unit output
| x | y |zx |nx |zy |ny | f |no | out |zr |ng |
| 0000000000000000 | 1111111111111111 | 1 | 0 | 1 | 0 | 1 | 0 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 1 | 1 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 1 | 0 | 1 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 0 | 0 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 0 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 0 | 1 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 0 | 1 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 1 | 1 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 1 | 1 | 1 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 1 | 1 | 1 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 1 | 1 | 1 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 1 | 1 | 0 | 0 | 1 | 0 | 1111111111111110 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 0 | 0 | 1 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 1 | 0 | 0 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 0 | 1 | 1 | 1 | 1111111111111111 | 0 | 1 |
| 0000000000000000 | 1111111111111111 | 0 | 0 | 0 | 0 | 0 | 0 | 0000000000000000 | 1 | 0 |
| 0000000000000000 | 1111111111111111 | 0 | 1 | 0 | 1 | 0 | 1 | 1111111111111111 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 1 | 0 | 1 | 0 | 1 | 0 | 0000000000000000 | 1 | 0 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 1 | 1 | 1 | 1 | 0000000000000001 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 1 | 0 | 1 | 0 | 1111111111111111 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 1 | 1 | 0 | 0 | 0000000000010001 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 0 | 0 | 0 | 0 | 0000000000000011 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 1 | 1 | 0 | 1 | 1111111111101110 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 0 | 0 | 0 | 1 | 1111111111111100 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 1 | 1 | 1 | 1 | 1111111111101111 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 0 | 0 | 1 | 1 | 1111111111111101 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 0 | 1 | 1 | 1 | 1 | 1 | 0000000000010010 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 0 | 1 | 1 | 1 | 0000000000000100 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 1 | 1 | 1 | 0 | 0000000000010000 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 1 | 1 | 0 | 0 | 1 | 0 | 0000000000000010 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 0 | 0 | 1 | 0 | 0000000000010100 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 0 | 1 | 0 | 0 | 1 | 1 | 0000000000001110 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 0 | 1 | 1 | 1 | 1111111111110010 | 0 | 1 |
| 0000000000010001 | 0000000000000011 | 0 | 0 | 0 | 0 | 0 | 0 | 0000000000000001 | 0 | 0 |
| 0000000000010001 | 0000000000000011 | 0 | 1 | 0 | 1 | 0 | 1 | 0000000000010011 | 0 | 0 |