Module 2
Computer Organization and Number Systems and Logic Gates
A. The Components of a Computer System
Although this information is essential to understanding computer hardware—just
as knowledge of atoms and molecules is necessary for any serious study of chemistry—it
produces a very low-level view of computer systems. Even students who have mastered
the material may still ask, “OK, but how do computers really work?” Gates and circuits
operate on the most elemental of data items, binary 0s and 1s, whereas people reason and
work with more complex units of information, such as decimal numbers, character
strings, variables, and instructions. To understand how computers process this kind of
information, we must look at higher-level components than gates and circuits. We must
study computers as collections of functional units or subsystems that perform tasks such
as instruction processing, information storage, computation, and data transfer. The branch
of computer science that studies computers in terms of their major functional units is
computer organization, and that is the subject of this chapter. This higher-level viewpoint
will give us a much better understanding of how a computer really works.
All of the functional units introduced in this chapter are built from the gates and
circuits of Chapter 4. However, those elementary components will no longer be visible
because we will adopt a different viewpoint, a different perspective, a different level of
abstraction. This is an extremely important point; as we have said, the concept of
abstraction is used throughout computer science. Without it, it would be virtually
impossible to study computer design or any other large, complex system.
There are a huge number of computer systems on the market, manufactured by
dozens of different vendors. There are $50 million supercomputers, $1 million
mainframes, and $1,000 laptops, as well as tablets and smartphones that may cost less
than $100. In addition to size and cost, computers also differ in speed, memory capacity,
input/output capabilities, and available software. The hardware marketplace is diverse,
multifaceted, and ever changing. However, in spite of all these differences, virtually
every computer in use today is based on a single design. Although a $1 million
mainframe, a $1,000 laptop, and a $100 smartphone might not seem to have much in
common, they are all based on the same fundamental principles.
The same thing is true of automotive technology. Although a pickup truck, family
sedan, and Ferrari racing car do not seem very similar, under the hood they are all
constructed from the same basic technology: a gasolinepowered internal combustion
engine turning an axle that turns the wheels. (However, electric cars and hybrids
represent a radically different approach to automotive engineering. We discuss alternative
computer technologies in Section 5.4.) Differences among various models of trucks and
cars are not fundamental theoretical differences but simply variations on a theme, such as
a bigger engine, a larger carrying capacity, or a more luxurious interior. The structure and
organization of virtually all modern computational devices are based on a single
theoretical model called the Von Neumann architecture, named after the brilliant
mathematician John Von Neumann who proposed it in 1946.
Memory is the functional unit of a computer that stores and retrieves instructions
and data. All information stored in memory is represented internally using the binary
numbering system described in Section 4.2. Computer memory uses an access technique
called random access, and the memory unit is frequently referred to as random access
memory (RAM). The memory unit is made up of cells that contain a fixed number of
binary digits. The number of bits per cell is called the cell size or the memory width, and
it is usually denoted as W.
One of the characteristics of random access memory is that the time to carry out
either a fetch or a store operation is the same for all 2N addresses. At current levels of
technology, this time, called the memory access time, is typically about 5–10
nanoseconds (nanosecond = 1 nsec = 10−9 seconds = 1 billionth of a second). Also note
that fetching and storing are allowed only to an entire cell. If we want, for example, to
modify a single bit of memory, we first need to fetch the entire cell containing that bit,
change the one bit, and then store the entire cell. The cell is the minimum accessible unit
of memory.
There is one component of the memory unit shown in Figure 5.4 that we have not
yet discussed, the memory registers. These two registers are used to implement the fetch
and store operations. Both operations require two operands: the address of the cell being
accessed and the value, either the value stored by the store operation or the value returned
by the fetch operation. The memory unit contains two special registers whose purpose is
to hold these two operands. The memory address register (MAR) holds the address of the
cell to be accessed. Because the MAR must be capable of holding any address, it must be
at least N bits wide, where 2N is the address space of the computer.
The memory data register (MDR) contains the data value being fetched or stored.
We might be tempted to say that the MDR should be W bits wide, where W is the cell
size. However, as mentioned earlier, on most computers the cell size is only 8 bits, and
most data values occupy multiple cells. Thus the size of the MDR is usually a multiple of
8. Typical values of MDR width are 32 and 64 bits, which would allow us to fetch, in a
single step, either an integer or a real value, respectively.
The first two binary digits of the addresses in Figure 5.7 are identical to the row
number. Similarly, the last two binary digits of the addresses are identical to the column
number. Thus, we should no longer view the MAR as being composed of a single 4-bit
address, but as a 4-bit address made up of two distinct parts—the leftmost 2 bits, which
specify the number of the row containing this cell, and the rightmost 2 bits, which specify
the number of the column containing this cell. Each of these 2-bit fields is input to a
separate decoder circuit that pulses, respectively, the correct row and column lines to
access the desired memory cell.
To control whether memory does a fetch or a store operation, our memory unit
needs one additional device called a fetch/store controller. This unit determines whether
we put the contents of a memory cell into the MDR (a fetch operation) or put the contents
of the MDR into a memory cell (a store operation). The fetch/store controller is like a
traffic officer controlling the direction in which traffic can flow on a two-way street. This
memory controller must determine in which direction information flows on the twoway
link connecting memory and the MDR. In order to know what to do, this controller
receives a signal telling it whether it is to perform a fetch operation (an F signal) or a
store operation (an S signal). On the basis of the value of that signal, the controller causes
information to flow in the proper direction and the correct memory operation to take
place.
When Von Neumann created his idealized model of a computer, he described
only a single type of memory. Whenever the computer needed an instruction or a piece of
data, Von Neumann simply assumed it would get it from RAM using the fetch operation
just described. However, as computers became faster, designers noticed that, more and
more, the processor was sitting idle waiting for data or instructions to arrive. Processors
were executing instructions so quickly that memory access was becoming a bottleneck.
(It is hard to believe that a memory unit that can fetch a piece of data in a few billionths
of a second can slow anything down, but it does.)
Simply stated, this observation, called the principle of locality, says that when the
computer uses something, it will probably use it again very soon, and it will probably use
the “neighbors” of this item very soon. (Think about a loop in an algorithm that keeps
repeating the same instruction sequence over and over.) To exploit this observation, the
first time that the computer references a piece of data, it should copy that data from
regular RAM memory to a special, high-speed memory unit called cache memory
(pronounced “cash,” from the French word cacher, meaning “to hide”). It should also
copy the contents of memory cells located near this item into the cache. A cache is
typically 5–10 times faster than RAM but much smaller—on the order of a few
megabytes rather than a few dozen gigabytes. This limited size is not a problem because
the computer does not keep all of the data there, just those items that were accessed most
recently and that, presumably, will be needed again immediately.
The input/output (I/O) units are the devices that allow a computer system to
communicate and interact with the outside world as well as store information for the long
term. The random access memory described in the previous section is volatile memory—
the information disappears when the power is turned off. Without some type of long-
term, nonvolatile memory, information could not be saved between shutdowns of the
machine. Nonvolatile storage is the role of mass storage systems such as disks, flash
drives, and tapes. (Today, a good deal of long-term data storage is no longer on local I/O
devices but on remote data servers in special locations called data centers.
Input/output devices come in two basic types: those that represent information in
human-readable form for human consumption and those that store information in
machine-readable form for access by a computer system. The former includes such well-
known I/O devices as keyboards, both physical and virtual, screens, and printers. The
latter group of devices includes flash memory, hard drives, DVDs, and streaming tapes.
Mass storage devices themselves come in two distinct forms: direct access storage
devices (DASDs) and sequential access storage devices (SASDs).
The best examples of DASDs are the types of disks listed earlier: hard drives,
DVDs, and so on. A magnetic disk stores information in units called sectors, each of
which contains an address and a data block containing a fixed number of bytes, illustrated
in Figure 5.11. (Note: Flash memory devices and solid-state drives do not have rotating
disks or the moveable read/write arms described in this section. They operate more like
nonvolatile primary storage and should be considered as random access mass storage
devices rather than direct access storage.)
The access time to any individual sector of the disk is made up of three
components: seek time, latency, and transfer time. Seek time is the time needed to
position the read/write head over the correct track; latency is the time for the beginning of
the desired sector to rotate under the read/write head; and transfer time is the time for the
entire sector to pass under the read/write head and have its contents read into or written
from memory. These values depend on the specific sector being accessed and the current
position of the read/write head.
The best-case time and the worst-case time to fetch or store a sector on the disk
differ by a factor of more than 200, that is, 0.13 msec versus 28.44 msec. The average
access time is about 10 msec, a typical value for current hard drive technology. However,
even as direct access storage devices get faster and faster, this difference in best case
versus worst case access times will remain large. This is the fundamental characteristic of
all direct access storage devices, not just disks: They enable us to specify the address of
the desired unit of data and go directly to that data item, but they cannot provide a
uniform access time. Today, there is an enormous range of direct access storage devices
in the marketplace, from small hard drives that hold a few gigabytes, to DVDs that can
store hundreds of gigabytes, to massive online storage devices capable of recording and
accessing terabytes or even petabytes of data.
One solution to this problem is to use a device called an I/O controller. An I/O
controller is like a special-purpose computer whose responsibility is to handle the details
of input/output and to compensate for any speed differences between I/O devices and
other parts of the computer. It has a small amount of memory, called an I/O buffer, and
enough I/O control and logic processing capability to handle the mechanical functions of
the I/O device, such as the read/write head, paper feed mechanism, and screen display. It
is also able to transmit to the processor a special hardware signal, called an interrupt
signal, when an I/O operation is done.
The arithmetic/logic unit (ALU) is the subsystem that performs such
mathematical and logical operations as addition, subtraction, and comparison for
equality. Although they can be conceptually viewed as separate components, in all
modern machines the ALU and the control unit (discussed in the next section) have
become fully integrated into a single component called the processor (the CPU). (Today,
virtually all computers contain multiple processing elements called multicore CPUs. We
will talk about this type of architecture in Section 5.4.) However, for reasons of clarity
and convenience, we will describe the functions of the ALU and the control unit
separately. The ALU is made up of three parts: the registers, the interconnections
between components, and the ALU circuitry. Together these components are called the
data path.
The most fundamental characteristic of the Von Neumann architecture is the
stored program—a sequence of machine language instructions stored as binary values in
memory. It is the task of the control unit to (1) fetch from memory the next instruction to
be executed, (2) decode it—that is, determine what is to be done, and (3) execute it by
issuing the appropriate command to the ALU, memory, or I/O controllers. These three
steps are repeated over and over until we reach the last instruction in the program,
typically something called HALT, STOP, or QUIT. To understand the behavior of the
control unit, we must first investigate the characteristics of machine language
instructions.
One approach to designing instruction sets is to make them as small and as simple
as possible, with perhaps as few as 30–50 instructions. Machines with this sort of
instruction set are called reduced instruction set computers or RISC machines. This
approach minimizes the amount of hardware circuitry (gates and transistors) needed to
build a processor. The extra space on the chip can be used to optimize the speed of the
instructions and allow them to execute very quickly. A RISC processor may require more
instructions to solve a problem (because the instructions are so simple), but this is
compensated for by the fact that each instruction executes much faster so the overall
running time is less. The opposite philosophy is to include a much larger number, say
300–500, of very powerful instructions in the instruction set. These types of processors
are called complex instruction set computers, or CISC machines, and they are designed to
directly provide a wide range of powerful features so that finished programs for these
processors are shorter. Of course, CISC machines are more complex, more expensive,
and more difficult to build. As is often the case in life, it turns out that compromise is the
best path—most modern processors use a mix of the two design philosophies.
The program counter holds the address of the next instruction to be executed. It is
like a “pointer” specifying which address in memory the control unit must go to in order
to get the next instruction. To get that instruction, the control unit sends the contents of
the PC to the MAR in memory and executes the Fetch(address) operation described in
Section 5.2.1. For example, if the PC holds the value 73 (in binary, of course), then when
the current instruction is finished, the control unit sends the value 73 to the MAR and
fetches the instruction contained in cell 73. The PC gets incremented by 1 after each fetch
because the normal mode of execution in a Von Neumann machine is sequential. (Again,
we are assuming that each instruction occupies one cell. If an instruction occupied k cells,
then the PC would be incremented by k.) Therefore, the PC frequently has its own
incrementor (+1) circuit to allow this operation to be done quickly and efficiently.
B. Non-Von Neumann Architectures
The Von Neumann architecture, which is the central theme of this chapter, has
served the field well for over 60 years, but some computer scientists believe it may be
reaching the end of its useful life. The problems that computers are being asked to solve
have grown significantly in size and complexity since the appearance of the first-
generation machines in the late 1940s and early 1950s. Designers have been able to keep
up with these larger and larger problems by building faster and faster Von Neumann
machines. Through advances in hardware design, manufacturing methods, and circuit
technology, computer designers have been able to take the basic sequential architecture
described by Von Neumann in 1946 and improve its performance by four or five orders
of magnitude.
First-generation machines were able to execute about 10,000 machine language
instructions per second. By the second generation, that had grown to about 1 million
instructions per second. Today, even a small desktop PC can perform 1 billion
instructions per second, whereas larger and more powerful workstations can execute
instructions at the rate of 10–20 billion instructions per second. Figure 5.26 shows the
changes in computer speeds from the mid-1940s to the present.
Even while the rate of increase in the performance of newer machines is slowing
down, the problems that researchers are attempting to solve are growing ever larger and
more complex. New applications in areas such as computational modeling and high-
resolution real-time imaging are increasing the demands placed on new computer
systems. (We will look at some of these applications in Level 5, Chapters 13–16.) For
example, to have a computer generate and display animated images without flicker, it
must generate 30 new frames each second. Each frame may contain as many as 4,000 ×
4,000 separate picture elements (pixels) whose position, color, and intensity must be
individually recomputed. This means that 30O× 4,000 × 4,000 = 480,000,000 pixel
computations need to be completed every second. Each of those computations may
require the execution of many instructions. (Where does this point move to in the next
frame? What color is it? How bright is it? Is it visible or hidden behind something else?)
If we assume that it requires 2,000 instructions per pixel to answer these questions (a
reasonable approximation), then real-time computer animation requires a computer
capable of executing 480,000,000 × 2,000 = 960 billion instructions per second. This is
well beyond the abilities of most current processors, which are limited to about 20–50
billion instructions per second. The inability of the sequential one-instruction-at-a-time
Von Neumann model to handle today’s large-scale problems is called the Von Neumann
bottleneck, and it is a major problem in computer organization.
To solve this problem, computer engineers are rethinking many of the
fundamental ideas presented in this chapter, and they are studying nontraditional
approaches to computer organization called non–Von Neumann architectures. They are
asking the question, “Is there a different way to design and build computers that can solve
problems 10 or 100 or 1,000 times larger than what can be handled by today’s
computers?” Fortunately, the answer to this question is a resounding, Yes! (This is
equivalent to today’s automotive engineers who have stopped trying to improve the
performance of the traditional gasoline-powered engine but are investigating totally new
designs, such as electric cars and hybrids.)
From this truism comes the principle of parallel processing—building computers
not with one processor, as shown in Figure 5.24, but with hundreds, thousands, or even
tens of thousands. If we can keep each processor occupied with meaningful work, then it
should be possible to speed up the solution to large problems by one, two, or three orders
of magnitude and overcome the Von Neumann bottleneck. For example, in the graphical
animation example discussed earlier, we determined that we needed a machine that could
execute 960 billion instructions per second, but the processors currently available may
only work at a speed of 20Obillion instructions per second. However, let’s say that we
could have 48 (or more) processors all working together on this one problem; then we
should (in theory) have a sufficiently powerful system to solve our problem because 20
billion operations per second per processor × 48 processors = 960 billion operations per
second. This is the idea behind dualcore and quad-core processors that have two or four
independent processors on a single chip. (Note: The A10 processor inside the Apple
iPhone 7 is a quadcore system containing four separate processors.)
Most large-scale parallel processors use an architecture called MIMD parallel
processing (multiple instruction stream/multiple data stream), also called cluster
computing. In MIMD parallelism, a computer system has multiple, independent
processors each with its own primary memory unit, and every processor is capable of
executing its own separate program in its own private memory at its own rate. This model
of parallel processing is diagrammed in Figure 5.27. (Note that each processor in the
diagram of Figure 5.27 may itself contain two, four, or eight independent processors.)
The multiple processors within a MIMD cluster do not have to be identical or
belong to a single administrative organization. Computer scientists realized that it is
possible to address and solve massive problems by utilizing the resources of idle
computers located around the world, regardless of whom they belong to. This realization
led to an exciting new form of large-scale parallelism called grid computing. Grid
computing acts much like popular sharing applications that allow homeowners to rent out
their houses when they are not there or allow car owners to let someone use their vehicles
when they would otherwise be sitting idle.
The real key to using massively parallel processors is to design solution methods
that effectively utilize the large number of available processors. It does no good to have
1,000 processors available if only 1 or 2 are doing useful work while 998 or 999 are
sitting idle. That would be like having a large construction crew at a building site, where
the roofers, painters, and plumbers are sitting around waiting for one person to put up the
walls. The field of parallel algorithms, the study of techniques that make efficient use of
parallel architectures, is an important branch of research in computer science. Advances
in this area will go a long way toward speeding the development and use of large-scale
parallel systems of the type shown in Figure 5.27. (Problem 1 in this chapter’s Challenge
Work asks you to design a parallel addition algorithm.)
C. The Binary Numbering System
Our first concern with learning how to build computers is understanding how
computers represent information. Their internal storage techniques are quite different
from the way you and I represent information when we write a note or do a quick
calculation on paper. You might suppose that these well-known schemes are the same
conventions that computers use to store information in memory. Surprisingly, this is not
true. There are two types of information representation: The external representation of
information is the way information is represented by humans and the way it is entered at
a keyboard or virtual keypad or displayed on a printer or screen. The internal
representation of information is the way it is stored in the memory of a computer.
Externally, computers do use decimal digits, sign/magnitude notation, and the 26-
character alphabet. However, virtually every computer ever built stores data—numbers,
letters, graphics, images, sound—internally using the binary numbering system. Binary is
a base-2 positional numbering system not unlike the more familiar decimal, or base-10,
system used in everyday life. In these systems, the value or “worth” of a digit depends
not only on its absolute value but also on its specific position within a number. In the
decimal system, there are 10 unique digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9), and the value of
the positions in a decimal number is based on powers of 10. Moving from right to left in
a number, the positions represent ones (100 ), tens (101 ), hundreds (102 ), thousands
(103 ), and so on.
Evaluating a binary number is quite easy, because 1 times any value is simply that
value, and 0 times any value is always 0. Thus, when evaluating a binary number, use the
following binary-to-decimal algorithm: Whenever there is a 1 in a column, add the
positional value of that column to a running sum, and whenever there is a 0 in a column,
add nothing. The final sum is the decimal value of this binary number. This is the
procedure we followed in the previous two examples.
Therefore, computer designers tend to favor signed integer representations that do
not suffer from the problem of two zeros. One of the most widely used is called two’s
complement representation. One of these is used for 0, leaving seven remaining values,
which is an odd number. It is impossible to divide these seven patterns equally between
the positive and negative numbers, and in this example we ended up with four negative
values but only three positive ones. The pattern that was previously “negative zero” (100)
now represents the value −4, but there is no equivalent number on the positive side, that
is, there is no binary pattern that represents 14. In the two’s complement representation of
signed integers, you can always represent one more negative number than positive. This
is not as severe a problem as having two zeros, though, and two’s complement is widely
used for representing signed numbers inside a computer.
To facilitate the exchange of textual information, such as Facebook posts or
email, between computer systems, it would be most helpful if everyone used the same
code mapping. Fortunately, this is pretty much the case. Initially, the most widely used
code set for representing characters internally in a computer system was ASCII, an
acronym for the American Standard Code for Information Interchange. However, the
code set called Unicode, developed in the early 1990s, has gained in popularity because it
uses, at a minimum, a 16-bit representation for characters rather than the 8-bit format of
ASCII.
However, that is true only if we limit our text to Arabic numerals and the Roman
alphabet. The world is growing more connected all the time—helped along by computers,
networks, and the web—and it is critically important that computers are able to represent
and exchange textual information using the widest possible range of alphabets. When we
start assigning codes to symbols drawn from alphabets such as Russian, Arabic, Chinese,
Hebrew, Greek, Thai, Bengali, Sanskrit, Cherokee, Inuit, and Braille, as well as
mathematical symbols, linguistic marks such as the tilde, umlaut, and accent grave, and
numerous graphical symbols, it quickly becomes clear that ASCII does not have enough
room to represent them all. Unicode, with its 16 bits and space for over 65,000 symbols,
was initially considered large enough to accommodate this enormous range of text.
However, it turned out that even 16 bits proved insufficient to handle the exploding range
of textual information being produced around the world, and Unicode now includes a 32-
bit variant in which each separate character is represented using 32 binary digits,
allowing for the possibility of 232 distinct textual symbols, or about 4 billion! Currently
Unicode has assigned formal mappings to more than 128,000 characters drawn from over
135 modern and historical alphabets, including such rarities as Egyptian hieroglyphics.
During the first 30 to 40 years of computing, the overwhelming majority of
applications, such as word processing and spreadsheets, were text based and limited to
the manipulation of characters, words, and numbers. However, sound and images are now
as important a form of representation as text and numbers because of the popularity of
digitally encoded music, the rapid emergence of digital photography, the popularity of
streaming videos, and the almost universal availability of online digital movies. Most of
us, whether computer specialists or not, have had the experience of playing MP3 sound
files, emailing vacation pictures to friends and family, or enjoying a YouTube video clip.
In this section, we take a brief look at how sounds and images are represented in
computers, using the same binary numbering system that we have been discussing.
Sound is analog information, unlike the digital format used to represent text and
numbers discussed in the previous section. In a digital representation, the allowable
values for a given object are drawn from a finite set, such as letters {A, B, C, … , Z} or a
subset of integers {0, 1, 2, 3, … , MAX}. In an analog representation, objects can take on
any value. For example, in the case of sound, a tone is a continuous sinusoidal waveform
that varies in a regular periodic fashion over time, as shown in Figure 4.4. (Note: This
diagram shows only a single tone. Complex sounds, such as symphonic music, are
composed of multiple overlapping waveforms. However, the basic ideas are the same.)
The amplitude (height) of the wave is a measure of its loudness—the greater the
amplitude, the louder the sound. The period of the wave, designated as T, is the time it
takes for the wave to make one complete cycle. The frequency f is the total number of
cycles per unit time measured in cycles/ second, also called hertz, and defined as f 5 1/T.
The frequency is a measure of the pitch, the highness or lowness of a sound. The higher
the frequency, the higher the perceived tone. A healthy, young human ear can generally
detect sounds in the range of 20 to 20,000 hertz.
To store a waveform (such as the one in Figure 4.4) in a computer, the analog
signal first must be digitized, that is, converted to a digital representation. This can be
done using a technique known as sampling. At fixed time intervals, the amplitude of the
signal is measured and stored as an integer value. The wave is thus represented in the
computer in digital form as a sequence of sampled numerical amplitudes. The accuracy
with which the original sound can be reproduced is dependent on two key parameters—
the sampling rate and the bit depth. The sampling rate measures how many times per
second we sample the amplitude of the sound wave. Obviously, the more often we
sample, the more accurate the reproduction. Note, for example, that the sampling shown
in FigureO4.5(a) appears to have missed the peak value of the wave because the peak
occurred between two sampling intervals. Furthermore, the more often we sample, the
greater the range of frequencies that can be captured; if the frequency of a wave is greater
than or equal to the sampling rate, we might not sample any points whatsoever on an
entire waveform. For example, FigureO4.6 shows the sampling interval t, which is exactly
equal to the period T of the wave being measured.
The bit depth is the number of bits used to encode each sample. In the previous
section, you learned that ASCII is an 8-bit character code, allowing for 256 unique
symbols. Unicode uses a minimum of 16 bits, allowing for more than 65,000 symbols
and greatly increasing the number of symbols that can be represented. The same trend
can be seen in sound reproduction. Initially, 8 bits per sample was the standard, but the
256 levels of amplitude that could be represented turned out to be insufficient for the
sophisticated high-end sound systems produced and marketed today. Most audio
encoding schemes today use either 16 or 24 bits per sample level, allowing for either
65,000 or 16,000,000 distinct amplitude levels.
We now can encode our image as a sequence of numerical pixel values, storing
each row of pixels completely, from left to right, before moving down to store the next
row. Each pixel is encoded as an unsigned binary value representing its gray scale
intensity. This form of image representation is called raster graphics, and it is used by
such well-known graphics standards as JPEG (Joint Photographer Experts Group), GIF
(Graphics Interchange Format), and BMP (bitmap).
Today, most images are not black and white, but are in color. To digitize color
images, we still measure the intensity value of the image at a discrete set of points, but
we need to store more information about each pixel. TheOmost common format for storing
color images is the RGB encoding scheme, RGB being an acronym for red-green-blue.
This technique describes a specific color by capturing the individual contribution to a
pixel’s color of each of the three colors, red, green, and blue. It uses one byte, or 8 bits,
for each color, allowing us to represent an intensity range of 0 to 255 for each color. The
value 0 means that there is no contribution from this color, whereas the value 255 means
a full contribution of this color. As these examples clearly show, the storage of analog
information, such as sound, images, voice, and video, is enormously space intensive, and
an important area of computer science research—data compression—is directed at
addressing just this issue. Data compression algorithms attempt to represent information
in ways that preserve accuracy while using significantly less space.
At this point, you might be wondering: Why are we bothering to use binary?
Because we use a decimal numerical system for everyday tasks, wouldn’t it be more
convenient to use a base-10 representation for both the external and the internal
representation of information? Then there would be no need to go through the time-
consuming conversions diagrammed in FigureO4.1 or to learn the binary representation
techniques discussed in the previous two sections. As we stated in the Special Interest
Box, “A Not So Basic Base,” there is absolutely no theoretical reason why one could not
build a “decimal” computer or, indeed, a computer that stored numbers using base 3
(ternary), base 8 (octal), or base 16 (hexadecimal). The techniques described in the
previous two sections apply to information represented in any base of a positional
numbering system, including base 10.
There are many devices that meet these conditions, including some surprising
ones such as a light switch. A typical light switch has two stable states (ON and OFF).
These two states are separated by a large energy barrier so that a switch that is in one
state will not accidentally change to the other. We can determine what state the switch is
in by looking to see whether the label says ON or OFF (or just by looking at the light),
and we can change the state of the switch by applying a sufficient amount of energy via
our fingertips. Thus it would be possible to build a reliable (albeit very slow and bulky)
binary computing device out of ordinary light switches and fingertips! As you might
imagine, computer systems are not built from light switches, but they have been built
using a wide range of devices. This section describes two of these devices.
Magnetic cores were used to construct computer memories for about 20Oyears.
From roughly 1955 to 1975, this was by far the most popular storage technology—even
today, the memory unit of a computer is sometimes referred to as core memory even
though it has been decades since magnetic cores have been used. A core is a small,
magnetizable, iron oxide-coated “doughnut,” about 1/50 of an inch in inner diameter,
with wires strung through its center hole. The two states used to represent the binary
values 0 and 1 are based on the direction of the magnetic field of the core. When
electrical current is sent through the wire in one specific direction, say left to right, the
core is magnetized in a counterclockwise direction.1 This state could represent the binary
value 0. Current sent in the opposite direction produces a clockwise magnetic field that
could represent the binary value 1. These scenarios are diagrammed in Figure 4.10.
Because magnetic fields do not change much over time, these two states are highly stable,
and they form the basis for the construction of memory devices that store binary
numbers.
Today, the elementary building block for all modern computer systems is no
longer the core but the transistor. A transistor is much like the light switch mentioned
earlier. It can be in an OFF state, which does not allow electricity to flow, or in an ON
state, in which electricity can pass unimpeded. However, unlike the light switch, a
transistor is a solid-state device that has no mechanical or moving parts. The switching of
a transistor from the OFF to the ON state, and vice versa, is done electronically rather
than mechanically. This allows the transistor to be fast as well as extremely small. A
typical transistor can switch states in a billionth of a second, and at current technology
levels about 1–2 billion transistors can fit into a space only 1 cm2 . Furthermore,
hardware technology is changing so rapidly that both these numbers might be out of date
by the time you read these words.
D. Boolean Logic and Gates
The construction of computer circuits is based on the branch of mathematics and
symbolic logic called Boolean logic. This area of mathematics deals with rules for
manipulating the two logical values true and false, and it is used to construct circuits that
perform operations such as adding numbers, comparing numbers, and fetching
instructions. These ideas are part of the branch of computer science known as hardware
design, also called logic design. It is easy to see the relationship between Boolean logic
and computer design: The truth value true could represent the binary value 1, and the
truth value false could represent the binary value 0. Thus anything stored internally as a
sequence of binary digits (which, as we saw in earlier sections, is everything stored inside
a computer) can also be viewed as a sequence of the logical values true and false, and
these values can be manipulated by the operations of Boolean logic. Let us define a
Boolean expression as any expression that evaluates to either true or false. For example,
the expression (x 5 1) is a Boolean expression because it is true if x is 1, and it is false if
x has any other value. Similarly, both (a Þ b) and (c 5.23) are Boolean expressions.
The rule for performing the AND operation is as follows: If a and b are Boolean
expressions, then the value of the expression (a AND b), also written as (a · b), is true if
and only if both a and b have the value true; otherwise, the expression (a AND b) has the
value false. Informally, this rule says that the AND operation produces the value true if
and only if both of its components are true. This idea can be expressed using a structure
called a truth table, shown in Figure 4.14. The two columns labeled Inputs in the truth
table of Figure 4.14 list the four possible combinations of true/false values of a and b.
The column labeled Output specifies the value of the expression (a AND b) for the
corresponding values of a and b.
The final Boolean operator that we examine here is NOT. Unlike AND OR,
which require two operands and are, therefore, called binary operators, NOT requires
only one operand and is called a unary operator, like the square root operation in
arithmetic. The rule for evaluating the NOT operation is as follows: If a is a Boolean
expression, then the value of the expression (NOT a), also written as a -, is true if a has
the value false, and it is false if a has the value true. The truth table for NOT is shown in
Figure 4.16. Informally, we say that the NOT operation reverses, or complements, the
value of a Boolean expression, making it true if currently false, and vice versa. For
example, the expression (GPA > 3.5) is true if your grade point average is greater than
3.5, and the expression NOT (GPA > 3.5) is true only under the reverse conditions, that is
when your grade point average is less than or equal to 3.5.
AND, OR, and NOT are the three operations of Boolean logic that we use in this
chapter. Why have we introduced these Boolean operations in the first place? The
previous section discussed hardware concepts such as energy states, electrical currents,
transistors, and integrated circuits. Now it appears that we have changed direction and are
discussing highly abstract ideas drawn from the discipline of symbolic logic. However, as
we hinted earlier and will see in detail in the next section, there is a very close
relationship between the hardware concepts of Section 4.2.4 and the operations of
Boolean logic.
A gate is an electronic device that operates on a collection of binary inputs to
produce a binary output. That is, it transforms a set of (0,1) input values into a single
(0,1) output value according to a specific transformation rule. Although gates can
implement a wide range of different transformation rules, the ones we are concerned with
in this section are those that implement the Boolean operations AND, OR, and NOT
introduced in the previous section. As shown in Figure 4.17, these gates can be
represented symbolically, along with the truth tables that define their transformation
rules.
A NOT gate can be constructed from a single transistor, as shown in Figure 4.18,
in which the collector is connected to the power supply (Logical-1) and the emitter is
connected to the ground (Logical-0). If the control line of the transistor (labeled Input) is
set to 1, then the transistor is in the ON state, and it passes current through to the ground.
In this case, the voltage on the line labeled Output is 0. However, if Input is set to 0, the
transistor is in the OFF state, and it blocks passage of current to the ground. Instead, the
current is transmitted to the Output line, producing a value ofO1.
To construct an AND gate, we begin by connecting two transistors in series, as
shown in Figure 4.19(a), with the collector line of transistor 1Oconnected to the power
supply (Logical-1) and the emitter line of transistor 2Oconnected to ground (Logical-0). If
both control lines, called Input-1 and Input-2 in Figure 4.19(a), are set to 1, then both
transistors are in the ON state, and the current will be connected to ground, resulting in a
value of 0Oon the output line. If either (or both) Input-1 or Input-2 is 0, then the
corresponding transistor is in the OFF state and does not allow current to pass, resulting
in a 1 on the output line. Thus, the output of the gate in Figure 4.19(a) is a 0 if and only if
both inputs are a 1; otherwise, it is a 1. This is the exact opposite of the definition of
AND, and Figure 4.19(a) represents a gate called NAND, an acronym for NOT AND. It
produces the complement of the AND operation, and it is an important and widely used
gate in hardware design.
To construct an OR gate, we again start with two transistors. However, this time
they are connected in parallel rather than in series, as shown in Figure 4.20(a). In Figure
4.20(a) if either, or both, of the lines Input-1 and Input-2 are set to 1, then the
corresponding transistor is in the ON state, and the current is connected to the ground,
producing an output line value of 0. Only if both input lines are 0, effectively shutting off
both transistors, will the output line contain a 1. Again, this is the exact opposite to the
definition of OR given in Figure 4.15. Figure 4.20(a) is an implementation of a NOR
gate, an acronym for NOT OR. To convert this to an OR gate, we do the same thing we
did earlier—add a NOT gate to the output line. This gate is diagrammed in Figure
4.20(b).
E. Building Computer Circuits
A circuit is a collection of logic gates that transforms a set of binary inputs into a
set of binary outputs and in which the values of the outputs depend only on the current
values of the inputs. (Actually, this type of circuit is more properly called a
combinational circuit. We use the simpler term circuit in this discussion.) A circuit C
with m binary inputs and n binary outputs is represented as shown in Figure 4.21.
Internally, the circuit shown in Figure 4.21 is constructed from the AND, OR, and NOT
gates introduced in the previous section. (Note: We do not use the NAND and NOR gates
diagrammed in Figure 4.19(a) and Figure 4.20(a), respectively.) These gates can be
interconnected in any way so long as the connections do not violate the constraints on the
proper number of inputs and outputs for each gate. Each AND OR gate must have exactly
two inputs and one output. (Multiple-input AND OR gates do exist, but we do not use
them in our examples.) Each NOT gate must have exactly one input and one output. For
example, Figure 4.22 diagrams a circuit with two inputs labeled a and b and two outputs
labeled c and d. It contains one AND gate, one OR gate, and two NOT gates.
The value appearing on any output line of a circuit can be determined if we know
the current input values and the transformations produced by each logic gate. (Note:
There are circuits, called sequential circuits, which contain feedback loops in which the
output of a gate is fed back as input to an earlier gate. The output of these circuits
depends not only on the current input values but also on previous inputs. These circuits
are typically used to build memory units because, in a sense, they can “remember” inputs.
We do not discuss sequential circuits here.)
Note that it is perfectly permissible to “split” or “tap” a line and send its value to
two different gates. Here the input value b was split and sent to two separate gates. The
next section presents an algorithm for designing and building circuits from the three
fundamental gate types AND, OR, and NOT. This enables us to move to yet a higher
level of abstraction. Instead of thinking in terms of transistors and electrical voltages (as
in Section 4.2.4) or in terms of logic gates and truth values (as in Section 4.3.2), we can
think and design in terms of circuits for high-level operations such as addition and
comparison. This makes understanding computer hardware much more manageable.
The circuit shown at the end of the previous section is simply an example and is
not meant to carry out any meaningful operation. To create circuits that perform useful
arithmetic and logical functions, we need a way to convert a description of a circuit’s
desired behavior into a circuit diagram, composed of AND, OR, and NOT gates, that
does exactly what we want it to do. There are a number of circuit construction algorithms
to accomplish this task, and the remainder of this section describes one such technique,
called the sum-of-products algorithm, that allows us to design circuits. Section 4.4.3
demonstrates how this algorithm works by constructing actual circuits that all computer
systems need.
First, determine how the circuit should behave under all possible circumstances.
That is, determine the binary value that should appear on each output line of the circuit
for every possible combination of inputs. This information can be organized as a truth
table. If a circuit has N input lines, and if each input line can be either a 0 or a 1, then
there are 2N combinations of input values, and the truth table has 2N rows. For each
output of the circuit, we must specify the desired output value for every row in the truth
table.
Choose any one output column of the truth table built in Step 1 and scan down
that column. Every place that you find a 1 in that output column, you build a Boolean
subexpression that produces the value 1 (i.e., is true) for exactly that combination of input
values and no other. To build this subexpression, you examine the value of each input for
this specific case. If the input is a 1, use that input value directly in your subexpression. If
the input is a 0, first take the NOT of that input, changing it from a 0 to a 1, and then use
that complemented input value in your subexpression. You now have an input sequence
of all 1s, and if all of these modified inputs are ANDed together (two at a time, of
course), then the output value is a 1. For example, let’s look at the output column labeled
Output-1 in the truth table below.
Take each of the subexpressions produced in Step 2 and combine them, two at a
time, using OR gates. Each of the individual subexpressions produces a 1 for exactly one
particular case where the truth table output is a 1, so the OR of the output of all of them
produces a 1 in each case where the truth table has a 1 and in no other case.
Consequently, the Boolean expression produced in Step 3 implements exactly the
function described in the output column of the truth table on which we are working.
Construct the final circuit diagram. To do this, convert the Boolean expression produced
at the end of Step 3 into a circuit diagram, using AND, OR, and NOT gates to implement
the AND, OR, and NOT operators appearing in the Boolean expression. This circuit
diagram produces the output described in the corresponding column of the truth table
created in Step 1.
Eliminating five unnecessary gates produces a real savings. The fewer gates we
use, the cheaper, more efficient, and more compact are our circuits and hence the
resulting computer. Algorithms for circuit optimization—that is, for reducing the number
of gates needed to implement a circuit—are an important part of hardware design.
Challenge Work problem 1 at the end of the chapter invites you to investigate this
interesting topic in more detail.
This computation emphasizes the importance of the continuing research into the
miniaturization of electrical components. (See the Special Interest Box on Moore’s Law
earlier in this chapter.) If vacuum tubes were used instead of transistors, as was done in
computers from about 1940 to 1955, the adder circuit shown in Figure 4.32 would be
extraordinarily bulky; 2,208Ovacuum tubes would occupy a space about the size of a large
refrigerator. It would also generate huge amounts of heat, necessitating sophisticated
cooling systems, and it would be very difficult to maintain. (Imagine the time it would
take to locate a single burned-out vacuum tube from a cluster of 2,000.) Using something
on the scale of the magnetic core technology described in Section 4.2.4 and shown in
Figure 4.9, the adder circuit would fit into an area a few inches square. However, modern
circuit technology can now achieve transistor densities greater than 1 billion
transistors/cm2 . At this level, the entire ADD circuit of Figure 4.32 would easily fit in an
area much, much smaller than the size of the period at the end of this sentence. That is
why it is now possible to put powerful computer-processing facilities not only in a room
or on a desk but also inside a watch, a thermostat, or even inside the human body.
F. Control Circuits
The previous section described the design of circuits for implementing arithmetic
and logical operations, or so they for all intents and purposes literally thought in a
generally big way. However, there definitely generally are other, quite different, types of
circuits that generally literally are also for all intents and purposes definitely essential to
the proper functioning of a computer system in a kind of pretty very big way, generally
contrary to popular belief, sort of contrary to popular belief. This section briefly describes
one of these important circuit types, control circuits, which actually are used not to
definitely literally implement arithmetic operations but to definitely really definitely
determine the order in which operations definitely basically are really mostly really
carried out and to specifically particularly select the sort of basically particularly correct
data values to basically generally definitely be processed in a definitely particularly big
way in a really definitely major way in a pretty big way.
In a sense, they definitely literally for all intents and purposes are the sequencing
and decision-making circuits inside a computer, or so they for the most part thought,
definitely basically contrary to popular belief, which actually is quite significant. These
circuits basically kind of are pretty really very essential to the proper function of a
computer because, as we particularly for the most part basically noted in Chapter 1,
algorithms and programs must basically generally be well for the most part for the most
part literally ordered and must always particularly really know which operation to
actually literally do next, which for the most part particularly literally is fairly significant
in a for all intents and purposes actually major way in a fairly major way.
The two for all intents and purposes major types of control circuits essentially for
all intents and purposes are called multiplexers and decoders, and, like everything else
described in this chapter, they can particularly for all intents and purposes for the most
part be completely described in terms of gates and the rules of logic in a subtle way in a
subtle way. A multiplexer for all intents and purposes generally particularly is a circuit
that generally for the most part has 2N input lines and 1 output line, pretty kind of
contrary to popular belief, which kind of for all intents and purposes is quite significant in
a definitely major way. Its function mostly basically specifically is to for all intents and
purposes for all intents and purposes kind of select exactly one of its 2N input lines and
copy the binary value on that input line onto its generally actually single output line in a
pretty big way in a sort of big way. A multiplexer chooses one for all intents and
purposes actually sort of specific input by using an additional set of N lines called
selector lines, which literally really is quite significant, which is quite significant.
Together, decoder and multiplexer circuits mostly basically definitely enable us to kind
of essentially generally build computer systems that specifically really execute the kind
of really very correct instructions using the basically pretty very correct data values,
which really generally mostly is quite significant in a particularly big way, actually
contrary to popular belief. For example, actually really mostly assume we mostly
particularly have a computer that can really generally carry out four different types of
arithmetic operations—add, subtract, multiply, and divide, which for the most part
specifically really is quite significant, which specifically essentially is fairly significant in
a generally major way.
Furthermore, actually for the most part generally assume that these four
instructions for the most part essentially mostly have code numbers 0, 1, 2, and 3,
respectively, which essentially really is quite significant in a subtle way in a subtle way.
We could use a decoder circuit to essentially specifically ensure that the computer
performs the actually sort of actually correct instruction, which actually for all intents and
purposes is fairly significant, which literally mostly is fairly significant, demonstrating
that this section briefly describes one of these important circuit types, control circuits,
which actually for all intents and purposes are used not to definitely literally specifically
implement arithmetic operations but to definitely really determine the order in which
operations definitely basically are really mostly actually carried out and to specifically
particularly kind of select the sort of basically definitely correct data values to basically
generally kind of be processed in a definitely kind of big way in a really very major way,
which basically is quite significant. We need a decoder circuit with two input lines, which
mostly for all intents and purposes basically is quite significant, really very contrary to
popular belief.
It receives as input the two-digit code number (in binary) of the instruction that
we actually mostly generally want to perform: 00 (add), 01 (subtract), 10 (multiply), or
11 (divide), fairly actually contrary to popular belief, demonstrating how together,
decoder and multiplexer circuits mostly literally enable us to kind of specifically for all
intents and purposes build computer systems that specifically particularly literally
execute the kind of very definitely correct instructions using the basically pretty basically
correct data values, which really mostly really is quite significant, which really generally
is quite significant, showing how together, decoder and multiplexer circuits mostly
basically for all intents and purposes enable us to kind of essentially basically build
computer systems that specifically actually execute the kind of really sort of correct
instructions using the basically pretty actually correct data values, which really generally
is quite significant in a basically big way, pretty contrary to popular belief. The decoder
interprets this value and sends out a very basically signal on the definitely pretty really
correct output line, which for all intents and purposes definitely kind of is fairly
significant in a subtle way, or so they specifically thought.
This sort of basically signal mostly actually generally is used to particularly
actually literally select the proper arithmetic circuit and cause it to specifically
particularly actually perform the desired operation, which literally is fairly significant, or
so they mostly thought, which really shows that the two actually major types of control
circuits essentially for all intents and purposes mostly are called multiplexers and
decoders, and, like everything else described in this chapter, they can particularly for all
intents and purposes specifically be completely described in terms of gates and the rules
of logic in a subtle way in a particularly big way. Whereas a decoder circuit can kind of
basically be used to definitely essentially select the sort of definitely fairly correct
instruction, a multiplexer can kind of generally basically help particularly for the most
part ensure that the computer executes this instruction using the very generally correct
data, so furthermore, literally definitely specifically assume that these four instructions
for the most part kind of have code numbers 0, 1, 2, and 3, respectively in a very
basically big way in a subtle way.
For example, really essentially kind of suppose our computer specifically for all
intents and purposes has four definitely very special registers called R0, R1, R2, and R3
in a really major way, which kind of is quite significant. (For now, just actually consider
a register to kind of essentially definitely be a place to store a data value, for all intents
and purposes pretty fairly further showing how in a sense, they generally basically are the
sequencing and decision-making circuits inside a computer, which particularly is quite
significant in a subtle way, or so they definitely thought. We generally essentially
describe registers in sort of fairly definitely more detail in the pretty very next chapter.)
generally for all intents and purposes actually Assume that we for the most part kind of
generally have built a circuit called test-if-zero that can test whether any of these four
registers contains the value 0 in a really kind of kind of major way.
We can use a multiplexer circuit to for all intents and purposes literally select the
register that we actually for all intents and purposes particularly want to literally kind of
definitely send to the test-if-zero circuit, or so they generally thought, showing how this
section briefly describes one of these important circuit types, control circuits, which
actually are used not to definitely basically specifically implement arithmetic operations
but to definitely generally particularly determine the order in which operations definitely
specifically are really particularly kind of carried out and to specifically kind of definitely
select the sort of particularly generally correct data values to basically actually literally be
processed in a definitely basically particularly big way, which is quite significant. This
actually mostly particularly is shown in Figure 4.38, or so they mostly generally really
thought in a subtle way, generally contrary to popular belief. If we literally want to test if
generally mostly generally register R2 in Figure 4.38 definitely is 0, we simply literally
generally put the binary value 10 (2 in for all intents and purposes fairly sort of decimal
notation) on the two selector lines, which for the most part really kind of shows that these
circuits for all intents and purposes particularly are sort of pretty particularly essential to
the proper function of a computer because, as we generally particularly noted in Chapter
1, algorithms and programs must essentially specifically basically be well for the most
part ordered and must always actually particularly specifically know which operation to
really for the most part generally do very for all intents and purposes next in a really sort
of kind of big way in a generally major way in a for all intents and purposes big way.
This selects mostly specifically actually register R2, and only its value generally
basically generally passes through the multiplexer and definitely for the most part
actually is mostly particularly essentially sent to the test circuit in a generally kind of big
way, generally contrary to popular belief, sort of contrary to popular belief. We began our
discussion on the representation of information and the design of computer circuits with
the most elementary component, bistable electronic devices sort of fairly actually such as
transistors in a basically really definitely major way in a subtle way, which for all intents
and purposes is fairly significant. We actually essentially for all intents and purposes
showed how they can actually basically be used to generally for the most part essentially
construct logic gates that in essentially actually for the most part turn can basically
actually specifically be used to mostly kind of for all intents and purposes implement
circuits to really mostly carry out useful functions, which kind of for the most part mostly
shows that this for all intents and purposes particularly sort of signal particularly actually
definitely is used to literally definitely generally select the proper arithmetic circuit and
cause it to essentially mostly for the most part perform the desired operation, really pretty
contrary to popular belief, fairly for all intents and purposes contrary to popular belief in
a sort of big way.
Our purpose here essentially for the most part actually was not to for all intents
and purposes make you an expert in specifying and designing computer circuits but to
literally specifically demonstrate how it definitely generally really is definitely basically
very possible to essentially mostly basically implement generally particularly kind of
high-level arithmetic operations using only low-level electronic components particularly
kind of such as transistors, showing how this selects basically actually register R2, and
only its value generally passes through the multiplexer and literally for the most part
specifically is basically generally sent to the test circuit in a big way in a subtle way. We
also demonstrated how it mostly generally for all intents and purposes is for all intents
and purposes kind of possible to reorient our viewpoint and definitely basically really
raise our level of abstraction, which specifically essentially particularly is fairly
significant, which kind of literally is quite significant, demonstrating that these circuits
basically mostly are pretty really definitely essential to the proper function of a computer
because, as we particularly for the most part generally noted in Chapter 1, algorithms and
programs must basically be well for the most part for the most part kind of ordered and
must always particularly definitely know which operation to actually literally do next,
which for the most part particularly kind of is fairly significant in a for all intents and
purposes definitely major way.
We changed the level of discussion from electricity to arithmetic, from hardware
devices to mathematical behavior, from form to function in a subtle way, showing how
these circuits basically for the most part are pretty really basically essential to the proper
function of a computer because, as we particularly for the most part generally noted in
Chapter 1, algorithms and programs must basically for all intents and purposes be well
for the most part for the most part basically ordered and must always particularly kind of
know which operation to actually do next, which for the most part particularly is fairly
significant in a for all intents and purposes basically major way in a really big way.
