PCC-253-COM- Computer Organization & Microprocessor Notes

Course Outcomes: Upon successful completion of this course, students will be able
to:

• CO1: Understand and analyze computer system design and historical development
of computers and foundational architectures like Von Neumann and Harvard.

Unit 1 Contents:
A Brief History of Computers
●​ Von Neumann Architecture,
●​ Harvard Architecture,
●​ Designing for Performance,
●​ Evolution of Intel processor architecture- 4 bit to 64 bit,
●​ performance assessment.
●​ A top level view of Computer function and interconnection Computer
Components, Interconnection structure
●​ bus interconnection,
●​ Computer Arithmetic-
●​ The Arithmetic and Logic Unit,
●​ addition and subtraction of signed numbers,
●​ design of adder and fast adder,
 UNIT-1 (A Brief History of Computers)

●​ carry look ahead addition,

●​ multiplication of positive numbers,
●​ signed operand multiplication,
●​ Booths algorithm for multiplying binary integers.
Case Study: Evolution (Brief History) of Microprocessors

Unit I: Computer Evolution and Performance

Before the invention of computers, people relied on simple tools like sticks, stones,
and bones to keep track of numbers and perform basic calculations. As technology
progressed and human understanding grew, more advanced devices were
developed, such as the abacus and Napier's Bones. While these early tools served
as basic computational devices, they were limited in their ability to handle complex
calculations.

Below, we take a look at some of the most significant computing devices

throughout history, tracing their evolution from the earliest forms to the most
advanced technologies that followed.

1.1 The Evolution of Computers

The history of computers spans thousands of years, from early counting devices to
the powerful systems we use today. Here's an overview of the key milestones in
the evolution of computers:

PCC-253-COM- Computer Organization & Microprocessor Notes 2

 UNIT-1 (A Brief History of Computers)

It is designed to give you a clear understanding of how computers have evolved

from simple calculators to complex modern systems.

1.2 A Brief History of Computers

The evolution of computers is generally divided into generations based on the

underlying technology:

●​ First Generation (1940-1956): Used Vacuum Tubes. They were enormous,

expensive, and consumed a lot of electricity (e.g., ENIAC). In the period of the
year 1940-1956, it was referred to as the period of the first generation of
computers. These machines are slow, huge, and expensive. In this generation of
computers, vacuum tubes were used as the basic components of CPU and memory.
Also, they were mainly dependent on the batch operating systems and punch cards.
Magnetic tape and paper tape were used as output and input devices.

●​ Second Generation (1956-1963):Used Transistors. These were smaller,

faster, and more [Link] were period of the year, 1957-1963 was

PCC-253-COM- Computer Organization & Microprocessor Notes 3

 UNIT-1 (A Brief History of Computers)

referred to as the period of the second generation of computers. It was the time
of the transistor computers. In the second generation of computers, transistors
(which were cheap in cost) are used. Transistors are also compact and consume
less power. Transistor computers are faster than first-generation computers. For
primary memory, magnetic cores were used, and for secondary memory magnetic
disc and tapes for storage purposes. In second-generation computers, COBOL and
FORTRAN are used as Assembly language and programming languages, and Batch
processing and multiprogramming operating systems are allowed in these
computers.

For example IBM 1620, IBM 7094, CDC 1604, CDC 3600, etc.

●​ Third Generation (1964-1971): Used Integrated Circuits (ICs). This

allowed for further miniaturization and increased [Link] the third generation of
computers, integrated circuits (ICs) were used instead of transistors(in the
second generation). A single IC consists of many transistors which increased the
power of a computer and also reduced the cost. The third generation computers
are more reliable, efficient, and smaller in size. It used remote processing,
time-sharing, and multiprogramming as operating systems. FORTRON-II TO IV,
COBOL, and PASCAL PL/1 were used which are high-level programming languages.

For example IBM-360 series, Honeywell-6000 series, IBM-370/168, etc.

●​ Fourth Generation (1971-Present): Used Microprocessors (VLSI). This led

to the birth of the Personal Computer (PC).The period of 1971-1980 was mainly
the time of fourth generation computers. It used VLSI(Very Large Scale
Integrated) circuits. VLSI is a chip containing millions of transistors and other
circuit elements and because of these chips, the computers of this generation are
more compact, powerful, fast, and affordable(low in cost). Real-time, time-sharing

PCC-253-COM- Computer Organization & Microprocessor Notes 4

 UNIT-1 (A Brief History of Computers)

and distributed operating system are used by these computers. C and C++ are used
as the programming languages in this generation of computers.

For example STAR 1000, PDP 11, CRAY-1, CRAY-X-MP, etc.

●​ Fifth Generation (Present & Beyond): Focuses on Artificial Intelligence

(AI) and parallel [Link] 1980 - to till date these computers have been
Internet used. The ULSI (Ultra Large Scale Integration) technology is used in
fifth-generation computers instead of the VLSI technology of fourth-generation
computers. Microprocessor chips with ten million electronic components are used
in these computers. Parallel processing hardware and AI (Artificial Intelligence)
software are also used in fifth-generation computers. The programming languages
like C, C++, Java, .Net, etc. are used.

For example Desktop, Laptop, NoteBook, UltraBook, etc.

1.3 Basic Computer Architecture:

Computer architecture defines how a computer’s components communicate through
electronic signals to perform input, processing, and output operations.

●​ It covers the design and organization of the CPU, memory, storage, and
input/output devices.
●​ Describes how these components interact through buses, control signals, and
data pathways.
●​ It directly influences the overall speed, functionality, and reliability of a
computer system.

PCC-253-COM- Computer Organization & Microprocessor Notes 5

 UNIT-1 (A Brief History of Computers)

1.3.1 Von Neumann Architecture

Von Neumann architecture is a computer design where instructions and data are
stored in the same memory space. This means the CPU fetches both instructions
and data from the same memory, using the same pathways. Historically there have
been 2 types of Computers:

●​ Fixed Program Computers - Their function is very specific, and they

couldn't be reprogrammed, e.g., calculators.
●​ Stored Program Computers - These can be programmed to carry out many
different tasks; applications are stored on them, hence the name.

PCC-253-COM- Computer Organization & Microprocessor Notes 6

 UNIT-1 (A Brief History of Computers)

Components of Von Neumann Architecture

The structure described in the figure outlines the basic components of a

computer system, particularly focusing on the memory and processor. It is made
up with three main components:

●​ CPU
●​ Memory
●​ I/O Devices

We have these 3 components lets us see more about them in detail:

CPU (Central Processing Unit)

