# CS10051 Review - Chapter 4 - Paul Durand

Sections 001/002 and 005/006 - Spring 2007

## Concepts

### Overview

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.

### Chapter Objectives

• The Binary Numbering System

• Boolean Logic and Gates

• Building Computer Circuits

• Control Circuits

### The Binary Numbering System

Information inside a digital computer is, ultimately, stored as a collection of binary data: ones and zeros.

#### Binary Representation of Numeric and Textual Information

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.

#### Binary Representation of Sound and Images

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.

#### The Reliability of Binary Representation

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.

#### Binary Storage Devices

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 and Gates

#### Boolean Logic

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.

#### Gates

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.

### Building Computer Circuits

#### Introduction

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.

#### A Circuit Construction Algorithm

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.

#### Examples of Circuit Design and Construction

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.

#### Summary

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.

### Control Circuits

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.

#### Conclusion

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.

## Key Terms

• Analog: Containing values that may take on any continuous value.
• Binary numbering system: A system of numbers made out of two values: 0 and 1.
• Bistable environment: An electronic setup that requires distinguishing two electric states from each other, and maintaining the two separate states.
• Bits: Binary Digits: a set of individual binary digits, each of which is 1 or 0.
• Boolean expression: An expression that evaluates to true or false, constructed of true-false predicates and the Boolean operations.
• Boolean logic: A logical system that describes rules for working with two values: true and false.
• Circuit: A collection of gates that together computes something.
• Control circuits: Circuits whose purpose is to control the order or choice of what a computer is doing.
• Data compression: A process of reducing the amount of space required to store large data files, sometimes without loss of detail, and sometimes with loss of detail.
• Decoder: A control circuit that turns on one of its outputs when given an input that matches it.
• Digitize: To transform analog data into a digital format.
• Gate: A hardware device which implements a boolean logic operation, e.g. and, or, not, xor...
• Hardware design: The process of designing circuits and other physical computer systems.
• Magnetic core: A form of memory storage from the past that used small iron disks to generate magnetic fields in response to electric currents.
• Mantissa: The base value of a decimal number written in scientific notation.
• Multiplexor: A control circuit that selects one of its input values to pass through to its output, depending on a code passed in along selector lines.
• Pixel: A single point sampled from a photographic image and stored in the digital format.
• Sampling: The process of reading values from analog data at regular intervals and using the sampled data to represent the analog version.
• Sum-of-products algorithm: A process for determining a circuit by starting with its truth table and then generating a Boolean expression for it.
• Transistor: A solid-state electronic device that either allows a current through or blocks it, changing state in response to an electronic control input.
• Truth table: A table showing the truth values of a Boolean expression for every possible combination of inputs.

## Things You Should Know How To Do

• Convert base 10 integers to base 2 integers
• unsigned to unsigned
• sign-magnitude to sign-magnitude format
• sign-magnitude to twos complement format

• Convert base 2 integers to base 10
• unsigned to unsigned
• sign-magnitude to sign-magnitude
• twos complement to sign-magnitude

• Convert base 10 real numbers to base 2 real numbers
• Convert whole part
• Convert fractional part

• Convert base 2 real numbers to normalized form

• Show how base 2 normalized real numbers are stored in computers
• Use book method ( sign, significand, sign, exponent)
• Use IEEE-754 method (sign, biased exponent, significand)

• Addition and subtraction of base two integers

• Complete truth tables for boolean AND, OR, NOT, XOR operations

• Evaluate simple and complex boolean expressions to determine their truth value ( T or F)

• Recognize (draw) symbols for AND, OR, NOT, XOR gates

• Apply DeMorgans laws to boolean expressions

• a · b = a + b

• a + b = a  ·  b

• Use sum-of-products algorithm
• Convert truth table to a sum-of-products boolean expression
• Convert a boolean expression to a circuit diagram

• Determine the truth table which corresponds to a given circuit diagram

• Demonstrate how a computer compares 4-bit numbers for equality using 1-bit compare for equality circuits.

• Demonstrate how computer addition of 4-bit numbers is done with 1-bit full adders

• Use text and figures to explain what decoders and multiplexors do

• Give an example with text and diagrams of how decoders and multiplexors are used

• Draw the circuit diagram for a 1-to-2 decoder (1 input, 2 outputs)

• Draw the circuit diagram for a 2-way multiplexor (2 data inputs, 1 control input, 1 output)