In Addition to That…

This is where we learn how to do addition in the lowest levels of computer architecture.

After completing project one you are left with five, 16-bit chips and no real idea where to go next, or why you made them. Luckily, you don’t have to be as smart as the guys who invented the computer in the first place, and you can always just continue on with the course. In project two you are commissioned to build five more chips. Four of them have to do with addition and the fifth one is the main ALU chip of CPU, which I will talk more about in a later post. One question you might have is what exactly do I mean by 16-bit chips. Well, in previous posts I have talked about the NOT and the MUX chip. Both of those would be considered single-bit chips, because you are feeding them one bit (a zero or one) at a time. So a 16-bit version of those can handle inputs of 16-bits at the same time. Why would you want to do that? Other than the obvious speed benefit when using 16 bits, all of the sudden you have the ability to start representing numbers greater than one. In fact, for an unsigned (only positive) 16-bit number can be as large as 65535, which is awesome because I don’t know about you but I am ready to get back to the real world where 1+1 = 2 despite what Boolean Algebra tries to tell you. But before we ascend to the world of comfort and normalcy that normal arithmetic offers, we must descend back into the weird world of binary. Let me give you a couple examples of how some of these 16-bit chips work.

‘NOT’ 16-bit

The single bit not chip is probably the easiest chip to comprehend it just takes what ever its given and returns the opposite. The 16-bit version does the same thing, it just does it 16 times.

Single Bit Not
In 0 Out 1
In 1 Out 0

NOT16
In 0101010101010101
Out 1010101010101010

As you can see there is nothing crazy about it. It is literally just going through one bit at a time (actually instantly) and flipping each bit to its opposite.

MUX8WAY 16-bit

This chip does vary a bit (another bad computer pun) from its single bit counter part but the general idea is the same. Instead of writing any binary examples it will probably just be easier to explain from a higher level.

If you remember, the purpose of the MUX chip was to – based on the position of a selector switch – return either input ‘a’ or ‘b’. Well, as I eluded to before, being able to handle more bits has given us the ability to handle more numbers. So now the selector switch that used to only have two positions has eight positions and eight inputs. On top of that, each of those single bit inputs has been upgraded to 16-bit. Based on the position of the selector it will return the associated input. For example, if the selector was at zero the chip would return input ‘a’ and if the selector is at position one the chip will return input ‘b’. Then if the selector was flipped all the way to position eight it would return input ‘h’. This will come in extremely handy in the future when we start discussing RAM architecture. Of course since this is a 16-bit chip each of those inputs are 16-bits. So whichever input is selected, a 16-bit value will be emitted. Now that you have an idea what I mean by 16-bit chips let me proceed in explaining the first chip that handles addition. Namely the “Half-Adder.”

Half-Adder

The differences between adding binary numbers and the addition that you learned in the second grade have very few differences. Actually, adding binary is even more simple than what we are used to. Let me give you a couple examples.

When adding binary you start from the right hand side and work left – just like we have learned before. On the far right we have 1+1. Since there is no symbol for ‘2’ in binary we carry the one to the next column. Just like you would if you were adding a ‘9’ and a ‘1’. Moving one column left we now see a 0+1 but we also are carrying a one so that gets changed to 1+1. Therefore we carry the one again, facing yet another 1+1 scenario. This results in one more carry, which leaves us with the result of 1000 in binary or 8 in decimal form (decimal form of course being the way we usually count). Easy! One thing to keep in mind is that we will build this “adder” chip with the idea of it being part of and limited to our 16-bit architecture. So when adding two 16-bit numbers together, if there is a carry into a 17th bit, then that bit will just get thrown away. Like this:

As you can see above, the extra one that we were carrying just gets tossed out because our system can only handle 16-bits. Now the very observant ones reading this would realize that the result of the binary addition comes out to 26,559. Which is nowhere near the actual 92,095. This is, of course, because we dropped the extra digit. What is interesting to note about this number is that it turns out to be the modulus of our 16-bit max, or in other words when you divide 92,095 by 65,536 (216 which is our max unsigned 16-bit number) you will be left with the remainder of 26,559. I’ll leave you to ponder the significance of this fact and to consider how inextricably intertwined the universe and we as individuals are.

Moving Forward

So how does one go about building a chip the provides this behavior? Well, lets take a closer look at our previous example and see if there are any observations we can make about the different states we encounter in the process of addition. Looking back at our first simple example:

Let’s take it one column at a time. What do we need to communicate to successfully add two bits together? Well for the first number all we need to communicate is the sum, and then if there is any resulting carry or not. This is exactly the specification of the “Half-Adder” chip. The Half-Adder chip has two inputs and two outputs. The two inputs are the two bits that are being added together. One output represents the sum of the two bits, while the other output holds the value of the carry.

While at first trying to imagine how to design a chip that could handle addition might have seemed daunting, when broken down into this simple little part it is actually quite simple. With the above definition we derive the following truth table that fully specifies the necessary behavior of this chip:

 |   a   |   b   |  sum  | carry |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |

From there we can use the logic that I have previously described to derive the following formula:

sum = (Not(a) & b) OR (a & Not(b))
carry = a & b

It turns out that both sum and carry can be defined with one chip. The behavior of sum is described by the XOR (aka Exclusive Or) chip. This chip only returns true when the two inputs are different. So the resulting HDL file looks like this:

By now maybe you’ve figured out why this is called the Half-Adder. It is called this because it only handles half the functionality we need it to. Lets look at that example again.

The Half-Adder works perfectly for the first column but will it work for the second? No! It can’t work because there is no way for it to realize that the column before it had created a carry. Therefore in order to add two numbers together that are more than single bits, we will need a chip that has three inputs. One for the two bits that are being added together, plus a third to handle carries.

The behavior for this chip is slightly more complicated, and therefore results in a slightly more complicated truth table.

 |   a   |   b   |in-carry|  sum  |out-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 |

While we may be tempted to run off and try writing a formula that solves this table, it might be helpful to step back and remember what we are trying to do. We have already successfully created a chip that, as long as there are no incoming carries, will output a sum and resulting carry. So using that single chip we can chain that behavior together to add bits ‘a’ and ‘b’ together. From there we can take the sum of ‘ab’ and add it again to the ‘in-carry’ bit. Then we can define that out-carry bit by whether or not either of the first two sums had a carry bit.

Maybe a visualization would help:

Now the name Half-Adder makes sense. It takes two Half-Adders to make a full adder. The above chip will now be able to successfully add multi-bit numbers together. The only thing that is left to do is to convert this into a chip that can handle 16-bit calculations. To do that, you string together one half-adder and 15 full-adders together in a similar way to the above schematic. Resulting in a chip that is able to do 16-bit addition.

Leave a Comment