16: Digital Adders
After this quick séance in physics, let’s get back to our gates.
Now that we have the basic building blocks of a computer, we can begin building what is known as an integrated circuit (IC). An IC is the eventual physical realization of parts of a computer so that all of the wires, transistors, resistors, etc., that we will be designing using logic gates can be found within ICs. The most famous type of IC that exists is likely to be the one known as the central processing unit, or CPU for short, which is the most important part of any computer. To build one, let us first create a circuit that adds two numbers together.
We’ll put aside the schematic of a multiplexer for now, which we have built two articles past. Let us instead think about computation: The central use of computers when they were first developed is computation, meaning nothing more than applying mathematical operations to numbers. Before computers, there were people who sat on small desks, basically computing endless series of calculations which would be used for engineering handbooks or real-time space missions.* But the step from a human person computing to a general purpose computer computing, is huge.
To slowly automate tedious computations, we begin by developing a circuit to automate addition, one of the most basic operations in mathematics. It is implicitly the first function we learn as babies, so it is fitting to start here.
Adding two small numbers in our heads is pretty straightforward: 2+3, 6+9, and even 13+24 are still “easy.” Recall how to add two numbers on paper, even when the two numbers are large: We write the two numbers needing addition stacked on top of each other and add digits on the same vertical together, starting from the right. Whenever the sum of two digits in the same vertical line equals 10 or more, we carry the 1 over to the next digit to the left. Afterward, we do the same operation on the vertical digits once to the left, and so on, until the two original has been fully added together. Anyone with this basic skill can safely add any two numbers together:
123476832047
51728437642 +
------------
175205269689As it turns out, computers do something frighteningly similar but with binary representations of numbers.
Remember that digital logic gates can only detect current being present or not, and cannot actually express numbers. For this reason, a computer “counts” from zero to some arbitrary number using a binary system. Humans don’t use this system, but most likely only because we were endowed with 10 fingers, instead of 2: one, two, three, etc. could easily be expressed by the amount of fingers we have pen. In time, once we mastered counting using our hands, we could extend addition beyond our ten fingers on our hands, meaning we counted to ten, eleven, twelve, etc. When we needed to write numbers, we never spelled them out with alphabetic characters but instead created our own symbols for these strange objects: 0, 1, 2, and so on. This way, a collection of “characters” can represent a number.
Clearly, our system hits a limit for numbers larger than nine (9). We don’t want to memorize an infinite number of symbols to express all the numbers. To mediate this deficiency, we chose to reuse the symbols we already used and combined two of them to create a new number: …8, 9, 10, 11, 12, and so on.
To be explicit: once we run out of symbols on the rightmost digit, we set that symbol to 0 and add a new character on the leftmost side.
This is a genius move. When we count to 19, we don’t simply add another 1 on the left side. We now count on the symbol to the left of the symbol that “hit the upper limit of characters”. In other words, we count from 19 to 20. And once that left symbol is depleted, as well as the first symbol (99), only then do we add another character on the left side to get 100. And so on.
This is the decimal system of counting, deca- coming from Latin meaning “ten”, standing in for the ten symbols we use (0123456789). Because computers have only two characters, 1 and 0, they necessarily must use a binary system of counting. In other words, computers do their math with binary numbers and then display the decimal number for us to read it more easily.
So if we were to count in binary, we would count 0 (0), 1 (1), 10 (2), 11 (3), 100 (4), 101 (5), 1100 (6), 1101 (7), …. When talking about binary numbers, we usually specify a maximum number of bits (binary digits) before we express the number. So if we were to specify that a number has four bits, then if we were to express the ‘full’ number 100 (four), we would express it as 0100. This helps us decide where one number starts and where one ends when presented with a long stream of 1s and 0s (also known as delimiting).
But in this transliteration, from our decimal system to the binary system, there is no reason why we cannot agree that 100 is equal to 6 instead of 4. We can do so in a systematic way by shifting the number the bits expressed by one bit. 0110 (6) can, in theory, express 12 if we agree to “shift” the bits by one space (1100 is 12). Because four bits can only express sixteen numbers (zero-fifteen, included), the number that formerly expressed fifteen (1111), after shifting the bits by one space, would now be expressed as 1110, fourteen.
Get 365 Days of Computer’s stories in your inbox
Join Medium for free to get updates from this writer.
These systems of counting are all different encodings. Many ways of “counting” were invented for various applications. In computers, however, the “standard” form is used, the one I introduced above, and in the image above, is known as the binary-coded decimal (BCD). We will continue to use this whenever we talk about binary numbers. BCD describes how one counts from zero to some higher-up number. To be perfectly clear: when counting on three bits in BCD mode, you count 000, 001, 010, 011, etc., just as we have above.
In other encodings such as the Gray code, you would instead count in such a way that only 1 digit ever changes from one number to the next: 001 (1), 011 (2), 010 (3), 110 (4), etc. Once the rightmost digit has been turned into a 1, we can reflect the counting on the last two digits so that we “count backward” (110, 111, 101, 100) to express any higher numbers. This is why this encoding is also called reflected binary code. There are instances in other fields of engineering that find application with this encoding. But luckily, not in computers.
Anyhow, let’s now finally build an adding circuit. We start with the circuit known as a 1-bit half-adder in BCD mode:
This circuit accepts two inputs, input1 & input2/A & B, which can only take on values of 1 or 0. Below is the truth table of the circuit (you can verify it yourself by tracing the inputs through the circuit):
If you interpret the A and B numbers as decimal 1s and 0s, you can tell that it’s reading the sum and carry in binary (1+1 = 2 = 10 in binary). The carry, as you can imagine, has the same function as our carrying over a 1 when doing addition on paper. This circuit is known as a half adder because it doesn’t cover all possible outputs when reading the sum output, i.e. it cannot accept a carry from a previous calculation.
To be able to accept a carry, we build a slightly modified circuit which we call the full-adder, which can take a carry into consideration so that it can now add two binary numbers together, along with a carry value from a half-adder.
In other words, if the circuit is given a carry from a previous component, such as the half-adder, it can now take bigger numbers into consideration: The half-adder adds the first two digits of a number together, then passes the carry to the full adder, which then calculates the next digit in line. Like this, instead of adding two numbers with only 1 digit, we can now add two numbers with 1 digit each, which outputs another carry value.
With this technique, we can add any two arbitrarily large numbers together, provided that we have the resources to keep adding full adders to our circuit. For a simple electronic circuit, then, as long as we input the correct binary numbers, we will always get the correct answer, generated at the speed at which electrons travel. This is why computers are so fast at adding numbers together. The same goes for the other basic mathematical operations if we can build circuits that can do them.
The whole circuit described above is known as a ripple-carry adder, named so, because the calculation of any full adder depends on the result from a previous adder.
With a bit of thought, it is clear that this type of addition is sequential, and hence inefficient: The final adder can only be computed once all of the previous adders have completed their computation. This slows down our addition of numbers so that for adders that are 64 bits long, it will take us 64 steps to execute the circuit. This is cumbersome and slow. As it turns out, we can construct a circuit (details not covered) that calculates the carries on each bit so that an addition can be computed in much fewer separate steps. This circuit is known as the look-ahead adder:
In this adder, additional logic has been squeezed between each half/full adder, which computes whether it outputs a carry. In the second step of the computation, the circuit calculates the sums of all bits while at the same time taking the carrys into consideration. This way, all computations can be done in parallel (meaning at the same time): we do the carry computation first and follow it up by computing the full sum.
And that it: We can now add numbers using only rocks and electricity.
This is the first step in building an intermediary circuit known as an arithmetic logic unit (ALU), which does all direct calculations of this sort, which is also a subcomponent of a CPU, . In a way, we have already built a primitive ALU because our circuit can add two numbers together, which means, well, it’s a unit doing arithmetic. But there are the operations of subtraction, multiplication, and division that can also be included in an ALU. For these, other dedicated circuits have been designed, which are, unlucky for us, significantly more complicated than what we have here. We will cover them briefly nonetheless.
Footnotes
*Because of the triviality of the task, as well as sexism, this job was usually handed off to women