The central processing unit (CPU) is the main part of a computer that controls how
it works. It is made up of the control unit, main memory, and the arithmetic logic
unit (ALU). The CPU handles instructions from programs, processes data, stores
information, and produces results. Without the CPU, a computer cannot perform
tasks or run any applications.

PCC-253-COM- Computer Organization & Microprocessor Notes 7

 UNIT-1 (A Brief History of Computers)

.CU (Control Unit)

The control unit manages how the processor works by sending control signals. It
decides how data should move inside the computer, controls input and output
operations, and fetches the instructions from memory for execution.

ALU (Arithmetic and Logic Unit)

The arithmetic and logic unit is the part of the CPU that handles the calculations
and decision-making tasks. It performs arithmetic operations like addition and
subtraction, logical operations such as comparisons, and tasks like shifting bits in
data.

Registers

PCC-253-COM- Computer Organization & Microprocessor Notes 8

 UNIT-1 (A Brief History of Computers)

Registers are the fastest type of memory located inside the CPU. They
temporarily store information that the processor is currently working on, making
program execution and operations faster and more efficient. Register serve as the
CPU's primary working memory.

●​ PC (Program Counter): Keeps track of the address of the next instruction

to be executed.
●​ IR (Instruction Register): Holds the current instruction being executed.
●​ MAR (Memory Address Register): Stores the address of the memory
location being accessed.
●​ MDR (Memory Data Register): Temporarily holds data being transferred to
or from memory.
●​ Accumulator: A register that stores intermediate results of arithmetic and
logic operations.
●​ General Purpose Registers: Used for temporary storage of data during
processing.

Bus

The bus is a communication system that transfers data, addresses, and control
signals between the CPU, memory, and I/O devices. In Von Neumann architecture,
a single bus is shared for both data and instructions, which can create a
bottleneck (known as the Von Neumann bottleneck).

I/O Bus

●​ I/O Interface: Connects the CPU and memory to input/output devices.

●​ Device: Refers to external hardware like keyboards, monitors, or storage
devices.

Key Characteristics

PCC-253-COM- Computer Organization & Microprocessor Notes 9

 UNIT-1 (A Brief History of Computers)

1.​ Single Memory for Data and Instructions: Both data and program
instructions are stored in the same memory.
2.​ Shared Bus: A single bus is used for transferring data, addresses, and
control signals, which can limit performance.
3.​ Sequential Execution: Instructions are executed one at a time in a
sequential manner.

Von Neumann bottleneck

Whatever we do to enhance performance, we cannot get away from the fact that
instructions can only be done one at a time and can only be carried out
sequentially. Both of these factors hold back the competence of the CPU. This is
commonly referred to as the 'Von Neumann bottleneck'. We can provide a Von
Neumann processor with more cache, more RAM, or faster components but if
original gains are to be made in CPU performance then an influential inspection
needs to take place of CPU configuration.

Applications
Von Neumann architecture is the foundation of most modern computing systems,
where both instructions and data are stored in the same memory. Here are the
some applications:

●​ Personal Computers and Laptops: Most PCs and laptops (Intel/AMD) use a
shared memory that stores both programs and data, enabling efficient running of
software like Windows and browsers. Example: Intel Core i7, AMD Ryzen
processors.
●​ Smartphones and Tablets: ARM-based devices use the shared memory
model to support multitasking and power efficiency in apps on iOS and Android.
Example: Qualcomm Snapdragon, Apple A-series chips
●​ Embedded Systems:Microcontrollers in cars, IoT devices, and appliances
use Von Neumann architecture for simple, cost-effective processing of

PCC-253-COM- Computer Organization & Microprocessor Notes 10

 UNIT-1 (A Brief History of Computers)

instructions and data in the same memory. Example Arduino Uno (ATmega328),
older ARM Cortex-M designs.
●​ Servers and Cloud Computing: Servers utilize shared memory systems to
handle large-scale software and data tasks for services like AWS and Netflix.
●​ Gaming Consoles: Consoles like PS5 and Xbox use unified memory to run
game code and manage inputs, enabling smooth gameplay.

1.3.2 Harvard Architecture

Harvard architecture is a computer design model where program instructions and

data are stored in separate memory units that are accessed through independent

buses. This separation allows the processor to fetch instructions and access data

simultaneously, which helps avoid the bottleneck present in traditional Von

Neumann systems.

●​ Eliminates the Von Neumann bottleneck.

●​ Faster and predictable performance (suitable for real-time systems).

●​ Parallel access to both instructions and data.

Working Principle
In Harvard Architecture, fetching an instruction from instruction memory and

reading/writing data from/to data memory happen at the same time without

waiting for one to finish. Separate buses prevent the bottleneck that occurs when

data and instructions share a path. For example, while an instruction is being

PCC-253-COM- Computer Organization & Microprocessor Notes 11

 UNIT-1 (A Brief History of Computers)

executed, the next instruction can be fetched simultaneously, speeding up

processing.

Buses
Buses are used as signal pathways. In Harvard architecture, there are separate

buses for both instruction and data. Types of Buses:

●​ Data Bus: It carries data among the main memory system, processor, and

I/O devices.

●​ Data Address Bus: It carries the address of data from the processor to the

main memory system.

●​ Instruction Bus: It carries instructions among the main memory system,

processor, and I/O devices.

PCC-253-COM- Computer Organization & Microprocessor Notes 12

 UNIT-1 (A Brief History of Computers)

●​ Instruction Address Bus: It carries the address of instructions from the

processor to the main memory system.

Components of Harvard Architecture

Harvard architecture is designed with specific components that handle instruction

execution, control, and data communication.

●​ Arithmetic and Logic Unit: The arithmetic logic unit is part of the CPU that

operates all the calculations needed. It performs addition, subtraction,

comparison, logical Operations, bit Shifting Operations, and various arithmetic

operations.

●​ Control Unit: The Control Unit is the part of the CPU that operates all

processor control signals. It controls the input and output devices and also

controls the movement of instructions and data within the system.

●​ Input/Output System: Input devices are used to read data into main

memory with the help of CPU input instruction. The information from a computer

as output is given through Output devices. The computer gives the results of

computation with the help of output devices.

Application of Harvard Architecture

Harvard architecture is a type of computer design where the memory for

instructions and data are kept separate. Here are the some applications:

Digital Signal Processors (DSPs):

PCC-253-COM- Computer Organization & Microprocessor Notes 13

 UNIT-1 (A Brief History of Computers)

●​ Audio and video processing, telecommunications, radar systems, and image

processing.

●​ Texas Instruments TMS320 for hearing aids.

Microcontrollers (MCUs):

