Sanjivani Rural Education Society’s
Sanjivani College of Engineering, Kopargaon-423 603
(An Autonomous Institute, Affiliated to Savitribai Phule Pune University, Pune)
NACC ‘A’ Grade Accredited, ISO 9001:2015 Certified
Department of Computer Engineering
(NBA Accredited)
Subject- Computer Organization & Architecture
Unit 2 – Computer Arithmetic
Signed Fast Multiplication
Dr. D. B. Kshirsagar, Professor & Head
E-mail : hodcompcoe@sanjivani.org.in
Contact No: 02434 – 222862 Ext :141, 9890472165
Bit-Pair Recoding of Multipliers
• Bit-pair recoding halves the maximum number of summands (versions of
the multiplicand).
Sign extension Implied 0 to right of LSB
1 1 1 0 1 0 0
0 0 1 +1 1 0
0 1 2
(a) Example of bit-pair recoding derived from Booth recoding
28-09-2021 Computer Organization: Arithmetic 2
Bit-Pair Recoding of Multipliers
Multiplier bit-pair Multiplier bit on the right Multiplicand
selected at position i
i + 1 i i 1
0 0 0 0 X M
0 0 1 + 1 X M
0 1 0 + 1 X M
0 1 1 + 2 X M
1 0 0 2 X M
1 0 1 1 X M
1 1 0 1 X M
1 1 1 0 X M
(b) Table of multiplicand selection decisions
28-09-2021 Computer Organization: Arithmetic 3
Bit-Pair Recoding of Multipliers
0 1 1 0 1
0 - 1 +1 - 1 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 1 1
0 0 0 0 1 1 0 1
1 1 1 0 0 1 1
0 1 1 0 1 ( + 13 ) 0 0 0 0 0 0
´ 1 1 0 1 0 (- 6 ) 1 1 1 0 1 1 0 0 1 0 ( - 78 )
0 1 1 0 1
0 -1 - 2
1 1 1 1 1 0 0 1 1 0
1 1 1 1 0 0 1 1
0 0 0 0 0 0
1 1 1 0 1 1 0 0 1 0
28-09-2021 Computer Organization: Arithmetic 4
Booth’s Algorithm
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 5
Example of Booth’s Algorithm
Multiplier Multiplicand
1110 + 0111 = 0101;
-2 + 7 = 5
Product
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 6
Signed multiplication (Booth Algorithm) Example
Multiplicand M: 1011 (-5)
M
Multiplier Q: 1010 (-6)
0 0 0 0 1 0 1 0 0 1 0 1 1
Q-1 Product: 0001 1110 (30)
A Q
0 0 0 0 0 1 0 1 0 shift First cycle
0 1 0 1 0 1 0 1 0 A = A-M
Second cycle
0 0 1 0 1 0 1 0 1 shift
1 1 0 1 1 0 1 0 1 A = A+M Third cycle
1 1 1 0 1 1 0 1
0 shift
0 0 1 1 1 1 0 1 0 A = A-M
Fourth cycle
0 0 0 1 1 1 1 0 1 shift
Product
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 7
Book References
• William Stallings, Computer Organization and Architecture: Designing for
performance, Pearson Education/ Prentice Hall of India, 10th Edition
• Zaky S, Hamacher, Computer Organization, McGraw-Hill Publications, 5th Edition
• John P Hays, Computer Architecture and Organization, McGraw-Hill Publication, 3rd
Edition.
• A. Tannenbaum, Structured Computer Organization, Prentice Hall of India, 4th
Edition
28-09-2021 Computer Organization: Introduction 8
