APPENDIX 9: TECHNICAL BACKGROUND TO
COMPUTING
1. Chapter 3 outlined sufficient of the key concepts
to provide a grounding for the discussion later in the Report.
This Appendix explores some of the technical background to electronic
digital computing in greater detail.
2. As noted in the body of the Report, computers
have become ubiquitous because they are universal. Ways have been
found to reduce almost every tasks to numbers. Computers can then
be programmed to do anything for which a suitable program can
be devised. To understand the ways in which a computer's silicon
chip can process numbers, it is necessary to start with some basic
properties of matter.
Materials and electricity
The composition of matter
3. In classical times, the Greeks deduced that
all matter was composed of atoms or tiny particles which could
not be further sub-divided. The work of Ernest Rutherford and
others in the 1920s showed that atoms are made up of smaller parts.
The sub-atomic world is perplexingly strange and not yet fully
understood. For the purposes of this Appendix, however, atoms
can be envisaged as a nucleus surrounded by a cloud of electrons.
4. The nucleus is made up of positively-charged
protons together with, in all but the lightest elements, some
neutral neutrons. That positive charge is balanced by the surrounding
cloud of negatively-charged electrons, one for each proton in
the nucleus. It is the number of protons in the nucleus and the
balancing electron shell that give each element its distinctive
properties. There is, however, no distinction at the sub-atomic
level: an electron in an atom of, say, iron, is no different from
an electron in an atom of sulphur.
Electricity
5. In some elements, the electrons form a tight
shell round the nucleus. In others, the electrons are held less
tightly and, under appropriate circumstances, are able to pass
between atoms. The flow of electrons through a chain of atoms
constitutes an electric current. The flow of water provides a
useful analogy. Imagine running a bath. First of all, there has
to be some pressure in the system. For electricity, the pressure
comes from the magnetic force (from a dynamo or generator) or
chemical force (from a battery or fuel cell) with which the electrons
are pushed and is measured in volts. Because this pressure exists
even if no current is flowing, voltage is sometimes referred to
as the potential difference.
6. The bath tap is the switch in the circuit:
when it is turned on, water flows. The power of the system (measured
in watts) is obtained by multiplying the force (voltage) with
which electrons are pushed by the rate at which they flow (i.e.
the number per second) as reflected in the measure of amps. That
flow is reduced by resistance in the circuit. Electrical resistance
is measured in units called ohms. The electrical equivalent of
the total volume of water delivered to the bath is the total number
of electrons — as reflected by the measure of coulombs.
7. Individual electrons move relatively slowly.
However, the effect of the current is felt at the other end of
the conductor much more quickly: each electron pushes the next
one along. Even so, an electrical signal does not propagate instantaneously.
Its speed is substantially less than the speed of light (the fastest
anything can travel) and is a significant constraint in the design
of microelectronic circuits.
8. Current electricity, as described above, needs
to be differentiated from static electricity. Under certain circumstances
(normally involving friction of some sort), atoms in a substance
can be stripped of some electrons. The effect of atoms seeking
to regain their lost electrons can be felt as a static electric
charge or field.
Conductors and insulators
9. Elements which permit the flow of electricity
are called conductors. All metals conduct electricity, as do some
non-metallic elements such as carbon. Elements which do not permit
such a flow of electrons (for example, sulphur) are called insulators.
Chemical compounds (in which atoms of different elements are bound
together by shared electrons) may also be either conductors or
insulators.
Semiconductors
10. Between conductors and insulators, there
is a third category of materials which, depending on the circumstances,
can act as either conductors or insulators. These materials may
be either elements (such as silicon, provided it is in crystalline
form[119])
or compounds (such as gallium arsenide).
11. The conductivity of semiconductors can be
substantially altered by doping them with small traces of other
substances. These dopants make the semiconductor either richer
(n-type) or poorer (p-type) in free electrons — that is,
electrons that are not tightly bound to the nuclei and are therefore
available to conduct an electric current.
Transistors
12. Transistors are, as described in paragraph
3.13, combinations of doped semiconducting materials through which
the flow of electricity can be regulated by a control input at
the gate. In early (bipolar) transistors, the control input was
a small current. In modern field-effect transistors (FETs), the
control is by an electric field (see paragraph 8 above) generated
by a voltage or potential difference at the gate. As this field
is exerted through an insulating layer, no current actually flows
in exercising the control of the main current through the transistor.
13. Transistors, like the thermionic valves they
have largely replaced, allow the current flowing through them
to be controlled smoothly from zero to the maximum permitted by
the circuit into which they are connected. With a few minor exceptions
(for example, to deal with the input or output of sound), the
transistors in microprocessors are used as simple switches. They
are either off or on depending on whether the current flowing
through them is at either zero (or close to zero) or the maximum
(or close to it).
Binary numbers
14. Our normal counting system uses a base of
ten. That is, any number can be represented by a combination of
the ten digits zero to nine set out in columns. By convention,
digits in the right hand column represent units. Moving to the
left, numbers in each succeeding column are worth ten times the
preceding column — units, tens, hundreds, thousands and
so on. The number written 107 is one 100, zero 10s and seven units.
15. Computers operate with binary numbers, that
is numbers with a base of 2. Any number can be represented by
digits zero and one arranged in columns in which the right hand
column is for units and each succeeding column is worth twice
the value of the preceding one. The number 107 in base ten is,
in binary notation, written as 1101011 being one 64, one 32, zero
16s, one 8, zero 4s, one 2 and one unit[120].
Thus any number may be represented by a series of transistorised
switches that are on or off. This avoids the potential for inaccuracy
there would be in having to differentiate between a transistor
being, say, either 60% or 70% on.
Computer logic
16. Moreover — and crucially — calculations
with binary numbers can be undertaken by the application of simple
logical rules rather than any arithmetical skills. Consider, for
example, the addition of two single digit numbers represented
by A and B.
Addition in base 10
17. In everyday base 10 numbers, A and B could
be anything from 0 to 9 and the sum could be anything from 0 to
18. The answer could thus have 0 to 9 units with either 0 or 1
tens. (In a larger calculation, the latter would be carried over
for the next stage of the addition.) To perform this addition,
an operator needs either to know (in computer terms, this would
mean searching a provided look-up table) that, say, 7 added to
9 gives the answer 6 units with 1 in the carry column or to work
from first principles by counting out 7 units and 9 more units
and then counting off the total. If that count was less that 10,
that would be the total with 0 for the carry over. If the count
reached 10, the carry over would be 1 rather than 0 and the count
would then be restarted to establish the number for the units
column of the answer.
Binary addition
18. In binary numbers, the digits A and B could
only be either 0 or 1. The only four possible input positions
are as set out below, together with the answers in each case.
| INPUT
| ANSWERS |
| A | B
| Sum | Carry
|
| 0 | 0
| 0 | 0
|
| 1 | 0
| 1 | 0
|
| 0 | 1
| 1 | 0
|
| 1 | 1
| 0 | 1
|
19. While a computer could be designed to undertake this addition
either by using a look up table or from first principles (as described
in paragraph 17), it is more straightforward to obtain the answers
by logical operations.
Boolean logic
20. Those logical operations are called Boolean algebra after
the 19th Century English mathematician George Boole. His highly
influential book, An Investigation Into the Laws of Thought,
on Which are Founded the Mathematical Theories of Logic and Probabilities,
published in 1854, laid the foundations for absolute rigour in
logical thinking.
21. Logical statements are either true or false. The train
of a logical argument can be written down using four operators.
(a) NOT operates on a single input and reverses
it. If A is true, NOT A is false.
(b) AND operates on two inputs. A AND
B is true only if both A and B are true. If one or both are false,
A AND B is false.
(c) OR also operates on two inputs. If either A or
B is true (or, indeed, if both are true), A OR
B is true. A OR B is false only
if both A and B are false.
(d) XOR (exclusive OR) is a constrained version of
OR. A XOR B is true only
if one or other of A and B is true. A XOR
B is false if A and B are either both true or both false.
22. If false and true are represented by the digits 0 and
1, the required answers in paragraph 18 above can be achieved
by applying Boolean logic to the inputs A and B:
(a) Sum = A XOR B; and
(b) Carry = A AND B.
23. In practice, it is of course rare for additions to involve
only two single binary digits or bits. Applying the same general
principles, however, more complicated Boolean formulæ can
be derived to deal with additions where it is necessary also to
take account of the carry over from a previous stage in the addition.
Equally, Boolean formulæ can be derived to deal with subtraction,
multiplication and division.
Logic gates
24. Boolean logic can be replicated by transistors connected
together so that the output of one controls the gate of another
and so on. Two transistors are needed to build an inverter or
logic element that will output 0 if its input is 1, and vice
versa. (This is the NOT function
referred to above.)
25. Six transistors are needed to build either an AND
logic element whose output is 1 only if both of its inputs are
1, or an OR logic element whose
output is 1 if either or both of its inputs are 1. An XOR
logic element may be constructed from two NOT,
two AND, and
one OR logic elements:
A XOR B is identical to (A AND
(NOT B)) OR
((NOT A) AND
B) where, by convention, the expressions within the deepest levels
of brackets are dealt with first.
Abstraction
26. Such logic elements are called gates — not to be
confused with the control gates of individual transistors. Their
configuration is well-established, and microprocessor designers
do not have to worry about how to design, for example, an AND
gate (let alone the transistors from which it is made). For
design purposes, an AND gate can
be regarded as a black box with two inputs and one output. The
output will be on only if both the inputs are on.
27. The mechanics of a computer (the hardware) are characterised
by levels of such abstractions. A typical hierarchy might be:
(a) transistors;
(b) logic gates and memory cells;
(c) single-bit adders;
(d) multiple-bit adders;
(e) arithmetic logic units (ALUs);
(f) central processor units (CPUs);
(g) integrated circuit chips;
(h) circuit boards; and
(i) the computer or other product.
Software
28. Computers and microprocessors are multi-purpose machines.
They can do a wide variety of things, effectively limited only
by the ingenuity of those writing the instructions for the machines
(also known as programs or, in contrast to the hardware, the software)
and arrangements for interfacing the computer with the real world.
However, the division between hardware and software is not absolute.
All hardware has at least some functions built in at the design
stage. At the very least, the machine needs to await its first
instruction when it is turned on, to be able to recognise that
instruction when it arrives and be equipped to perform the intended
action.
29. In practice, computer designers simplify the programmer's
task by generally building in wide range of arithmetic and other
functions that can be executed by relatively simple program instructions.
This does, however, add to the complexity of both design and operation.
An alternative approach is Reduced Instruction Set Computing (RISC)
where the designer limits the built-in routines to the essential
minimum. Generally, such a computer will run faster although more
complicated routines will require more programming and thus more
instructions to execute.
Machine code
30. The machine code (a series of standard length binary numbers)
that controls the step by step operation of computers is highly
detailed. A sequence to add together the numbers stored in two
memory locations and store the result in a third location might
be as below.
| Code | Action[121]
|
| 00100110 | Copy the number stored in the memory location specified by the next two numbers into the CPU register A[122].
|
| 11011010 | First part of memory address.
|
| 01011101 | Second part of memory address.
|
| 00100111 | Copy the number stored in the memory location specified by the next two numbers into the CPU register B.
|
| 10011110 | First part of memory address.
|
| 11010101 | Second part of memory address.
|
| 00011011 | Add the numbers in CPU registers A and B, and copy the result into the memory location specified by the next two numbers.
|
| 11011011 | First part of memory address.
|
| 01011111 | Second part of memory address.
|
High-level language
31. In the early days of computing, code had to be written
as a string of numbers as in the first column above. Apart from
being laborious, it was very easy to make mistakes, any one of
which would have unexpected and often catastrophic consequences
for the application. It was not long before software was written
which enabled programmers to write in more natural (although highly
structured) high-level language, letting the computer work out
the consequent machine code.
Hierarchy of software
32. In the same way as hardware (see paragraph 27 above),
software has a hierarchy of abstraction. Once written and found
to be robust, program elements or modules do not need to be reinvented.
They can be reused without any thought about their internal structure,
thus simplifying the generation of new applications which nowadays
typically require tens of million lines of high-level programming
languages.
Algorithms
33. At a high level of abstraction within the overall program
(or any constituent module) is the algorithm — the problem-solving
logic that is implemented by the detailed programming. While the
programming will be specific to the processor on which the software
is to be run, algorithms are not.
34. For example, a common task in computing is to sort items
into order. The simplest way of doing this is to work through
the list item by item, compare each one with the next one and,
if they are in the wrong order, swap them over while noting that
a swap has been made. On reaching the end of the list, the process
is repeated until no swap has to be made showing that the list
is in right order.
35. While this bubble sort[123]
is easy to program, it is very inefficient for more than a few
items. There are other sorting algorithms offering greater efficiency
for longer lists. Although more complicated to understand[124]
and program (and may consume more machine resources while they
are running), they are worth implementing in appropriate cases.
36. Picking the right algorithm — which may mean developing
a new one — is thus a crucial part of software development.
(Algorithms are also an integral part of the routines a chip designer
builds into the hardware, as discussed in paragraphs 28 and 29
above.)
Implications for the user
37. Thanks to the skill of programmers and the evolution of
user-friendly and more intuitive interfaces between user and machine
(facilitated by the increasing power of microprocessors which
can now deal with many millions of instructions per second), it
is not necessary to know any of the above to use computers. Users
can benefit from the many sophisticated applications available,
without concern for their delivery.
38. However, this highly desirable ease of use means that
it is easy to ignore the astonishing range of technical and intellectual
achievements that computers embody.
119
i.e. the atoms have settled into a regular three-dimensional lattice. Back
120
There are various conventions - beyond the scope of this note
- for also dealing with fractions, negative numbers and very large
numbers. Back
121
The code results in the action indicated only because that is
what the designer has built into the device so that the necessary
interconnections are switched on in response to the input. Back
122
Or, to be absolutely precise, set the series of transistorised
switches in CPU register A on or off (see paragraph 15 above)
in the same pattern as found at the specified memory location. Back
123
So called because items bubble up through the list on each pass. Back
124
In some cases, requiring substantial mathematical expertise. Back
| 
