Computer organization

hey everyone, I need help with Boolean expression, binary addition, combintional circuits. All Questions are in attached file

PS the latter needed for question two is (F,R)

Logic and Computer Design Fundamentals
M. Morris Mano Charles Kime
Fourth Edition
Pearson Education Limited
Edinburgh Gate
Harlow
Essex CM20 2JE
England and Associated Companies throughout the world
Visit us on the World Wide Web at: www.pearsoned.co.uk
© Pearson Education Limited 2014
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted
in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without either the
prior written permission of the publisher or a licence permitting restricted copying in the United Kingdom
issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC1N 8TS.
All trademarks used herein are the property of their respective owners. The use of any trademark
in this text does not vest in the author or publisher any trademark ownership rights in such
trademarks, nor does the use of such trademarks imply any affiliation with or endorsement of this
book by such owners.
ISBN 10: 1-292-02468-2
ISBN 13: 978-1-292-02468-4
British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library
Printed in the United States of America
P E
A
R
S
O
N
C U
S T O
M
L
I
B
R
A
R Y
Table of Contents
1. Digital Systems and Information
M. Morris Mano, Charles R. Kime
1
2. Combinational Logic Circuits
M. Morris Mano, Charles R. Kime
35
3. Combinational Logic Design
M. Morris Mano, Charles R. Kime
99
4. Arithmetic Functions and HDLs
M. Morris Mano, Charles R. Kime
155
5. Sequential Circuits
M. Morris Mano, Charles R. Kime
215
6. Selected Design Topics
M. Morris Mano, Charles R. Kime
305
7. Registers and Register Transfers
M. Morris Mano, Charles R. Kime
347
8. Memory Basics
M. Morris Mano, Charles R. Kime
427
9. Instruction Set Architecture
M. Morris Mano, Charles R. Kime
459
10. Computer Design Basics
M. Morris Mano, Charles R. Kime
507
11. Input–Output and Communication
M. Morris Mano, Charles R. Kime
563
12. Memory Systems
M. Morris Mano, Charles R. Kime
601
13. RISC and CISC Central Processing Units
M. Morris Mano, Charles R. Kime
633
I
Index
II
689
DIGITAL SYSTEMS
AND INFORMATION
From Chapter 1 of Logic and Computer Design Fundamentals, Fourth Edition. M. Morris Mano,
Charles R. Kime. Copyright © 2008 by Pearson Education, Inc. Published by Pearson Prentice
Hall. All rights reserved.
1
LCD
Screen
Hard Drive
Keyboard
Drive Controller
Bus Interface
Graphics Adapter
Internal
FPU Cache
CPU MMU
Processor
RAM
External
Cache
Generic Computer
Note: The companion website for this text is http://www.prenhall.com/mano
2
DIGITAL SYSTEMS
AND INFORMATION
T
his text deals with logic circuits and digital computers. Early computers were
used for computations with discrete numeric elements called digits (the Latin
word for fingers)—hence the term digital computer. The use of “digital” spread
from the computer to logic circuits and other systems that use discrete elements of
information, giving us the terms digital circuits and digital systems. The term logic is
applied to circuits that operate on a set of just two elements with values True (1) and
False (0). Since computers are based on logic circuits, they operate on patterns of
elements from these two-valued sets, which are used to represent, among other
things, the decimal digits. Today, the term “digital circuits” is viewed as synonymous
with the term “logic circuits.”
The general-purpose digital computer is a digital system that can follow a stored
sequence of instructions, called a program, that operates on data. The user can
specify and change the program or the data according to specific needs. As a result of
this flexibility, general-purpose digital computers can perform a variety of informationprocessing tasks, ranging over a very wide spectrum of applications. This makes the
digital computer a highly general and very flexible digital system. Also, due to its
generality, complexity, and widespread use, the computer provides an ideal vehicle for
learning the concepts, methods, and tools of digital system design. To this end, we
use the exploded pictorial diagram of a computer of the class commonly referred to as
a PC (personal computer) given on the opposite page. We employ this generic
computer to highlight the significance of the material covered and its relationship to
the overall system. A bit later in this chapter, we will discuss the various major
components of the generic computer and see how they relate to a block diagram
commonly used to represent a computer. Otherwise, the remainder of the chapter
focuses on the digital systems in our daily lives and introduces approaches for
representing information in digital circuits and systems.
3
DIGITAL SYSTEMS AND INFORMATION
1 INFORMATION REPRESENTATION
Digital systems store, move, and process information. The information represents a
broad range of phenomena from the physical and man-made world. The physical
world is characterized by parameters such as weight, temperature, pressure, velocity, flow, and sound intensity and frequency. Most physical parameters are continuous, typically capable of taking on all possible values over a defined range. In
contrast, in the man-made world, parameters can be discrete in nature, such as
business records using words, quantities, and currencies, taking on values from an
alphabet, the integers, or units of currency, respectively. In general, information
systems must be able to represent both continuous and discrete information. Suppose that temperature, which is continuous, is measured by a sensor and converted
to an electrical voltage, which is likewise continuous. We refer to such a continuous
voltage as an analog signal, which is one possible way to represent temperature.
But, it is also possible to represent temperature by an electrical voltage that takes
on discrete values that occupy only a finite number of values over a range, e.g., corresponding to integer degrees centigrade between 40 and +119. We refer to such
a voltage as a digital signal. Alternatively, we can represent the discrete values by
multiple voltage signals, each taking on a discrete value. At the extreme, each signal can be viewed as having only two discrete values, with multiple signals representing a large number of discrete values. For example, each of the 160 values just
mentioned for temperature can be represented by a particular combination of
eight two-valued signals. The signals in most present-day electronic digital systems
use just two discrete values and are therefore said to be binary. The two discrete
values used are often called 0 and 1, the digits for the binary number system.
We typically represent the two discrete values by ranges of voltage values called
HIGH and LOW. Output and input voltage ranges are illustrated in Figure 1(a). The
HIGH output voltage value ranges between 0.9 and 1.1 volts, and the LOW output voltage value between 0.1 and 0.1 volts. The high input range allows 0.6 to
1.1 volts to be recognized as a HIGH, and the low input range allows 0.1 to 0.4
volts to be recognized as a LOW. The fact that the input ranges are wider than the
OUTPUT
HIGH
Voltage (Volts)
1.0
INPUT
1.0
0.9
HIGH
0.5
Time
0.0
(b) Time-dependent voltage
0.6
0.4
1
LOW
0.1
0.0
Volts
(a) Example voltage ranges
LOW
Time
0
(c) Binary model of time-dependent voltage
FIGURE 1
Examples of Voltage Ranges and Waveforms for Binary Signals
4
DIGITAL SYSTEMS AND INFORMATION
output ranges allows the circuits to function correctly in spite of variations in their
behavior and undesirable “noise” voltages that may be added to or subtracted
from the outputs.
We give the output and input voltage ranges a number of different names.
Among these are HIGH (H) and LOW (L), TRUE (T) and FALSE (F), and 1 and
0. It is natural to associate the higher voltage ranges with HIGH or H, and the
lower voltage ranges with LOW or L. For TRUE and 1 and FALSE and 0, however, there is a choice. TRUE and 1 can be associated with either the higher or
lower voltage range and FALSE and 0 with the other range. Unless otherwise indicated, we assume that TRUE and 1 are associated with the higher of the voltage
ranges, H, and that FALSE and 0 are associated with the lower of the voltage
ranges, L. This particular convention is called positive logic.
It is interesting to note that the values of voltages for a digital circuit in
Figure 1(a) are still continuous, ranging from 0.1 to +1.1 volts. Thus, the voltage is actually analog! The actual voltages values for the output of a very highspeed digital circuit are plotted versus time in Figure 1(b). Such a plot is
referred to as a waveform. The interpretation of the voltage as binary is based
on a model using voltage ranges to represent discrete values 0 and 1 on the
inputs and the outputs. The application of such a model, which redefines all
voltage above 0.5 V as 1 and below 0.5 V as 0 in Figure 1(b), gives the waveform in Figure 1(c). The output has now been interpreted as binary, having only
discrete values 1 and 0, with the actual voltage values removed. We note that
digital circuits, made up of electronic devices called transistors, are designed to
cause the outputs to occupy the two distinct output voltage ranges for 1 (H)
and 0 (L) in Figure 1, whenever the outputs are not changing. In contrast, analog circuits are designed to have their outputs take on continuous values over
their range, whether changing or not.
Since 0 and 1 are associated with the binary number system, they are the preferred names for the signal ranges. A binary digit is called a bit. Information is represented in digital computers by groups of bits. By using various coding techniques,
groups of bits can be made to represent not only binary numbers, but also other
groups of discrete symbols. Groups of bits, properly arranged, can even specify to
the computer the program instructions to be executed and the data to be processed.
Why is binary used? In contrast to the situation in Figure 1, consider a system with 10 values representing the decimal digits. In such a system, the voltages
available—say, 0 to 1.0 volts—could be divided into 10 ranges, each of length
0.1 volt. A circuit would provide an output voltage within each of these 10 ranges.
An input of a circuit would need to determine in which of the 10 ranges an applied
voltage lies. If we wish to allow for noise on the voltages, then output voltage
might be permitted to range over less than 0.05 volt for a given digit representation, and boundaries between inputs could vary by less than 0.05 volt. This would
require complex and costly electronic circuits, and the output still could be disturbed by small “noise” voltages or small variations in the circuits occurring during
their manufacture or use. As a consequence, the use of such multivalued circuits is
very limited. Instead, binary circuits are used in which correct circuit operation can
be achieved with significant variations in values of the two output voltages and the
5
DIGITAL SYSTEMS AND INFORMATION
Memory
CPU
Control
unit
Datapath
Input/Output
FIGURE 2
Block Diagram of a Digital Computer
two input ranges. The resulting transistor circuit with an output that is either
HIGH or LOW is simple, easy to design, and extremely reliable. In addition, this
use of binary values makes the results calculated repeatable in the sense that the
same set of input values to a calculation always gives exactly the same set of outputs. This is not necessarily the case for multivalued or analog circuits, in which
noise voltages and small variations due to manufacture or circuit aging can cause
results to differ at different times.
The Digital Computer
A block diagram of a digital computer is shown in Figure 2. The memory stores
programs as well as input, output, and intermediate data. The datapath performs
arithmetic and other data-processing operations as specified by the program. The
control unit supervises the flow of information between the various units. A datapath, when combined with the control unit, forms a component referred to as a
central processing unit, or CPU.
The program and data prepared by the user are transferred into memory by
means of an input device such as a keyboard. An output device, such as an LCD
(liquid crystal display), displays the results of the computations and presents them
to the user. A digital computer can accommodate many different input and output
devices, such as CD-ROM and DVD drives, scanners, and printers. These devices
use digital logic circuits, but often include analog electronic circuits, optical sensors,
LCDs (liquid crystal displays), and electromechanical components.
The control unit in the CPU retrieves the instructions, one by one, from the
program stored in the memory. For each instruction, the control unit manipulates
the datapath to execute the operation specified by the instruction. Both program
and data are stored in memory. A digital computer can perform arithmetic computations, manipulate strings of alphabetic characters, and be programmed to make
decisions based on internal and external conditions.
6
DIGITAL SYSTEMS AND INFORMATION
Beyond the Computer
In terms of world impact, computers, such as the PC, are not the end of the story.
Smaller, often less powerful, single-chip computers called microcomputers or
microcontrollers, or special-purpose computers called digital signal processors
(DSPs) actually are more prevalent in our lives. These computers are parts of
everyday products and their presence is often not apparent. As a consequence of
being integral parts of other products and often enclosed within them, they are
called embedded systems. A generic block diagram of an embedded system is
shown in Figure 3. Central to the system is the microcomputer (or its equivalent).
It has many of the characteristics of the PC, but differs in the sense that its software programs are often permanently stored to provide only the functions
required for the product. This software, which is critical to the operation of the
product, is an integral part of the embedded system and referred to as embedded
software. Also, the human interface of the microcomputer can be very limited or
nonexistent. The larger information-storage components such as a hard drive and
compact disk or DVD drive frequently are not present. The microcomputer contains some memory; if additional memory is needed, it can be added externally.
With the exception of the external memory, the hardware connected to the
embedded microcomputer in Figure 3 interfaces with the product and/or the outside world. The input devices transform inputs from the product or outside world
into electrical signals, and the output devices transform electrical signals into outputs to the product or outside world. The input and output devices are of two
types, those which use analog signals and those which use digital signals. Examples
of digital input devices include a limit switch which is closed or open depending on
whether a force is applied to it and a keypad having ten decimal integer buttons.
Examples of analog input devices include a thermistor which changes its electrical
Analog
Input Devices
and Signal
Conditioning
D-to-A
Converters
A-to-D
Converters
Digital
Input Devices
and Signal
Conditioning
Microcomputer,
Microcontroller,
or Digital Signal
Processor
Signal
Conditioning
and Digital
Output Devices
Signal
Conditioning
and Digital
Output Devices
External
Memory
FIGURE 3
Block Diagram of an Embedded System
7
DIGITAL SYSTEMS AND INFORMATION
resistance in response to the temperature and a crystal which produces a charge
(and a corresponding voltage) in response to the pressure applied. Typically, electrical or electronic circuitry is required to “condition” the signal so that it can be
read by the embedded system. Examples of digital output devices include relays
(switches that are opened or closed by applied voltages), a stepper motor that
responds to applied voltage pulses, or an LED digital display. Examples of analog
output devices include a loudspeaker and a panel meter with a dial. The dial position is controlled by the interaction of the magnetic fields of a permanent magnet
and an electromagnet driven by the voltage applied to the meter.
Next, we illustrate embedded systems by considering a temperature measurement performed by using a wireless weather station. In addition, this example also
illustrates analog and digital signals, including conversion between the signal types.
EXAMPLE 1
Temperature Measurement and Display
A wireless weather station measures a number of weather parameters at an outdoor site and transmits them for display to an indoor base station. Its operation
can be illustrated by considering the temperature measurement illustrated in Figure 4 with reference to the block diagram in Figure 3. Two embedded microprocessors are used, one in the outdoor site and the other in the indoor base station.
The temperature at the outdoor site ranges continuously from 40°F to
+115°F. Temperature values over one 24-hour period are plotted as a function of
time in Figure 4(a). This temperature is measured by a sensor consisting of a thermistor (a resistance that varies with temperature) with a fixed current applied by
an electronic circuit. This sensor provides an analog voltage that is proportional to
the temperature. Using signal conditioning, this voltage is changed to a continuous
voltage ranging between 0 and 15 volts, as shown in Figure 4(b).
The analog voltage is sampled at a rate of once per hour (a very slow sampling rate used just for illustration), as shown by the dots in Figure 4(b). Each
value sampled is applied to an analog-to-digital (A/D) converter, as in Figure 3,
which replaces the value with a digital number written in binary and having decimal values between 0 and 15, as shown in Figure 4(c). A binary number can be
interpreted in decimal by multiplying the bits from left to right times the respective
weights, 8, 4, 2, and 1, and adding the resulting values. For example, 0101 can be
interpreted as 0  8  1  4  0  2  1  1  5 . In the process of conversion, the
value of the temperature is quantized from an infinite number of values to just 16
values. Examining the correspondence between the temperature in Figure 4(a) and
the voltage in Figure 4(b), we find that the typical digital value of temperature represents an actual temperature range up to 5 degrees above or below the digital
value. For example, the analog temperature range between 25 and 15 degrees is
represented by the digital temperature value of 20 degrees. This discrepancy
between the actual temperature and the digital temperature is called the quantization error. In order to obtain greater precision, we would need to increase the number of bits beyond four in the output of the A/D converter. The hardware
8
DIGITAL SYSTEMS AND INFORMATION
Temperature (degrees F)
120
80
40
0
40
0
4
8
12
16
20
24
(a) Analog temperature
Sensor and
Signal Conditioning
Voltage (Volts)
16
12
Time (hours)
Sampling point
8
4
0
Time (Hours)
0
4
8
12
16
20
(b) Continuous (analog) voltage
24
Analog-to-Digital
(A/D) Conversion
Digital numbers (binary)
16
11
00
00
01
01 01
01 01
01 00
0
00 0
1
00 1
11
4
01
8
00
1
00 1
00 11
1
011
00
01
0
011
10
01
1
01 1
01 11
1
01 1
0111
1
01 1
10
01
0
00 0
0011
0011
11
12
Time (hours)
0
0
4
8
12
16
20
24
20
24
20
24
(c) Digital voltage
Digital-to-Analog
(D/A) Conversion
Voltage (volts)
16
12
8
4
0
Time (hours)
0
4
8
12
16
(d) Discrete (digital) voltage
Signal Conditioning
Voltage (volts)
16
12
8
4
0
0
4
8
12
16
Time (hours)
Output
(e) Continuous (analog) voltage
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
20 40 60
0 Temp 80
20
100
40 120
(f) Continuous (analog) readout
FIGURE 4
Temperature Measurement and Display
9
DIGITAL SYSTEMS AND INFORMATION
components for sensing, signal conditioning, and A/D conversion are shown in the
upper left corner of Figure 3.
Next, the digital value passes through the microcomputer to a wireless transmitter as a digital output device in the lower right corner of Figure 3. The digital
value is transmitted to a wireless receiver, which is a digital input device in the
base station. The digital value enters the microcomputer at the base station, where
calculations may be performed to adjust its value based on thermistor properties.
The resulting value is to be displayed with an analog meter shown in Figure 4(f) as
the output device. In order to support this display, the digital value is converted to
an analog value by a digital-to-analog converter, giving the quantized, discrete
voltage levels shown in Figure 4(d). Signal conditioning, such as processing of the
output by a low-pass analog filter, is applied to give the continuous signal in Figure 4(e). This signal is applied to the analog voltage display, which has been
labeled with the corresponding temperature values shown for five selected points
over the 24-hour period in Figure 4(f).
■
TABLE 1
Embedded System Examples
Application Area
Product
Banking, commerce and manufacturing Copiers, FAX machines, UPC scanners, vending machines, automatic teller machines,
automated warehouses, industrial robots
10
Communication
Cell phones, routers, satellites
Games and toys
Video games, handheld games, talking stuffed
toys
Home appliances
Digital alarm clocks, conventional and microwave ovens, dishwashers
Media
CD players, DVD players, flat panel TVs,
Digital cameras, digital video cameras
Medical equipment
Pacemakers, incubators, magnetic resonance
imaging
Personal
Digital watches, MP3 players, personal digital
assistants
Transportation and navigation
Electronic engine controls, traffic light controllers, aircraft flight controls, global positioning systems
DIGITAL SYSTEMS AND INFORMATION
You might ask: “How many embedded systems are there in my current living
environment?” Do you have a cell phone? An iPodTM? An XboxTM? A digital camera? A microwave oven? An automobile? All of these are embedded systems! In
fact, a late-model automobile can contain more than 50 microcontrollers, each controlling a distinct embedded system, such as the engine control unit (ECU), automatic braking system (ABS), and stability control unit (SCU). Further, a
significant proportion of these embedded systems communicate with each other
through a CAN (controller area network). A new automotive network called
FlexRay promises to provide high-speed, reliable communication for safety-critical
tasks such as braking-by-wire and steering-by-wire, eliminating primary dependence on mechanical and hydraulic linkages and enhancing the potential for additional safety features such as collision avoidance. Table 1 lists examples of
embedded systems classified by application area.
Considering the widespread use of personal computers and embedded systems, the impact of digital systems on our lives is truly mind boggling! Digital
systems play central roles in our medical diagnosis and treatment, our educational institutions and workplaces, in moving from place to place, in our homes,
in interacting with others, and in just having fun! Considering the complexity of
many of these systems, it is a wonder that they work at all. Thanks to the invention of the transistor and the integrated circuit and to the ingenuity and perseverance of millions of engineers and programmers, they indeed work and usually
work well.
More on the Generic Computer
At this point, we will briefly discuss the generic computer and relate its various
parts to the block diagram in Figure 2. At the lower left of the diagram at the
beginning of this chapter is the heart of the computer, an integrated circuit called
the processor. Modern processors such as this one are quite complex and consist of
tens to hundreds of millions of transistors. The processor contains four functional
modules: the CPU, the FPU, the MMU, and the internal cache.
We have already discussed the CPU. The FPU (floating-point unit) is somewhat like the CPU, except that its datapath and control unit are specifically
designed to perform floating-point operations. In essence, these operations process information represented in the form of scientific notation (e.g., 1.234  107 ),
permitting the generic computer to handle very large and very small numbers.
The CPU and the FPU, in relation to Figure 2, each contain a datapath and a
control unit.
The MMU is the memory management unit. The MMU plus the internal cache
and the separate blocks near the bottom of the computer labeled “External Cache”
and “RAM” (random-access memory) are all part of the memory in Figure 2. The
two caches are special kinds of memory that allow the CPU and FPU to get at the
data to be processed much faster than with RAM alone. RAM is what is most commonly referred to as memory. As its main function, the MMU causes the memory
11
DIGITAL SYSTEMS AND INFORMATION
that appears to be available to the CPU to be much, much larger than the actual
size of the RAM. This is accomplished by data transfers between the RAM and the
hard drive shown at the top of the drawing of the generic computer. So the hard
drive, which we discuss later as an input/output device, conceptually appears as a
part of both the memory and input/output.
The connection paths shown between the processor, memory, and external
cache are the pathways between integrated circuits. These are typically implemented as fine copper conductors on a printed circuit board. The connection paths
below the bus interface are referred to as the processor bus. The connections above
the bus interface are the input/output (I/O) bus. The processor bus and the I/O bus
attached to the bus interface carry data having different numbers of bits and have
different ways of controlling the movement of data. They may also operate at different speeds. The bus interface hardware handles these differences so that data
can be communicated between the two buses.
All of the remaining structures in the generic computer are considered part of
I/O in Figure 2. In terms of sheer physical volume, these structures dominate. In
order to enter information into the computer, a keyboard is provided. In order to
view output in the form of text or graphics, a graphics adapter card and LCD (liquid
crystal display) screen are provided. The hard drive, discussed previously, is an electromechanical magnetic storage device. It stores large quantities of information in
the form of magnetic flux on spinning disks coated with magnetic materials. In order
to control the hard drive and transfer information to and from it, a drive controller
is used. The keyboard, graphics adapter card, and drive controller card are all
attached to the I/O bus. This allows these devices to communicate through the bus
interface with the CPU and other circuitry connected to the processor buses.
The generic computer consists mainly of an interconnection of digital modules.
To understand the operation of each module, we need a basic knowledge of digital
systems and their general behavior.
Earlier, we mentioned that a digital computer manipulates discrete elements
of information and that all information in the computer is represented in binary
12
DIGITAL SYSTEMS AND INFORMATION
form. Operands used for calculations may be expressed in the binary number system or in the decimal system by means of a binary code. The letters of the alphabet are also converted into a binary code. The remainder of this chapter
introduces the binary number system, binary arithmetic, and selected binary codes
as a basis for further study. In relation to the generic computer, this material is
very important and spans all of the components, excepting some in I/O that
involve mechanical operations and analog (as contrasted with digital) electronics.
2 NUMBER SYSTEMS
The decimal number system is employed in everyday arithmetic to represent
numbers by strings of digits. Depending on its position in the string, each digit
has an associated value of an integer raised to the power of 10. For example, the
decimal number 724.5 is interpreted to represent 7 hundreds plus 2 tens plus 4
units plus 5 tenths. The hundreds, tens, units, and tenths are powers of 10
implied by the position of the digits. The value of the number is computed as
follows:
724.5  7  102  2  101  4  100  5  101
The convention is to write only the digits and infer the corresponding powers of 10
from their positions. In general, a decimal number with n digits to the left of the
decimal point and m digits to the right of the decimal point is represented by a
string of coefficients:
An  1 An  2… A1A0.A1A2… A m  1 Am
Each coefficient Ai is one of 10 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). The subscript
value i gives the position of the coefficient and, hence, the weight 10i by which
the coefficient must be multiplied.
The decimal number system is said to be of base or radix 10, because the
coefficients are multiplied by powers of 10 and the system uses 10 distinct digits. In
general, a number in base r contains r digits, 0, 1, 2, …, r − 1, and is expressed as a
power series in r with the general form
An  1 r
n 1
 An  2 r
 A 1 r
