28 Mar 2009

The Development of Digital Carry Technology

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]

The Development of Digital Carry Technology

Later we will discuss the philosophical implications of the carry technique for positional numeral systems. Here we will follow its development from primitive techniques to modern technologies.

First an Illustration:
Carrying-Capacity and Carrying-Over

Water falls. A small bucket catches some.

Quickly it fills.

It can carry only one liter. When it reaches its carrying capacity, it tips-over and pours into a larger container below it

Then the little bucket flips back upward, and fills again.

When it reaches its carrying capacity again, it carries-over its contents another time to the larger container. Now the larger one has two liters in it.

The process repeats. Eventually this larger container reaches its carrying capacity, which is ten liters.

Then it carries over its contents to another container that is ten times as large. This one fills at one hundred liters. So after ten carry-overs of the middle container, the largest one fills. But to get to that point, one hundred of the smallest containers must carry over their contents.

We can imagine this series continuing. Each time, the next largest container is ten times the size of the previous one.

Hands: The First Digital Computers

Counting and adding most likely we performed using hand signs, before written symbols were invented.

Each of our fingers we call a 'digit.' As well, each discrete numerical value we call digits as well. These discrete quantities are the formal foundation of digital technology.

We have ten fingers, so we can have ten different digits (as well as zero, or the absence of a digit)

But when we get to ten fingers, we run out of digits (although some cultures went to their toes. They have a base twenty numeral system). Thus we "carry" the ten-value so we can then count together "one and ten." The English word eleven comes from "ein lifon" or "one left over." Twelve comes from "twe lif" or "two over ten." And thirteen "three and ten;" fourteen "four and ten." Twenty comes from "twe-tig," or "two tens." Also, hundred comes from "ten times," meaning, ten times ten. Then we add back again at the first decimal place, saying, "one hundred and one..." and so on. (Eves 12b) So we see that our hands can only contain ten digit values. Then they must carry-over to the tens place. When that containment category is filled, then we must carry-over to the hundreds place, and so on.

The Abacus' Token Digits

Until Arabic numerals had arrived in Europe, this carry procedure was aided by the abacus. We use rows of objects. They could be pebbles in a sand tray, beads on a rack, and so forth. Each row has a carrying-capacity of ten objects. But the objects' values for each row ascend according to powers of ten. So one bead in the single digit place is worth only one unit. But one token in the tens place is worth the value of ten smaller ones, and so on.

So let's look at an abacus with beads sliding along rods. We will set it so that all the beads are to one side.

This setting will be equal zero. Now to make it display the value of one, we take a bead from the bottom row, and slide it to the left.

So to make it read two, we slide over another bead.

We will slide seven more to display nine.

Now, when we slide over another to make ten, we have reached the carrying capacity for that row. So it carries that value over to the next one. But we only move one bead from the next row. We keep in mind, however, that every bead in this row symbolizes ten beads in the first row.

Hence the abacus now displays ten, even though only one bead is found to the left.

Let's add eighty-nine to the ten already shown. We then obtain ninety-nine.

We will add one. But that causes us to reach our carrying capacity for the first row. So we will carry the value over to the next row.

To make the carry, we first empty the first row by moving all the beads to the right. Then we add one more unit in the next row. This one bead is worth the same as the ten beads below it that carried over.

But now we have reached the carrying capacity for the tens row. So we empty it. And carry that value to the top row. Here, each bead is worth ten from the middle tens-row, and a hundred from the bottom units-row.

So we see how the abacus allows us to mechanically carry-over values to the next place.

Using our Hands to Manipulate Abstractions:
Symbolic Computation

From around 700 A.D. to 1500 A.D., the abacus was gradually replaced by Hindu-Arabic numerals:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
These allowed us to perform the carry operations by manipulating symbols rather than object-tokens.

Engineered Mathematics:
Mechanical Digital Calculators

As we see, the carry method using symbols is still very mechanical. And it would seem that a machine could do such a thing if it were correctly engineered. Philosophers Blaise Pascal and Gottfried Leibniz endeavored to create such machines. Leibniz said: "It is unworthy of excellent men to lose hours like slaves in the labour of calculation which could safely be relegated to anyone else if machines were used." [Smith Sourcebook 181] We will detail the mechanics of their machines later. What we will focus-on here is a simplification of the carry mechanism. Imagine we are looking at a box. It displays two numbers beside each other. There is a crank to turn the numbers on the right.

Now consider if the top panel were transparent.

In fact, we will merely look inside the box. The white squares around the bottom number just tells us which number is being displayed at that time.

We will presume that each number 'pops' into place as we turn the crank. In other words, we cannot set the gears to display a value in between 1 and 2 for example. This will keep the device digital and not analog [we later discuss analog computation machines.] Now we will turn the crank to display the value for one.

