Elements of Computing Systems - Chapter 2 - Understandings

Great book and I am proud to own one!
  • Int this chapter, we build the ALU the Arithmetic Logical Unit.
  • The ALU is the centerpiece chip that executes all the arithmetic and logical operations performed by the computer.
  • Building the ALU functionality is an important step toward understanding how the CPU the Central Processing Unit and the overall computer work. 
Binary Addition
Let 's see an example first:

  • A pair of binary numbers can be added digit by digit from right to left.
  • First, we add the two right-most digits, also called the least significant bits (LSB) of the two binary numbers.
  • Next, we add the resulting carry bit (which is either 0 or 1) to the sum of the next pair of bits up the significance ladder.
  • We continue the process until the two most significant bits (MSB) are added.
  • If the last bit-wise addition generates a carry of 1, we can report overflow.
  • 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).
  • The transfer of the resulting carry bit forward to the addition of the next significant pair of bits can be easily accomplished by proper wiring of the 3-bit adder gates.
Half Adder
Ok, so in order to be able to add binary numbers, first we will have 2 inputs and 2 outputs. This operation will be done by an Half Adder chip.

Here is the Truth Table for the Half Adder:

And here is my implementation:
CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);

Full Adder
A Full Adder will be needed to add 3 inputs (2 binary inputs from the operation itself and the carry bit..) 
Here is the Truth Table for the Full Adder:

And here is my implementation for Full Adder:
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=foo, carry=bar);
    HalfAdder(a=foo, b=c, sum=sum, carry=baz);
    Or(a=bar, b=baz, out=carry);

The trick here is that, bar and baz can both never be 1. Only one of them can be 1. If one of them is 1, the carry will be 1 as well..

This is a chip that will make an addition operation on 2 16 bit length bus'. Let 's see the Truth Table:

Well note that Overflow is neither detected, nor handled! Here is my implementation:
CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];
    FullAdder(a=a[1],b=b[1],c=carry0, sum=out[1],carry=carry1);
    FullAdder(a=a[2],b=b[2],c=carry1, sum=out[2],carry=carry2);
    FullAdder(a=a[3],b=b[3],c=carry2, sum=out[3],carry=carry3);
    FullAdder(a=a[4],b=b[4],c=carry3, sum=out[4],carry=carry4);
    FullAdder(a=a[5],b=b[5],c=carry4, sum=out[5],carry=carry5);
    FullAdder(a=a[6],b=b[6],c=carry5, sum=out[6],carry=carry6);
    FullAdder(a=a[7],b=b[7],c=carry6, sum=out[7],carry=carry7);
    FullAdder(a=a[8],b=b[8],c=carry7, sum=out[8],carry=carry8);
    FullAdder(a=a[9],b=b[9],c=carry8, sum=out[9],carry=carry9);
    FullAdder(a=a[10],b=b[10],c=carry9, sum=out[10],carry=carry10);
    FullAdder(a=a[11],b=b[11],c=carry10, sum=out[11],carry=carry11);
    FullAdder(a=a[12],b=b[12],c=carry11, sum=out[12],carry=carry12);
    FullAdder(a=a[13],b=b[13],c=carry12, sum=out[13],carry=carry13);
    FullAdder(a=a[14],b=b[14],c=carry13, sum=out[14],carry=carry14);
    FullAdder(a=a[15],b=b[15],c=carry14, sum=out[15],carry=carry15);

16-bit Incrementer
This is a simple but elegant chip:

And here is my implementation:
CHIP Inc16 {
    IN in[16];
    OUT out[16];
    FullAdder(a=in[1],b=false,c=carry0, sum=out[1],carry=carry1);
    FullAdder(a=in[2],b=false,c=carry1, sum=out[2],carry=carry2);
    FullAdder(a=in[3],b=false,c=carry2, sum=out[3],carry=carry3);
    FullAdder(a=in[4],b=false,c=carry3, sum=out[4],carry=carry4);
    FullAdder(a=in[5],b=false,c=carry4, sum=out[5],carry=carry5);
    FullAdder(a=in[6],b=false,c=carry5, sum=out[6],carry=carry6);
    FullAdder(a=in[7],b=false,c=carry6, sum=out[7],carry=carry7);
    FullAdder(a=in[8],b=false,c=carry7, sum=out[8],carry=carry8);
    FullAdder(a=in[9],b=false,c=carry8, sum=out[9],carry=carry9);
    FullAdder(a=in[10],b=false,c=carry9, sum=out[10],carry=carry10);
    FullAdder(a=in[11],b=false,c=carry10, sum=out[11],carry=carry11);
    FullAdder(a=in[12],b=false,c=carry11, sum=out[12],carry=carry12);
    FullAdder(a=in[13],b=false,c=carry12, sum=out[13],carry=carry13);
    FullAdder(a=in[14],b=false,c=carry13, sum=out[14],carry=carry14);
    FullAdder(a=in[15],b=false,c=carry14, sum=out[15],carry=carry15);

Negative Binary Numbers

Let 's take a 4 bit example and calculate all possible values it can represent and their equiavalent values in Decimal system:

Well would 't it be better if we could represent negative numbers? A system called 2's Complement is used in Binary Numbers where Binary Numbers are said to be Signed Binary Numbers.

In this fashion, a negative value is represented by: 2^n - x = - x

With Signed Binary Numbers we will have the following table:

Computing -x from x

(Which means we can do y - x simply by y + (-x)

Input: x
Output: -x

Idea: 2^n - x = 1 + (2^n - 1) - x

2^n - 1 will always be: 1111111...
1111111.. - x is easy: Flip bits of x (Xor..) 
Well now, simply add 1 and you get -x...

Here is an other way (The one that we will use in our ALU implementation).

Remember, this is only when 2's complement is used!

Arithmetic Logical Unit