From Nand to Tetris(Nand2tetris) Project 2

Arithmetic & Logic Unit

Without the endeavor and intelligence of the great mathematicians like Von Neumann and Turing, the development of computer science might be delayed for decades. Hats off to them!

From the picture we can tell that the CPU is the heart of a computer, and ALU is the most import element of the CPU. All of the calculations and comparisons are happened in the ALU.

For example, if we write such a program in ruby:

a = 3
b = 5
if a < b
   p "a is smaller that b"
end

How could the computer know what to do when it receives such a document? Computer only have gates, 0 and 1s. How could the ALU calculate?

Let’s start from the easiest calculation ADD.

a = 3
b = 5
a + b = ?

Remember everything in the computer are 0s and 1s, so all the numbers are represented by binaries. So when the computer see the codes it can only see

0000 0000 0000 0011
0000 0000 0000 0101
ADD

A 16 bit Add can be translated into

CHIP HalfAdder {
     IN a, b;
     OUT sum, carry;
     PARTS:
     Xor(a=a, b=b, out=sum);
     And(a=a, b=b, out=carry);
}
CHIP FullAdder {
     IN a, b, c;
     OUT sum, carry;
     PARTS:
     HalfAdder(a=a, b=b, sum=absum, carry=abcarry);
     HalfAdder(a=c, b=absum, sum=sum, carry=abccarry);
     Or(a=abcarry, b=abccarry, out=carry);
}
CHIP ADD16 {
     IN a[16], b[16];
     OUT sum[16];
     PARTS:
     HalfAdder(a=a[0], b=b[0], sum=sum[0], carry=carry0);
     FullAdder(a=a[1], b=b[1], c=carry0, sum=sum[1], carry=carry1);
     FullAdder(a=a[2], b=b[2], c=carry1, sum=sum[2], carry=carry2);
     ...
     ...
     FullAdder(a=a[15], b=b[15], c=carry14, sum=sum[15], carry=c);
}

Now we have ADD, and at the mean time we have sub, that is because a-b = a + (-b), so we only have to consider how to calculate -b?

we know that b + (-b) = 0. So if b is 10101010, then -b must be something that turns all the 1s of b into zeros, but how to do that?

Imagine we have an 8 digits system, we can use them to represent 256 decimal numbers. It could be 0..255. But we also want to represent the negative numbers, so we’d better not use all of them as positive numbers, people may say that we can use the first digit to represent the sign, say if 00000001 is 1, then 10000001 will be -1, but this will also be problematic as 1 + (-1) is not 0 but 10000010, which in that definition, would be -2, so this is wrong. Then we may have an idea, if 0000 0001 + something = 0000 0000 then that something must be -1, because our 8 digit addition don’t have to worry about overflow, and we can use simple binary addition to get this equation: 1111 1111 + 0000 0001 = 1 0000 0000, which will be deemed as 0000 0000 in the computer. Bingo, we now know how to represent a negative number.

This method is call 2’s complement.

CHIP NEG {
     IN in[16];
     OUT out[16];
     PARTS:
     NOT16(in=in, out=notin);
     Add16(a=notin, b=1, out=out);
}

I am not very sure whether this is correct, because the Add16 might not take 1 as 0000 0000 0000 0001, it may take it as a true value, which might brought some trivial issues, but it can be easily fixed.

We have ADD and SUB, then we will also have Multiply and Divide, but of course we may have more advanced algorithm to deal with them, but we still can see multiply as multiple ADD, and divide as multiple SUB.

That being said, our primitive ALU is almost done:

CHIP ALU {
   IN
      x[16], y[16],  // 16-bit inputs
      zx, // zero the x input?   x => 0
      nx, // negate the x input? x => !x
      zy, // zero the y input?   y => 0
      ny, // negate the y input? y => !y
      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:
      // x zero / negate
      Mux16(a=x, sel=zx, out=x1);
      Not16(in=x1, out=negatedX);
      Mux16(a=x1, b=negatedX, sel=nx, out=x2);

      // y zero / negate
      Mux16(a=y, sel=zy, out=y1);
      Not16(in=y1, out=negatedY);
      Mux16(a=y1, b=negatedY, sel=ny, out=y2);

      // x + y OR x & y
      Add16(a=x2, b=y2, out=added);
      And16(a=x2, b=y2, out=xyAnd);
      Mux16(a=xyAnd, b=added, sel=f, out=result);

      // negate the output?
      Not16(in=result, out=negatedResult);
      Mux16(a=result, b=negatedResult, sel=no, out=out, out[15]=firstOut, out[0..7]=finalLeft, out[8..15]=finalRight);

      // output == 0 (zr)
      Or8Way(in=finalLeft, out=zrl);
      Or8Way(in=finalRight, out=zrr);
      Or(a=zrl, b=zrr, out=nzr);
      Not(in=nzr, out=zr);

      // output < 0 (ng)
      And(a=firstOut, b=true, out=ng);
}

Our ALU is still very simple, but it is good enough to deal with our daily calculations. We have 2 input buses which are x[16] and y[16], we also have 6 control bits, which are zx, nx, zy, ny, f, no(has been clearly explained in the code). With this ALU, we can do vast amount of things. We can even develop a high level language and run some interesting games on it, like Tetris. But those are for the later projects.