2015-12-22

How we teach computers to do additions

Computers are really good at calculation. Well... they are computers after all, right?

But how do they know what "addition" means?
We had to find a way to be able to give them two numbers, and to get their sum as a result.

We're going to see what computers actually do when we ask them to perform an addition, and we will even build our own circuit that adds up integers of any size!

# Logic Gates

We are going to use (virtual) logic gates, because they are a nice way to abstract ourselves from the transistor level and use logic operations directly (logic gates can easily be made with transistors).
Some logical operations we could implement are AND, OR, NOT;
They will allow us to reproduce with a good accuracy the way computers work and how we can help them to count.

The way a logic gate works is pretty straightforward: we give some input(s) to the gate ( wire with or without electrical current ) , and the gate gives as an output in the form of electrical current too.

But let's view them in action to see what they can do: I will quickly present a few logical gates, with a truth table and a little circuit simulation that I wrote in JavaScript, where you'll see the diagram representation of the gate, with switches you can click (the inputs) and bulbs that will show you the output. I hope this will be helpful :)

# The NOT Gate

This one is really easy, it takes one input and returns the opposite: if the input is positive the output will be negative, and vice versa.

Input	Output
0	1
1	0

# The AND Gate

It takes two inputs, and the result is positive only if both of the inputs also are:

A	B	Output
0	0	0
0	1	0
1	0	0
1	1	1

# The OR Gate

No surprise, the result is positive only if at least one of the inputs is:

A	B	Output
0	0	0
0	1	1
1	0	1
1	1	1

# The XOR Gate

You might not know this logical operation, XOR, or exclusive-or, means that the output is positive if only one of the inputs is positive (so, it's like "A or B" without "A and B" ):

A	B	Output
0	0	0
0	1	1
1	0	1
1	1	0

# The NAND Gate

The NAND gate corresponds to not-and, it is the opposite of the AND gate: it will therefore give a positive output when at least one input is negative

A	B	Output
0	0	1
0	1	1
1	0	1
1	1	0

Nand gates (and NOR gates) are functionally complete, which means you can build any logical circuit using only such gates. We won't be using them, but it's nice to know that we could use only NANDs to get any kind of logical operation done :).

# Let's add bits: the Half-Adder

The first circuit we will build is called a Half Adder. It will allow us to give two inputs to the circuit, and get the result of their addition, in binary.

Our circuit will have two outputs, and we will use one of them for units , and the other one for the twos .
Here is the result we expect:

input A	input B	twos output	unit output	Corresponding Binary operation
0	0	0	0	0 + 0 = 0
0	1	0	1	0 + 1 = 1
1	0	0	1	1 + 0 = 1
1	1	1	0	1 + 1 = 10

you can see that the result will be the sum of A and B.

Now if we take a closer look at the outputs, we can see a recognizable pattern that we saw with some gates we talked about: indeed, the unit output corresponds to a XOR operation on the inputs , and the twos output corresponds to an AND operation!

So we can build the following circuit:

You can play with the inputs to check how the signal is modified and it's effect on the outputs.

We now have a circuit that is capable of producing the sum of two bits:

If all the inputs are off, all the outputs will be off too;
If only one input is on, no matter which, then the unit output will be on
If both outputs are on then the twos output will be on, and not the unit one.

Awesome, we can count from zero to two!

Well all right, I can understand if you're not convinced yet. But billions and billions are almost there!

# One step further: the Full-Adder

Now we need to step back a little bit.
We have our great half adder, it does it's job pretty well: adding two bits. But what about larger numbers?
We will want to add other numbers, and we need a more general kind of circuit for that.

The full-adder will be our building block for that purpose:
It's a circuit derived from the Half-Adder, but we add one input and rename the outputs:

Three inputs:

Carry in
Bit A
Bit B

and two outputs:

Output Bit ("unit")
Carry out ("twos")

The circuit will sum up the three inputs, it's almost the same as the Half-Adder:

if no input is on, no output is;
if only one input is on then only the unit output will be on
if two outputs are on (again, we don't care about which inputs, we just do their sum), then only the Carry out will be on,
and if all three inputs are on, then both outputs will be on.

We renamed the twos output because we don't want our full adder to deal with it by itself:

To put things in another way, the core of the Full Adder is the inputs A and B , and the unit output.

And then, the Carry in and Carry out are there to allow the chaining of several adders: that's how we can calculate numbers larger than two.
(the carry is indeed the same one as when we write an addition on paper, and an adder's carry out will be connected to another adder's carry in , we'll see that below)

# Additions

Here is a quick remainder on the fact that binary additions are the same than decimal ones:

With our decimal numbers we have to carry when the sum of the two digits is more than 9:

And with binary numbers, since each digit can only be 0 or 1, we have to carry when the sum is bigger than one:

and we need to keep doing it until we can actually stop:

and in binary:

And this is exactly what the Carry inputs/outputs are going to do for us.

# How it's going to work

Let me present to you our first version of the full adder:

Yes, this is just a black box for now, because we will first be sure to understand what we want from it:

each Full-Adder will take care of one order of magnitude in the operation: in other words, each Full-Adder handles the digits of one column of the addition, taking the carry (if needed) from the previous column, and sending it's carry (if there is one) to the next column.

Here is a -poor- representation of an addition as we would write it, overlayed by the action of each part of a full adder:

And This is how they connect to each other:

# Building the thing

Okay, it's time to get it done.
here is the table of truth we want:

input A	input B	Carry in	Carry out	Output Bit
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

You shouldn't even really look at it actually, that's a lot of numbers everywhere.

To achieve this result, we will need two Half Adder ( who would have guessed? :) . I will not discuss the logic of it, because it is pretty straightforward and way easier to understand by playing with it and studying the diagram.

Here it is, our magnificent Full Adder!

With one full adder we can't achieve much more than what we could do with one half adder.
But with several of them, the dream comes true :)

# 4-bits Full Adder

Finally we can start to add up bigger numbers.

With a 4 bits adder, we can deal with numbers up to 1111 (binary), that is 15 in decimal!

The thing is taking quite a lot of space, but I still want to be able to see the path of each wire for this one, so I put the adders in a diagonal way.
You can zoom on it, it will still render nicely.

The corresponding additions are written under the circuit, both in binary and decimal, so you can easily see what is happening.

Also remember that this little program is NOT using any '+' or any mathematical calculation to find the result: it is only designed to simulate the circuit that is drawn, and it writes the corresponding numbers from the values of the little bulbs (the outputs of our circuit)

The leftmost inputs represent the first number to add, and the rightmost ones the second number.

# n-bits Full Adder

Now that we have done that, we can build circuits of the size we want, that will be capable of adding any integer, for example a 64 bits Full Adder can handle numbers from 0 to 18,446,744,073,709,551,615 !

Just for the fun, you can generate a circuit of the size you want here:

Numberphile will never disappoint us: