Why Binary?

The same sort of addition algorithm will work in any number base so why choose binary for computers?

The answer is that, initially at least, the choice of binary wasn’t at all obvious.

When Babbage planned his giant mechanical computer the obvious choice was decimal.

Why?

Simply because he could build cogs and gears that counted in lots of ten and this was the arithmetic system he was used to.

More to the point building a decimal computer allowed the values to be entered without the complication of converting to base 2. After all this is the scheme that was used by all of the mechanical calculators that predated Babbage’s idea and that came after it.

You could build a binary mechanical computer and it would have been simpler and perhaps might even have been within the capabilities of Babbage’s day but it wasn’t an obvious thing to do.

It wasn’t even an obvious thing to do in the early days of the electronic computer - but it probably should have been.

Remember the comment about only needing to know how to add together the symbols used in the base to add any two numbers together. It turns out that this is the clue as to why binary is the best choice. The algorithm for place value addition needs a table of how each pair of symbols adds.

For example in decimal you need the table:

   0   1   2   3   4   5   6   7   8   9
0  0   1   2   3   4   5   6   7   8   9
1  1   2   3   4   5   6   7   8   9   0/1
2  2   3   4   5   6   7   8   9   0/1 1/1
3  3   4   5   6   7   8   9   0/1 1/1 2/1
4  4   5   6   7   8   9   0/1 1/1 2/1 3/1
5  5   6   7   8   9   0/1 1/1 2/3 3/1 4/1
6  6   7   8   9   0/1 1/1 2/1 3/1 4/1 5/1
7  7   8   9   0/1 1/1 2/1 3/1 4/1 5/1 6/1
8  8   9   0/1 1/1 2/1 3/1 4/1 5/1 6/1 7/1
9  9   0/1 1/1 2/1 3/1 4/1 5/1 6/1 7/1 8/1



where the notation 9/1 means result 9 carry 1.

You can see that this table is quite large and it is what small children have to learn when they first start doing arithmetic. The size of the table gives you some idea how complex any circuitry or mechanism that does place value arithmetic has to be. There are obvious symmetries in the table that can be used to make the addition mechanism simpler but it is still quite a complex table.

Now compare this to a binary addition table:

   0  1
0  0  1
1  1  0/1


This is very simple. In fact it is as simple as an addition table can be and this makes it much easier to implement an addition mechanism in binary than any other base. 

Logic and switches

After George Boole had described his Boolean logic, and after various people had built logical machines based on it, the simplicity of the “true/false” algebra was beginning to be understood.

Charles Pierce sketched out how batteries and switches could be used to calculate logic but this was ahead of its time. Fifty years later in the 1940 Claude Shannon looked at the ideas again and noticed that he could build not just logic circuits using high and low voltages to represent true and false, he could also build arithmetic circuits.

All you have to do is write down the addition table for binary arithmetic for a single “digit” or bit:

       A + B = R
       0   0   0
       0   1   1
       1   0   1
       1   1   0

You might recognise this as the truth table for the Exclusive OR and this is indeed all that is needed to add two bits together - as long as you are prepared to ignore the carry.

In other words the addition table for binary symbols is the same as the Exclusive OR in logic.

If you want to generate the carry then you need to add another column to the logic table

       A + B = R C
       0   0   0 0
       0   1   1 0
       1   0   1 0
       1   1   0 1

Now you can see that the carry is simply an And operation.

Looking back at the addition table for binary you can now see that it can be represented using nothing but an Exclusive OR and an And gate.

Put the two together and you can add two bits and generate a result and a carry - this is called a half adder because it doesn’t deal with the problem of taking account of anything that might have been generated by an earlier pair of bits being added.

A half adder takes two bits and adds them to give a result and a carry

To create a full adder all we need to do is combine two half adders so that the first adds the two bits to produce a result and a carry and the second adds the result and the carry to produce a final result and a final carry.

A full adder takes two bits and the carry from the previous addition and produces a result and a carry

A little while after Shannon worked out that binary arithmetic was very easy to implement, the same idea was rediscovered by George Stibitz. He was musing on the problems of using relays in telephone circuits when he suddenly realised that he could use the open/closed positions as 0/1 and do arithmetic.

He quickly worked out a half adder and built it on his kitchen table using light bulbs to show the results. In 1940 he demonstrated a simple binary relay computer and in the audience was John Mauchly who went on to build, with John Eckert, the first electronic computer - ENIAC.

Shannon and his first adder

Decimal Not Yet Dead!

The big shock is that ENIAC, one of the first electronic computers, was a decimal computer not a binary computer.

Part of the reason was that the electro-mechanical computers that came before it were decimal but it must also have been that the advantages of binary just weren’t that obvious - even though this seems incredible.

The only exception to the rule that early computers were decimal was Conrad Zuse’s Z1 built in 1936. It also seems that he realised that binary was the way to build a computer in 1935, which gives him a strong claim to have thought of the idea before Shannon or Stibitz. Switching to binary was such a simplification that Zuse was able to build complete computers on his kitchen table.

Representing numbers in binary makes the connection not only with electro-mechanical switching circuits but with more advanced electronics. Once you settle on using binary it becomes very easy to find physical systems that have two states that can be used to represent 0 and 1. This makes creating storage and memory devices very simple.

You can use everything from holes punched in paper tape or cards to the direction of magnetisation to represent numbers in binary. However, there is a cost-efficiency. If you code a number using binary then each storage location stores a single bit but if you can find a way to store more than just two states at a particular location then you can store more data in the same space.

Put another way, a binary number has more bits in it than the equivalent decimal number has digits. For example, the decimal number 1234 is 10011010010 in binary. Binary numbers take more space and we trade space for simplicity. Some forms of Flash memory, for example, use three or more voltage levels to store data using non-binary bases.

So far no one has gone back to basics to build a decimal computer but one day, when binary computers have run out of steam, perhaps Babbage will be proved right.

For more on binary numbers and two's complement representation in particular, see Binary - negative numbers

Related Articles

Binary - negative numbers

Floating point numbers

Boolean Logic

Charles Babbage

Claude Shannon

Eckert & Mauchly and ENIAC

The Greeks, George Boole and Prolog

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

<ASIN:0262640686>

<ASIN:0750645822>

<ASIN:0297847384>

<ASIN:1568811608>

<ASIN:0070650500>

<ASIN:0425176444>

<ASIN:0767917073>

<ASIN:3540689028>

<ASIN:0780334264>

<ASIN:0789736136>

<ASIN:0767917073>

<ASIN:3540689028