1
n 2
1
 …  A1 r  A0 r
 A 2 r
2
0
 …  A m  1 r
m 1
 A m r
m
When the number is expressed in positional notation, only the coefficients and the
radix point are written down:
An  1An  2… A1A0.A1A2 … A m  1Am
In general, the “.” is called the radix point. An – 1 is referred to as the most significant digit (msd) and Am as the least significant digit (lsd) of the number. Note that
13
DIGITAL SYSTEMS AND INFORMATION
if m  0, the lsd is A0  A0 . To distinguish between numbers of different bases, it
is customary to enclose the coefficients in parentheses and place a subscript after
the right parenthesis to indicate the base of the number. However, when the context makes the base obvious, it is not necessary to use parentheses. The following
illustrates a base 5 number with n  3 and m  1 and its conversion to decimal:
( 312.4 )5  3  52  1  51  2  50  4  51
 75  5  2  0.8  ( 82.8 )10
Note that for all the numbers without the base designated, the arithmetic is performed with decimal numbers. Note also that the base 5 system uses only five digits, and, therefore, the values of the coefficients in a number can be only 0, 1, 2, 3,
and 4 when expressed in that system.
An alternative method for conversion to base 10 that reduces the number of
operations is based on a factored form of the power series:
( …( ( An  1r  An  2 )r  An  3 )r  …  A1 )r  A0
 ( A 1  ( A 2  ( A 3  …  ( A  m  2  ( A  m  1  A m r
1
)r
1
1
)r …) r
1
)r
1
)r
1
For the example above,
( 312.4 )5  ( ( 3  5  1 )  5)  2  4  51
 16  5  2  0.8  ( 82.8 )10
