The hardware - The Computing Universe: A Journey through a Revolution - page 27

In binary:

100101
101
100101
10010100
1011100

×

(shiftedtwo places to theleft)

1

As this example shows, all we need to perform binary multiplication is an
implementation of these basic rules of binary addition including the carry and
shift operations.
We can perform a binary addition physically by using a set of strips of
plastic with compartments, rather like ice cube trays, and small pebbles
to specify the binary numbers. An empty compartment corresponds to the
binary digit 0; a compartment containing a pebble represents the binary digit
1. We can lay out the two strips with the numbers to be added plus a strip
underneath them to hold the answer ( Fig. 2.5 ).
The abstract mathematical problem of adding 1101 to 10110 has now
been turned into a set of real world rules for moving the pebbles. Remarkably,
with these simple rules we can now add two numbers of any size ( Fig. 2.6 ).
What this shows is that the basic operations of addition and multiplication
can be reduced to a very simple set of rules that are easy to implement in a
variety of technologies - from pebbles to relays to silicon chips. This is an
example of functional abstraction.
The word bit was used by Shannon as a contraction of the phrase “binary
digit” in his groundbreaking paper “A Mathematical Theory of Communication.”
In this paper, Shannon laid the foundations for the new field of information
theory. Modern computers rarely work with single bits but with a larger group-
ing of eight bits, called a “byte,” or with groupings of multiple bytes called
“words.” The ability to represent all types of information by numbers is one of
the groundbreaking discoveries of the twentieth century. This discovery forms
the foundation of our digital universe. Even the messages that we have sent out
into space are encoded by numbers ( Fig. 2.7 ).

Addends

Result

Fig. 2.5. Addition of binary numbers as
illustrated by pebbles.

Universal building blocks

With this introduction, we can now explain how a small set of basic
logic building blocks can be combined to produce any logical operation. The
logic blocks for AND and OR are usually called logic gates. These gates can
be regarded just as “black boxes,” which take two inputs and give one output
depending entirely on the inputs, without regard to the technology used to
implement the logic gate. Using 1s and 0s as inputs to these gates, their oper-
ation can be summarized in the form of “truth tables.” The truth table for the
AND gate is shown in Figure 2.8 , together with its standard pictorial symbol.
This table reflects the fundamental property of an AND gate, namely, that the
output of A AND B is 1 only if both input A is 1 and input B is 1. Any other com-
bination of inputs gives 0 for the output. Similarly, the truth table for the OR

Fig. 2.6. A Russian abacus, used in
almost all shops across the Soviet Union
well into the 1990s. It is fast, reliable,
and requires no electricity or batteries. It
was common practice in shops that the
results calculated by an electronic till
were double-checked on the abacus.