●​ Embedded systems in consumer electronics, automotive systems, IoT

devices, and industrial automation.

●​ PIC in automotive ABS

Network Processors:

●​ Routers, switches, and network security appliances.

●​ Broadcom StrataXGS

Automotive Systems:

●​ Engine control units (ECUs), advanced driver-assistance systems (ADAS),

and infotainment systems.

●​ NXP S32K for engine control

eature Von Neumann Architecture arvard Architecture

PCC-253-COM- Computer Organization & Microprocessor Notes 14

 UNIT-1 (A Brief History of Computers)

Memory Single shared memory for data and Separate memories for data and
instructions. instructions.
Structure

us System One set of buses (Address & Data). Two sets of buses (one for

each memory).

Speed/Performance Slower (cannot fetch both at once). Faster

(supports parallel fetching).

Space Efficiency i Low (unused space in one memory

annot be used by the other).
(free memory can be used for

either data or code).

Complexity Simple hardware design. Complex and more

expensive hardware.

Typical Use General-purpose PCs, workstations. Microcontrollers

PCC-253-COM- Computer Organization & Microprocessor Notes 15

 UNIT-1 (A Brief History of Computers)

(AVR, PIC), DSPs.

1.3.3 Difference between Von Neumann Architecture and Harvard

Architecture

Difference between Von Neumann and Harvard Architecture

Von Neumann and Harvard architectures are the two basic models in the field of

computer architecture, explaining the organization of memory and processing units

in a computer system. For those involved in Computer Science or working in

companies providing computing technologies, it is essential to understand the

characteristics of these architectures.

There are two models of multiprocessing architectures: Von Neumann and

Harvard. While the former occupies a dominant position, this article will discuss

its principal differences from the latter, along with their respective advantages

and disadvantages, to help you understand which architecture is more suitable for

a given application.

Von Neumann Architecture

Von Neumann Architecture is a digital computer architecture whose design is

based on the concept of stored program computers where program data and

instruction data are stored in the same memory. This architecture was designed

by the famous mathematician and physicist John Von Neumann in 1945.

PCC-253-COM- Computer Organization & Microprocessor Notes 16

 UNIT-1 (A Brief History of Computers)

Advantages of Von Neumann Architecture

●​ Simplicity: The fact that all data and instructions are stored in a single

memory space helps the process of designing a computer system as there is no

need to create complicated systems of routing since pathways may coincide.

●​ Cost-Effective: A smaller number of components is needed as compared to

the other architectural designs hence more economical.

●​ Flexibility: A program can Always be changed or altered without

experiencing a change in some underlying physical aspects such as the circuitry.

Disadvantages of Von Neumann Architecture

●​ Bottleneck Issues: The shared bus can be a problem because the data and

control instructions cannot be obtained simultaneously and therefore it becomes

slow.

●​ Memory Corruption: Since the data and instructions reside in the same

memory, then there is a temptation of one erasing the other thereby producing

system faults.

PCC-253-COM- Computer Organization & Microprocessor Notes 17

 UNIT-1 (A Brief History of Computers)

Harvard Architecture
Harvard Architecture is the digital computer architecture whose design is based

on the concept where there are separate storage and separate buses (signal path)

PCC-253-COM- Computer Organization & Microprocessor Notes 18

 UNIT-1 (A Brief History of Computers)

for instruction and data. It was basically developed to overcome the bottleneck of

Von Neumann Architecture.

Features

●​ Separate memory spaces

●​ Fixed instruction length

●​ Parallel instruction and data access

●​ More efficient memory usage

●​ Suitable for embedded systems

●​ Limited flexibility

Advantages of Harvard Architecture

●​ Faster Processing: The availability of two buses for data and instructions

avoids a problem of contention where only one bus is used and this enhances the

velocity of the system.

●​ Improved Security: In this way the chance of memory corruption is at least

cut in half since data is not stored in the same locations as instructions.

●​ Efficient Use of Resources: It enables the use of different memory for

data and for instructions of different sizes as this help in optimal utilization of

the buses and other resources.

Disadvantages of Harvard Architecture

PCC-253-COM- Computer Organization & Microprocessor Notes 19

 UNIT-1 (A Brief History of Computers)

●​ Complexity: The design and the implementation of this type are more
intricate, thus necessitating other hardware facilities.
●​ Higher Cost: Since the concept of Harvard architecture calls for two sets
of memory and two separate buses, their implementation costs are comparatively
high than Von Neumann architecture.
●​ Less Flexibility Competitors : Changing or even improving the system can also
be a little tricky because of the different memory regions.

The Von Neumann and Harvard architectures are fundamental concepts in

computer organization, each with distinct memory and processor setups. To fully
grasp these architectures and their significance in modern computing, the GATE

PCC-253-COM- Computer Organization & Microprocessor Notes 20

 UNIT-1 (A Brief History of Computers)

CS Self-Paced Course dives deep into computer architecture, making the learning
process straightforward and exam-ready.
Difference between Von Neumann and Harvard Architecture

VON NEUMANN ARCHITECTURE HARVARD ARCHITECTURE

It is ancient computer architecture based on t is modern computer architecture based on Harvard

stored program computer concept. Mark I relay based model.

Same physical memory address is used for Separate physical memory address is used for

instructions and data. instructions and data.

There is common bus for data and instruction Separate buses are used for transferring data and

transfer. instruction.

wo clock cycles are required to execute single

An instruction is executed in a single cycle.
instruction.

PCC-253-COM- Computer Organization & Microprocessor Notes 21

 UNIT-1 (A Brief History of Computers)

It is cheaper in cost. It is costly than Von Neumann Architecture.

CPU can not access instructions and CPU can access instructions and read/write at the

read/write at the same time. same time.

It is used in personal computers and small

It is used in micro controllers and signal processing.
computers.

1.4 Designing for Performance

A Computer involves many components that have their own speed, size and power
consumption requirements. There are different operating systems that use these
computers. Due to different kind of devices and software, the following issues
arise in design.

PCC-253-COM- Computer Organization & Microprocessor Notes 22

 UNIT-1 (A Brief History of Computers)

Performance

●​ Maximising processing speed, memory speed, and I/O performance.

●​ Designing energy-efficient systems for reducing environmental impact and

improving battery life.

●​ Processors operate much faster than memory and IO devices, creating a

bottleneck that can significantly slow down the overall system.

Security

●​ Protecting sensitive data from unauthorized access and breaches through

robust encryption and authentication.

Compatibility and User Experience

PCC-253-COM- Computer Organization & Microprocessor Notes 23

 UNIT-1 (A Brief History of Computers)

