Middleton W.M. (ed.) Reference Data for Engineers: Radio, Electronics, Computer and Communications
Подождите немного. Документ загружается.
REFERENCE
DATA
FOR ENGINEERS
Pressley, R.
J.,
ed. Handbook of Lasers With Selected
Data
on
Optical Technology. Cleveland,
0.:
Chemical Rubber Co.,
1971.
Weber, M.
J.,
ed. Handbook
of
Laser Science and
Technology. Vol. I, Lasers and Masers; Vol. 11,
Gas Lasers. Cleveland,
0.:
Chemical Rubber Co.,
1982.
Willett,
C. S.
Introduction to Gas Lasers. New York:
Pergamon Press, Inc.,
1974.
Semiconductor Lasers
Agrawal,
G.
P., and Dutta, N. K.
Long
Wavelength
Semiconductor Lasers. New York: Van Nostrand
Reinhold,
1986.
Casey, H. C., Jr., and Panish, M. B. Heterostructure
Lasers: Part
A
and Part B. New York: Academic,
1978.
Kressel, H., ed. Semiconductor Devices for Optical
Communications. Vol.
39
in Topics
of
Applied
Physics. Berlin: Springer-Verlag,
1980.
Kressel, H., and Butler,
Y.
K.
Semiconductor Lasers
and Heterojunction LED’s. New York: Academic
Press, Inc.,
1977.
Thompson,
G.
H. B. Physics of Semiconductor Laser
Devices. New York: John Wiley
&
Sons, Inc.,
1980.
Dye Lasers
Hansch, T. W. “Repetitively Pulsed Tunable Dye Laser
for High Resolution Spectroscopy.
”
Applied Op-
Wallenstein, R. “Pulse Dye Lasers,” in Laser Hand-
book, Vol.
3.
M. L. Stitch, ed. New York:
North-Holland Publishing Co.,
1979.
tic~,
4, 1972,
pp.
895-898.
Nonlinear
Optics
Bloembergen, N. Nonlinear Optics. New York:
W.
A.
Benjamin Inc.,
1965.
Hellwege, K. H. and Hellwege, A. M., eds. Londolt-
Bornstein New Series Group
Ill
Vol.
2.
Berlin:
Springer-Verlag,
1979.
(See also A. Yariv, Quan-
tum Electronics, Chapters
14-19.)
Shen, Y.
R.
The Principles of Nonlinear Optics. New
York: John Wiley,
1984.
Pulse
Behavior
Modelocking
Haus, H. A. “Theory of Mode Locking With a Slow
Saturable Absorber.” IEEE
J.
of Quant. Electr.,
IEEE
J.
of Quant. Electr.,
QE-19,
1983.
Special issue
on Picosecond Phenomena and references cited
therein.
Kuzenga, D. J., and Siegman,
A.
E.
“FM and AM
Mode Locking
of
the Homogeneous Laser.” Part
I,
Theory. IEEE
J.
of Quant. Electr.,
QE-6, 1970,
p.
694.
Laubereau, A., and Eisenthal,
K.
B., eds. Picosecond
Phenomena
III.
Berlin: Springer-Verlag
,
1982.
Shank, C.
V.,
Ippen,
E.
P., and Shapiro,
S.
L.,
eds.
Picosecond Phenomena. Berlin: Springer-Verlag
,
1978.
Shapiro,
S.
L., ed. Ultrushort Light Pulses. Berlin:
Springer-Verlag,
1979.
Q-Switching
Hellwarth, R. W. “Control
of
Fluorescent Pulsations,”
in Advances in Quantum Electronics,
J.
R. Singer,
ed.
New York: Columbia University Press,
1961.
Hellwarth, R.
W.
“A Modulation of Lasers,” in Losers
I, A.
K.
Levine, ed. New York: Marcel Dekker
Inc.,
1966.
Wagner, W.
G.,
and Lengyel, B. A. “Evolution of a
Giant Pulse in a Laser.”
J.
of Appl. Phys.,
34,
1963,
p.
2044.
QE-11, 1975,
pp.
736-746.
Computer Organization
and Programming
John
Wakerly
Introduction
42-3
Hardware
Software
Computer Data Types
Number Systems and Arithmetic
42-4
Decimal and Binary Positional Number Systems
Octal and Hexadecimal Numbers
General Positional Number System Conversions
Addition and Subtraction of Nondecimal Numbers
Representation of Negative Numbers
Twos-Complement Addition and Subtraction
Binary Multiplication
Binary Division
Fixed-point and Floating-Point Representations
BCD Representation
Character Codes
Basic Computer Organization
42-10
Processors
Memory
Input/Output
Processors and Programming
42-14
Organization of a General-Register Processor
Instruction Formats
Instruction Set
Addressing Modes
Operands and Operations
A
Machine Language Program
42-22
Assembly Language
42-
1
42-2
REFERENCE
DATA
FOR ENGINEERS
Operation of a Simple Program
42-25
Indirect Addressing
Subroutines
Input/Output
42-30
Buses
Devices and Interfaces
Ports
I/O
Programming
COMPUTER ORGANIZATION AND PROGRAMMING
42-3
INTRODUCTION*
Computers come in all shapes and sizes, from large
corporate data-processing machines that fill a room to
tiny microcontrollers buried deep in automobiles, ster-
eo
systems, and toasters. Even though computers span a
wide range of sizes, capabilities, and cost, they share a
great many characteristics and operating principles. The
goal of this chapter is to describe general principles of
computer organization and programming that apply to
computers of any category.
Taken as a whole, a computer is an incredibly
complex system, with many more levels of detail than,
say, the noncomputer part of a radio. Fortunately, a
computer system
is
structured into many levels,
so
that
it is easy to understand
if
taken one level at a time; see
Fig.
1.
Hardware
Central to the organization,
or
indeed existence, of
a computer is its
architecture.
The architecture of
a computer
is
really an abstract concept-it is just a
definition
of
the functionality
of
the computer as seen
by a machine-language programmer. A user of a
particular computer architecture does not care how its
functions are achieved, only that they match their
definitions. An example of a particular computer archi-
tecture, the Motorola
68000,
is given later in the
chapter.
At the next level down is
implemenration,
the logic
structures used to accomplish the functions defined by
the architecture. An implementation consists of a block
diagram of the system hardware modules, their inter-
connections,
and further refinements
of
the internal
logic structure
of
each module. Note that implementa-
tion is still a somewhat abstract concept in that an
implementation can exist
on
paper without the machine
actually having been built. Chapter
43
discusses logic
design-the tools and techniques for designing hard-
ware modules.
The lowest level of detail in a computer is its
hurdfiure realizarion-the
electronic circuits and other
components from which the computer is built. Realiza-
tion encompasses integrated-circuit technologies, such
as those discussed in Chapter
20,
as well as packaging,
interconnections, and all other physical details of the
machine.
The bottom three levels
of
a computer just described
are often grouped together and simply called “the
hardware.” The higher levels in Fig.
1
are usually
grouped together as “software.”
*
The
material in this chapter is adapted, with permission,
from portions
of
Chapters
1,
4,
5,
and
10
of
Microcomputer
Architecture and Programming: The
68000
Family
by John
F.
Wakerly,
0
1989
by
John
Wiley
&
Sons, Inc., New
York.
Software
Computer
software
consists of the instructions and
data that the computer hardware manipulates
to
perform
useful work.
A
sequence of instructions for a computer
is called
aprogram.
The data manipulated by a program
is called a
data base,
a
file,
input,
or simply
data,
depending on its nature and extent.
The most primitive instructions that can be given to a
computer are those interpreted directly by hardware,
in
the
machine language
of the computer. Machine-
language instructions are encoded as strings of bits in
the computer memory, often one instruction per memo-
ry location. The processor fetches machine instructions
from memory and executes them one by one.
Since it is difficult for humans to read and recognize
strings of bits, machine-language programs are written
in
assembly language
and translated into bit strings by
an
assembler.
Assembly language represents machine
instructions by mnemonic names and allows memory
addresses and other constants to be represented by
symbols rather than bit strings.
Most programs are written in
high-level languriges
that allow common operations such as expression
evaluation, repetition, assignment, and conditional ac-
tion to be invoked in a single high-level
stcitemenr.
Popular high-level languages include BASIC,
FOR-
TRAN, and Pascal.
Few computers execute a high-level language direct-
ly. Therefore, a
compiler
is needed to translate a
high-level-language program into a sequence of ma-
chine instructions that performs the desired task.
Assemblers and compilers are not the only
sofnture
tools
that a programmer may encounter. Other
useful
tools related to program development are interpreters,
simulators, and on-line debuggers. Like a compiler. an
interpreter
processes a high-level-language program.
Unlike a compiler, an interpreter actually executes the
high-level-language program one statement at a time.
rather than translating each statement into a sequence
of
machine instructions
to
be
run
later. Most BASIC
environments use an interpreter.
A
simulator
is a program that simulates individual
machine instructions, usually
on
a machine other than
the one being simulated.
A
typical
use
of a simulator
is
to test programs to be run on a processor before the
processor hardware is available. An
on-line
debugger
executes a program
on
a machine one
or
a
few instruc-
tions at a time, allowing the programmer to see the
effects of small pieces
of
the program and thereby
isolate programming errors
(bugs).
Texr
editors
are used
to
enter and edit text in a
general-purpose computer. whether the text is a letter.
a
report,
or
a computer program.
Text
furmuffen
read
text with imbedded formatting commands and produce
formatted documents such as this book.
Text editors
and formatters belong to the area of computing known
as
word processing.
In a medium to large computer system. cooperating
42-4
I--..-
-
APPLICATION PROGRAMS COMMAND INTERPRETERS
I
HIGH-LEVEL LANGUAGES FILE SYSTEM
I
OPERATING SYSTEM
ASSEMBLY LANGUAGE
MACHINE LANGUAGE
ARCHITECTURE
IMPLEMENTATION
HARDWARE REALIZATION
REFERENCE DATA FOR ENGINEERS
Fig.
1.
Levels
of
~~
detail
of
a
computer.
programs run under the control of an
operating
system.
An operating system schedules programs for execution,
controls the use of
I/O
devices, and provides utility
functions for all of the programs that run on the
computer. Programs and text stored
on
disks and other
mass-storage devices are managed by afile
system,
a
collection of programs for reading, writing, and struc-
turing such information in “files.” The operating
systems in most computers include file systems. Even a
very small computer with no mass-storage or file system
has a simple operating system, at least to monitor inputs
and accept commands from the outside world.
Computer Data Types
The basic unit of information storage in a digital
computer is the
bit,
which has a value of either
0
or
1.
Obviously a single-bit data type is not very useful for
numeric computation, since
it
only allows
us
to count
from
0
to 1.
By assembling two or more bits into a string, we can
represent more than two values or conditions. The bits
in a string of
n
bits can take on 2” different combina-
tions of values.
Strings of eight bits
are
usually referred to as
bytes.
The name “byte” was invented at IBM in the early days
of electronic computers. The name for a string of four
bits is fancifully derived from the byte-the
pibble.
A bit string manipulated by a computer in one
operation is usually called a
word.
Some computers
have a
word length
as short as four bits, others as long
as
64
bits or more. For many minicomputers and
microcomputers, the nomenclature has been standard-
ized to use “word” to describe 16-bit strings and
“double word” or “long word” to describe 32-bit
strings.
Bits, nibbles, bytes, and words are easy data types to
classify because they require differing amounts of
storage
in
the computer memory. There are other data
types that are classified not by how much storage they
take, but by how they are interpreted and used by the
computer hardware and software. For example, the
following three data types, all using an eight-bit byte,
might be defined for a microcomputer:
Unsigned integer:
The byte represents an unsigned
integer between
0
and 255.
SOFTWARE
i
HARDWARE
1
Signed integer:
The byte represents a signed integer
Character:
The byte represents an ASCII character.
Even though all three data types are stored exactly the
same way in the computer memory, they may be
manipulated differently by the hardware and software.
between
-
128 and
+
127.
NUMBER SYSTEMS AND
ARlTH METlC
Decimal and Binary Positional
Number Systems
Positional number systems are used in all computers
and almost all day-to-day business of people. In a
positional number system,
a number is represented by a
string of digits in which each digit position has an
associated weight. For example, the value
D
of a 4-digit
decimal number,
d3d,dldo,
is
D
=
d3
.
lo3
+
d2
.
lo2
+
dl
.
10’
+
do .
IOo
Each digit
di
has a weight of 10’. Thus, the value
of
6851 is computed as follows:
6851
=
6
.
1000
+
8
.
100
+
5
.
10
+
1
.
1
A
decimal point is used to allow negative as well as
positive powers
of
10
in a decimal number representa-
tion. Thus,
dldo
.
d-,d-,
has the value
D
=
dl .
10’
+
do .
10’
+
d-,
.
lo-’
+
d-,
.
lo-’
In a general positional number system, each digit
position has an associated weight
of
bi,
where
b
is
called the
base,
or
radix,
of
the number system. The
general form of a number in such a system is
dp-ldp-2
.
. . dido
.
d-Id-2 . . . d-,
where there are
p
digits to the left
of
the point and
n
digits to the right of the point, called the
radix point.
42-5
The value of the number is
D=
P-
1
di
*
b'
-n
the summation of each digit times the corresponding
power of the radix. If the radix point is missing, it is
assumed to be to the right of the rightmost digit. Except
for possible leading and trailing zeros, the representa-
tion of a number in a positional number system is
unique. (Obviously, 34.85 equals 034.85000, and
so
on
.)
The
binary radix
is used in almost all computers.
The allowable digits,
0
and 1, are called
bits,
and each
bit
di
has weight 2'. In the examples below, subscripts
distinguish between radix-2 and radix-10 numbers.
100012
=
1.16
+
0.8
+
0.4
+
0.2
110.O1l2
=
1
*
4
+
1
*
2
+
0.
1
+
0
-
0.5
+
1
.
0.25
+
1
.
0.125
=
6.375,,
The leftmost bit of a biqary number is called the
high-order
or
most signijicant bit
(MSB);
the rightmost
is the
low-order
or
least significant bit
(LSB).
Octal
and Hexadecimal
Numbers
Most computer software uses either the
octal nuqber
system
(radix
8)
or the
hexadecimal number system
(radix
16)
to represent binary numbers. Table 1 shows
the binary numbers from
0
through 1111 and their
octal, decimal, and hexadecimal equivalents. The octal
system uses eight digits, 0-7. The hexadecimal system
requires 16 digits,
so
the letters A-F are used in
addition to the digits 0-9 of the decimal system.
The octal and hexadecimal number systems are
useful for representing binary numbers because their
radices are powers
of
two. Since a string of three bits
can take on eight different combinations, it follows that
each 3-bit string is uniquely represented by one octal
digit, according
to
the third and fourth columns of Table
1. Likewise, a 4-bit string is represented by one
hexadecimal digit according to the fifth and sixth
columns of the table.
Thus, it is very easy
to
convert a binary integer to
octal (or hexadecimal). Starting at the binary point and
working left, we simply separate the bits into groups of
three (or four) and replace each group with the corre-
sponding octal (or hexadecimal) digit:
101011OOO110~
=
101
011
000
110,
=
5306,
=
1010 1100 01102
=
Ac616
11011001110101001,
=
011011001 110 101001,
=
331651,
=
0001
1011 0011 1010 1001,
=
1B3A916
Conversion from octal
or
hexadecimal to binary is
easy, too. We simply replace each octal or hexadecimal
digit with the corresponding 3-
or
4-bit string. And
to
convert from octal to hexadecimal or vice versa, we first
convert to binary:
15738
=
001 101 111 0112
=
0011 0111 1011,
TABLE 1. BINARY, DECIMAL,
OCTAL,
AND
HEXADECIMAL NUMBERS
3-Bit 4-Bit
Binary Decimal Octal String Hexadecimal String
0
0
0
000
0
0000
1
1 1
00
1 1
000
1
10 2
2
010 2 0010
11
3
3
01 1
3
0011
100
4
4
100
4
0100
101
5
5
101
5
0101
110 6 6 110 6 01
10
111
7
I
111
I
0111
8
1000
9
1001
A
1010
B
101 1
C
1100
D
1101
E
1110
F
1111
1000
8
10
-
1001
9
11
-
1010 10
12
-
101 1 11
13
-
1100 12
14
-
1101 13 15
-
1110 14
16
-
1111 15
17
-
REFERENCE DATA FOR ENGINEERS
General Positional Number
f
2
=
1 remainder
0
+
2
=
0
remainder
1
(MSB)
System Conversions
In the more general case, conversion between two
bases cannot be done by simple substitutions; base- 10
arithmetic operations are generally required.
The base-10 value of a number in any base can be
found from the expansion formula given earlier:
891,
=
1011001~
3417
f
16
=
213 remainder
9
(LSD)
D=
di.b'
+
16
=
13 remainder
5
p-1
2
i
b
-n
+
16
=
0
remainder 13
(MSD)
We convert each digit
di
of the number to its base-10
equivalent and expand the formula using base-10 arith-
metic. For example:
3417,0
=
D59,6
1BEgI6
=
1
.
1fj3
+
11
.
16'
+
14
*
16'
+
8
'
16'
=
166210
In the opposite direction, to convert a decimal
number
D
to
base
b,
we perform a series of divisions by
b.
In the first step, we divide
D
by
b;
the remainder is
used as the least significant digit
(LSD)
of
the desired
result, and the quotient is used as the input to the next
step. At each succeeding step, we divide the input
number by
6,
use the remainder as the next-higher-order
digit of the result, and use the quotient as the input to
the next step. Since a remainder is always less than
b,
it
is always representable as a single base-b digit. The
process eventually terminates when a zero quotient is
produced. Examples are given below.
89
f
2
=
44 remainder
1
(LSB)
f
2
=
22 remainder
0
Addition and Subtraction
of
Nondecimal Numbers
Addition and subtraction of nondecimal numbers by
hand uses the same technique that we learned in
grammar school
for
decimal numbers; the only catch is
that the addition and subtraction tables are different.
Table
2
gives the addition and subtraction tables for
binary numbers. To add two binary numbers
X
and
Y,
we add together the least 'significant bits with an initial
carry
(tin)
of
0,
producing sum
(x
+
y
+
tin)
and carry
(tout)
bits according to the table. We continue process-
ing bits from right to left, including the carry out of
each column in the sum for the next column. Two
examples
of
decimal additions and the corresponding
binary additions are shown below, with the carries
shown as a bit string,
C.
c
101 11 1000
X
190
10111110
+
141
+
10001 101
33 1 10100101 1
Y
X+Y
+
2
=
11 remainder
0
c
00101 loo0
+
2
=
5
remainder
1
X
173 10101101
Y
+44
+OOlOl100
f
2
=
2 remainder 1
X+Y
217 1101 1001
TABLE
2.
BINARY ADDITION
AND
SUBTRACTION TABLE
c,,
0
0
0
0
1 1
1
1
X
0
0
1
1
0
0
1
1
Y
0
1
0
1
0
1
0
1
x+y+c,,
0
1
1
0
1
0 0
1
COUL
0
0
0
1
0
1 1
1
b,,
0
0
0
0
1
1 1
1
X
0
0
1 1
0
0
1
1
Y
0
1
0
1
0
1
0
1
x-y-bi,
0
1
1
0
1
0
0
1
bnut
0
1
0 0
1
1
0
1
COMPUTER ORGANIZATION AND PROGRAMMING
42-7
Subtraction is performed similarly, except with bor-
rows
(bin
and bout) instead of carries:
B
001 11 1100
X
229 11 100101
Y
-
46
-00101 110
x-Y
183 101 101 11
Addition and subtraction tables can be developed for
octal and hexadecimal numbers, or any other desired
base. However, rather than memorize tables, many
computer engineers use hand-held “hex calculators” to
perform arithmetic on binary, octal, and hexadecimal
numbers.
Representation
of
Negative
Numbers
So
far, we have dealt only with positive numbers.
There are many ways to represent negative numbers.
The representation of decimal numbers used in
everyday business is called the signed-magnitude sys-
tem. In this system, a number consists
of
a magnitude
and a symbol indicating whether the magnitude is
positive or negative. The signed-magnitude system can
be applied to binary numbers quite easily by using an
extra bit position
to
represent the sign. Traditionally, the
most significant bit (MSB) is used to represent the sign
(0
=
plus,
1
=
minus), and the lower-order bits contain
the magnitude. In this system, there are two representa-
tions of zero, ‘‘plus zero” and “minus zero.”
To
add two signed-magnitude numbers, we follow the
rules that we learned in grammar school. If the signs are
the same, we add the magnitudes and give the result the
same sign. If the signs are different, we subtract the
smaller magnitude from the larger and give.the result
the sign
of
the larger. To subtract signed-magnitude
numbers, we change the sign of the subtrahend and
proceed as in addition.
Despite the conceptual simplicity of the signed-mag-
nitude system, for performance and efficiency reasons
negative numbers in a computer are usually represented
in complement number systems. In such a system, a
number
is
negated not by inverting a sign bit, but rather
by “taking the complement.”
Complement number systems can be defined for any
base
or
radix, but we shall concentrate on the base-2
radix complement, commonly called the twos-comple-
ment system. In this system, we assume that a binary
number,
E,
has
n
bits,
B
=
b,-,b,-,.
.
.bibo,
so
that the radix point
is
on the right and the number is
an integer.
If
any operation produces a result that
requires more than n bits, we throw away the extra
high-order bit(s).
By definition, the twos complement of an n-bit
number,
B,
is obtained by subtracting
B
from
2“.
If
B
is
between
1
and
2“
-
1,
this subtraction will result in
another number between
1
and
2“
-
1.
If
B
is
0,
the result
of
the subtraction is
b”;
this has the form
100
. . .
00,
where there are a total of
n
+
1
bits. We
throw away the extra high-order bit and get the result
00
. .
100
=
0.
Thus there is only one representation of
zero in the twos-complement system.
From the foregoing, it might seem that a subtraction
operation is needed to
form
the twos complement of a
number
B.
However, this subtraction is avoided by
rewriting
2”
as
(2“
-
1)
+
1
and
b”
-
B
as
((2”
-
1)
-
B)+
l.Since2“-1hasthefom11...11,anyn-bit
number
B
may be subtracted from it by simply comple-
menting each bit of
B.
Thus,
the twos complement of
B
is obtained by complementing the individual bits of
B
and adding
1.
Some examples
of
8-bit numbers and
their twos complements
are
shown below.
171,
=
OOO1OOO12
11
101 110
(complement bits)
+1
11101111~
=
-1710
11910
=
OlllOlll~
10001000
(complement bits)
+1
100010012
=
-11910
01,
=
00000000,
1
1
1
11
1 1
1
+l
(complement bits)
11
00000000,
=
o10
-991,
=
100111012
01
100010
(complement bits)
+1
01100011,
=
9910
The decimal value of a twos-complement number can
be obtained from the same expansion formula that we
showed for unsigned numbers, except that the weight of
the
MSB
is
-2”-’
instead of
+2”-’
(for example,
-119
=
-128
+
8
+
1
above).
Some computers use the ones-complement system, in
which the complement of
an
n-bit number,
B,
is
defined
to be
2”
-
1
-
B.
Thus, the ones complement
of
a
number is obtained by simply inverting its bits. Al-
though taking the complement is faster, addition may
be slower than in the twos-complement system, requir-
ing an “end-around carry” operation. Also, there are
two representations
of
zero,
00
. . .
00
and
11
. .
.
11.
42-8
REFERENCE DATA
FOR
ENGINEERS
Twos-Complement Addition
and Subtraction
Twos-complement numbers, regardless of sign, are
added by ordinary binary addition, ignoring any carries
beyond the MSB. The result is always the correct sum as
long as the range of the number system is not exceeded.
Some examples of decimal addition and the corre-
sponding 4-bit twos-complement additions illustrate
this:
+3
0011
-2
1110
+
-6
+
1010
+7
0111
-8
111000
--
+
+4 +0100
+6
0110
+4
0100
+
-7
$1001
+3 1/0011 -3 1101
-~
+
-3
+
1101
If an addition operation produces a result that ex-
ceeds the range of the number system,
overflow
is said
to occur. Addition of two numbers with different signs
can never produce overflow, but addition of two num-
bers
of
like sign can, as shown by the following
examples:
-3
1101
+5
0101
-9
110111
=
+7
+I1 1011
=
-5
+
-6
+lo10
+
+6
0110
-8
1000
+7
0111
+
-8
+lo00
+
+7
+Olll
-16
110000
=
+O
+14 lllo=
-2
Fortunately, there is a simple rule for detecting
overflow in addition: an addition overflows if the signs
of the addends are the same and the sign
of
the sum is
different. Most computers have built-in hardware for
detecting overflow.
Two numbers may be subtracted by negating the
subtrahend and adding the result to the minuend. A
twos-complement number
is
negated by taking its twos
complement. Thus, negating the subtrahend and adding
the minuend can be accomplished with only one addi-
tion operation as follows: Perform a bit-by-bit comple-
ment of the subtrahend, and add the complemented
subtrahend to the minuend with an initial carry
of
1
instead
of
0.
Examples are the following:
1-initial carry
+4
0100 0100
-
+3
-001
1
+
1100
+1 110001
+3
-
+4
-1
+3
-
-4
1-initial carry
001
1
001
1
-0100
+
101 1
1111
1-initial carry
001 1 001 1
-
1100 fool
1
0111
+7
Overflow in subtraction can be detected by examining
the signs of the minuend and the
complemented
subtra-
hend, using the same rule as in addition.
Since twos-complement numbers are added and sub-
tracted by the same basic binary addition and subtrac-
tion algorithms as unsigned numbers, most computers
have only one type of addition
or
subtraction instruction
that handles both signed and unsigned numbers. How-
ever, a program must interpret the results of such an
instruction differently, depending on whether it thinks it
is dealing with signed numbers (e.g.,
-8
through
+7)
or unsigned numbers (e.g.,
0
through 15).
Thus, most computers have an
overflow
flag to
indicate that the range of signed numbers has been
exceeded, and a
carry
or
borrow
flag to indicate that the
range of unsigned numbers has been exceeded. Addi-
tion and subtraction instructions affect both flags, but a
program
looks
only at the flag for the number system it
is using. Also, a program interprets the MSB of a
number as a sign bit only when dealing with signed
numbers.
Binary Multiplication
In grammar school, we learned to multiply by adding
a list of shifted multiplicands computed according to the
digits
of
the multiplier. The same technique can be used
to obtain the product
of
two unsigned binary numbers as
shown below:
11
X
13
33
11
143
101 1
x
1101
1011
0000
101 1
101
1
multiplicand
multiplier
shifted multiplicands
10001 1
1
1
product
COMPUTER ORGANIZATION AND PROGRAMMING
Forming the shifted multiplicands is trivial in binary
multiplication, since the only possible values of the
multiplier digits are
0
and
1.
Instead of listing all the shifted multiplicands and
then adding, in a computer it is more convenient to add
each shifted multiplicand as it is created to a
partial
product.
The previous example is repeated in Chart
1,
calculated with this technique.
When we multiply an n-bit word and an m-bit word in
a computer, the resulting product will take at most
n
+
m
bits to express. Therefore, a typical multiplication
instruction multiplies two n-bit words and produces a
2n-bit double-word product.
Multiplication of signed numbers can be accom-
plished by using unsigned multiplication and the usual
grammar-school rules: Perform an unsigned multiplica-
tion of the magnitudes, and make the product positive if
the operands had the same sign, negative if they had
different signs.
Binary Division
The simplest binary division algorithm is also based
on the technique we learned
in
grammar school, as
shown in Chart
2.
In
both the decimal and binary cases,
we mentally compare the reduced dividend with multi-
ples of the divisor to determine which multiple of the
shifted divisor to subtract. In the decimal case, we first
pick
11
as the smallest multiple of
11
less than
21,
and
then pick 99 as the smallest multiple less than 107.
In
the binary case, the choice is somewhat simpler, since
the only two choices are zero and the divisor itself.
Still,
a comparison operation
is
needed to pick the proper
shifted divisor.
Unsigned division in a computer processor is comple-
mentary to multiplication. A typical division instruction
accepts a double-word dividend and a single-word
divisor, and produces single-word quotient and remain-
der. Such a division
overflows
if the divisor is zero or
the quotient would take more than one word to express.
The second situation occurs only if the divisor is less
than or equal to the high-order word of the dividend.
CHART
1.
MULTIPLICATION WITH
PARTIAL PRODUCTS
101
1
x
1101
00000000
101
1
0000101
1
0000101
1
101
1
0000
001
101
11
10001
11
1
101
1
multiplicand
multiplier
partial product
shifted multiplicand
partial product
shifted multiplicand
partial product
shifted multiplicand
partial product
shifted multiplicand
product
42-9
CHART
2.
EXAMPLE
OF
LONG
DIVISION
19
1001
1 quotient
11)217 1011)11o11001 dividend
11
1011
107 0101
99
0000
-
-
8
1010
0000
10100
101
1
1001 1
101
1
1000
-
-
shifted divisor
reduced dividend
shifted divisor
reduced dividend
shifted divisor
reduced dividend
shifted divisor
reduced dividend
shifted divisor
remainder
Fixed-point and Floating-point
Representations
All of the number systems discussed
so
far
fix
the
binary point to the right of the rightmost bit. Thus, a
16-bit unsigned number lies in the range
0
through
+65
535.
This type of number system is most appropri-
ate for programs that count objects or otherwise deal
with integer quantities. However, many programs must
deal with fractional quantities. For example,
in
a
scientific program that computes a table
of
positive
sines, it might be convenient to
fix
the binary point to
the right of the
leftmost
bit of a 16-bit number,
so
that
numbers range between
0
and 1.999 969
482
421
875
in increments of
0.000
030
517
578
125
(TI5).
In either case, the binary point is fixed in a particular
location for
all
numbers in the system.
Thus,
the system
is called a
fied-point representation.
Addition and
subtraction may be performed directly on fixed-point
numbers without regard to the location of the binary
point; however, scaling may be required after multipli-
cation and division operations.
To avoid error-prone bookkeeping and to represent a
large range of numbers with relatively few bits, a
joating-point representation
can be used to encode
explicitly a scale factor in each number. Similar to
numbers in scientific notation, a floating-point number
has two variable components, the mantissa
(M)
and the
exponent
(E).
The value
of
the number
is
M
.
RE,
where
R
is a fixed
radix.
In decimal scientific notation, the
radix is
10,
while in the floating-point representations
of most computers, the radix is
2.
Within
a
computer, a floating-point number
is
repre-
sented by a bit string containing explicit fields for the
mantissa and the exponent; the radix is implicit. The
number
of
mantissa bits determines the precision
of
the
number system, while the number
of
exponent bits
determines the dynamic range
of
the system (the ratio
between the largest and smallest nonzero numbers).
Both the mantissa and the exponent are signed numbers,
allowing representation of a large range
of
positive and
negative numbers with absolute values both greater than
and less than 1. Floating-point formats
in
typical