In addition to decimal, three number systems are used in computer work:
binary, octal, and hexadecimal. These are base 2, base 8, and base 16 number systems, respectively.
Binary Numbers
The binary number system is a base 2 system with two digits: 0 and 1. A binary
number such as 11010.11 is expressed with a string of 1s and 0s and, possibly, a
binary point. The decimal equivalent of a binary number can be found by expanding the number into a power series with a base of 2. For example,
( 11010 )2  1  24  1  23  0  22  1  21  0  20  ( 26 )10
As noted earlier, the digits in a binary number are called bits. When a bit is equal
to 0, it does not contribute to the sum during the conversion. Therefore, the conversion to decimal can be obtained by adding the numbers with powers of two corresponding to the bits that are equal to 1. For example,
( 110101.11 )2  32  16  4  1  0.5  0.25  ( 53.75 )10
14
DIGITAL SYSTEMS AND INFORMATION
TABLE 2
Powers of Two
n
2n
n
2n
n
2n
0
1
2
3
4
5
6
7
1
2
4
8
16
32
64
128
8
9
10
11
12
13
14
15
256
512
1,024
2,048
4,096
8,192
16,384
32,768
16
17
18
19
20
21
22
23
65,536
131,072
262,144
524,288
1,048,576
2,097,152
4,194,304
8,388,608
The first 24 numbers obtained from 2 to the power of n are listed in Table 2. In
digital systems, we refer to 210 as K (kilo), 220 as M (mega), 230 as G (giga), and 240 as
T (tera). Thus,
4K  22 × 210 = 212 = 4096
and
16M  24 × 220 = 224 = 16,777,216
This convention does not necessarily apply in all cases, with more conventional usage of K, M, G, and T as 103, 106, 109 and 1012, respectively, sometimes applied as
well. So caution is necessary in interpreting and using this notation.
The conversion of a decimal number to binary can be easily achieved by a
method that successively subtracts powers of two from the decimal number. To
convert the decimal number N to binary, first find the greatest number that is a
power of two (see Table 2) and that, subtracted from N, produces a positive difference. Let the difference be designated N1 . Now find the greatest number that is a
power of two and that, subtracted from N1 , produces a positive difference N2 .
Continue this procedure until the difference is zero. In this way, the decimal number is converted to its powers-of-two components. The equivalent binary number is
obtained from the coefficients of a power series that forms the sum of the components. 1s appear in the binary number in the positions for which terms appear in
the power series, and 0s appear in all other positions. This method is demonstrated
by the conversion of decimal 625 to binary as follows:
625  512  113  N1
512  29
113  64  49  N2
64  26
49  32  17  N3
32  25
17  16  1  N4
16  24
1  1  0  N5
1  20
( 625 )10  29  26  25  24  20  ( 1001110001 )2
15
DIGITAL SYSTEMS AND INFORMATION
Octal and Hexadecimal Numbers
As previously mentioned, all computers and digital systems use the binary representation. The octal (base 8) and hexadecimal (base 16) systems are useful for representing binary quantities indirectly because their bases are powers of two. Since
23  8 and 24  16, each octal digit corresponds to three binary digits and each
hexadecimal digit corresponds to four binary digits.
The more compact representation of binary numbers in either octal or
hexadecimal is much more convenient for people than using bit strings in binary
that are three or four times as long. Thus, most computer manuals use either
octal or hexadecimal numbers to specify binary quantities. A group of 15 bits, for
example, can be represented in the octal system with only five digits. A group of
16 bits can be represented in hexadecimal with four digits. The choice between an
octal and a hexadecimal representation of binary numbers is arbitrary, although
hexadecimal tends to win out, since bits often appear in strings of size divisible
by four.
The octal number system is the base 8 system with digits 0, 1, 2, 3, 4, 5, 6, and
7. An example of an octal number is 127.4. To determine its equivalent decimal
value, we expand the number in a power series with a base of 8:
( 127.4 )8  1  82  2  81  7  80  4  81  ( 87.5 )10
Note that the digits 8 and 9 cannot appear in an octal number.
It is customary to use the first r digits from the decimal system, starting with
0, to represent the coefficients in a base r system when r is less than 10. The letters
of the alphabet are used to supplement the digits when r is 10 or more. The hexadecimal number system is a base 16 system with the first 10 digits borrowed from
the decimal system and the letters A, B, C, D, E, and F used for the values 10, 11,
12, 13, 14, and 15, respectively. An example of a hexadecimal number is
(B65F)16  11  163  6  162  5  161  15  160  ( 46687 )10
The first 16 numbers in the decimal, binary, octal, and hexadecimal number systems are listed in Table 3. Note that the sequence of binary numbers follows a prescribed pattern. The least significant bit alternates between 0 and 1, the second
significant bit between two 0s and two 1s, the third significant bit between four 0s
and four 1s, and the most significant bit between eight 0s and eight 1s.
The conversion from binary to octal is easily accomplished by partitioning
the binary number into groups of three bits each, starting from the binary point
and proceeding to the left and to the right. The corresponding octal digit is then
assigned to each group. The following example illustrates the procedure:
( 010 110 001 101 011. 111 100 000 110)2  ( 26153.7406 )8
The corresponding octal digit for each group of three bits is obtained from the first eight
entries in Table 3. To make the total count of bits a multiple of three, 0s can be added
on the left of the string of bits to the left of the binary point. More importantly, 0s must
16
DIGITAL SYSTEMS AND INFORMATION
TABLE 3
Numbers with Different Bases
Decimal
(base 10)
Binary
(base 2)
Octal
(base 8)
Hexadecimal
(base 16)
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
00
01
02
03
04
05
06
07
10
11
12
13
14
15
16
17
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
be added on the right of the string of bits to the right of the binary point to make the
number of bits a multiple of three and obtain the correct octal result.
Conversion from binary to hexadecimal is similar, except that the binary
number is divided into groups of four digits, starting at the binary point. The previous binary number is converted to hexadecimal as follows:
( 0010 1100 0110 1011. 1111 0000 0110)2  ( 2C6B.F06 )16
The corresponding hexadecimal digit for each group of four bits is obtained by reference to Table 3.
Conversion from octal or hexadecimal to binary is done by reversing the procedure just performed. Each octal digit is converted to a 3-bit binary equivalent,
and extra 0s are deleted. Similarly, each hexadecimal digit is converted to its 4-bit
binary equivalent. This is illustrated in the following examples:
(673.12)8 = 110 111 011. 001 010 = (110111011.00101)2
(3A6.C)16 = 0011 1010 0110. 1100
= (1110100110.11)2
Number Ranges
In digital computers, the range of numbers that can be represented is based on the
number of bits available in the hardware structures that store and process information. The number of bits in these structures is most frequently a power of two, such
as 8, 16, 32, and 64. Since the numbers of bits is fixed by the structures, the addition
of leading or trailing zeros to represent numbers is necessary, and the range of
numbers that can be represented is also fixed.
17
DIGITAL SYSTEMS AND INFORMATION
For example, for a computer processing 16-bit unsigned integers, the number 537 is represented as 0000001000011001. The range of integers that can be
handled by this representation is from 0 to 216  1, that is, from 0 to 65,535. If the
same computer is processing 16-bit unsigned fractions with the binary point to the
left of the most significant digit, then the number 0.375 is represented by
0.0110000000000000. The range of fractions that can be represented is from 0 to
(216  1)/216, or from 0.0 to 0.9999847412.
We will deal with fixed-bit representations and ranges for binary signed
numbers and floating-point numbers. In both of these cases, some bits are used
to represent information other than simple integer or fraction values.
3 ARITHMETIC OPERATIONS
Arithmetic operations with numbers in base r follow the same rules as for decimal
numbers. However, when a base other than the familiar base 10 is used, one must
be careful to use only r allowable digits and perform all computations with base r
digits. Examples of the addition of two binary numbers are as follows (note the
names of the operands for addition):
Carries:
00000
101100
Augend:
01100
10110
Addend:
10001
10111
11101
101101
Sum:
The sum of two binary numbers is calculated following the same rules as for decimal numbers, except that the sum digit in any position can be only 1 or 0. Also, a
carry in binary occurs if the sum in any bit position is greater than 1. (A carry in
decimal occurs if the sum in any digit position is greater than 9.) Any carry
obtained in a given position is added to the bits in the column one significant position higher. In the first example, since all of the carries are 0, the sum bits are simply the sum of the augend and addend bits. In the second example, the sum of the
bits in the second column from the right is 2, giving a sum bit of 0 and a carry bit of
1 (2  2  0). The carry bit is added with the 1s in the third position, giving a sum
of 3, which produces a sum bit of 1 and a carry of 1 (3  2  1).
The following are examples of the subtraction of two binary numbers; as with
addition, note the names of the operands:
Borrows:
00000
00110
Minuend:
10110
10110
10011
11110
10010
10011
11110
10011
00100
00011
Subtrahend:
Difference:
18
00110
01011
DIGITAL SYSTEMS AND INFORMATION
The rules for subtraction are the same as in decimal, except that a borrow into a
given column adds 2 to the minuend bit. (A borrow in the decimal system adds 10
to the minuend digit.) In the first example shown, no borrows occur, so the difference bits are simply the minuend bits minus the subtrahend bits. In the second
example, in the right position, the subtrahend bit is 1 with the minuend bit 0, so it
is necessary to borrow from the second position as shown. This gives a difference
bit in the first position of 1 (2  0  1  1). In the second position, the borrow is
subtracted, so a borrow is again necessary. Recall that, in the event that the subtrahend is larger than the minuend, we subtract the minuend from the subtrahend
and give the result a minus sign. This is the case in the third example, in which this
interchange of the two operands is shown.
The final operation to be illustrated is binary multiplication, which is quite
simple. The multiplier digits are always 1 or 0. Therefore, the partial products are
equal either to the multiplicand or to 0. Multiplication is illustrated by the following example:
Multiplicand:
1011
× 101
Multiplier:
1011
00000
101100
Product:
110111
Arithmetic operations with octal, hexadecimal, or any other base r system
will normally require the formulation of tables from which one obtains sums and
products of two digits in that base. An easier alternative for adding two numbers
in base r is to convert each pair of digits in a column to decimal, add the digits in
decimal, and then convert the result to the corresponding sum and carry in the
base r system. Since addition is done in decimal, we can rely on our memories
for obtaining the entries from the familiar decimal addition table. The sequence
of steps for adding the two hexadecimal numbers 59F and E46 is shown in
Example 2.
EXAMPLE 2
Hexadecimal Addition
Perform the addition ( 59F )16  ( E46 )16:
Hexadecimal
Equivalent Decimal Calculation
1
59F
E46
13E5
5
14
Carry
1 19  16  3
1
9
4
14  E
15
6
Carry
21  16  5
19
DIGITAL SYSTEMS AND INFORMATION
The equivalent decimal calculation columns on the right show the mental reasoning that must be carried out to produce each digit of the hexadecimal sum. Instead
of adding F  6 in hexadecimal, we add the equivalent decimals, 15  6  21. We
then convert back to hexadecimal by noting that 21  16  5. This gives a sum
digit of 5 and a carry of 1 to the next higher-order column of digits. The other two
columns are added in a similar fashion.
■
In general, the multiplication of two base r numbers can be accomplished by
doing all the arithmetic operations in decimal and converting intermediate results
one at a time. This is illustrated in the multiplication of two octal numbers shown in
Example 3.
EXAMPLE 3
Octal Multiplication
Perform the multiplication ( 762 )8  ( 45 )8:
Octal
Octal
Decimal
Octal
762
45
5×2
 10  8  2  12
