CO & OS MATERIAL

Unit – I – Basic structure of computers and Computer arithmetic

BASIC STRUCTURE OF COMPUTERS: Computer Types, Functional units, Basic operational

concepts, Bus structures, Software, Performance, multiprocessors and multi computers. Data types,
Complements, Data Representation. Fixed Point Representation.Floating – Point Representation.

COMPUTER ARITHMETIC: Addition and subtraction, multiplication Algorithms, Division

Algorithms, Floating point Arithmetic operations. Decimal Arithmetic unit, Decimal Arithmetic
operations.

UNIT I

Basic Structure of Computers

Computer Architecture in general covers three aspects of computer design namely: Computer
Hardware, Instruction set Architecture and Computer Organization.
Computer hardware consists of electronic circuits, displays, magnetic and optical storage media and
communication facilities.
Instruction set Architecture is programmer visible machine interface such as instruction set,
registers, memory organization and exception handling. Two main approaches are mainly CISC
(Complex Instruction Set Computer) and RISC (Reduced Instruction Set Computer)
Computer Organization includes the high level aspects of a design, such as memory system,
thebus structure and the design of the internal CPU.

Computer Types
Computer is a fast electronic calculating machine which accepts digital input, processes it according
to the internally stored instructions (Programs) and produces the result on the output device. The

Figure 1: Fetch, Decode and Execute steps in a Computer System

Page 1
CO & OS MATERIAL

internal operation of the computer can be as depicted in the figure below:

The computers can be classified into various categories as given below:

• Micro Computer
• Laptop Computer
• Work Station
• Super Computer
• Main Frame
• Hand Held
• Multi core

Micro Computer: A personal computer; designed to meet the computer needs of an individual.
Provides access to a wide variety of computing applications, such as word processing, photo editing,
e-mail, and internet.

Laptop Computer: A portable, compact computer that can run on power supply or a battery unit.
All components are integrated as one compact unit. It is generally more expensive than a
comparable desktop. It is also called a Notebook.

Work Station: Powerful desktop computer designed for specialized tasks. Generally used fortasks
that requires a lot of processing speed. Can also be an ordinary personal computer attached to a
LAN (local area network).

