Foundations of Computer Science/Computing Machinery

Computing Machinery

We have studied some fundamental principles of computing and seen the power of computing demonstrated in powerful technologies that operate on these principles. At the beginning we imagined that computing can be done purely mechanically and blindly through symbol manipulation if we can build a simple device that is capable of some simple tasks. In this lesson we will study the history of the development of computers and the principles on which all modern computer hardware operate. We will see on the physical layer a computer is nothing but a simple device that follows simple rules to manipulate two symbols.

Computer Hardware

Computer hardware that can carry out computation automatically has been around for too long. There is a short history from early computers to modern computers we have today.

Mechanical Computers

Charles Babbage invented the concept of a programmable computer and designed the first mechanical computer in the early 19th century. His difference engine and analytical engine are mechanical devices designed to tabulate polynomial functions. The input to the machines are programs and data on punched cards and the output number can be pouched onto cards or directed to a printer, a curve plotter and a bell. The machines use ordinary base-10 fixed-point arithmetic. Charles Babbage's engine is the first design for a general-purpose computer that is Turing-complete.

Analog Computers

In early 20th century mechanical analog computers are designed to perform increasingly sophisticated computing, e.g. solving differential equations by integration. Analog computers use continuously changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model/quantify computation, which lack the accuracy of modern digital computers.

Digital Computers

The world's first fully automatic digital computer is the electromechanical programmable computer Z3 made by Konrad Zuse in 1941. Z3 uses electric switches that drive mechanical relays to perform computation. It replaces the decimal system with the binary system and pioneered the use of floating point numbers. Program and data are stored on punched film. The distinction between a digital device and an analog device is whether the representations of values are discrete or continuous. For example, black and white are discrete values but their infinite number of grayish colors (a grayscale).

Electronic Digital Computers

The world's first electronic digital programmable computer is Colossus, built with a large number of valves (vacuum tubes) in 1943. The design was all electronic and was used to break the German Enigma code.

Transistor Computers

From 1955 vacuum tubes were replaced by transistors in computer designs resulting in smaller, more reliable and more power efficient second generation computers, giving rise to the "second generation" of computers.

Integrated Circuit Computers

The invention of integrated circuit in 1952 ushered in a new era of computing machinery - micro-computers. Microprocessors with integrated circuit are used to build common computing devices you see today: desktop computers, laptop computers, phones, and greeting cards.

Principles of Digital Computing

The mathematical foundation of digital computing is Boolean logic invented by George Boole. Claude Shannon proved in the 1930s that electronic circuits can compute in binary using Boolean logic, which becomes the fundamental principle/idea behind all modern computing devices.

Boolean Algebra

Boolean algebra has three operations AND, OR, and NOT on two values: true and false. The rules for evaluating the three operations are shown in the figure.

A Boolean operation operates on Boolean values and always result in a Boolean value. For the AND operation the result is true only when both operands are true. The OR operation, on the other hand, only results in a false value if either of the two operands is false. The NOT operation takes one operand and simply negates it. We will see if we can build electronic circuits that implement the three operations we can build circuits that can perform all kinds of arithmetic and logic functions.

The three boolean operations can be implemented physically using transistors. A transistor is fundamentally a tiny switch as shown in the figure.

When a high voltage (logical 1) is applied to the control pin the switch is closed connecting the in pin directly to the out pin. Transistor operates on two voltages: high and low, which can be used to represent two different logical values: true and false or two binary values: 1 and 0. We will use a high voltage to physically represent a logical 1 and a low voltage a logical 0.

Transistors and Logic Gates

Transistors are simple devices that are tiny, but it is fundamental building block of electronic circuits. For example we can build a device called NOT gate using a single transistor as shown in the figure.

If we treat what's inside the red box as a unit it behaves like negator, which is known as an NOT gate in digital logic design. As shown in the truth table for this device (next to the figure) when the input is logical 1 the switch is closed connecting the output to the ground dragging the output voltage to a low signifying a logical 0. On the other hand, when the input is logical 0 the switch stays open which result in a high voltage on the output line because it is connected to the power through a resister and without a current the resister will not cause any drop in power. Once this device is built we can use it as a building block to construct more complicated circuits. Will use the following symbol to represent a NOT gate.

With transistors and the NOT gate we can build a device that performs the AND operation.

As shown in the figure the device performs exact an AND operation. The output is logical 1 (high voltage) only when both inputs are logical 1, which causes both switches to close dragging the output before the NOT gate to low. The NOT gate then negates the output to be high voltage or logical 1.

Similarly we can build a device for performing the OR operation.

A shown in the figure this kind of parallel structure guarantees that the output is high voltage as long as any transistor is closed. In other words, the relationship between the two inputs and the output is a OR logical function.

Gates to Circuits

With the three basic gates (AND, OR, NOT) we can build any combinational logic circuit. A circuit consists of input wires, gates connected by wires, and output wires. Once a circuit is designed it can be viewed as a black box that implements some logic mapping input to output. Here is the standard circuit construction algorithm:

1. build a truth table from the desired logic
2. build a logic expression in sum-of-products form
3. convert the expression to circuit design using gates

We want to construct a circuit that test the equality of two bits. The two inputs are the two bits represented physically by a high voltage (logical 1) or a low voltage (logical 0). According to the desired logic of the circuit we can draw the following truth table:

The first two columns enumerates all possible value combinations of the two input lines. The output is logical 1 (true) only when the two inputs are the same. Based on the truth table, we can derive the following logic expression (sum-of-products form):

(a AND b) OR ((NOT a) AND (NOT b))

To derive the sum-of-products form we check lines in the truth table with a logical 1 for the output. We know the input combinations shown in these lines are supposed to cause the output to become logical 1. We can represent each of these lines using a logic expression, for instance, (a AND b) represents the last line because when both a and b are logical 1 the expression evaluates to a logical 1 according to the definition of the AND operation. Similarly ((NOT a) AND (NOT b)) represents the first line. If we combine the two cases, we can represent the desired logic using a single expression: (a AND b) OR ((NOT a) AND (NOT b)). If we plugin the inputs for the cases in the truth table this expression should evaluate to the same desired output values for the corresponding cases. Because we know how to build the devices (gates) that implement AND, OR, and operations we can build a device that can compare whether two bits are equal. This is device will be able to perform this kind of operation purely mechanically (blindly) because it doesn't know the meaning of the operation.

Using the same methodology we can gradually build more and more complicated circuits. For example we could build a device that can add two binary digits: one-bit adder. It is just a matter of figuring out the desired logic and construct the device using the building blocks we already know how to make.

Once we get the sum-of-products form of the logic expression from the truth table it is straight forward for us to construct the circuit because all we need are the three types of logic gates and wire connection. The following figure shows the design of a one-bit adder (with carry-in) circuit using the three basic logic gates.

We can construct multi-bit adders by connecting multiple one-bit adders. The following figure shows that a two-bit adder can be formed by connecting the carry-out of the first one-bit adder to the carry-in of the second one-bit adder.

A Simple Flow Chart for a Lamp Diagnosis Algorithm

A Flow Chart for the Algorithm that Computes N! (factorial of N)

Computer data storage