●​ Ensuring that systems run seamlessly across various operating systems and

hardware configurations.

●​ Designing systems that are intuitive and easy for users to operate.

System Architecture and Infrastructure

●​ Building fault tolerant systems that can withstand and recover from failures

without significant downtime.

●​ Modern systems are highly complex, requiring careful management of design,

optimization, and integration to avoid excessive costs and development time.

Resource and Technical Constraints

●​ It must work within the constraints of physical limitations, acknowledging

that both computer speed and memory capacity are finite.

●​ Effective techniques are needed to manage memory usage, especially when

dealing with large applications or datasets, to prevent slowdowns and crashes.

1.5 Evolution of Intel Processors (4-bit to 64-bit)

Intel’s journey mirrors the rapid growth of computing power.

●​ 4-bit (4004): The first microprocessor (1971). Used in calculators.

●​ 8-bit (8008, 8085): Allowed for more complex characters and basic
personal computing.

PCC-253-COM- Computer Organization & Microprocessor Notes 24

 UNIT-1 (A Brief History of Computers)

●​ 16-bit (8086): Introduced the x86 architecture used today.

●​ 32-bit (80386): Enabled multitasking and larger memory addressing (up to
4GB).
●​ 64-bit (Pentium 4/Core series): Can address massive amounts of RAM (16
Exabytes theoretically) and handle complex multimedia/scientific tasks.

Generation Key Processor Year Notable

Features

4-bit Intel 4004 1971 First single-chip

CPU; designed
for calculators;
~2,300
transistors

8-bit Intel 8008 / 1972 / 1976 Used in early

8085 computers and
weighing scales;
8085 widely used
in industrial
controllers

16-bit Intel 8086 / 1978 / 1982 8086 introduced

80286 x86
architecture;
80286
introduced
Protected Mode

PCC-253-COM- Computer Organization & Microprocessor Notes 25

 UNIT-1 (A Brief History of Computers)

32-bit Intel 80386 / 1985 / 1989 Supported

80486 multitasking and
4 GB memory
addressing;
80486
integrated Math
Coprocessor

32-bit (MMX) Pentium Series 1993–2000 Superscalar

architecture;
MMX support for
multimedia
processing

64-bit Core 2 / Core 2006–Present Supports >4 GB

i-Series RAM; multi-core
and hybrid
(P-core / E-core)
architectures

Key Architectural Shifts

The transition across these widths involved more than just "bigger numbers."

The 32-bit Revolution (x86)

The 80386 was the most critical leap. It allowed for "flat memory addressing,"
meaning programmers no longer had to deal with the messy memory "segments" of
the 16-bit era. This paved the way for modern Windows and Linux operating
systems.

The 64-bit Shift (x64)

PCC-253-COM- Computer Organization & Microprocessor Notes 26

 UNIT-1 (A Brief History of Computers)

While 32-bit could handle 4GB of RAM, 64-bit processors (starting with the Core
2 Duo era for mainstream) theoretically allow up to 16 Exabytes.

●​ Compatibility: Intel adopted the x86-64 standard, which allows 64-bit chips
to run 32-bit software natively without a speed penalty.

1.5 Performance Assessment

Performance Assessment is the process of measuring and evaluating how

effectively a computer system performs a given task. In technical terms, it is
usually defined as the inverse of execution time.

Performance = 1 / Execution Time

●​ If System A runs a program in 10 seconds and System B runs it in 5 seconds,

System B is twice as fast and has higher performance.

.2 Importance of Performance Assessment

●​ Buying Decisions: Helps users choose the right hardware.

●​ Design Optimization: Helps engineers identify bottlenecks (slow parts) in
the CPU.
●​ Cost Efficiency: Determines if a $1000 upgrade actually provides a $1000
worth of speed.
●​ Benchmarking: Allows for a fair comparison between different
architectures (like Intel vs. AMD or Apple M-series).

3. Key Performance Metrics

To measure a computer, we use specific "rulers" or metrics:

A. Execution Time (Response Time)

The total time required to complete a task, including disk accesses, memory
accesses, I/O activities, and operating system overhead.

●​ Lower is better.

PCC-253-COM- Computer Organization & Microprocessor Notes 27

 UNIT-1 (A Brief History of Computers)

B. Throughput
The total amount of work done in a given time (e.g., tasks per hour).

●​ Higher is better.

C. Clock Rate (Frequency)

The speed at which a processor executes cycles, measured in Hertz (Hz).

●​ Example: A 3.5 GHz processor performs $3.5 \times 10^9$ clock cycles per
second.

D. CPI (Cycles Per Instruction)

The average number of clock cycles it takes for a processor to execute one
instruction.

Formula: CPI = Total CPU Clock Cycles / Instruction Count

4. The CPU Performance Equation

This is the "Holy Grail" of COA performance. Every architect uses this to
calculate CPU time:

CPU Time = Instruction Count × CPI × Clock Cycle Time

OR Since: ​
Clock Cycle Time = 1 / Clock Rate

CPU Time = (Instruction Count × CPI) / Clock Rate

Explanation of Components:

1.​ Instruction Count (IC): Determined by the Program, ISA, and Compiler.
2.​ CPI: Determined by the CPU Organization and ISA.
3.​ Clock Rate: Determined by the Hardware Technology and Pipeline design.

5. Factors Affecting Performance

PCC-253-COM- Computer Organization & Microprocessor Notes 28

 UNIT-1 (A Brief History of Computers)

●​ Algorithm: Better algorithms reduce the number of instructions executed

●​ Programming Language: High-level languages may generate more instructions

●​ Compiler: Optimization affects both instruction count and cycles per

instruction

●​ ISA: Determines instruction complexity, format, and execution speed

●​ Microarchitecture: Pipeline, cache, and execution units affect CPI and clock

speed

6. Performance Comparison and Speedup

To compare two machines (X and Y), we use the Speedup ratio:

Simple explanation

●​ Speedup (n) indicates how many times system X is faster than system Y.​

●​ If n > 1 → X is faster​

●​ If n = 1 → same performance​

●​ If n < 1 → X is slower

Amdahl’s Law: This is an advanced concept stating that the performance

improvement is limited by the part of the task that cannot be improved.

PCC-253-COM- Computer Organization & Microprocessor Notes 29

 UNIT-1 (A Brief History of Computers)

7. Benchmarks

Since we can't test every program, we use Benchmarks—standardized programs

used to compare performance.

●​ SPEC (Standard Performance Evaluation Corporation): The most common

industry-standard benchmark suite.

●​ MIPS (Millions of Instructions Per Second): An older, often misleading

metric (some instructions do more work than others).