We turn it again to show two.

We turn it seven more times to display nine.

Now, we see that the single tooth on the units dial is currently touching tooth a of the gear above it. So far, we have moved up to nine, and the top gear has not turned at all. But now we see that if we turn the units gear one more time, its tooth will press against top gear's tooth a. This will cause it rotate. But that will then make the left gear turn one place.

So this single tooth triggered the carry mechanism, which is the top gear. It carries over the value to the next decimal place. Its value reads only "1." But it is worth ten of the units. So in this way, mechanical calculators are able to carry-over values automatically. Recall that with the abacus, the human operator had to make the decision to perform the carry operation. But here the machine performs that action automatically for us. So we do not need to "think" in order to perform the carry. The machine does this mathematical work.

Binary Digitalization

We will now look at the mechanisms involved in the digital computation of electronic circuitry.

But before we do that, we will examine the binary representation and computation of quantities, rather than the decimal system we have been using so far.

In binary, our containers' carrying-capacities progress according to powers of two, and not to powers of ten. So one liter pours into the first bucket.

But it reaches its carrying capacity at two liters.

Then at two liters it carries-over its contents to the next container.

We only have two liters so far. But because we carried at two, we now represent it as 10 [See the entry on Leibniz' explanation of the binary system.] Then the first container receives another liter, but it is now at half its carrying capacity.

So we do not yet carry from the units place. Hence the binary number for three is "11." Yet when the first container fills for the fourth time, it will carry-over to the next one. But then this one will reach its carrying capacity, so then it spills into an even larger container.

There is only one 'load' or 'spill' in this lowest container. But it is worth four liters. Yet, there were two carries, so the binary representation is "100," (a zero for each carry) even though the decimal form is "4." We can perhaps see this operation better on a binary abacus. Instead of each row having a capacity of ten beads, they carry-over when they reach two. So we set the abacus at zero.

Then we move one bead to the left to display one.

Then we bring-over the other one. But that fills the carrying capacity.

So we will 'empty' or clear the units row, and carry-over its value to the next row.

Now we want to add another value of one. So we move one bead over on the bottom units row.

The abacus now reads '11.' We will add another unit. But then we reach our carrying capacity again.

So we empty the units row, and carry one unit over in the next row above.

But then we reach the carrying capacity for this row. So we carry-over again.

So we can better see this carry operation. We could perform it using symbols this way.

The Logic of Discrete Flow:
Digital Electronic Computation

Now we will turn to the electronic digital circuits that perform calculations for us using binary values.

We need only picture the electric flow as water. It moves through pipes. Either it flows or it does not flow. When it reaches a gate, there are certain conditions that allow the water to pass through it. Our gates will take-in two channels of flow. They follow two basic logical operations, conjunction and exclusive disjunction.

Let's first review the logic of these gates.

Image a crime. Our boss was murdered in his office. The previous day we got in fight with him about whether or not we were allowed to take-off work the next day. The whole office of co-workers heard the commotion. No resolution was met. And we stormed out furious, saying out loud, "I could kill him! Just kill him!" So the next day when he was murdered, we were arrested as a suspect. Now we stand trial.

We give the prosecution our alibi: "I was away-from the scene of the crime, and I was on vacation." We have sworn-in, so any lie is perjury. Clearly if we were clocked-into work and thus near the crime scene, we have perjured ourselves.

Or consider this other possibility. We took-off work, but went there anyway to say 'hi' to co-workers. But we do not want to place ourselves at the scene. So if we say that we were on vacation, but we were not at the scene, then again we have perjured ourselves.

So even though one part of our statement was true, the whole claim is false. Or, maybe what really happened was we had snuck-out-of work while being clocked-in. We do not want to admit this fact, because then the jury would question our character. So in that case, we were actually away from the scene, but we lied by saying that we were on vacation.

So again, even though one-half of the whole defense is true, the conjunction of the claims is false. The only way that both our alibi's claims would be true is if we were both on vacation and we were away from the crime scene.

There is a logic behind these truth calculations. This is the logic of conjunction. Our adding-circuit will have two gates. Both will operate according to a logical operation. One of them will be conjunction or 'AND' like the one above. Instead of "true" or "T," we will use "1." And instead of "false" or "F," we will use "0."

So we will have two input channels of water (or electrical) current. They are A and B. Their pipes are connected directly to an AND gate. But if no water is flowing through either of them, then nothing will be flowing-out on the other side either.

And even if channel A is flowing, still that will not satisfy the conjunction condition.

Likewise if just B is flowing.

Only if both A and B are flowing will the AND gate allow the current to flow through it.

Now there is another level of logic calculus involved. The other gate is the exclusive disjunction or XOR gate.

B's current will travel there.

And A's current will also.

The current flowing out of the XOR gate will give us the sum of the two A and B values. If they reach the binary carrying-capacity of two, then the AND output will tell us that we have carried to the next binary place.

Now we need to grasp the logic of the XOR exclusive disjunction gate. We saw that for conjunction, the two logical values of two propositions were conjoined together by "and." Now for disjunction, two logical values will find themselves at a cross-roads. They are joined by an "either/or, but not both" relation. Only one can be true. Imagine we mistakenly told the prosecution at one point in our testimony that we were near our work place, but at another part of our examination, we said that we were definitely not near the crime scene. The prosecutor then says, "Well, either you were at the scene of the crime, or you were away from it." If it is one option or the other, we cannot say it was neither one.

However, there is no contradiction if we say that we were not at the crime scene, because we were away from it.

And vice versa, we also do not contradict ourselves if we say that were at the crime scene, because we were not away from it.

However, we will contradict ourselves if we say that we were both at the crime scene, and we were away from it. For, it must be one or the other. They cannot both be true.

Now let's return to our "half-adder" circuit.

A and B are different variables. So we do not take their values together as though they were two digits of the same number. So if A is '1' and B is '0,' that does not mean we are inputting '10,' which has the value of two in binary numerals. Rather, A is its own value, and B is its own value. After the circuit computes their additive value, then the output displays a binary number. So if the sum category shows '0' and the carry output shows '1,' then in fact we do have the binary numeral '10,' which means two, that is, the sum of one and one. We will now examine the logical calculus that the circuit performs so that it always gives us the correct addition.

First we will input zero plus zero. There is no current flowing through the channels. Given the conditions of our logic gates, none will flow out either.

So zero plus zero is 0. Now we will add one plus zero by sending current through the A channel.

A's flow alone will not trigger the AND gate to send current through the carry channel. However, it will trigger the XOR gate. So current flows through the sum channel, and our result of one plus zero is '1.' We will now add zero plus one by sending current through the B channel, but not through the A channel.

Again, B's current alone is not enough to trigger the AND gate, so the carry channel is not activated. However, B alone satisfies the conditions for the XOR gate, so it activates the sum channel. Like before, we obtain the output '1' for zero plus one. Now we will add one plus one by sending current through both the A and B channels.

We are sending current from both channels to both gates. But the XOR gate will not allow current through if it receives flow in both inputs. This is like saying "I was at the crime scene while I was away from it." So we send no current out through the sum channel. That is no matter, because we have satisfied the conditions to send current through the AND gate. Hence we have carried the value from the first digit place over to the second place. We obtain our sum for 'one and one' as the binary digit "10," which is equal to two or the decimal '2.'

So we see that there is still a mechanics of sorts involved in electronic digital computation. When we added two values to one row of the binary abacus, we first cleared the filled row. Then we carried-over the value of two into the second row, using only one token, which symbolized two single units.

We see now that the clearing operation in the digital circuit is performed by the exclusive disjunction (XOR) gate. When it receives both, it sends out no current, or a zero value. But, when the XOR gate receives both channels of flow, that means the conjunction (AND) gate is also receiving both flows. When it receives both, then it sends out a single channel of flow. So the AND gate performs the carry-over operation. Together, the two logic gates co-operate to perform the two hand-motions we use when operating the abacus, or when symbolically writing "0" in the sum column, then writing a '1' as carried-over in the next digit place column.

The gear mechanisms condect the clear operation by circularly placing the 9 next to the 0 on the first wheel. The carry operation that transfered the first dial's total value was performed by having a single tooth move the next wheel once every full revolution.

The development of the carry technique has been one of increasing automation of the mechanical procedure. Now with digital circuits, we do not need to
a) say "ten and one,"
b) manually clear one row of abacus tokens and carry the value over to the next row,
c) use pencils and paper to write the carry in the next written column, or
d) use physical force to turn extra gears so that the value can be carried to another wheel.
We now push single buttons, and logically-processed electrical currents perform both operations without us needing to apply extra mental or physical effort.

Eves, Howard. An Introduction to the History of Mathematics. London: Brooks/Cole - Thomson Learning, 1990.

Leibniz. "Machina arithmetica in qua non additio tantum et subtractio sed et multiplicatio nullo, divisio vero paene nullo animi labore peragantur" in David Eugene Smith A Soucebook in Mathematics Transl. Mark Kormes. Mineola, N.Y.: Dover Publications, 1959.

The hand sign image is from:

Two of the logic gate images are from:

No comments:

Post a Comment