Sections 001/002 and 005/006 - Spring 2007
This chapter begins the discussion of computer hardware at its lowest level: digital logic. It examines the binary numbering system, and explores binary representations of numbers, text, sound, and images. Binary storage devices are discussed via on-off switches, magnetic cores, and transistors. A simple visual model introduces the transistor, which is then used to construct AND, OR and NOT gates. The chapter discusses Boolean logic and the sum of products algorithm for constructing a combinational circuit (a collection of gates) for any logical truth table. The chapter ends by building some non-trivial circuits: a test-for-equality circuit, an adder, a multiplexor, and a decoder.
• The Binary Numbering System
• Boolean Logic and Gates
• Building Computer Circuits
• Control Circuits
Information inside a digital computer is, ultimately, stored as a collection of binary data: ones and zeros.
Binary numbers are a base-2 positional numbering system. All numbers in binary are built out of two digits, instead of the ten digits that our normal numbering system uses. In decimal numbers, each place represents a power of 10: from the right, ones, tens, hundreds, thousands, and so forth. In binary numbers, each place represents a power of 2: ones, twos, fours, eights, and so forth.
Binary integers on a particular computer are represented as some sequence of binary digits. The number of digits limits the size of unsigned integer that can be represented. In addition to unsigned integers, computers need to represent signed integers, decimal numbers, and text. Signed numbers must include both the sign and the magnitude. Decimal numbers are converted to a binary form of scientific notation and normalized. Then the mantissa and base are stored. Text characters are mapped onto integers of a particular size: the ASCII encoding uses eight bits per character, and has a total of 256 different characters. The newer UNICODE encoding uses 16 bits per character, allowing for 65,536 unique characters.
Modern computers have many multimedia applications, so the efficient representation of sound and images has become of major importance. Both sound and photographic data are naturally analog and must be digitized for storage in a computer. A digital representation will be a “sample” of the actual data: the value of the analog data is sampled at regular intervals and the resulting discrete values are stored. Sound data is typically sampled by measuring its amplitude. The sound wave may be reconstructed to some degree of accuracy. When images are sampled, the color and intensity are measured at points spread evenly across the surface. Each sampled point is a pixel in the digital image. Sound and image data takes up a great deal of space: data compression algorithms are an important current area of development.
Electronic devices work most reliably when operating in bistable environments: when only two different electronic states need be distinguished. Thus computers use binary digits to represent data.
Magnetic cores and transistors are examples of electronic devices used to construct computers. Magnetic cores were used for computer memory between 1955 and 1975. Each bit of memory was stored by a magnetic field generated by passing current through the center of a metallic ring. The direction of current determined one of two detectable forms for the magnetic field. Transistors are solid-state devices that have two states, analogous to a light switch. In one state the transistor lets electric current flow, in the other it stops it. A second input line to a transistor causes it to change state. In modern computers, transistors can be printed photographically on silicon in very high density, allowing incredible miniaturization of computing devices.
Boolean logic is integral to computer science because the two values in binary representations map easily onto true and false. Operations on Boolean values include AND, OR, and NOT. The Boolean expression A AND B is true when A is true and B is also true. A OR B is true when either A or B are true (or both), and NOT A is true when A is false. These relationships are often captured with a truth table that shows the value of an expression for each combination of simple values.
A gate is a piece of electronics that maps multiple input lines into a single output line. Each line provides a binary input: either current is flowing or it is not. Gates may be built to simulate the effect of Boolean operations, where true/false values are mapped to 1/0, on/off electric signals. The existence of such gates frees a hardware designer from worrying about the detailed electronics of the ultimate device: the computer’s behavior may be specified entirely in terms of Boolean logic.
Circuits are constructed out of AND, OR, and NOT gates. The gates discussed in this section have no feedback loops where an output from a gate is fed back as input to an earlier gate. Every circuit constructed from AND, OR, or NOT gates may also be described as a Boolean expression or a truth table.
The sum-of-products algorithm constructs a description of what a circuit should do as a truth table, builds a Boolean expression for it, and thus determines the gates of the circuit. The algorithm first expresses what the circuit should do in terms of a truth table. Then each 1 output in the truth table is handled separately by building Boolean expressions using AND and NOT that produce that 1. These expressions are combined together with OR expressions. Then the circuit is constructed to match the Boolean expression. If there are multiple outputs to the circuit, then the process is repeated for each output.
The compare-for-equality circuit produces a 1 if both its inputs are 1, or if both its inputs are 0. Its Boolean expression is (a AND b) OR (NOT a AND NOT b). An N-bit compare-for-equality circuit may be constructed using the 1-CE circuit at each point. The second example of circuit construction is an addition circuit called ADD that performs binary addition on two unsigned N-bit integers. The ADD circuit is designed by, first, building the 1-ADD circuit that adds a single pair of binary digits, along with a carry digit, and then, producing the N-bit full adder circuit ADD by interconnecting N of these 1-ADD circuits.
This section provided a brief introduction to circuit design. It demonstrated how it is possible to implement high-level arithmetic operations using only low-level electronic components such as transistors. It also demonstrated how it is possible to reorient our viewpoint and raise our level of abstraction.
Besides arithmetic and logical operations, computers require other sorts of circuits. Control circuits determine the order of operations in a computer; two examples are multiplexors and decoders. A multiplexor selects one of its input lines and copies its value to its output line. Which line is selected depends on a set of selector lines which input a binary number mapped onto the input lines. A decoder takes in a binary number on its input lines, which is used to select one of its many output lines. The selected output line sends a 1 value, the rest of the outputs send 0. A decoder may be used to select one from among a set of circuits to activate: for instance, to choose the correct arithmetic operation, given a code for it. A multiplexor may be used to select which of a collection of memory locations should send its value to an arithmetic circuit.
This chapter has focused on the physical and logical underpinnings of modern electronic computers. Binary representations of data, and circuits constructed from transistors, are necessary to understand, but very low level. Later chapters discuss how the architecture and operating system build upon the topics from this chapter.