●​ MFLOPS: Millions of Floating-Point Operations Per Second (used for

scientific computers).

8. Cost vs. Performance Trade-off

In the real world, "the fastest" isn't always "the best."

●​ Increasing clock rate increases power consumption and heat.

●​ Adding more cores increases silicon cost.

●​ The goal of an architect is to maximize Performance per Watt or

Performance per Dollar.

PCC-253-COM- Computer Organization & Microprocessor Notes 30

 UNIT-1 (A Brief History of Computers)

1.6 Computer Components: The Functional Modules

At a top level, every computer consists of three primary modules:

●​ Central Processing Unit (CPU): The "brain" that fetches, decodes, and
executes instructions. It consists of the ALU, Control Unit, and Registers.
●​ Main Memory: A volatile storage area that holds the active program
instructions and the data being processed.
●​ I/O Modules: Interfaces that connect the computer to the outside world
(keyboard, monitor, disk drives).

5. Interconnection Structure

PCC-253-COM- Computer Organization & Microprocessor Notes 31

 UNIT-1 (A Brief History of Computers)

An interconnection structure is the collection of paths that connect these

modules. To function, the computer must support the following types of data
transfers:

●​ Memory to Processor: The CPU reads an instruction or a data word from

memory.
●​ Processor to Memory: The CPU writes a result or data word into memory.
●​ I/O to Processor: The CPU reads data from an input device via an I/O
module.
●​ Processor to I/O: The CPU sends data to an output device.
●​ I/O to or from Memory: Used in DMA (Direct Memory Access), where an
I/O module and memory exchange data without involving the CPU.

6. Bus Interconnection (The System Bus)

The most common interconnection structure is the Bus. A bus is a shared

communication pathway consisting of multiple lines. The bus that connects the
major components (CPU, Memory, I/O) is called the System Bus.

It is logically divided into three functional groups:

Bus Type Direction Description

Data Bus Bidirectional Carries the actual data and instructions. The
width (e.g., 32-bit or 64-bit) determines how
much data can be transferred at a time.

Address Bus Unidirectional Carries the address of the memory location

or I/O port to be accessed. Its width
determines the maximum memory capacity
(2ⁿ).

PCC-253-COM- Computer Organization & Microprocessor Notes 32

 UNIT-1 (A Brief History of Computers)

Control Bus Bidirectional Transmits command and timing signals such

as Memory Read, Memory Write, I/O Read,
Reset, and Clock.

1.7 Computer Interconnection & Bus Structure

A computer is a system of modules (CPU, Memory, I/O) that must communicate.

●​ System Bus: A communication pathway connecting major components.

○​ Data Bus: Carries the actual data.
○​ Address Bus: Specifies where the data is going (source or destination).
○​ Control Bus: Sends signals like "Read" or "Write" to manage the system.

6.2 Practical Example: Fetching Data from Memory

If the CPU needs to read a piece of data from a specific memory address:

1.​ Step 1: The CPU places the target address on the Address Bus.
2.​ Step 2: The CPU sends a "Memory Read" signal on the Control Bus.
3.​ Step 3: The Memory unit recognizes its address, retrieves the data, and
places it on the Data Bus.
4.​ Step 4: The CPU "latches" (reads) the data from the Data Bus into its
internal register.

7. Instruction Cycle (Fetch-Decode-Execute cycle)

The Instruction Cycle (also known as the Fetch-Decode-Execute cycle) is the

fundamental process by which a computer retrieves, understands, and carries out
program instructions.

PCC-253-COM- Computer Organization & Microprocessor Notes 33

 UNIT-1 (A Brief History of Computers)

Here is a detailed breakdown of how the CPU uses the System Bus (Address,
Data, and Control) during each phase.

1. The Fetch Phase

The goal of this phase is to get the instruction from the Main Memory (RAM) into
the CPU’s Instruction Register (IR).

●​ Step 1: The Program Counter (PC) holds the address of the next
instruction. This address is copied to the Memory Address Register (MAR).
●​ Step 2: The MAR places the address on the Address Bus.
●​ Step 3: The Control Unit sends a "Memory Read" signal across the Control
Bus.
●​ Step 4: The Memory unit sees the address and the read signal, finds the
instruction, and places it on the Data Bus.
●​ Step 5: The instruction travels along the Data Bus and is stored in the
Memory Data Register (MDR) (or MBR).
●​ Step 6: The instruction is copied from the MDR into the Instruction
Register (IR). Simultaneously, the Program Counter (PC) is incremented (by 1 or
the instruction length) to point to the next instruction.

2. The Decode Phase

In this phase, the CPU translates the binary code into specific control signals.

●​ Step 1: The Control Unit examines the "Opcode" (the first part of the
instruction) stored in the IR.
●​ Step 2: The decoder circuitry interprets what the instruction is (e.g., ADD,
JUMP, LOAD).
●​ Step 3: If the instruction requires data from memory (an operand), the CPU
determines where that data is located.

PCC-253-COM- Computer Organization & Microprocessor Notes 34

 UNIT-1 (A Brief History of Computers)

●​ Bus Usage: Usually, there is minimal external bus activity here as the
decoding happens internally within the CPU's control unit.

3. The Execute Phase

This is where the actual "work" happens.

●​ Step 1: If data is needed, the CPU repeats a "fetch-like" process: it puts

the operand's address on the Address Bus and reads the data via the Data Bus.
●​ Step 2: The Arithmetic Logic Unit (ALU) performs calculations or logic
comparisons if required.
●​ Step 3: The result is either stored in an internal Accumulator (ACC) or
written back to memory.
●​ Step 4 (Write Back): To save a result to RAM, the CPU puts the target
address on the Address Bus, the result on the Data Bus, and sends a "Memory
Write" signal on the Control Bus.

Bus Activity:

Phase Address Bus Data Bus Control Bus

Fetch Carries the Carries the Sends READ

instruction instruction code control signal
address from from memory to from CPU to
PC/MAR to MDR. memory.
memory.

Decode Generally idle. Generally idle. Manages internal

control and signal
routing.

Execute Carries operand Carries data to Sends READ or

or data or from the CPU. WRITE control
addresses (if signals.

PCC-253-COM- Computer Organization & Microprocessor Notes 35

 UNIT-1 (A Brief History of Computers)

required).

1.8 COMPUTER ARITHMETIC

Introduction:

Data is manipulated by using the arithmetic instructions in digital computers.

Data is manipulated to produce results necessary to give solution for the

computation problems.

The Addition, subtraction, multiplication and division 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.

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-2’s complement representation.