5 × 6  1  31  24  7  37
4672
37100
5 × 7  3  38  32  6  46
4×2
 8  8  0  10
43772
4 × 6  1  25  24  1  31
4 × 7  3  31  24  7  37
Shown on the right are the mental calculations for each pair of octal digits. The octal
digits 0 through 7 have the same value as their corresponding decimal digits. The
multiplication of two octal digits plus a carry, derived from the calculation on the
previous line, is done in decimal, and the result is then converted back to octal. The
left digit of the two-digit octal result gives the carry that must be added to the digit
product on the next line. The blue digits from the octal results of the decimal calculations are copied to the octal partial products on the left. For example,
( 5  2 )8  ( 12 )8. The left digit, 1, is the carry to be added to the product ( 5  6 )8,
and the blue least significant digit, 2, is the corresponding digit of the octal partial
product. When there is no digit product to which the carry can be added, the carry is
written directly into the octal partial product, as in the case of the 4 in 46.
■
Conversion from Decimal to Other Bases
We convert a number in base r to decimal by expanding it in a power series and
adding all the terms, as shown previously. We now present a general procedure for
the operation of converting a decimal number to a number in base r that is the
reverse of the alternative expansion to base 10 as discussed earlier. If the number
includes a radix point, we need to separate the number into an integer part and a
fraction part, since the two parts must be converted differently. The conversion of a
decimal integer to a number in base r is done by dividing the number and all successive
20
DIGITAL SYSTEMS AND INFORMATION
quotients by r and accumulating the remainders. This procedure is best explained by
example.
EXAMPLE 4
Conversion of Decimal Integers to Octal
Convert decimal 153 to octal:
The conversion is to base 8. First, 153 is divided by 8 to give a quotient of 19 and
a remainder of 1, as shown in blue. Then 19 is divided by 8 to give a quotient of 2
and a remainder of 3. Finally, 2 is divided by 8 to give a quotient of 0 and a
remainder of 2. The coefficients of the desired octal number are obtained from
the remainders:
153/8  19  1/8
Remainder  1
19/8  29  3/8
3
2/8  0  2/8
2
Least significant digit
Most significant digit
(153)10  (231)8
■
Note in Example 4 that the remainders are read from last to first, as indicated
by the arrow, to obtain the converted number. The quotients are divided by r until
the result is 0. We also can use this procedure to convert decimal integers to binary,
as shown in Example 5. In this case, the base of the converted number is 2, and
therefore, all the divisions must be done by 2.
EXAMPLE 5
Conversion of Decimal Integers to Binary
Convert decimal 41 to binary:
41/2  20  1/2
Remainder  1
20/2  10
0
10/2  5
0
5/2  2  1/2
1
2/2  1
0
1/2  0  1/2
1
Least significant digit
Most significant digit
(4l)10  (l0l001)2
Of course, the decimal number could be converted by the sum of powers of two:
(41)10  32  8  1  (101001)2
■
The conversion of a decimal fraction to base r is accomplished by a method
similar to that used for integers, except that multiplication by r is used instead of
21
DIGITAL SYSTEMS AND INFORMATION
division, and integers are accumulated instead of remainders. Again, the method is
best explained by example.
EXAMPLE 6
Conversion of Decimal Fractions to Binary
Convert decimal 0.6875 to binary:
First, 0.6875 is multiplied by 2 to give an integer and a fraction. The new fraction is
multiplied by 2 to give a new integer and a new fraction. This process is continued until
the fractional part equals 0 or until there are enough digits to give sufficient accuracy.
The coefficients of the binary number are obtained from the integers as follows:
0.6875 × 2  1.3750
0.3750 × 2  0.7500
0.7500 × 2  1.5000
0.5000 × 2  1.0000
(0.6875)10  (0.1011)2
Integer  1
0
1
1
Most significant digit
Least significant digit
■
Note in the foregoing example that the integers are read from first to last, as
indicated by the arrow, to obtain the converted number. In the example, a finite
number of digits appear in the converted number. The process of multiplying fractions by r does not necessarily end with zero, so we must decide how many digits of
the fraction to use from the conversion. Also, remember that the multiplications
are by number r. Therefore, to convert a decimal fraction to octal, we must multiply the fractions by 8, as shown in Example 7.
EXAMPLE 7
Conversion of Decimal Fractions to Octal
Convert decimal 0.513 to a three-digit octal fraction:
0.513 × 8  4.104
0.104 × 8  0.832
0.832 × 8  6.656
0.656 × 8  5.248
Integer  4
0
6
5
Most significant digit
Least significant digit
The answer, to three significant figures, is obtained from the integer digits. Note
that the last integer digit, 5, is used for rounding in base 8 of the second-to-the-last
digit, 6, to obtain
(0.513)10  (0.407)8
■
The conversion of decimal numbers with both integer and fractional parts is
done by converting each part separately and then combining the two answers.
Using the results of Example 4 and Example 7, we obtain
(153.513)10  (23l.407)8
22
DIGITAL SYSTEMS AND INFORMATION
4 DECIMAL CODES
The binary number system is the most natural one for a computer, but people are
accustomed to the decimal system. One way to resolve this difference is to convert
decimal numbers to binary, perform all arithmetic calculations in binary, and then
convert the binary results back to decimal. This method requires that we store the
decimal numbers in the computer in such a way that they can be converted to
binary. Since the computer can accept only binary values, we must represent the
decimal digits by a code that contains 1s and 0s. It is also possible to perform the
arithmetic operations directly with decimal numbers when they are stored in the
computer in coded form.
An n-bit binary code is a group of n bits that assume up to 2n distinct combinations of 1s and 0s, with each combination representing one element of the set
being coded. A set of four elements can be coded with a 2-bit binary code, with
each element assigned one of the following bit combinations: 00, 01, 10, 11. A set of
8 elements requires a 3-bit code, and a set of 16 elements requires a 4-bit code. The
bit combinations of an n-bit code can be determined from the count in binary from
0 to 2n  1. Each element must be assigned a unique binary bit combination, and
no two elements can have the same value; otherwise, the code assignment is
ambiguous.
A binary code will have some unassigned bit combinations if the number of
elements in the set is not a power of 2. The ten decimal digits form such a set. A
binary code that distinguishes among ten elements must contain at least four bits,
but six out of the 16 possible combinations will remain unassigned. Numerous different binary codes can be obtained by arranging four bits into 10 distinct combinations. The code most commonly used for the decimal digits is the straightforward
binary assignment listed in Table 3. This is called binary-coded decimal and is commonly referred to as BCD. Other decimal codes are possible.
Table 4 gives a 4-bit code for each decimal digit. A number with n decimal
digits will require 4n bits in BCD. Thus, decimal 396 is represented in BCD with
12 bits as
0011 1001 0110
with each group of four bits representing one decimal digit. A decimal number in
BCD is the same as its equivalent binary number only when the number is
between 0 and 9, inclusive. A BCD number greater than 10 has a representation
different from its equivalent binary number, even though both contain 1s and 0s.
Moreover, the binary combinations 1010 through 1111 are not used and have no
meaning in the BCD code.
Consider decimal 185 and its corresponding value in BCD and binary:
(185)10  (0001 1000 0101)BCD  (10111001)2
23
DIGITAL SYSTEMS AND INFORMATION
TABLE 4
Binary-Coded Decimal (BCD)
Decimal
Symbol
BCD
Digit
0
1
2
3
4
5
6
7
8
9
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
The BCD value has 12 bits, but the equivalent binary number needs only 8 bits. It
is obvious that a BCD number needs more bits than its equivalent binary value.
However, BCD representation of decimal numbers is still important, because computer input and output data used by most people needs to be in the decimal system. BCD numbers are decimal numbers and not binary numbers, even though
they are represented using bits. The only difference between a decimal and a BCD
number is that decimals are written with the symbols 0, 1, 2, …, 9, and BCD numbers use the binary codes 0000, 0001, 0010, …, 1001.
BCD Addition
Consider the addition of two decimal digits in BCD, together with a possible
carry of 1 from a previous less significant pair of digits. Since each digit does not
exceed 9, the sum cannot be greater than 9  9  1  19, the 1 being a carry.
Suppose we add the BCD digits as if they were binary numbers. Then the binary
sum will produce a result in the range from 0 to 19. In binary, this will be from
0000 to 10011, but in BCD, it should be from 0000 to 1 1001, the first 1 being a
carry and the next four bits being the BCD digit sum. When the binary sum is
less than 1010 (without a carry), the corresponding BCD digit is correct. But
when the binary sum is greater than or equal to 1010, the result is an invalid
BCD digit. The addition of binary 6, (0110)2, to the sum converts it to the correct
digit and also produces a decimal carry as required. The reason is that the difference between a carry from the most significant bit position of the binary sum and
a decimal carry is 16  10  6. Thus, the decimal carry and the correct BCD sum
24
DIGITAL SYSTEMS AND INFORMATION
digit are forced by adding 6 in binary. Consider the next three-digit BCD addition example.
EXAMPLE 8
BCD Addition
110
448
489
BCD carry
937
Binary sum
Add 6
BCD sum
BCD result
1
0100
0100
1
0100
1000
1000
1001
1001
1101
0110
1 0001
0110
1 0011
0011
1 0111
0111
1001
In each position, the two BCD digits are added as if they were two binary numbers.
If the binary sum is greater than 1001, we add 0110 to obtain the correct BCD digit
sum and a carry. In the right column, the binary sum is equal to 17. The presence of
the carry indicates that the sum is greater than 16 (certainly greater than 9), so a
correction is needed. The addition of 0110 produces the correct BCD digit sum,
0111 (7), and a carry of 1. In the next column, the binary sum is 1101 (13), an
invalid BCD digit. Addition of 0110 produces the correct BCD digit sum, 0011 (3),
and a carry of 1. In the final column, the binary sum is equal to 1001 (9) and is the
correct BCD digit.
■
5 ALPHANUMERIC CODES
Many applications of digital computers require the handling of data consisting not
only of numbers, but also of letters. For instance, an insurance company with thousands of policyholders uses a computer to process its files. To represent the names
and other pertinent information, it is necessary to formulate a binary code for the
letters of the alphabet. In addition, the same binary code must represent numerals
and special characters such as $. Any alphanumeric character set for English is a
set of elements that includes the ten decimal digits, the 26 letters of the alphabet,
and several (more than three) special characters. If only capital letters are
included, we need a binary code of at least six bits, and if both uppercase letters
and lowercase letters are included, we need a binary code of at least seven bits.
Binary codes play an important role in digital computers. The codes must be in
binary because computers can handle only 1s and 0s. Note that binary encoding
merely changes the symbols, not the meaning of the elements of information being
encoded.
25
DIGITAL SYSTEMS AND INFORMATION
ASCII Character Code
The standard binary code for the alphanumeric characters is called ASCII
(American Standard Code for Information Interchange). It uses seven bits to
code 128 characters, as shown in Table 5. The seven bits of the code are designated by B1 through B7 , with B7 being the most significant bit. Note that the
most significant three bits of the code determine the column of the table and
the least significant four bits the row of the table. The letter A, for example, is
represented in ASCII as 1000001 (column 100, row 0001). The ASCII code contains 94 characters that can be printed and 34 nonprinting characters used for
various control functions. The printing characters consist of the 26 uppercase
letters, the 26 lowercase letters, the 10 numerals, and 32 special printable characters such as %, @, and $.
The 34 control characters are designated in the ASCII table with abbreviated
names. They are listed again below the table with their full functional names. The
control characters are used for routing data and arranging the printed text into a
prescribed format. There are three types of control characters: format effectors,
information separators, and communication control characters. Format effectors
are characters that control the layout of printing. They include the familiar typewriter controls such as backspace (BS), horizontal tabulation (HT), and carriage
return (CR). Information separators are used to separate the data into divisions—
for example, paragraphs and pages. They include characters such as record separator (RS) and file separator (FS). The communication control characters are used
during the transmission of text from one location to the other. Examples of communication control characters are STX (start of text) and ETX (end of text),
which are used to frame a text message transmitted via communication wires.
ASCII is a 7-bit code, but most computers manipulate an 8-bit quantity as a
single unit called a byte. Therefore, ASCII characters most often are stored one per
byte, with the most significant bit set to 0. The extra bit is sometimes used for specific purposes, depending on the application. For example, some printers recognize
an additional 128 8-bit characters, with the most significant bit set to 1. These characters enable the printer to produce additional symbols, such as those from the
Greek alphabet or characters with accent marks as used in languages other than
English.
UNICODE This supplement on Unicode, a 16-bit standard code for representing the
symbols and ideographs for the world’s languages, is available on the Companion
Website (http://www.prenhall.com/mano) for the text.
Parity Bit
To detect errors in data communication and processing, an additional bit is sometimes added to a binary code word to define its parity. A parity bit is the extra bit
26
DIGITAL SYSTEMS AND INFORMATION
TABLE 5
American Standard Code for Information Interchange (ASCII)
B7 B6 B5
B4 B3 B2 B1
000
001
010
011
100
101
110
111
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
NULL
SOH
STX
ETX
EOT
ENQ
ACK
BEL
BS
HT
LF
VT
FF
CR
SO
SI
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
SP
!
”
#
$
%
&
0
1
2
3
4
5
6
7
8
9
:
;
< = >
?
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
`
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
DEL

(
)
*
+
,
.
/
Control Characters
NULL
SOH
STX
ETX
EOT
ENQ
ACK
BEL
BS
HT
LF
VT
FF
CR
SO
SI
SP
NULL
Start of heading
Start of text
End of text
End of transmission
Enquiry
Acknowledge
Bell
Backspace
Horizontal tab
Line feed
Vertical tab
Form feed
Carriage return
Shift out
Shift in
Space
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
DEL
Data link escape
Device control 1
Device control 2
Device control 3
Device control 4
Negative acknowledge
Synchronous idle
End of transmission block
Cancel
End of medium
Substitute
Escape
File separator
Group separator
Record separator
Unit separator
Delete
27
DIGITAL SYSTEMS AND INFORMATION
included to make the total number of 1s in the resulting code word either even or
odd. Consider the following two characters and their even and odd parity:
1000001
1010100
With Even Parity
With Odd Parity
01000001
11010100
11000001
01010100
In each case, we use the extra bit in the most significant position of the code to produce an even number of 1s in the code for even parity or an odd number of 1s in
the code for odd parity. In general, one parity or the other is adopted, with even
parity being more common. Parity may be used with binary numbers as well as
with codes, including ASCII for characters, and the parity bit may be placed in any
fixed position in the code.
EXAMPLE 9
Error Detection and Correction for ASCII Transmission
The parity bit is helpful in detecting errors during the transmission of information
from one location to another. Assuming that even parity is used, the simplest case
is handled as follows: An even (or odd) parity bit is generated at the sending end
for all 7-bit ASCII characters; the 8-bit characters that include parity bits are transmitted to their destination. The parity of each character is then checked at the
receiving end; if the parity of the received character is not even (odd), it means
that at least one bit has changed its value during the transmission. This method
detects one, three, or any odd number of errors in each character transmitted. An
even number of errors is undetected. Other error-detection codes, some of which
are based on additional parity bits, may be needed to take care of an even number
of errors. What is done after an error is detected depends on the particular application. One possibility is to request retransmission of the message on the assumption
that the error was random and will not occur again. Thus, if the receiver detects a
parity error, it sends back a NAK (negative acknowledge) control character consisting of the even-parity eight bits, 10010101, from Table 5. If no error is detected,
the receiver sends back an ACK (acknowledge) control character, 00000110. The
sending end will respond to a NAK by transmitting the message again, until the
correct parity is received. If, after a number of attempts, the transmission is still in
error, an indication of a malfunction in the transmission path is given.
■
6 GRAY CODES
As we count up or down using binary codes, the number of bits that change from
one binary value to the next varies. This is illustrated by the binary code for the
octal digits on the left in Table 6. As we count from 000 up to 111 and “roll over”
28
DIGITAL SYSTEMS AND INFORMATION
TABLE 6
Gray Code
Binary Bit
Code Changes
Gray Bit
Code Changes
000
001
010
011
100
101
110
111
000
000
001
011
010
110
111
101
100
000
1
2
1
3
1
2
1
3
1
1
1
1
1
1
1
1
to 000, the number of bits that change between the binary values ranges from
1 to 3.
For many applications, multiple bit changes as the circuit counts is not a
problem. There are applications, however, in which a change of more than one
bit when counting up or down can cause serious problems. One such problem is
illustrated by an optical shaft-angle encoder shown in Figure 5(a). The encoder
is a disk attached to a rotating shaft for measurement of the rotational position
of the shaft. The disk contains areas that are clear for binary 1 and opaque for
binary 0. An illumination source is placed on one side of the disk, and optical
sensors, one for each of the bits to be encoded, are placed on the other side of
the disk. When a clear region lies between the source and a sensor, the sensor
responds to the light with a binary 1 output. When an opaque region lies
between the source and the sensor, the sensor responds to the dark with a
binary 0.
The rotating shaft, however, can be in any angular position. For example,
suppose that the shaft and disk are positioned so that the sensors lie right at the
111
000
100
000
B0
110
101
B1
B2
001
010
100
011
(a) Binary code for positions 0 through 7
101
111
001
G0
G1
G2
011
110
010
(b) Gray code for positions 0 through 7
FIGURE 5
Optical Shaft-Angle Encoder
29
DIGITAL SYSTEMS AND INFORMATION
boundary between 011 and 100. In this case, sensors in positions B2, B1 and B0
have the light partially blocked. In such a situation, it is unclear whether the three
sensors will see light or dark. As a consequence, each sensor may produce either a
1 or a 0. Thus, the resulting encoded binary number for a value between 3 and 4
may be 000, 001, 010, 011, 100, 101, 110, or 111. Either 011 or 100 will be satisfactory in this case, but the other six values are clearly erroneous!
To see the solution to this problem, notice that in those cases in which only
a single bit changes when going from one value to the next or previous value,
this problem cannot occur. For example, if the sensors lie on the boundary
between 2 and 3, the resulting code is either 010 or 011, either of which is satisfactory. If we change the encoding of the values 0 through 7 such that only one
bit value changes as we count up or down (including rollover from 7 to 0), then
the encoding will be satisfactory for all positions. A code having the property
that only one bit at a time changes between codes during counting is a Gray code
named for Frank Gray, who patented its use for shaft encoders in 1953. There are
multiple Gray codes for any set of n consecutive integers, with n even.
A specific Gray code for the octal digits, called a binary reflected Gray code,
appears on the right in Table 6. Note that the counting order for binary codes is
now 000, 001, 011, 010, 110, 111, 101, 100, and 000. If we want binary codes for processing, then we can build a digital circuit or use software that converts these codes
to binary before they are used in further processing of the information.
Figure 5(b) shows the optical shaft-angle encoder using the Gray code from
Table 6. Note that any two segments on the disk adjacent to each other have only
one region that is clear for one and opaque for the other.
The optical shaft encoder illustrates one use of the Gray code concept. There
are many other similar uses in which a physical variable, such as position or voltage, has a continuous range of values that is converted to a digital representation.
A quite different use of Gray codes appears in low-power CMOS (Complementary
Metal Oxide Semiconductor) logic circuits that count up or down. In CMOS,
power is consumed only when a bit changes. For the example codes given in Table
6 with continuous counting (either up or down), there are 14 bit changes for binary
counting for every eight bit changes for Gray code counting. Thus, the power consumed at the counter outputs for the Gray code counter is only 57 percent of that
consumed at the binary counter outputs.
A Gray code for a counting sequence of n binary code words (n must be
even) can be constructed by replacing each of the first n/2 numbers in the sequence
with a code word consisting of 0 followed by the even parity for each bit of the
binary code word and the bit to its left. For example, for the binary code word
0100, the Gray code word is 0, parity(0, 1), parity(1, 0), parity(0, 0) = 0110. Next,
take the sequence of numbers formed and copy it in reverse order with the leftmost 0 replaced by a 1. This new sequence provides the Gray code words for the
second n/2 of the original n code words. For example, for BCD codes, the first five
Gray code words are 0000, 0001, 0011, 0010, and 0110. Reversing the order of these
codes and replacing the leftmost 0 with a 1, we obtain 1110, 1010, 1011, 1001, and
1000 for the last five Gray codes. For the special cases in which the original binary
codes are 0 through 2n  1, each Gray code word may be formed directly from the
30
DIGITAL SYSTEMS AND INFORMATION
corresponding binary code word by copying its leftmost bit and then replacing
each of the remaining bits with the even parity of the bit of the number and the bit
to its left.
7 CHAPTER SUMMARY
In this chapter, we introduced digital systems and digital computers and showed
why such systems use signals having only two values. We briefly introduced the
structure of the stored-program digital computer and showed how computers can
be applied to a broad range of specialized applications by using embedded systems.
We then related the computer structure to a representative example of a personal
computer (PC).
Number-system concepts, including base (radix) and radix point, were presented. Because of their correspondence to two-valued signals, binary numbers were
discussed in detail. Octal (base 8) and hexadecimal (base 16) were also emphasized,
since they are useful as shorthand notation for binary. Arithmetic operations in bases
other than base 10 and the conversion of numbers from one base to another were
covered. Because of the predominance of decimal in normal use, Binary-Coded Decimal (BCD) was treated. The representation of information in the form of characters
instead of numbers by means of the ASCII code for the English alphabet was presented. The parity bit was presented as a technique for error detection, and the Gray
code, which is critical to selected applications, was defined.
REFERENCES
1. GRAY, F. Pulse Code Communication. U. S. Patent 2 632 058, March 17, 1953.
2. PATTERSON, D. A., AND J. L. HENNESSY, Computer Organization and Design:
The Hardware/Software Interface, 3rd ed. San Francisco: Morgan Kaufmann,
2004.
3. WHITE, R. How Computers Work: Millennium Edition, 5th ed. Indianapolis:
Que, 1999.
PROBLEMS
The plus (+) indicates a more advanced problem, and the asterisk (*) indicates that
a solution is available on the Companion Website for the text.
1.
This problem concerns wind measurements made by the wireless weather
station illustrated in Example 1. The wind-speed measurement uses a
31
DIGITAL SYSTEMS AND INFORMATION
rotating anemometer connected by a shaft to an enclosed disk that is onehalf clear and one-half black. There is a light above and a photodiode below
the disk in the enclosure. The photodiode produces a 3 V signal when
exposed to light and a 0 V signal when not exposed to light. (a) Sketch the
relative appearance of voltage waveforms produced by this sensor (1) when
the wind is calm, (2) when the wind is 10 mph, and (3) when the wind is 100
mph. (b) Explain verbally what information the microcomputer must have
available and the tasks it must perform to convert the voltage waveforms
produced into a binary number representing wind speed in miles per hour.
32
2.
Using the scheme in Example 1, find the discrete, quantized value of voltage
and the binary code for each of the following Fahrenheit tempera-tures: −34,
+31, +77, and +108.
3.
*List the binary, octal, and hexadecimal numbers from 16 to 31.
4.
What is the exact number of bits in a memory that contains (a) 96K bits;
(b) 640M bits; (c) 4G bits?
5.
How many bits are in 1 Tb? [Hint: Depending on the tool used to calculate
this, you may need to use a trick to get the exact result. Note that 220 =
1,000,00010 + d, where d is the difference between 220 and 1,000,00010, and
that 1T = (1,000,00010 + d)2. Expand the equation for 1T into a sum-ofproducts form, insert the value of d, find the three products, and then find
their sum.]
6.
What is the decimal equivalent of the largest binary integer that can be
obtained with (a) 11 bits and (b) 25 bits?
7.
*Convert the following binary numbers to decimal: 1001101, 1010011.101,
and 10101110.1001.
8.
Convert the following decimal numbers to binary: 193, 751, 2007, and 19450.
9.
*Convert the following numbers from the given base to the other three
bases listed in the table:
Decimal
Binary
Octal
Hexadecimal
369.3125
?
?
?
?
10111101.101
?
?
?
?
326.5
?
?
?
?
F3C7.A
10.
*Convert the following decimal numbers to the indicated bases, using the
methods of Examples 4 and 7:
(a) 7562.45 to octal (b) 1938.257 to hexadecimal (c) 175.175 to binary.
11.
*Perform the following conversion by using base 2 instead of base 10 as the
intermediate base for the conversion:
(a) (673.6)8 to hexadecimal (b) (E7C.B)16 to octal (c) (310.2)4 to octal
DIGITAL SYSTEMS AND INFORMATION
12.
Perform the following binary multiplications:
(a) 1101 × 1011 (b) 0101 × 1010
(c) 100111 × 011011
13.
+Division is composed of multiplications and subtractions. Perform the
binary division 1010110 ÷ 101 to obtain a quotient and remainder.
14.
A limited number system uses base 12. There are at most four integer digits.
The weights of the digits are 123, 122, 12, and 1. Special names are given to
the weights as follows: 12 = 1 dozen, 122 = 1 gross, and 123 = 1 great gross.
(a) How many beverage cans are in 6 great gross + 8 gross + 7 dozen + 4?
(b) Find the representation in base 12 for 756910 beverage cans.
15.
Considerable evidence suggests that base 20 has historically been used for
number systems in a number of cultures.
(a) Write the digits for a base 20 system, using an extension of the same digit
representation scheme employed for hexadecimal.
(c) Convert (BCI.G)20 to decimal.
(b) Convert (2007)10 to base 20.
16.
*In each of the following cases, determine the radix r:
(a) (BEE)r  (2699)10
(b) (365)r  (194)10
17.
The following calculation was performed by a particular breed of unusually
intelligent chicken. If the radix r used by the chicken corresponds to its total
number of toes, how many toes does the chicken have on each foot?
((34)r + (24)r) × (21)r = (1480)r
18.
*Find the binary representations for each of the following BCD numbers:
(a) 0100 1000 0110 0111
(b) 0011 0111 1000.0111 0101
19.
*Represent the decimal numbers 694 and 835 in BCD, and then show the
steps necessary to form their sum.
20.
*Internally in the computer, with few exceptions, all numerical computation
is done using binary numbers. Input, however, often uses ASCII, which is
formed by appending 011 to the left of a BCD code. Thus, an algorithm that
directly converts a BCD integer to a binary integer is very useful. Here is
one such algorithm:
1. Draw lines between the 4-bit decades in the BCD number.
2. Move the BCD number one bit to the right.
3. Subtract 0011 from each BCD decade containing a binary value > 0111.
4. Repeat steps 2 and 3 until the leftmost 1 in the BCD number has been
moved out of the least significant decade position.
5. Read the binary result to the right of the least significant BCD decade.
(a) Execute the algorithm for the BCD number 0111 1000.
(b) Execute the algorithm for the BCD number 0011 1001 0111.
33
DIGITAL SYSTEMS AND INFORMATION
21.
Internally in a computer, with few exceptions, all computation is done using
binary numbers. Output, however, often uses ASCII, which is formed by
appending 011 to the left of a BCD code. Thus, an algorithm that directly
converts a binary integer to a BCD integer is very useful. Here is one such
algorithm:
1. Draw lines to bound the expected BCD decades to the left of the binary
number.
2. Move the binary number one bit to the left.
3. Add 0011 to each BCD decade containing a binary value > 0100.
4. Repeat steps 2 and 3 until the last bit in the binary number has been
moved into the least significant BCD decade position.
5. Read the BCD result.
(a) Execute the algorithm for the binary number 1111000.
(b) Execute the algorithm for the binary number 01110010111.
34
22.
What bit position in an ASCII code must be complemented to change the
ASCII letter represented from uppercase to lowercase and vice versa?
23.
Write your full name in ASCII, using an 8-bit code (a) with the leftmost bit
always 0 and (b) with the leftmost bit selected to produce even parity.
Include a space between names and a period after the middle initial.
24.
Decode the following ASCII code: 1000111 1101111 0100000 1000010
1100001 1100100 1100111 1100101 1110010 1110011 0100001.
25.
*Show the bit configuration that represents the decimal number 255 in
(a) binary, (b) BCD, (c) ASCII, (d) ASCII with odd parity.
26.
(a) List the 6-bit binary number equivalents for 32 through 47 with a parity
bit added in the rightmost position, giving odd parity to the overall 7-bit
numbers. (b) Repeat for even parity.
27.
Using the procedure given in Section 5, find the hexadecimal Gray code.
28.
This problem concerns wind measurements made by the wireless weather
station in Example 1. The wind direction is to be measured with a disk
encoder like the one shown in Figure 5(b). (a) Assuming that the code 000
corresponds to N, list the Gray code values for each of the directions, S, E,
W, NW, NE, SW, and SE. (b) Explain why the Gray code you have assigned
avoids the reporting of major errors in wind direction.
29.
+What is the percentage of power consumed for continuous counting (either
up or down but not both) at the outputs of a binary Gray code counter (with
all 2n code words used) compared to a binary counter as a function of the
number of bits, n, in the two counters?
COMBINATIONAL LOGIC
CIRCUITS
From Chapter 2 of Logic and Computer Design Fundamentals, Fourth Edition. M. Morris Mano,
Charles R. Kime. Copyright © 2008 by Pearson Education, Inc. Published by Pearson Prentice
Hall. All rights reserved.
35
LCD
Screen
Hard Drive
Keyboard
Drive Controller
Bus Interface
Graphics Adapter
Internal
FPU Cache
CPU MMU
Processor
RAM
External
Cache
Generic Computer
Note: The companion website for this text is http://www.prenhall.com/mano
36
COMBINATIONAL
LOGIC CIRCUITS
I
n this chapter we will learn about gates, the most primitive logic elements used in
digital systems. In addition, we will learn the mathematical techniques for
designing circuits from these gates and learn how to design cost-effective circuits.
These techniques, which are fundamental to the design of almost all digital circuits,
are based on Boolean algebra. One aspect of design is to avoid unnecessary circuitry
and excess cost, a goal accomplished by a technique called optimization. Karnaugh
maps provide a graphical method for enhancing understanding of logic design and
optimization and solving small optimization problems for “two-level” logic circuits.
More general optimization methods for circuits with two or more levels are introduced.
Types of logic gates characteristic of contemporary integrated-circuit implementation
are discussed. Exclusive-OR and exclusive-NOR gates are introduced, along with
associated algebraic techniques.
Concepts from this chapter apply to most of the generic computer. Exceptions are
circuits that are largely memory, such as caches and RAM, and analog electronic
circuits in the monitor and hard disk controller. Nevertheless, with its use throughout
the design of most of the computer, what we study in this chapter is fundamental to
an in-depth understanding of computers and digital systems and how they are
designed.
1 BINARY LOGIC
AND
GATES
Digital circuits are hardware components that manipulate binary information. The
circuits are implemented using transistors and interconnections in complex semiconductor devices called integrated circuits. Each basic circuit is referred to as a
logic gate. For simplicity in design, we model the transistor-based electronic
circuits as logic gates. Thus, the designer need not be concerned with the internal
37
COMBINATIONAL LOGIC CIRCUITS
electronics of the individual gates, but only with their external logic properties.
Each gate performs a specific logical operation. The outputs of gates are applied to
the inputs of other gates to form a digital circuit.
In order to describe the operational properties of digital circuits, we need to
introduce a mathematical notation that specifies the operation of each gate and
that can be used to analyze and design circuits. This binary logic system is one of a
class of mathematical systems generally called Boolean algebras (after the English
mathematician George Boole, who in 1854 published a book introducing the mathematical theory of logic). The specific Boolean algebra we will study is used to
describe the interconnection of digital gates and to design logic circuits through the
manipulation of Boolean expressions. We first introduce the concept of binary logic
and show its relationship to digital gates and binary signals. We then present the
properties of the Boolean algebra, together with other concepts and methods useful in designing logic circuits.
Binary Logic
Binary logic deals with binary variables, which take on two discrete values, and
with the operations of mathematical logic applied to these variables. The two values the variables take may be called by different names, but for our purpose, it is
convenient to think in terms of binary values and assign 1 or 0 to each variable. In
this chapter, variables are designated by letters of the alphabet, such as A, B, C, X,
Y, and Z. Later this notation is expanded to include strings of letters, numbers, and
special characters. Associated with the binary variables are three basic logical
operations called AND, OR, and NOT:
1. AND. This operation is represented by a dot or by the absence of an operator. For example, Z  X · Y or Z  XY is read “Z is equal to X AND Y.” The
logical operation AND is interpreted to mean that Z  1 if and only if X  1
and Y  1; otherwise Z  0. (Remember that X, Y, and Z are binary variables and can be equal to only 1 or 0.)
2. OR. This operation is represented by a plus symbol. For example, Z  X  Y
is read “Z is equal to X OR Y,” meaning that Z  1 if X  1 or if Y  1, or if
both X  l and Y  1. Z  0 if and only if X  0 and Y  0.
3. NOT. This operation is represented by a bar over the variable. For example,
Z  X is read “Z is equal to NOT X,” meaning that Z is what X is not. In
other words, if X  1, then Z  0; but if X  0, then Z  1. The NOT operation is also referred to as the complement operation, since it changes a 1 to 0
and a 0 to 1.
Binary logic resembles binary arithmetic, and the operations AND and OR
have similarities to multiplication and addition, respectively. This is why the symbols used for AND and OR are the same as those used for multiplication and addition. However, binary logic should not be confused with binary arithmetic. One
should realize that an arithmetic variable designates a number that may consist of
38
COMBINATIONAL LOGIC CIRCUITS
many digits, whereas a logic variable is always either a 1 or a 0. The following equations define the logical OR operation:
000
011
101
111
These resemble binary addition, except for the last operation. In binary logic, we
have 1  1  1 (read “one OR one is equal to one”), but in binary arithmetic, we
have 1  1  10 (read “one plus one is equal to two”). To avoid ambiguity, the
symbol ∨ is sometimes used for the OR operation instead of the  symbol. But as
long as arithmetic and logic operations are not mixed, each can use the  symbol
with its own independent meaning.
The next equations define the logical AND operation:
0·00
0·10
1·00
1·11
This operation is identical to binary multiplication, provided that we use only a single bit. Alternative symbols to the  for AND and + for OR, are symbols ∧ and ∨ ,
respectively, that represent conjunctive and disjunctive operations in propositional
calculus.
For each combination of the values of binary variables such as X and Y,
there is a value of Z specified by the definition of the logical operation. The definitions may be listed in compact form in a truth table. A truth table for an operation
is a table of combinations of the binary variables showing the relationship
between the values that the variables take on and the values of the result of the
operation. The truth tables for the operations AND, OR, and NOT are shown in
Table 1. The tables list all possible combinations of values for two variables and
the results of the operation. They clearly demonstrate the definition of the three
operations.
TABLE 1
Truth Tables for the Three Basic Logical Operations
AND
OR
X
Y
Z = XY
X
Y
Z
0
0
1
1
0
1
0
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
NOT
=X+Y
X
Z=X
0
1
1
0
39
COMBINATIONAL LOGIC CIRCUITS
Logic Gates
Logic gates are electronic circuits that operate on one or more input signals to produce an output signal. Electrical signals such as voltages or currents exist throughout a digital system in either of two recognizable values. Voltage-operated circuits
respond to two separate voltage ranges that represent a binary variable equal to
logic 1 or logic 0. The input terminals of logic gates accept binary signals within the
allowable range and respond at the output terminals with binary signals that fall
within a specified range. The intermediate regions between the allowed ranges in
the figure are crossed only during changes from 1 to 0 or from 0 to 1. These
changes are called transitions, and the intermediate regions are called the transition
regions.
The graphics symbols used to designate the three types of gates—AND, OR,
and NOT—are shown in Figure 1(a). The gates are electronic circuits that produce
the equivalents of logic-1 and logic-0 output signals in accordance with their
respective truth tables if the equivalents of logic-1 and logic-0 input signals are
applied. The two input signals X and Y to the AND and OR gates take on one of
four possible combinations: 00, 01, 10, or 11. These input signals are shown as timing diagrams in Figure 1(b), together with the timing diagrams for the corresponding output signal for each type of gate. The horizontal axis of a timing
diagram represents time, and the vertical axis shows a signal as it changes between
X
ZXY
Y
X
ZXY
Y
NOT gate or
inverter
OR gate
AND gate
(a) Graphic symbols
X
0
0
1
1
Y
0
1
0
1
(AND) X  Y
0
0
0
1
XY
0
1
1
1
1
1
0
0
(OR)
(NOT) X
(b) Timing diagram
tG
(AND) X  Y
0
0
0
1
(c) AND timing diagram with gate delay tG
FIGURE 1
Digital Logic Gates
40
ZX
X
COMBINATIONAL LOGIC CIRCUITS
the two possible voltage levels. The low level represents logic 0 and the high level
represents logic 1. The AND gate responds with a logic-1 output signal when both
input signals are logic 1. The OR gate responds with a logic-1 output signal if either
input signal is logic 1. The NOT gate is more commonly referred to as an inverter.
The reason for this name is apparent from the response in the timing diagram. The
output logic signal is an inverted version of input logic signal X.
In addition to its function, each gate has another very important property
called gate delay, the length of time it takes for an input change to result in the
corresponding output change. Depending on the technology used to implement
the gate, the length of time may depend on which of the inputs are changing. For
example, for the AND gate shown in Figure 1(a), with both inputs equal to 1,
the gate delay when input B changes to 0 may be longer than the gate delay when
the input A changes to 0. Also, the gate delay when the output is changing from 0
to 1 may be longer than when the output is changing from 1 to 0, or vice versa. In
the simplified model introduced here, these variations are ignored and the gate
delay is assumed to have a single value, tG. This value may be different for each
gate type, number of inputs, and the underlying technology and circuit design of
the gate. In Figure 1(c), the output of the AND gate is shown taking into consideration the AND gate delay, tG . A change in the output waveform is shifted tG
time units later compared to the change in input X or Y that causes the it. When
gates are attached together to form logic circuits, the delays down each path from
an input to an output add together.
AND and OR gates may have more than two inputs. An AND gate with
three inputs and an OR gate with six inputs are shown in Figure 2. The threeinput AND gate responds with a logic-l output if all three inputs are logic l. The
output is logic 0 if any input is logic 0. The six-input OR gate responds with a
logic 1 if any input is logic 1; its output becomes a logic 0 only when all inputs are
logic 0.
2 BOOLEAN ALGEBRA
The Boolean algebra we present is an algebra dealing with binary variables and
logic operations. The variables are designated by letters of the alphabet, and the
three basic logic operations are AND, OR, and NOT (complementation). A Boolean expression is an algebraic expression formed by using binary variables, the constants 0 and 1, the logic operation symbols, and parentheses. A Boolean function
can be described by a Boolean equation consisting of a binary variable identifying
A
B
C
F  ABC
(a) Three-input AND gate
A
B
C
D
E
F
GABCDEF
(b) Six-input OR gate
FIGURE 2
Gates with More than Two Inputs
41
COMBINATIONAL LOGIC CIRCUITS
the function followed by an equals sign and a Boolean expression. Optionally, the
function identifier is followed by parentheses enclosing a list of the function variables separated by commas. A single-output Boolean function is a mapping from
each of the possible combinations of values 0 and 1 on the function variables to
value 0 or 1. A multiple-output Boolean function is a mapping from each of the
possible combinations of values 0 and 1 on the function variables to combinations
of 0 and 1 on the function outputs.
EXAMPLE 1
Boolean Function Example – Power Windows
Consider an example Boolean equation representing electrical or electronic logic
for control of the lowering of the driver’s power window in a car.
L ( D, X, A )  DX  A
The window is raised or lowered by a motor driving a lever mechanism connected
to the window. The function L = 1 means that the window motor is powered up to
turn in the direction that lowers the window. L = 0 means the window motor is not
powered up to turn in this direction. D is an output produced by pushing a panel
switch on the inside of the driver’s door. With D = 1, the lowering of the driver’s
window is requested, and with D = 0, this action is not requested. X is the output of
a mechanical limit switch. X = 1 if the window is at a limit—in this case, in the fully
down position. X = 0 if the window is not at its limit—i.e., not in the fully down
position. A = 1 indicates automatic lowering of the window until it is in the fully
down position. A is a signal generated by timing logic from D and X. Whenever D
has been 1 for at least one-half second, A becomes 1 and remains at 1 until X = 1.
If D = 1 for less than one-half second, A = 0. Thus, if the driver requests that the
window be lowered for one-half second or longer, the window is to be lowered
automatically to the fully down position.
The two parts of the expression, DX and A, are called terms of the expression
for L. The function L is equal to 1 if term DX is equal to 1 or if term A is equal to
1. Otherwise, L is equal to 0. The complement operation dictates that if X = 1, then
X = 0. Therefore, we can say that L  1 if D  1, and X  0 or if A  1. So what
does the equation for L say if interpreted in words? It says that the window will be
lowered if the window is not fully lowered (X = 0) and the switch D is being
pushed (D = 1) or if the window is to be lowered automatically to fully down position (A = 1).
■
A Boolean equation expresses the logical relationship between binary variables. It is evaluated by determining the binary value of the expression for all possible combinations of values for the variables. A Boolean function can be
represented by a truth table. A truth table for a function is a list of all combinations
of 1s and 0s that can be assigned to the binary variables and a list that shows the
value of the function for each binary combination. The truth tables for the logic
operations given in Table 1 are special cases of truth tables for functions. The
42
COMBINATIONAL LOGIC CIRCUITS
TABLE 2
Truth Table
for the Function L  DX  A
D
X
A
L
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
1
number of rows in a truth table is 2n, where n is the number of variables in the
function. The binary combinations for the truth table are the n-bit binary numbers
that correspond to counting in decimal from 0 through 2n  1. Table 2 shows the
truth table for the function L  DX  A. There are eight possible binary combinations that assign bits to the three variables D, X, and A. The column labeled L contains either 0 or 1 for each of these combinations. The table shows that the
function L is equal to 1 if D  1 and X  0 or if A  1. Otherwise, the function L
is equal to 0.
An algebraic expression for a Boolean function can be transformed into a circuit diagram composed of logic gates that implements the function. The logic circuit diagram for function L is shown in Figure 3. An inverter on input X generates
the complement, X. An AND gate operates on X and D, and an OR gate combines
DX and A. In logic circuit diagrams, the variables of the function F are taken as the
inputs of the circuit, and the binary variable F is taken as the output of the circuit.
If the circuit has a single output, F is a single output function. If the circuit has multiple outputs, function F is a multiple output function with multiple variables and
equations required to represent its outputs. Circuit gates are interconnected by
wires that carry logic signals. Logic circuits of this type are called combinational
logic circuits, since the variables are “combined” by the logical operations. This is in
contrast to sequential logic, in which variables are stored over time as well as being
combined.
There is only one way that a Boolean function can be represented in a truth
table. However, when the function is in algebraic equation form, it can be
D
X
L
A
FIGURE 3
Logic Circuit Diagram for L  DXA
43
COMBINATIONAL LOGIC CIRCUITS
expressed in a variety of ways. The particular expression used to represent the
function dictates the interconnection of gates in the logic circuit diagram. By
manipulating a Boolean expression according to Boolean algebraic rules, it is often
possible to obtain a simpler expression for the same function. This simpler expression reduces both the number of gates in the circuit and the numbers of inputs to
the gates. To see how this is done, we must first study the basic rules of Boolean
algebra.
Basic Identities of Boolean Algebra
Table 3 lists the most basic identities of Boolean algebra. The notation is simplified
by omitting the symbol for AND whenever doing so does not lead to confusion.
The first nine identities show the relationship between a single variable X, its complement X, and the binary constants 0 and 1. The next five identities, 10 through 14,
have counterparts in ordinary algebra. The last three, 15 through 17, do not apply
in ordinary algebra, but are useful in manipulating Boolean expressions.
The basic rules listed in the table have been arranged into two columns that
demonstrate the property of duality of Boolean algebra. The dual of an algebraic
expression is obtained by interchanging OR and AND operations and replacing 1s
by 0s and 0s by 1s. An equation in one column of the table can be obtained from
the corresponding equation in the other column by taking the dual of the expressions on both sides of the equals sign. For example, relation 2 is the dual of relation
1 because the OR has been replaced by an AND and the 0 by 1. It is important to
note that most of the time the dual of an expression is not equal to the original
expression, so that an expression usually cannot be replaced by its dual.
The nine identities involving a single variable can be easily verified by substituting each of the two possible values for X. For example, to show that X  0 
X, let X  0 to obtain 0  0  0, and then let X  1 to obtain 1  0  1. Both
TABLE 3
Basic Identities of Boolean Algebra
44
1.
X 0  X
2.
X1  X
3.
X 1  1
4.
X0  0
5.
X X  X
6.
XX  X
7.
X X  1
8.
XX  0
9.
XX
10.
X Y  Y X
11.
XY  YX
Commutative
12.
13.
X( YZ )  ( XY )Z
Associative
14.
X  (Y  Z)  (X  Y )  Z
X( Y  Z )  XY  XZ
15.
X  YZ  ( X  Y )( X  Z )
Distributive
16.
X Y  XY
17.
XY  X Y
DeMorgan’s
COMBINATIONAL LOGIC CIRCUITS
equations are true according to the definition of the OR logic operation. Any
expression can be substituted for the variable X in all the Boolean equations
listed in the table. Thus, by identity 3 and with X  AB  C, we obtain
AB  C  1  1
Note that identity 9 states that double complementation restores the variable to its
original value. Thus, if X  0, then X  1 and X  0  X.
Identities 10 and 11, the commutative laws, state that the order in which the
variables are written will not affect the result when using the OR and AND operations. Identities 12 and 13, the associative laws, state that the result of applying an
operation over three variables is independent of the order that is taken, and therefore, the parentheses can be removed altogether, as follows:
X  (Y  Z)  (X  Y )  Z  X  Y  Z
X( YZ )  ( XY )Z  XYZ
These two laws and the first distributive law, identity 14, are well known from ordinary algebra, so they should not pose any difficulty. The second distributive law,
given by identity 15, is the dual of the ordinary distributive law and does not hold
in ordinary algebra. As illustrated previously, each variable in an identity can be
replaced by a Boolean expression, and the identity still holds. Thus, consider the
expression (A  B) (A  CD). Letting X  A, Y  B, and Z  CD, and applying
the second distributive law, we obtain
( A  B )( A  CD )  A  BCD
The last two identities in Table 3,
X  Y  X  Y and X  Y  X  Y
are referred to as DeMorgan’s theorem. This is a very important theorem and is
used to obtain the complement of an expression and of the corresponding function.
DeMorgan’s theorem can be illustrated by means of truth tables that assign all the
possible binary values to X and Y. Table 4 shows two truth tables that verify the
first part of DeMorgan’s theorem. In (a), we evaluate X  Y for all possible values
of X and Y. This is done by first evaluating X  Y and then taking its complement.
In (b), we evaluate X and Y and then AND them together. The result is the same
TABLE 4
Truth Tables to Verify DeMorgan’s Theorem
(a) X
Y
X Y
X Y
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
(b) X
Y
X
Y
XY
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
1
0
0
0
45
COMBINATIONAL LOGIC CIRCUITS
for the four binary combinations of X and Y, which verifies the identity of the
equation.
Note the order in which the operations are performed when evaluating an
expression. In part (b) of the table, the complement over a single variable is evaluated first, followed by the AND operation, just as in ordinary algebra with multiplication and addition. In part (a), the OR operation is evaluated first. Then, noting
that the complement over an expression such as X  Y is considered as specifying
NOT (X  Y), we evaluate the expression within the parentheses and take the
complement of the result. It is customary to exclude the parentheses when complementing an expression, since a bar over the entire expression joins it together.
Thus, ( X  Y ) is expressed as X  Y when designating the complement of X  Y.
DeMorgan’s theorem can be extended to three or more variables. The general DeMorgan’s theorem can be expressed as
X1  X2  …  Xn  X1X2…Xn
X1X2…Xn  X1  X2  …  Xn
Observe that the logic operation changes from OR to AND or from AND to OR.
In addi…