Home COA Computer Fundamentals
Booth's Multiplication Algorithm
The booth algorithm is a multiplication algorithm that
allows us to multiply the two signed binary integers in
2's complement, respectively. It is also used to speed
up the performance of the multiplication process. It is
very efficient too. It works on the string bits 0's in the
multiplier that requires no additional bit only shift the
right-most string bits and a string of 1's in a multiplier
bit weight 2k to weight 2m that can be considered as
2k+ 1 - 2m.
Following is the pictorial representation of the Booth's
Algorithm:
In the above flowchart, initially, AC and Qn + 1 bits are
set to 0, and the SC is a sequence counter that
represents the total bits set n, which is equal to the
number of bits in the multiplier. There are BR that
represent the multiplicand bits, and QR represents
the multiplier bits. After that, we encountered two bits
of the multiplier as Qn and Qn + 1, where Qn represents
the last bit of QR, and Qn + 1 represents the
incremented bit of Qn by 1. Suppose two bits of the
multiplier is equal to 10; it means that we have to
subtract the multiplier from the partial product in the
accumulator AC and then perform the arithmetic shift
operation (ashr). If the two of the multipliers equal to
01, it means we need to perform the addition of the
multiplicand to the partial product in accumulator AC
and then perform the arithmetic shift operation (ashr),
including Qn + 1. The arithmetic shift operation is used
in Booth's algorithm to shift AC and QR bits to the right
by one and remains the sign bit in AC unchanged. And
the sequence counter is continuously decremented till
the computational loop is repeated, equal to the
number of bits (n).
ADVERTISEMENT
Working on the Booth Algorithm
1. Set the Multiplicand and Multiplier binary bits as
M and Q, respectively.
2. Initially, we set the AC and Qn + 1 registers value
to 0.
3. SC represents the number of Multiplier bits (Q),
and it is a sequence counter that is continuously
decremented till equal to the number of bits (n)
or reached to 0.
4. A Qn represents the last bit of the Q, and the
Qn+1 shows the incremented bit of Qn by 1.
5. On each cycle of the booth algorithm, Qn and Qn
+ 1 bits will be checked on the following
parameters as follows:
i. When two bits Qn and Qn + 1 are 00 or 11,
we simply perform the arithmetic shift
right operation (ashr) to the partial
product AC. And the bits of Qn and Qn + 1
is incremented by 1 bit.
ii. If the bits of Qn and Qn + 1 is shows to 01,
the multiplicand bits (M) will be added to
the AC (Accumulator register). After that,
we perform the right shift operation to the
AC and QR bits by 1.
iii. If the bits of Qn and Qn + 1 is shows to 10,
the multiplicand bits (M) will be subtracted
from the AC (Accumulator register). After
that, we perform the right shift operation
to the AC and QR bits by 1.
ADVERTISEMENT
6. The operation continuously works till we reached
n - 1 bit in the booth algorithm.
7. Results of the Multiplication binary bits will be
stored in the AC and QR registers.
There are two methods used in Booth's Algorithm:
1. RSC (Right Shift Circular)
It shifts the right-most bit of the binary number, and
then it is added to the beginning of the binary bits.
ADVERTISEMENT
2. RSA (Right Shift Arithmetic)
It adds the two binary bits and then shift the result to
the right by 1-bit position.
ADVERTISEMENT
Example: 0100 + 0110 => 1010, after adding the binary
number shift each bit by 1 to the right and put the first
bit of resultant to the beginning of the new bit.
Example: Multiply the two numbers 7 and 3 by using
the Booth's multiplication algorithm.
Ans. Here we have two numbers, 7 and 3. First of all,
we need to convert 7 and 3 into binary numbers like 7 =
(0111) and 3 = (0011). Now set 7 (in binary 0111) as
multiplicand (M) and 3 (in binary 0011) as a multiplier
(Q). And SC (Sequence Count) represents the number
of bits, and here we have 4 bits, so set the SC = 4.
Also, it shows the number of iteration cycles of the
booth's algorithms and then cycles run SC = SC - 1
time.
Qn Qn M = (0111) AC Q Qn SC
M' + 1 =
+1 +1
(1001) &
Operation
1 0 Initial 0000 0011 0 4
Subtract 1001
(M' + 1)
1001
Perform 1100 1001 1 3
Arithmetic
Right Shift
operations
(ashr)
1 1 Perform 1110 0100 1 2
Arithmetic
Right Shift
operations
(ashr)
0 1 Addition (A 0111
+ M)
0101 0100
Perform 0010 1010 0 1
Arithmetic
right shift
operation
0 0 Perform 0001 0101 0 0
Arithmetic
right shift
operation
The numerical example of the Booth's Multiplication
Algorithm is 7 x 3 = 21 and the binary representation of
21 is 10101. Here, we get the resultant in binary
00010101. Now we convert it into decimal, as
(000010101)10 = 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.
ADVERTISEMENT
Example: Multiply the two numbers 23 and -9 by
using the Booth's multiplication algorithm.
Here, M = 23 = (010111) and Q = -9 = (110111)
Qn M=010111 AC Q Qn
M' + 1 = 1 0 1 0 +1
Qn + 1 01
SC
Initially 000000 110111 0
1 Subtract M 101001
0
101001
Perform 110100 111011 1
Arithmetic right
shift operation 5
1 Perform 111010 011101 1
1 Arithmetic right
shift operation 4
1 Perform 111101 001110 1
1 Arithmetic right
shift operation 3
0 Addition (A + M) 010111
1
010100
Perform 001010 000111 0
Arithmetic right
shift operation 2
1 Subtract M 101001
0
110011
Perform 111001 100011 1
Arithmetic right
shift operation 1
1 Perform 111100 110001 1
1 Arithmetic right
shift operation 0
Qn + 1 = 1, it means the output is negative.
Hence, 23 * -9 = 2's complement of 111100110001 =>
(00001100111)
← Prev Next →
For Videos Join Our Youtube
Youtube
Channel: Join Now
Feedback
Send your Feedback to feedback@javatpoint.com
Help Others, Please Share
Learn Latest Tutorials
Splunk tutorial SPSS tutorial
Splunk SPSS
Swagger tutorial T-SQL tutorial
Swagger Transact-SQL
Tumblr tutorial React tutorial
Tumblr ReactJS
Regex tutorial
Regex Reinforcement
Learning
RxJS tutorial
R Programming RxJS
React Native Python Design
Patterns
Python Pillow Python Turtle
Keras tutorial
Keras
Preparation
Aptitude
Aptitude Reasoning
Verbal Ability
Verbal Ability Interview Questions
Company Questions
Trending Technologies
AWS Tutorial
Artificial AWS
Intelligence
Selenium tutorial Cloud Computing
Selenium Cloud Computing
Hadoop tutorial ReactJS Tutorial
Hadoop ReactJS
Data Science Angular 7
Git Tutorial
Blockchain Git
DevOps Tutorial
Machine Learning DevOps
B.Tech / MCA
DBMS tutorial
DBMS Data Structures
DAA tutorial Operating System
DAA Operating System
Computer Network Compiler Design
Computer Discrete
Organization Mathematics
Ethical Hacking
Ethical Hacking Computer Graphics
html tutorial
Software Web Technology
Engineering
Automata Tutorial
Cyber Security Automata
C++ tutorial
C Programming C++
Java tutorial
Java .Net
Python tutorial List of Programs
Python Programs
Control System Data Mining
Data Warehouse