PCC-253-COM- Computer Organization & Microprocessor Notes 36

 UNIT-1 (A Brief History of Computers)

• 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 of previous 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 rectangular boxes and the

decision steps are indicated inside diamond-shaped boxes from which 2 or more

alternate path emerge

Addition and Subtraction:

There are three ways of representing negative fixed point binary numbers:

1. Signed-magnitude representation ---- used for the representation of mantissa

for floating point operations by most [Link] value is obtained by

changing the MSB from 0 to 1 of the corresponding positive [Link] ex, +5 is

represented by 0101 & -5 represented by 1101

PCC-253-COM- Computer Organization & Microprocessor Notes 37

 UNIT-1 (A Brief History of Computers)

2.​ Signed-1’s complement: negative values are obtained by complementing each bit
of the corresponding positive number.

For ex, -5 is obtained by complementing each bit in 0101 to yield 1010.

(In other words, the operation of forming the 1's complement of a given number is
equivalent to subtracting that number from 2n-1).

3. Signed -2’s complement—Most computers use this form for performing

arithmetic operation with integers. forming the 2's complement of a number is

done by subtracting that number from 2n.

For ex, -5 is obtained by complementing each bit in 0101 & then adding 1 to yield

1011.(In other words, the 2's complement of a number is obtained by adding 1 to

the 1's complement of that number).

PCC-253-COM- Computer Organization & Microprocessor Notes 38

 UNIT-1 (A Brief History of Computers)

●​ 2's complement system yields the most efficient way to carry out

addition/subtraction operations

Addition for signed-magnitude data:

The representation of numbers in signed-magnitude is familiar because it is used

in arithmetic calculations.

• 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.

PCC-253-COM- Computer Organization & Microprocessor Notes 39

 UNIT-1 (A Brief History of Computers)

• 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

• 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.

PCC-253-COM- Computer Organization & Microprocessor Notes 40

 UNIT-1 (A Brief History of Computers)

• 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.

• Following are the two rules for addition and subtraction of n-bit signed

numbers using the 2'scomplement representation system (Figure 1.6).

Rule 1:

Ø To Add two numbers, add their n-bits and ignore the carry-out signal from the

MSB position.

Ø Result will be algebraically correct, if it lies in the range -2n-1 to +2n-1-1.

Rule 2:

Ø To Subtract two numbers X and Y (that is to perform X-Y), take the 2's

complement of Y andthen add it to X as in rule 1.

Ø Result will be algebraically correct, if it lies in the range (2n-1) to +(2n-1-1).

• When the result of an arithmetic operation is outside the representable-range,

an arithmetic overflowis said to occur.

• To represent a signed in 2's complement form using a larger number of bits,

repeat the sign bit asmany times as needed to the left. This operation is called

sign extension.

• In 1's complement representation, the result obtained after an addition

operation is not always correct. The carry-out(cn) cannot be ignored. If cn=0, the

result obtained is correct. If cn=1, then a 1 must be added to the result to make it

correct.

PCC-253-COM- Computer Organization & Microprocessor Notes 41

 UNIT-1 (A Brief History of Computers)

Addition signed-2’s complement Data

• The addition of two numbers in signed-2's complement form consists of

adding the numbers with the sign bits treated the same as the other bits of the

number.

• A carry-out of the sign-bit position is discarded.

• The subtraction consists of first taking the 2's complement of the

subtrahend and then adding it to the minuend.

• The register configuration for the hardware implementation is shown in

Figure below.

PCC-253-COM- Computer Organization & Microprocessor Notes 42

 UNIT-1 (A Brief History of Computers)

Algorithm for adding and subtracting numbers in 2’s complement form

• The sum is obtained by adding the contents of AC and BR (including their

sign bits).

• The overflow bit V is set to 1 if the exclusive-OR of the last two carries is

1, and it is cleared to 0 otherwise.

• The subtraction operation is accomplished by adding the content of AC to

the 2's complement of BR.

• Taking the 2's complement of BR has the effect of changing a positive

number to negative, and vice versa.

PCC-253-COM- Computer Organization & Microprocessor Notes 43

 UNIT-1 (A Brief History of Computers)

• An overflow must be checked during this operation because the

​ two numbers added could have the same sign.

• The programmer must realize that if an overflow occurs, there will be an

erroneous result in the AC register.

OVERFLOW IN INTEGER ARITHMETIC

• When result of an arithmetic operation is outside the representable-range, an

arithmetic overflow is said to occur.

• For example: If we add two numbers +7 and +4, then the output sum S is
1011(ß0111+0100),which is the code for -5, an incorrect result.

• An overflow occurs in following 2 cases

1.​ Overflow can occur only when adding two numbers that have the same sign.
2.​ The carry-out signal from the sign-bit position is not a sufficient indicator
of overflow whenadding signed numbers

PCC-253-COM- Computer Organization & Microprocessor Notes 44

 UNIT-1 (A Brief History of Computers)

3.​

DESIGN OF ADDER AND FAST ADDER

PCC-253-COM- Computer Organization & Microprocessor Notes 45

 UNIT-1 (A Brief History of Computers)

●​ A cascaded connection of n full-adder blocks can be used to add 2-bit

numbers

●​ Since carries must propagate (or ripple) through cascade, the configuration

is called an n-bit ripplecarry adder (Figure 9.1).

PCC-253-COM- Computer Organization & Microprocessor Notes 46

 UNIT-1 (A Brief History of Computers)

DESIGN OF ADDER

PCC-253-COM- Computer Organization & Microprocessor Notes 47

 UNIT-1 (A Brief History of Computers)

●​ The n-bit adder can be used to add 2's complement numbers X and Y
(Figure 9.3).
●​ Overflow can only occur when the signs of the 2 operands are the same.
●​ In order to perform the subtraction operation X-Y on 2's complement
numbers X and Y; we form the2's complement of Y and add it to X.
●​ Addition or subtraction operation is done based on value applied to the
Add/Sub input control-line.
●​ Control Line = 0 for addition, applying the Y vector unchanged to one of the
[Link]-line=1 for subtraction, the Y vector is 2's complemented.

DESIGN OF FAST ADDERS

• Drawback of ripple carry adder: If the adder is used to implement the
addition/subtraction, allsum bits are available in 2n gate delays.

• Two approaches can be used to reduce delay in adders:

PCC-253-COM- Computer Organization & Microprocessor Notes 48

 UNIT-1 (A Brief History of Computers)

1) Use the fastest possible electronic-technology in implementing the ripple-carry

design.

2) Use an augmented logic-gate network structure.

CARRY-LOOKAHEAD ADDITIONS