Super Computer: A computer that is considered to be fastest in the world. Used to execute tasks
that would take lot of time for other computers. For Ex: Modeling weather systems, genome
sequence, etc (Refer site: http://www.top500.org/)

Main Frame: Large expensive computer capable of simultaneously processing data for hundreds or
thousands of users. Used to store, manage, and process large amounts of data that need to be
reliable, secure, and centralized.

Hand Held: It is also called a PDA (Personal Digital Assistant). A computer that fits into a pocket,
runs on batteries, and is used while holding the unit in your hand. Typically used asan appointment
book, address book, calculator and notepad.

Multi Core: Have Multiple Cores – parallel computing platforms. Many Cores or computing
elements in a single chip. Typical Examples: Sony Play station, Core 2 Duo, i3, i7 etc.

GENERATION OF COMPUTERS
Development of technologies used to fabricate the processors, memories and I/O units ofthe
computers has been divided into various generations as given below:
• First generation
• Second generation
• Third generation
• Fourth generation
• Beyond the fourth generation

Page 2
CO & OS MATERIAL

First generation:
1946 to 1955: Computers of this generation used Vacuum Tubes. The computes were built using
stored program concept. Ex: ENIAC, EDSAC, IBM 701. Computers of this age typically used about ten
thousand vacuum tubes. They were bulky insize had slow operating speed, short life time and limited
programming facilities.

Second generation:
1955 to 1965: Computers of this generation used the germanium transistors as the active switching
electronic device. Ex: IBM 7000, B5000, IBM 1401. Comparatively smaller insize About ten times
faster operating speed as compared to first generation vacuum tube based computers. Consumed
less power, had fairly good reliability. Availability of large memory was an added advantage.

Third generation:
1965 to 1975: The computers of this generation used the Integrated Circuits as the active electronic
components. Ex: IBM system 360, PDP minicomputer etc. They were still smaller in size. They had
powerful CPUs with the capacity of executing 1 million instructions per second (MIPS). Used to
consume very less power consumption.

Fourth generation:
1976 to 1990: The computers of this generation used the LSI chips like microprocessor astheir active
electronic element. HCL horizen III, and WIPRO‟S Uniplus+ HCL‟s BusybeePC etc. They used high
speed microprocessor as CPU. They were more user friendly and highly reliablesystems. They had
large storage capacity disk memories.

Beyond Fourth Generation:

1990 onwards: Specialized and dedicated VLSI chips are used to control specific functionsof these
computers. Modern Desktop PC‟s, Laptops or Notebook Computers.

Functional Unit
A computer in its simplest form comprises five functional units namely input unit, output unit
memory unit, arithmetic & logic unit and control unit. Figure 2 depicts the functional units of a
computer system.

Page 3
CO & OS MATERIAL

Figure 2: Basic functional units of a computer

Let us discuss about each of them in brief:

1. Input Unit: Computer accepts encoded information through input unit. The
standard input device is a keyboard. Whenever a key is pressed, keyboard controller
sends the code to CPU/Memory.
Examples include Mouse, Joystick, Tracker ball, Light pen, Digitizer, Scanner etc.

2. Memory Unit: Memory unit stores the program instructions (Code), dataand
results of computations etc. Memory unit is classified as:
• Primary /Main Memory
• Secondary /Auxiliary Memory

Primary memory is a semiconductor memory that provides access at high speed. Run time
program instructions and operands are stored in the main memory. Main memory is
classified again as ROM and RAM. ROM holds system programs and firmware routines such
as BIOS, POST, I/O Drivers that are essential to manage the hardware of a computer. RAM
is termed as Read/Write memory or user memory that holds run time program instruction
and data. While primary storage is essential, it is volatile in nature and expensive. Additional
requirement of memory could be suppliedas auxiliary memory at cheaper cost. Secondary
memories are non volatile in nature.

3. Arithmetic and logic unit: ALU consist of necessary logic circuits like adder,
comparator etc., to perform operations of addition, multiplication, comparison of
two numbers etc.

4. Output Unit: Computer after computation returns the computed results, error
messages, etc. via output unit. The standard output device is a video monitor,
LCD/TFT monitor. Other output devices are printers, plotters etc.

Page 4
CO & OS MATERIAL

5. Control Unit: Control unit co-ordinates activities of all units by issuing control
signals. Control signals issued by control unit govern the data transfers and then
appropriate operations take place. Control unit interprets or decides the
operation/action to be performed.
The operations of a computer can be summarized as follows:

1. A set of instructions called a program reside in the main memory of computer.

2. The CPU fetches those instructions sequentially one-by-one from the main memory,
decodes them and performs the specified operation on associated data operands in
ALU.
3. Processed data and results will be displayed on an output unit.

4. All activities pertaining to processing and data movement inside the computer
machine are governed by control unit.

Basic Operational Concepts

An Instruction consists of two parts, an operation code and operand/s as shown below:

OPCODE OPERAND/s

Let us see a typical instruction

ADD LOCA, R0
This instruction is an addition operation. The following are the steps to execute the instruction:
Step 1: Fetch the instruction from main memory into the processor
Step 2: Fetch the operand at location LOCA from main memory into the processor
Step 3: Add the memory operand (i.e. fetched contents of LOCA) to the contents of registerR0
Step 4: Store the result (sum) in R0.
The same instruction can be realized using two instructions as
Load LOCA,R1 Add R1, R0

The steps to execute the instructions can be enumerated as below:

Step 1: Fetch the instruction from main memory into the processor
Step 2: Fetch the operand at location LOCA from mainmemory into the processor Register R1
Step 3: Add the content of Register R1 and the contents of registerR0
Step 4: Store the result (sum) in R0.

Figure 3 below shows how the memory and the processor are connected. As shown in the diagram,
in addition to the ALU and the control circuitry, the processor contains a number of registers used
for several different purposes. The instruction register holds the instruction thatis currently being
executed. The program counter keeps track of the execution of the program. It contains the memory
address of the next instruction to be fetched and executed. There are n general purpose registers R0
to Rn-1 which can be used by the programmers during writing programs.

Page 5
CO & OS MATERIAL

Figure 3: Connections between the processor and the memory

The interaction between the processor and the memory and the direction of flow of
information is as shown in the diagram below:

Figure 4: Interaction between the memory and the ALU

BUS STRUCTURES
Group of lines that serve as connecting path for several devices is called a bus (one bit per line).
Individual parts must communicate over a communication line or path for exchanging data, address
and control information as shown in the diagram below. Printer example – processor to printer. A
common approach is to use the concept of buffer registers to hold the content during the transfer.

Figure 5: Single bus structure

Page 6
CO & OS MATERIAL

SOFTWARE:
If a user wants to enter and run an application program, he/she needs a System Software. System
Software is a collection of programs that are executed as needed to perform functionssuch as:

• Receiving and interpreting user commands

• Entering and editing application programs and storing then as files in
secondarystorage devices
• Running standard application programs such as word processors, spread
sheets,games etc…
Operating system - is key system software component which helps the user to exploit the
below underlying hardware with the programs.

USER PROGRAM and OS ROUTINE INTERACTION

Let‟s assume computer with 1 processor, 1 disk and 1 printer and application program is in machine
code on disk. The various tasks are performed in a coordinated fashion, which is called multitasking.
t0, t1 …t5 are the instances of time and the interaction during various instances as given below:

t0: the OS loads the program from the disk tomemory

t1: program executes
t2: program accesses disk
t3: program executes somemore
t4: program accessesprinter
t5: program terminates

Figure 6 :User program and OS routine sharing of

theprocessor

Page 7
CO & OS MATERIAL

PERFORMANCE
The most important measure of the performance of a computer is how quickly it can execute
programs. The speed with which a computer executes program is affected bythe design of
its hardware. For best performance, it is necessary to design the compiles, the machine
instruction set, and the hardware in a coordinated way. The total time required to execute
the program is elapsed time is a measure of the performance of the entire computer system.
It is affected by the speed of the processor, the disk and the printer. The time needed to
execute a instruction is called the processor time.

Just as the elapsed time for the execution of a program depends on all units in a computer
system, the processor time depends on the hardware involved in the execution of individual
machine instructions. This hardware comprises the processor and the memory which are
usually connected by the bus. The pertinent parts of the fig. c is repeated in fig. d which
includes the cache memory aspart of the processor unit.

Let us examine the flow of program instructions and data between the memory and the
processor. At the start of execution, all program instructions and the required data are stored
in the main memory. As the execution proceeds, instructions are fetched one by one over the
bus into the processor, and a copy is placed in the cache later if the same instruction or data
item is needed a second time, it is read directly from the cache.

The processor and relatively small cache memory can be fabricated on a single IC chip. The
internal speed of performing the basic steps of instruction processing on chip is very high
and is considerably faster than the speed at which the instruction and data can be fetched
from the main memory. A program will be executed faster if the movementof instructions
and data between the main memory and the processor is minimized, which is achieved by
using the cache.
For example:- Suppose a number of instructions are executed repeatedly over a short period
of time as happens in a program loop. If these instructions are available in the cache, they can
be fetched quickly during the period of repeated use. The same appliesto the data that are
used repeatedly.

Processor clock:

Processor circuits are controlled by a timing signal called clock. The clock designer the regular
time intervals called clock cycles. To execute a machine instruction the processor divides the
action to be performed into a sequence of basic steps that each stepcan be completed in one
clock cycle. The length P of one clock cycle is an important parameter that affects the
processor performance.
Processor used in today‟s personal computer and work station have a clock rates that range
from a few hundred million to over a billion cycles per second.

Basic performance equation:

We now focus our attention on the processor time component of the total elapsed time.
Let „T‟ be the processor time required to execute a program that has been prepared
in some high-level language. The compiler generates a machine language object program that
corresponds to the source program. Assume that complete execution of theprogram requires
the execution of N machine cycle language instructions. The numberN is the actual number

Page 8
CO & OS MATERIAL

of instruction execution and is not necessarily equal to the number of machine cycle
instructions in the object program. Some instruction may be executed more than once, which
in the case for instructions inside a program loop othersmay not be executed all, depending
on the input data used.

Suppose that the average number of basic steps needed to execute one machine cycle
instruction is S, where each basic step is completed in one clock cycle. If clockrate is „R‟
cycles per second, the program execution time is given by

T=N*S/R

this is often referred to as the basic performance equation.

We must emphasize that N, S & R are not independent parameters changing one may affect
another. Introducing a new feature in the design of a processor will lead to improved
performance only if the overall result is to reduce the value of T.

Performance measurements:

It is very important to be able to access the performance of a computer, comp designers use
performance estimates to evaluate the effectiveness of new features.
The previous argument suggests that the performance of a computer is given by the execution
time T, for the program of interest.
Inspite of the performance equation being so simple, the evaluation of „T‟ is highly complex.
Moreover the parameters like the clock speed and various architectural features are not
reliable indicators of the expected performance.
Hence measurement of computer performance using bench mark programs is done to make
comparisons possible, standardized programs must be used.
The performance measure is the time taken by the computer to execute a given bench mark.
Initially some attempts were made to create artificial programs that could be used as bench
mark programs. But synthetic programs do not properly predict the performance obtained
when real application programs are run.
A non profit organization called SPEC- system performance evaluation corporation selects and
publishes bench marks.
The program selected range from game playing, compiler, and data base applications to
numerically intensive programs in astrophysics and quantum chemistry. In each case,the
program is compiled under test, and the running time on a real computer ismeasured. The
same program is also compiled and run on one computer selected as reference.
The „SPEC‟ rating is computed as follows.
Running time on the reference computer
SPEC rating =
Running time on the computer under
testIf the SPEC rating = 50

Multiprocessor & microprocessors:

Large computers that contain a number of processor units are called multiprocessor system.
These systems either execute a number of different application tasks in parallel or execute
subtasks of a single large task in parallel. All processors usually have access to all memory
locations in such system & hence they are called shared memory multiprocessor systems. The

Page 9
CO & OS MATERIAL

high performance of these systems comes with much increased complexity and cost. In
contrast to multiprocessor systems, it is also possible to use an interconnected group of
complete computers to achieve high totalcomputational power. These computers normally
have access to their own memory units when the tasks they are executing need to
communicate data they do so by exchanging messages over a communication network. This
properly distinguishes them from shared memory multiprocessors, leading to name message-
passing multi computer.

Data Representation:

Information that a Computer is dealing with

Data
Numeric Data
Numbers( Integer,
real)Non-numeric
Data Letters,
Symbols
Relationship between data elements
Data Structures
Linear Lists, Trees, Rings, etc
Program(Instruction)
Numeric Data Representation

Decimal Binary Octal Hexadecimal

00 0000 00 0
01 0001 01 1
02 0010 02 2
03 0011 03 3
04 0100 04 4
05 0101 05 5
06 0110 06 6
07 0111 07 7
08 1000 10 8
09 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F

Page 10
CO & OS MATERIAL

Fixed Point Representation:

It‟s the representation for integers only where the decimal point is always fixed. i.e atthe
end of rightmost point. it can be again represented in two ways.
1. Sign and Magnitude Representation
In this system, he most significant (leftmost) bit in the word as a sign bit. If the sign bitis 0,
the number is positive; if the sign bit is 1, the number is negative.
The simplest form of representing sign bit is the sign magnitude representation.
One of the draw back for sign magnitude number is addition and subtraction need toconsider
both sign of the numbers and their relative magnitude.
Another drawback is there are two representation for 0(Zero) i.e +0 and -0.
2. One’s Complement (1’s) Representation
In this representation negative values are obtained by complementing each bit of the
corresponding positive number.
For example 1s complement of 0101 is 1010 . The process of forming the 1s complement of
a given number is equivalent to subtracting that number from 2n -1 i.e from 1111 for 4 bit
number.
Two‟s Complement (2‟s) Representation Forming the 2s complement of a number is done
by subtracting that number from 2n . So 2s complement of a number is obtained by adding
1 to 1s complement of that number.
Ex: 2‟s complement of 0101 is 1010 +1 = 1011
NB: In all systems, the leftmost bit is 0 for positive number and 1 for negative number.

Floating-point representation
Floating-point numbers are so called as the decimal or binary point floats over the base
depending on the exponent
value.It consists two
components.
• Exponent
• Mantissa
Example: Avogadro's number can be written as 6.02x1023 in base 10. And the mantissaand
exponent are 6.02 and 1023 respctivly. But computer floating-point numbers are usually
based on base two. So 6.02x1023 is approximately (1 and 63/64)x278 or 1.111111 (base two)
x 21001110 (base two)

COMPUTER ARITHMETIC:

Addition, subtraction, multiplication are the four basic arithmetic operations. Using these operations
other arithmetic functions can be formulated and scientific problems can be solved by numerical
analysis methods.

Page 11
CO & OS MATERIAL

Arithmetic Processor:

It is the part of a processor unit that executes arithmetic operations. The arithmetic instructions
definitions specify the data type that should be present in the registers used . The arithmetic instruction
may specify binary or decimal data and in each case the data may be in fixed-point or floating point form.

Fixed point numbers may represent integers or fractions. The negative numbers may be in signed-
magnitude or signed- complement representation. The arithmetic processor is very simple if only a
binary fixed point add instruction is included. It would be more complicated if it includes all four
arithmetic operations for binary and decimal data in fixed and floating point representations.

Algorithm:

Algorithm can be defined as a finite number of well defined procedural steps to solve a problem. Usually,
an algorithm will contain a number of procedural steps which are dependent on results ofprevious steps.
A convenient method for presenting an algorithm is a flowchart which consists of rectangular and
diamond –shaped boxes. The computational steps are specified in the rectangularboxes and the decision
steps are indicated inside diamond-shaped boxes from which 2 or more alternate path emerge.

Addition and Subtraction:

3 ways of representing negative fixed point binary numbers:

1. Signed-magnitude representation---- used for the representation of mantissa for floating point
operations by most computers.
2. Signed-1’s complement
3. Signed -2’s complement—Most computers use this form for performing arithmetic operation
with integers
Addition and subtraction algorithm for signed-magnitude data

Let the magnitude of two numbers be A & B. When signed numbers are added or subtracted,
there are 4 different conditions to be considered for each addition and subtraction depending
on the sign of the numbers. The conditions are listed in the table below. The table shows the
operation to be performed with magnitude(addition or subtraction) are indicated for different
conditions.

Page 12
CO & OS MATERIAL

Add Subtract magnitudes

Sl.No Operation Magnitudes
When A> B When A< B When A=B

1 ( +A ) + (+B ) +(A+B)

2 ( +A ) + (-B ) +( A-B ) -( B-A ) +( A-B )

3 ( -A ) + (+B ) -( A-B ) +( B-A ) +( A-B )

4 ( -A ) + (-B ) -(A+B)

5 ( +A ) - (+B ) +( A-B ) -( B-A ) +( A-B )

6 ( +A ) - (-B ) +(A+B)

7 ( -A ) - (+B ) -(A+B)

8 ( -A ) - (-B ) -( A-B ) +( B-A ) +( A-B )

The last column is needed to prevent a negative zero. In other words, when two equal numbers
are subtracted, the result should be +0 not -0.

The algorithm for addition and subtraction ( from the table above):

Addition Algorithm:
When the signs of A and B are identical, add two magnitudes and attach the sign of A to the
result. When the sign of A and B are different, compare the magnitudes and subtract the smaller
number from the larger. Choose the sign of the result to be the same as A if A>B or the
complement of sign of A if A < B. If the two magnitudes are equal, subtract B from A and make
te sign of the result positive.
Subtraction algorithm:
When the signs of A and B are different, add two magnitudes and attach the sign of A to the
result. When the sign of A and B are identical, compare the magnitudes and subtract the smaller
number from the larger. Choose the sign of the result to be the same as A if A>B or the
complement of sign of A if A < B. If the two magnitudes are equal, subtract B from A and make
te sign of the result positive.
Hardware Implementation:
Let A and B are two registers that hold the numbers.
AS and BS are 2, flip-flops that hold sign of corresponding numbers. The result is stored In A andAS
.and thus they form Accumulator register.
We need to perform micro operation, A+ B and hence a parallel adder.A
comparator is needed to establish if A> B, A=B, or A<B.
We need to perform micro operations A-B and B-A and hence two parallel subtractor. An
exclusive OR gate can be used to determine the sign relationship, that is, equal or not.

Page 13
CO & OS MATERIAL

Thus the hardware components required are a magnitude comparator, an adder, and two
subtractors.
Reduction of hardware by using different procedure:
1. We know subtraction can be done by complement and add.
2. The result of comparison can be determined from the end carry after the subtraction.
We find An adder and a complementer can do subtraction and comparison if 2’s
complement is used for subtraction.

Hardware forsigned-magnitude addition and subtraction:

AVF Add overflow flip flop. It hold the overflow bit when A & B are added.
Flip flop E—Output carry is transferred to E. It can be checked to see the relative magnitudes of the two
numbers.

A-B = A +( -B )= Adding a and 2’s complement of B.

The A register provides other micro operations that may be needed when the sequence of steps in the
algorithm is specified.

The complementer Passes the contents of B or the complement of B to the Parallel Adder depending on
the state of the mode control B. It consists of EX-OR gates and the parallel adder consists of full adder
circuits. The M signal is also applied to the input carry of the adder.

When input carry M=0, the sum of full adder is A +B. When M=1, S = A + B’ +1= A – BHardware

algorithm:

Flow Chart for Add and Subtract operations:

The EX-OR gate provides 0 as output when the signs are identical. It is 1 when the signs are different.

A + B is computed for the following and the sum is stored in EA:

1. When the signs are same and addition operation is required.

2. When the signs are different and subtract operation is required.

Page 14
CO & OS MATERIAL

The carry in E after addition indicates an overflow if it is 1 and it is transferred to AVF, the
addoverflow flag

A-B = A+ B’+1 computed for the following:

1. When the signs are different and addition operation is required.
2. When the signs are same and subtract operation is required.
No overflow can occur if the numbers are subtracted and hence AVF is cleared to Zero.

[ the subtraction of 2 n-digit un signed numbers M-N ( N≠0) in base r can be done as follows:
1. Add minuend M to thee r’s complement of the subtrahend N. This performs M-N +rn .
2. If M ≥ N, The sum will produce an end carry rnwhich is discarded, and what is left is the result M-N.
3. If M< N, the sum does not produce an end carry and is equal to rn–( N-M ), which is the r’s complement of the sum and place a negative
sign in front.]
A 1 in E indicates that A ≥ B and the number in A is the correct result.
If this number in A is zero, the sign AS must be made positive to avoid a negative zero.
A 0 in E indicates that A< B. For this case it is necessary to take the 2’s complement of
the value in A.
In the algorithm shown in flow chart, it is assumed that A register has circuits for micro
operations complement and increment. Hence two complement of value in A is obtained
in 2, micro operations. In other paths of the flow chart , the sign of the result is the same
as the sign of A, so no change in AS is required.
However When A < B, the sign of the result is the complement of original sign of A.Hence
The complement of AS stored in AS.
Final Result: AS A
Flow chart for ADD and Subtract operations:

Addition and Subtraction with signed-2’s complement Data.:

Page 15
CO & OS MATERIAL

Arithmetic Addition:
This method does not need a comparison or subtraction but only addition and
complementation. The procedure is as below:
1. Represent the negative numbers in 2’s complement form.
2. Add the two numbers including the sign bits and discard any carry out of sign bit
position.
3. The overflow bit V is set to 1 if there is a carry into sign bit and no carry out of sign
bit or if there is a no carry into sign bit and a carry out of sign bit. Otherwise it is set
to zero.
4. If the result is negative, take the 2’s complement of the result to get a correct
negative result.

Arithmetic Subtraction:

1. Represent the negative numbers in 2’s complement form.

2. Take the 2’s complement of the subtrahend including the sign bit and add it to the
minuend including the sign bit.
3. The overflow bit V is set to 1 if there is a carry into sign bit and no carry out of sign
bit or if there is a no carry into sign bit and a carry out of sign bit. Otherwise it is set
to zero.
4. Discard the carry out of the sign bit position.

Note: A subtraction operation can be changed to an addition operation if the sign of the subtrahend is
changed.
BR Register

V Complementer&Parallel Adder

Overflow

AC Register

Fig: Hardware for Signed 2/s complement for addition/ subtractioin.

Page 16
CO & OS MATERIAL

Multiplication Algorithm:

Hardware implementation of multiplication of numbers in signed – magnitude form:

1. A adder is provided to add two binary numbers and the partial product is accumulated in a register.
2. Instead of shifting the multiplicand to the left, the partial product is shifted to the right, which result
in leaving the partial product and the multiplicand in the required relative positions.
3. When the corresponding bit of the multiplier is zero, there is no need to add all zeros to the partial
product, since it will not alter it’s value.

The hardware consists of 4 flipflops, 3 registers, one sequence counter , an adder and complementer.

Q register & QS flip flop : contains multiplier & Its sign

Sequence counter : It is set to a value equal to the number of bits in the multiplier
B Register& BS flipflop : It contains the multiplicand,& its sign
A Register, E Flip flop : Initialized to ‘ 0’. AS denotes sign of partial product
EA Register : hold partial product, with carry generated in addition being shifted to E .

Page 17
CO & OS MATERIAL

Qn: Rightmost bit of the multiplier; AQ : will contain the final product. As AQ represent product register,
both AS QS represent the sign of the partial product or product. The number to be multiplied are stores in
memory as n bit sign magnitude numbers and when transferred to register msb bit go to sign flipflop and
remaining n-1 bits go to registers. Hence SC isinitially set to n-1. Let the lower order bit of the multiplier
in Qn tested.

If it is 1, the multiplicand in B is added to the present partial product in A. If it is a ‘0’, nothing is done.
Register EAQ is then shifted once to the right to form the new partial product. The sequence counter is
decremented by 1 and it’s new value checked. If it is not equal tozero, the process is repeated and a new
partial product is formed. The process stops when SC = 0.

The final product is available in both A and Q, with A holding the most significant bits and Q holding the
least significant bits.

Flowchart for multiply operation:

Page 18
CO & OS MATERIAL

Numerical Example for the above algorithm:

Multiplicand B= 10111 E A Q SC

Multiplier in Q 0 00000 10011 101

Qn =1;add B 10111

First Partial Product 0 10111

Shift Right EAQ 0 01011 11001 100

Qn =1;add B 10111

Second Partial Product 1 00010

Shift Right EAQ 0 10001 01100 011

Qn =0; Shift Right EAQ 0 01000 10110 010

Qn =0; Shift Right EAQ 0 00100 01011 001

Qn =1;add B 10111

Fifth Partial Product 0 11011

Shift Right EAQ 0 01101 10101 000

Final Product in AQ

AQ = 0110110101

Booth Multiplication Algorithm:

Multiplication of signed- 2’s complement integers:

This algorithm uses the following facts.

1. A string of 0’s in the multiplier requires no addition but just shifting.

2. A string of 1’s in the multiplier from bit weight 2k to weight 2m can be treated as 2k+1 - 2m.

Example: Consider the binary number: 001110( +14 )

The number has a string of 1’s from 23 to 21 . Hence k = 3 and m= 1. As other bits are 0’s, the number
can be represented as 2k+1 - 2m = 24 – 21 = 16-2 = 14. Therefore the multiplication M * 14 ,where M
is the multiplicand and 14 the multiplier can be done as Mx 24 –M x 21.

Page 19
CO & OS MATERIAL

This can be achieved by shifting binary multiplicand M four times to the left and subtracting Mshifted
left once which is equal to (Mx 24 –M x 21. ).

Shifting and addition/subtraction rules for multiplicand in Booth’s Algorithm:

1. The multiplicand is subtracted from the partial product upon encountering the first least
significand 1 in a string of I’s in the multiplier.
2. The multiplicand is added to the partial product upon encountering the first 0 ( provided that
there was a previous 1)in a string of 0’s in the multiplier.
3. The partial product does not change when the multiplier bit is identical to the previous
multiplier bit
Hardware Implementation of Booth Algorithm:

Note: Sign bit is not separated from register. QR register contains the multiplier register and
Qnrepresent the least significant bit of the multiplier in QR. Qn+1 is an extra flip flop appended to
QR to facilitate a double bit inspection of the multiplier.
AC register and appended Qn+1 are initially cleared to 0.
Sequence counter Sc is set to the number n which is equal to the number of bits of bits In the
multiplier.
QnQn+1 are to successive bits in the multiplier

Example for multiplication using Boot h algorithm:

Page 20
CO & OS MATERIAL

QnQn+1 BR = 1011 ,𝐵𝑅′+1 = 01001 AC QR Qn+1 SC

10 Initial 00000 10011 0 101

Subtract BR 01001
01001
ashr 00100 11001 1 100

11 ashr 00010 01100 1 011

01 Add BR 10111
11001
ashr 11100 10110 0 010

00 ashr 11110 01011 0 001

10 Subtract BR 01001

00111
Ashr 00011 10101 1 000

Algorithm in flowchart for multiplication of signed 2’s complement numbers.

Page 21
CO & OS MATERIAL

Array Multiplier:
2 -bit by 2- bit Array Multiplier:

Multiplicand bits are b1 and b0 .Multiplier bits are a1 and a0 .The first partial product is obtained
by multiplying a0 by b1 b0 . The bit multiplication is implemented by AND gate. First partial
product is made by two AND gates. Second partial product is made by two AND gates. The two
partial products are added with two half adder circuits.

Page 22
CO & OS MATERIAL

Combinational circuit binary multiplier:

A bit of the multiplier is ANDed with each bit of the multiplicand in as many levels as there bits in the
multiplier. The binary output in each level of the AND gates is added in parallel with the partial product
of the previous level to form a ne partial product. The last level produces the product. For j multiplier
and k multiplicand bits, we need j*k AND Gates and (j-1)*k bit adders to ptoduce a product of j+k bits.

4- bit by 3-bit Array Multiplier:

Page 23
CO & OS MATERIAL

Division Algorithms:

Division Process for division of fixed point binary number in signed –magnitude representation:

Let dividend A consists of 10 bits and divisor B consists of 5 bits.

1. Compare the 5 most significant bits of the dividend with that of divisor.
2. If the 5 bit number is smaller than divisor B, then take 6 bits of the dividend and compare with the 5 bit divisor.
3. The 6 bit number is greater than divisor B. Hence place a 1 for the quotient bit in the sixth position above the
dividend. Shift the divisor once to the right and subtracted from the dividend. The difference is called partial
remainder.
4. Repeat the process with the partial remainder and divisor. If the partial remainder is equal or greater than or equal to
the divisor, the quotient bit is equal to 1.The divisor is then shifted right and subtracted from the partial remainder. If
the partial remainder is small than the divisor, then the quotient bit is zero and no subtraction is needed. The divisor
is shifted once to the right in any case,.

Hardware Implementation of division for signed magnitude fixed point numbers:

To implement division using a digital computer, the process is changed slightly for convenience.
1. Instead of shifting the divisor to the right, the dividend or the partial remainder, is shifted to the left so as to
leave the two numbers in the required relative position.
2. Subtraction may be achieved by adding A (dividend)to the 2’s complement of B(divisor). The information about
the relative magnitude is then available from end carry.
3. Register EAQ is now shifted to the left with 0 inserted into Qn and the previous value of E is lost..
4. The divisor is stored in B register and the double length dividend is stored in registers A and Q.
5. The dividend is shifted to the left and the divisor is subtracted by adding it’s 2’s complement value.
6. If E= 1, it signifies that A ≥ B.A quotient bit is inserted into Qnand the partial remainder is shifted to the left to
repeat the process.
7. If E = 0, it signifies that A < B so the quotient Qn remains 0( inserted during the shift). The value of B is then added
to restore the partial remainder in A to its previous value. The partial remainder is shifted to the left andthe
process is repeated again until all 5 quotient bits are formed.
8. At the end Q contains the quotient and A the remainder. If the sign of dividend and divisor are alike, the quotient
is positive and if unalike, it is negative. The sign of the remainder is the same as dividend.

Page 24
CO & OS MATERIAL

B Register Sequence Counter( SC)

Complementer and parallel

adder

AS QS
Qn

A Register Q Register 0
E
Hardware for implementing division of fixed point signed- Magnitude Numbers Example

of Binary division with digital hardware: Divisor B = 10001, B + 1 = 01111

E A Q SC

Dividend: 01110 00000 5

Shl EAQ 11100 00000

Add , B +1 01111

E=1 1 01011

Set Qn= 1 1 01011 00001 4

Shl EAQ 0 10110 00010

Add , B +1 01111

E=1 1 00101

Set Qn= 1 1 00101 00011 3

Shl EAQ 0 01010 00110

Add , B +1 01111

E= 0; Leave Qn= 0 0 11001 00110

Add B 10001

**

Page 25
CO & OS MATERIAL

Restore remainder 1 01010 2

Shl EAQ 0 10100 01100

Add , B +1 01111

E=1 1 00011

Set Qn= 1 1 00011 01101 1

Shl EAQ 0 00110 11010

Add , B +1 01111

E= 0; Leave Qn= 0 0 10101 11010

Add B 10001

Restore remainder 1 00110 11010 0

Neglect E

Remainder in A 00110 11010

Quotient in Q

Divide overflow:

When the dividend is twice as long as the divisor, the condition for overflow can be stated as follows:

A divide-overflow condition occurs if the higher order half bits of the dividend constitute a number greater
than or equal to the divisor. If the divisor is zero, then the dividend will definitely be greater than or equal
to divisor. Hence divide overflow condition occurs and hence the divide-overflow –flip flopwill be set. Let
the flip flop be called DVF.

Handling DVF:

1. Check if DVF is set after each divide instruction. If DVF is set, then the program branches to a
subroutine that takes corrective measures such as rescaling the data to avoid overflow.
2. An interrupt is generated if DVF is set. The interrupt causes the processor to suspend the
current program and branch to interrupt service routine to take corrective measure. The most

Page 26
CO & OS MATERIAL

common corrective measure is to remove the program and type an error message that explains
the reasons.
3. The divide overflow can be handled very simply if the numbers are represented in floating point
representation.

Flow chart for divide operation:

Assumption:

Operands are transferred from memory to registers as n bit words.n-1 bit form magnitude and 1 bit
shows the sign.

Page 27
CO & OS MATERIAL

A divide overflow condition is tested by subtracting the divisor in B from half of the bits of dividend stored
in A. If vA ≥ B, the DVF is set and the operation is terminated prematurely. If A < B, no DVF occurs and so
the value of dividend is restored by adding B to A.

The division of the magnitudes starts by shifting the dividend in AQ to the left, with the higher order bit
shifted into E. If the bit shifted into E is 1, we know that EA is greater than B because EA consists of a 1
followed by n-1 bits while B consists of only n-1 bits. In this case, B must be subtracted from EA and 1
inserted into Qn for the quotient bit. Since register A is missing the higher order bit of the dividend (which
is in E), it’s value is EA – 2n-1 . Adding to this value the 2’s complement of B results in

(EA-2n-1 ) + ( 2n-1 –B )= E-B. The carry from the addition is not transferred to E if we want E to remain a 1.

If the shift left operation inserts a zero into E, the divisor is subtracted by adding it’s 2’s complement value
and the carry is transferred into E. If E = 1, it signifies that A ≥ B and hence Qn is set to 1. If E = 0, it signifies
that A < B and the original number is restored by adding B to A. In the latter case we leave a 0 inQn .( 0 was
inserted during the shift).

This process is repeated again with register A holding the partial remainder. After n-1 times, the
quotient magnitude is formed in the register Q and the remainder is found in register A.

Page 28
CO & OS MATERIAL

Page 29
CO & OS MATERIAL

2.
Page 30
CO & OS MATERIAL

Page 31
CO & OS MATERIAL

Page 32
CO & OS MATERIAL

Page 33
CO & OS MATERIAL

Page 34
CO & OS MATERIAL

Page 35
CO & OS MATERIAL

Page 36
CO & OS MATERIAL

Page 37
CO & OS MATERIAL

Page 38
CO & OS MATERIAL

Page 39
CO & OS MATERIAL

Page 40
CO & OS MATERIAL

Page 41
CO & OS MATERIAL

Page 42
CO & OS MATERIAL

Page 43
CO & OS MATERIAL

Page 44
CO & OS MATERIAL

Page 45
CO & OS MATERIAL

Page 46
CO & OS MATERIAL

Page 47
CO & OS MATERIAL

Page 48