Building a computer from scratch part II

Part 1 is here.

After reviewing basic boolean operations and seeing how to implement them in their corresponding digital gates, we can now make boolean arithmetic operations. In chapter 3 of Nand2Tetris, we take the digital gates we created (And, Or, Mux, Xor, etc) and create an ALU, or Arithmetic Logic Unit. This is the heart of a computer.

But before going into the implementation of an ALU, it’s helpful to demonstrate how we can do basic arithmetic using boolean numbers.

Our numbering system is based on the decimal system, which was handed down to us by the Greeks, Roman and as far back as ancient Egypt. One way to represent a number, say 13, is by thinking about each decimal place as a digit times a multiple of ten, in increasing order. So, 5 could be thought of as 5 plus 10 to the power of 0 (since it’s the first position). 13 is 3 plus 10 to the power of one. 125 can be thus represented as follows:

1 * 102 + 2 * 101 + 5 * 100 = 100 + 20 + 5 = 125

Hieroglyphs of numbers carved into a temple wall in Egypt | Ancient history  archaeology, Ancient world history, Ancient egyptian
Egyptian glyphs for the number 1 million, three hundred thousand, thirty thousand thirty three hundred and thirty three.
AtoZChallenge X for X - that's ten in Roman Numerals - TravelGenee
Are those numbers or roman numerals?

In a generalized form:

(x_{n}x_{n-1}…x_{0}) = \sum_{i=0}^{n} x_{i}b^{i}

Where b is the base system we want to use (10, 2 or even 16!), x is the number we want to represent and i is the index.

Adding two numbers in binary is easy:

1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
1 + 1 = 10

When two ones are added, we get zero and move a carry to the next place, just like we do in our own decimal numbering system. What happens if we get 5 – 3? What about subtraction? To calculate this, we have to include negative numbers in our computer. To do it, we use the 2’s complement system:

  1. We use the last bit as a sign operator (0 denoting positive, 1, denoting negative)
  2. We represent negative numbers by taking the 2’s complement of the number.

The number 4 in a 4-bit computer is 0010, and -4 is 1101, which also represents the number 13. We know this represents a negative number because the first sign bit is 1, meaning negative. To get the 2’s complement, we reverse the numbers so that 0s become 1s and 1s become 0s, and then add 1 to it.

Dropping In on Gottfried Leibniz—Stephen Wolfram Writings
Gottfried Leibniz’s explanation on binary numbers is unfortunately not much better than mine.

A special feature of using the 2’s complement system is that subtraction can be performed by using addition. For example, let’s say you want to do the following calculation, 5-3. To do it, we can represent the operation as 5 – 3 = 5 + (-3). To solve, we can just add five to the 2’s complement of 3 and get our result:

5 in binary: 0101

3 in binary: 0011
1’s complement of 3: 1100
2’s complement of 3: 1101

To subtract 5 from 3, add the 2’s complement of 5 and -3, then drop the overflow:
0101 + 1101 = 0010.

Which is 2. The implications of these results are significant, it means that a single chip will be able to encapsulate all the basic arithmetic operators on a hardware unit. This unit we call the ALU (Arithmetic Logic Unit).

The course was smart, in my opinion, in having the student create incremental chips that make up the ALU, rather than diving head first into it. Like many things in engineering, solving a really hard problem usually starts by breaking it into smaller, more manageable problems. Thus the following chips were incrementally implemented:

  • Half Adder: a chip that can add two bits
  • Full Adder: a chip that can add two bits plus a carry
  • Adder: a chip that add two binary numbers up to n bits (in our case, 16 bits)
  • Incrementor: Adds a binary number by 1, takes care of carry.

Compared with the rest of the chips that I previously implemented, the ALU is a monster of a chip:

Elements of Computing Systems

Let’s break it down. On the input side:
zx: zero the x input
ny: negate the x input
zy: zero the y input
ny: negate the y input
f: function that computes the output to be x + y (if f is 1) or x & y (if f is 0)
no: negate the output

On the output side:
out: output of the computation
zr: 1 if out is 0, 0 otherwise
ng: 1 if out is less than 0,  0 otherwise

Conceptually, we can think of the ALU as a chip that takes two input numbers and applies a series of boolean functions to it depending on whether those “control bits” are 1 or 0. The making of the ALU took quite some time to figure out, but it ended up being, as the previous lesson proved, an exercise in breaking down complex problems into smaller, more manageable problems. One thing to note is that this ALU was designed specifically for the Nand2Tetris course and the professors cautioned that this is a very simple version of an ALU, yet it is completely functional.

A small part of the logic gate design for my ALU

This was a great lesson where I was able to my continue learnings on how to make digital gates. It’s humbling to think, as a software engineer, that all operations and fancy code libraries we create are reduced to simple addition operations between two binary numbers – done billions of times over. I think it’s a testament to the rock-solid mathematical principles that underly these systems. The early programmers did not have a bunch of code libraries to help them: they had to rely on themselves to create these extremely complex systems at very small scale and I think the only way they were able to do it was by relying on mathematical certainty and reliable hardware engineering to enable their creations to work.

After this lesson, I wonder what methods or processes I can use to enable me to write code that accomplishes the task well and does it in a way that takes advantage of the hardware beneath it.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s