• The logic expression for si(sum) and ci+1(carry-out) of stage i are

si=xi+yi+ci ​ ------(1)
​ ci+1=xiyi+xici+yici---------------------------------------- (2)

• Factoring (2) into

ci+1=xiyi+(xi+yi)ci

we can write-

ci+1=Gi+PiCi ​ where Gi=xiyi and Pi=xi+yi

• The expressions Gi and Pi are called generate and propagate functions (Figure
9.4).

• If Gi=1, then ci+1=1, independent of the input carry ci. This occurs when both xi
and yi are 1. Propagate function means that an input-carry will produce an
output-carry when either xi=1 oryi=1.
• All Gi and Pi functions can be formed independently and in parallel in one
logic-gate delay.

• Expanding ci terms of i-1 subscripted variables and substituting into the ci+1
expression, we obtainci+1=Gi+PiGi-1+PiPi-1Gi-2. . . .

. .+P1G0+PiPi-1.................................................................................................................. P0c0

• Conclusion: Delay through the adder is 3 gate delays for all carry-bits &4 gate
delays for all sum-bits.

PCC-253-COM- Computer Organization & Microprocessor Notes 49

 UNIT-1 (A Brief History of Computers)

• Consider the design of a 4-bit adder. The carries can be implemented

asc1=G0+P0c0
c2=G1+P1G0+P1P0c0
c3=G2+P2G1+P2P1G0+P2P1P0c0 c4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0c0

• The carries are implemented in the block labeled carry-lookahead logic. An

adder implemented in thisform is called a Carry-Lookahead Adder.
●​ Limitation: If we try to extend the carry-lookahead adder for longer
operands, we run into a problemof gate fan-in constraints

PCC-253-COM- Computer Organization & Microprocessor Notes 50

 UNIT-1 (A Brief History of Computers)

HIGHER-LEVEL GENERATE & PROPAGATE FUNCTIONS

• 16-bit adder can be built from four 4-bit adder blocks (Figure 9.5).

• These blocks provide new output functions defined as Gk and Pk,where k=0 for
the first 4-bit block,

k=1 for the second 4-bit block and so on.

• In the first block,

P0=P3P2P1P0

& G0=G3+P3G2+P3P2G1+P3P2P1G0
• The first-level Gi and Pi functions determine whether bit stage i generates or
propagates a carry, and the second level Gk and Pk functions determine whether
block k generates or propagates a carry.
• Carry c16 is formed by one of the carry-lookahead circuits as
c16=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0c0

Conclusion: All carries are available 5 gate delays after X, Y and c0 are applied as
inputs

PCC-253-COM- Computer Organization & Microprocessor Notes 51

 UNIT-1 (A Brief History of Computers)

MULTIPLICATION OF POSITIVE NUMBERS:

PCC-253-COM- Computer Organization & Microprocessor Notes 52

 UNIT-1 (A Brief History of Computers)

PCC-253-COM- Computer Organization & Microprocessor Notes 53

 UNIT-1 (A Brief History of Computers)

ARRAY MULTIPLICATION

• The main component in each cell is a full adder(FA)..

• The AND gate in each cell determines whether a multiplicand bit mj, is added to
the incoming partial-product bit, based on the value of the multiplier bit qi
(Figure9.6).

• An Array multiplier is implemented with combinational circuit.

• Consider the multiplication of two 2-bit numbers as shown in figure.

• The multiplicand bits are b1 and bo; the multiplier bits are a1 and a0 and

the product is c3c2c1c0.

• The partial product is formed by multiplying a0 by b1b0.

• The multiplication of two bits such as ao and b0 produces a result 1 if both

bits are 1; otherwise , it produces a 0.

• This is identical to an AND operation and can be implemented with an AND

gate.

• As shown in the figure, the first partial product is formed by means of two

AND gates.

• The second partial product is formed by multiplying a1 by b1b0 and is

shifted to one position to the left.

• The two partial products are added with two half adders circuits.

2 bit by 2 bit Array multiplier

PCC-253-COM- Computer Organization & Microprocessor Notes 54

 UNIT-1 (A Brief History of Computers)

BINARY MULTIPLIER (SEQUENTIAL CIRCUIT)

• Registers A and Q combined hold PPi(partial product)

while the multiplier bit qi generates the signal Add/Noadd

PCC-253-COM- Computer Organization & Microprocessor Notes 55

 UNIT-1 (A Brief History of Computers)

• The carry-out from the adder is stored in flip-flop C (Figure 9.7).

• Procedure for multiplication:

1.​ Multiplier is loaded into register Q, Multiplicand is loaded into register

M and
2.​ C & A are cleared to 0.
3.​ If q0=1, add M to A and store sum in A. Then C, A and Q are shifted
right one [Link] q0=0, no addition performed and C, A & Q are
shifted right one bit-position.
4.​ After n cycles, the high-order half of the product is held in register A
andthe low-order half is held in register Q

5.​

PCC-253-COM- Computer Organization & Microprocessor Notes 56

 UNIT-1 (A Brief History of Computers)

6.​
SIGNED OPERAND MULTIPLICATION:

• This algorithm

→ generates a 2n-bit product

→ treats both positive & negative 2's-complement n-bit operands uniformly(Figure

9.9-9.12).

• Attractive feature: This algorithm achieves some efficiency in the number of

addition required whenthe multiplier has a few large blocks of 1s.

PCC-253-COM- Computer Organization & Microprocessor Notes 57

 UNIT-1 (A Brief History of Computers)

• This algorithm suggests that we can reduce the number of operations required

for multiplication byrepresenting multiplier as a difference between 2 numbers.

For e.g. multiplier(Q) 14(001110) can be represented as

010000 (16) - 000010 (2) = 001110 (14)

●​ Therefore, product P=M*Q can be computed by adding 24 times the M to

the 2's complement of 21times the M.

PCC-253-COM- Computer Organization & Microprocessor Notes 58

 UNIT-1 (A Brief History of Computers)

FAST MULTIPLICATION
BIT-PAIR RECODING OF MULTIPLIERS

●​ This method

→ derived from the booth algorithm

→ reduces the number of summands by a factor of 2

●​ Group the Booth-recoded multiplier bits in pairs. (Figure 9.14 & 9.15).
●​ The pair (+1 -1) is equivalent to the pair (0 +1)

PCC-253-COM- Computer Organization & Microprocessor Notes 59

 UNIT-1 (A Brief History of Computers)

●​

PCC-253-COM- Computer Organization & Microprocessor Notes 60

 UNIT-1 (A Brief History of Computers)

Carry-save Addition of Summands:

●​ Consider the array for 4*4 multiplication. (Figure 9.16 & 9.18).
●​ Instead of letting the carries ripple along the rows, they can be "saved" and
introduced into the nextrow, at the correct weighted positions

PCC-253-COM- Computer Organization & Microprocessor Notes 61

 UNIT-1 (A Brief History of Computers)

PCC-253-COM- Computer Organization & Microprocessor Notes 62

 UNIT-1 (A Brief History of Computers)

•The full adder is input with three partial bit products in the first row.

• Multiplication requires the addition of several summands.

• CSA speeds up the addition process.

• Consider the array for 4x4 multiplication shown in fig 9.16.

• First row consisting of just the AND gates that implement the bit products
m3q0, m2q0, m1q0 and m0q0.
• The delay through the carry-save array is somewhat less than delay through the
ripple-carry array. This is because the S and C vector outputs from each row are
produced in parallel in one full-adder delay.

• Consider the addition of many summands in fig 9.18.

• Group the summands in threes and perform carry-save addition on each of these
groups in parallel togenerate a set of S and C vectors in one full-adder delay
• Group all of the S and C vectors into threes, and perform carry-save addition on
them, generating afurther set of S and C vectors in one more full-adder delay

• Continue with this process until there are only two vectors remaining

• They can be added in a RCA or CLA to produce the desired product.

• When the number of summands is large, the time saved is proportionally much
greater.

• Delay: AND gate + 2 gate/CSA level + CLA gate delay, Eg., 6 bit number require
15 gate delay,array 6x6 require 6(n-1)-1 = 29 gate Delay.

• In general, CSA takes 1.7 log2k-1.7 levels of CSA to reduce k summands.

PCC-253-COM- Computer Organization & Microprocessor Notes 63

 UNIT-1 (A Brief History of Computers)

BOOTH MULTIPLICATION ALGORITHMN FOR INTEGER NUMBER

Booth algorithm gives a procedure for multiplying binary integers in signed-2's

complement representation

FIG:

• As in all multiplication schemes, Booth algorithm requires examination of

the multiplier bits and shifting of the partial product.

• Prior to the shifting, the multiplicand may be added to the partial product,

subtracted from the partial product, or left unchanged according to the following

rules:

1.​ The multiplicand is subtracted from the partial product upon encountering

the first least significant 1 in a string of 1'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.

PCC-253-COM- Computer Organization & Microprocessor Notes 64

 UNIT-1 (A Brief History of Computers)

3.​ The partial product does not change when the multiplier bit is identical to

the previous multiplier bit.

The hardware implementation of Booth algorithm requires the ​register

configuration shown in Figure.

Qn designates the least significant bit of the multiplier in register QR. An extra

flip-flop Qn+1is appended to QR to facilitate a double bit inspection of the

multiplier

PCC-253-COM- Computer Organization & Microprocessor Notes 65

 UNIT-1 (A Brief History of Computers)

The flowchart for Booth algorithm is shown in Figure .

• AC and the appended bit Qn+1 are initially cleared to 0 and the sequence

counter SC is set to a number n equal to the number of bits in the multiplier.

• The two bits of the multiplier in Qn and Qn+1 are inspected.

• If the two bits are equal to 10, it means that the first 1 in a string of 1's

has been encountered. This requires a subtraction of the multiplicand from the

partial product in AC.

PCC-253-COM- Computer Organization & Microprocessor Notes 66

 UNIT-1 (A Brief History of Computers)

• If the two bits are equal to 01, it means that the first 0 in a string of 0's

has been encountered. This requires the addition of the multiplicand to the partial

product in AC.

• When the two bits are equal, the partial product does not change. An

overflow cannot occur because the addition and subtraction of the multiplicand

follow each other.

• The next step is to shift right the partial product and the multiplier

(including bit Qn+1).

• This is an arithmetic shift right (ashr) operation which shifts AC and QR

to the right and leaves the sign bit in AC unchanged.

• The sequence counter is decremented and the computational loop is

repeated n times.

• A numerical example of Booth algorithm is shown in Table 5. It shows the

step-by-step multiplication of (-9) x (-13) = + 117.

• Here the multiplier in QR is negative and that the multiplicand in BR is also

negative. The 10-bit product appears in AC and QR and is positive.

PCC-253-COM- Computer Organization & Microprocessor Notes 67

 UNIT-1 (A Brief History of Computers)

Table : Example of Multiplication with Booth Algorithm

• Now Result is available in Registers AR and QR. i.e. 0001110101 =>+117.

PCC-253-COM- Computer Organization & Microprocessor Notes 68

 UNIT-1 (A Brief History of Computers)

SOLVED PROBLEMS:

Problem 1:
Represent the decimal values 5, -2, 14, -10, 26, -19, 51 and -43 as
signed 7-bit numbers in the following binary formats:
●​ sign-and-magnitude
●​ 1’s-complement
●​ 2’s-complement

Solution:
The three binary representations are given as:

Problem 2:
(a) Convert the following pairs of decimal numbers to 5-bit 2’s-complement numbers,
then add [Link] whether or not overflow occurs in each case.

a) 5 and 10 ​b) 7 and 13

c) –14 and 11 ​ d) –5 and 7

e) –3 and –8

Repeat Problem 1.7 for the subtract operation, where the second number of each pair is tobesubtracted
from the first number. State whether or not overflow occurs in each case

PCC-253-COM- Computer Organization & Microprocessor Notes 69

 UNIT-1 (A Brief History of Computers)

SOLUTION:

(b) To subtract the second number, form its 2's-complement and add it to the first
number.

Problem 3:
Perform following operations on the 6-bit signed numbers using 2's complement
representation system. Also indicate whether overflow has occurred

PCC-253-COM- Computer Organization & Microprocessor Notes 70

 UNIT-1 (A Brief History of Computers)

SOLUTIONS:

PCC-253-COM- Computer Organization & Microprocessor Notes 71

 UNIT-1 (A Brief History of Computers)

PROBLEM 4:

Perform signed multiplication of following 2’s complement numbers using

Booth’s algorithm.

(a) A=010111 and B=110110 ​ (b) A=110011 and B=101100

( c ) A=110101 and B=011011 ​ (d) A=001111 and B=001111

(e) A=10100 and B=10101 f) A=01110 and B=11000

PCC-253-COM- Computer Organization & Microprocessor Notes 72

 UNIT-1 (A Brief History of Computers)

SOLUTION:

PCC-253-COM- Computer Organization & Microprocessor Notes 73

 UNIT-1 (A Brief History of Computers)

PCC-253-COM- Computer Organization & Microprocessor Notes 74