BOOTH’S ALGORITHM, DIVISION

AND LOGIC OPERATIONS

BOOTH’S ALGORITHM
 Introduction
• The algorithm was invented by Andrew Donald Booth in 1950 while doing research

Saturday, May 24, 2025

on crystallography at Birkbeck College in Bloomsbury, London.

3
Left: Andrew Donald Booth; Right: Birkbeck College, Bloomsbury, London.
• Booth algorithm provides the procedure of multiplication of binary integers with 2's
complement representation, hence the number of additions and subtractions is

Saturday, May 24, 2025

reduced.

• If there would be more blocks of 1's and 0's booth will work great.

• It will require more calculation if there would be more multiples.

4
 Hardware Implementation
• The multiplicand is stored in BR register; forming each partial product.

Saturday, May 24, 2025

the multiplier is stored in QR register.
• When the content of the counter reaches
• AC is a register of the same size as the size zero, the product is formed and the
of the multiplier. process stops.

• Final product will be stored in AC and QR

register.

• The sequence counter SC is initially set to

a number equal to the number of bits in
the multiplier.
5
• The counter is decremented by 1 after
• Qn shows the least significant bit of the multiplier in register QR.

Saturday, May 24, 2025

• An extra flip-flop Qn+1 is appended to QR to facilitate a double bit inspection of the
multiplier.

6
 Flow Chart
• AC and the appended bit Qn+1 are that the first 0 in a string of 0’s have been
initially set to 0. encountered. This requires the addition

Saturday, May 24, 2025

of the multiplicand to the partial product
in AC.
• The sequence counter SC is set to a ―When the two bits are equal, the partial
number n equal to the number of bits in product does not change.
the multiplier.
• The next step is to shift right the partial
• The two bits of the multiplier in Qn and product and the multiplier (including bit
Qn+1 are inspected. Qn+1).
―If the two bits are equal to 10, it means
that the first 1 in a string of 1’s has been • The SC is decremented and the
encountered. This requires a subtraction computational loop is repeated n times.
of the multiplicand from the partial
product in AC. 7
―If the two bits are equal to 01, it means
 Saturday, May 24, 2025
8
Example: Multiply the two numbers 23 and -9 by using the Booth's multiplication
algorithm.
Ans.

Saturday, May 24, 2025

9
Qn + 1 = 1, it means the output is negative.
Hence, 23 *(-9) = 2's complement of 111100110001 => (00001100111)
• Best Case and Worst Case Occurrence:
i. Best case is when there is a large block of consecutive 1’s and 0’s in the multipliers, so

Saturday, May 24, 2025

that there is minimum number of logical operations taking place, as in addition and
subtraction.
ii. Worst case is when there are pairs of alternate 0’s and 1’s, either 01 or 10 in the
multipliers, so that maximum number of additions and subtractions are required.

• Advantages of booth's multiplication:

i. Easy calculation of multiplication problem.
ii. Consecutive additions will be replaced.
iii. Less complex and ease in scaling.
• Disadvantages of booth's multiplication:
i. This algorithm will not work on alternate pair of 0’s and 1’s. (Worst Case)
ii. It is time consuming.
10
iii. If digital gates are more, chip area would be large.
DIVISION ALGORITHM
 Introduction

Saturday, May 24, 2025

• The division algorithm is generally of two types which is
i. Fast Division Algorithm - Goldschmidt and Newton-Raphson.
ii. Slow Division Algorithm - STR algorithm, Restoring algorithm, Non-
Performing algorithm, and the Non-Restoring Algorithm.

• Here, we will discuss the slow division algorithm namely:

i. Restoring Algorithm
ii. Non-Restoring Algorithm

12
 Restoring Division Algorithm
• Step 1: The corresponding value will be • Step 4: Now, check the most significant
initialized to the registers, i.e., register A bit of register A.

Saturday, May 24, 2025

= 0, register M = Divisor, register Q = ―If this bit of register A is 0, then the least
Dividend, and N = number of bits in the significant bit of register Q will be set with
dividend. a value 1.

• Step 2: In this step, registers A and Q, will ―If the most significant bit of A is 1, then
the least significant bit of register Q will
be treated as a single unit, and the value
be set to with value 0, and restore the
of both the registers will be shifted left.
value of A that means it will restore the
value of register A before subtraction with
• Step 3: After that, the value of register M M.
will be subtracted from register A. The
result of subtraction will be stored in • Step 5: After that, the value of n will be
register A. decremented. Here n is used as a counter. 13
• Step 6: Now, if the value of n is 0, we will
break the loop. Otherwise, we have to

Saturday, May 24, 2025

again go to step 2.

• Step 7: This is the last step. In this step,

the quotient is contained in the register
Q, and the remainder is contained in
register A.

14
 Non-Restoring Division Algorithm
• Step 1: The corresponding value will be into left and perform AC = AC - M.
initialized to the registers, i.e., register A

Saturday, May 24, 2025

= 0, register M = Divisor, register Q = ―That means in case of 0, the 2's
Dividend, and N = number of bits in the complement of M is added into register
dividend. A, and the result is stored into A.

• Step 2: In this step, we will check the • Step 4: Now, we will check the sign bit of
sign bit of A. A again.

• Step 3: The scenarios for this step are: • Step 5: If this bit of register A is 1, then
―If this bit of register A is 1, then shift the Q[0] will become 0. If this bit is 0, then
value of AQ through left, and perform AC Q[0] will become 1. Here Q[0] indicates
= AC + M. the least significant bit of Q.
15
―If this bit is 0, then shift the value of AQ
• Step 6: After that, the value of N will be
decremented. Here N is used as a
counter.

Saturday, May 24, 2025

• Step 7: If the value of N = 0, then we will
go to the next step. Otherwise, we have
to again go to step 2.

• Step 8: We will perform AC = AC + M if

the sign bit of register A is 1.

• Step 9: This is the last step. In this step,

register A contains the remainder, and
register Q contains the quotient.
16
• Example: Dividend = 11, Divisor = 3 and -M = 11101.

Saturday, May 24, 2025

17
KEY POINTS
• As per the paper ‘Comparative Study of Different Division Algorithms for Fixed and
Floating Point Arithmetic Unit for Embedded Applications’, the advantages and
limitations of the division algorithms is as follows:

Saturday, May 24, 2025

19
 Logic Microoperation

02/13/14 20
 Logic Operation
• Logic Microoperations specify binary operations for strings of bits
stored in registers.
• These operations consider each bit of the register separately and
treat them as binary variables.
• For example
P: R1  R1 R2 +
• It specifies a logic microoperation to be executed on the individual
bits of the registers provided that the control variable P = 1.

02/13/14 21
 Logic Operation
• The Exclusive-OR microoperation stated above symbolizes the
following logic computation :

1010 content of R1
1100 content of R2
0110 content of R1 after P = 1
• The logic microoperations are seldom used in scientific
computations, but they are very useful for bit manipulation of
binary data and making logical decisions.

02/13/14 22
 Logic Operation
• Special Symbol

Logic Microoperations are:

OR V
AND ˄
NOT ¯
Add operation

P + Q: R1  R2 + R3, R4  R5 V R6
+ --- OR Operation in Control Function OR Operation

02/13/14 23
 List of Logic Microoperations
F10 F11 F12 F13 F14 F15
x y F0 F F2 F3 F4 F5 F6 F7 F8 F9
1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

02/13/14 24
 Logic Microoperations
Boolean Function Microoperation Name
F0 = 0 F0 Clear
F1 = xy F A˄ B AND
F2 = xy` F A˄ B
F3 = x FA Transfer A
F4 = x`y FA ˄B
F5 = y FB Transfer B
+ +
F6 = x y FA B Exclusive-OR

02/13/14 25
 Logic Microoperations
Boolean Function Microoperation Name
F7 = x + y F  AV B OR
F8 = (x + y)` F  AV B NOR
F9 = (x y+)` FA B+ Exclusive-NOR
F10 = y` FB Complement B
F11 = x + y` F  AV B
F12 = x` FA Complement A
F13 = x` + y F  AV B
02/13/14 26
 Logic Microoperations
Boolean Function Microoperation Name

F14 = (xy)` F  A˄B NAND

F15 = 1 F  all 1’s Set to all 1’s

02/13/14 27
 Hardware Implementation
• The hardware implementation of logic microoperations requires
that logic gates be inserted for each bit or pair of bits in the
registers to perform the required logic function.
• Although there are 16 logic microoperations, most computers use
only four – AND, OR, XOR , and complement – from which all
others can be derived.

02/13/14 28
 Hardware Implementation

S1
S0 S1 S0 Output Operation
0 0 E=A˄B AND
0 1 E=AVB OR
Ai
4 X 1 MUX Ei 1 0 E=A B +
EX-OR
0
Bi 1 1 E =A Complement

OR 1

EX-OR 2
3
NOT

02/13/14 29
 Hardware Implementation
SOME APPLICATIONS
• Useful for manipulating individual bits or a portion of a word stored in a register.
• They can be used to change bit values, delete a group of bits,or insert new bit
values into a register.
• The following examples show how the bits of one register (designated by A) are
manipulated by logic microoperation as a function of the bits if another register
(designated by B)
• Selective-Set
• The selective-set operation sets to 1 the bits in register A where there are
corresponding 1’s in register B. It does not affects bit positions that have 0’s in B.

02/13/14 30
 Selective-Set

1010 A before
1100 B (logic operand)
---------------
1110 A after
*** Therefore , the OR microoperation can be used to selectively set bits of a register.

02/13/14 31
 Selective-Complement
• The Selective-Complement operation complements bits in A where
there are corresponding 1’s in B.It does not effects bit positions that
have 0’s in B.

1010 A before
1100 B (logic operand)
--------
0110 A after
Therefore, exclusive-OR microoperation can be used to selective
complements bits of a register.
02/13/14 32
 Selective-Clear
• The Selective-clear operation clears to 0 the bits in A only where there
are corresponding 1’s in B.

1010 A before
1100 B (logic operand)
-------
0010 A after
The corresponding logic microoperation is
A  A ˄ B or AB`
02/13/14 33
 Mask
• The Mask operation is similar to the selective-clear operation except
that bits of A cleared only where there are corresponding 0’s in B.

1010 A before
1100 B (logic operand)
-------
1000 A after masking
The mask operation is an AND operation .

02/13/14 34
 INSERT
• The insert operation inserts a new value into a group of bits.
• This is done by first masking the bits and then ORing them with the
required value.

0110 1010 A before

0000 1111 B (mask)
----------------
0000 1010 A after masking

02/13/14 35
 INSERT
• and then Insert new value

0000 1010 A before

1001 0000 B (insert)
-----------------
1001 1010 A after insertion
The mask operation is an AND operation and the insert operation is an
OR microoperation.

02/13/14 36
 Clear
• The clear operation compares the words in A and B and produces an all
0’s result if the two numbers are equal.
1010 A
1010 B
--------
0000 A  A B
+

02/13/14 37
 Shift Microoperations
• Shift microoperations are used for serial transfer of a data.
• They can also used in conjunction with arithmetic, logic, and other
data processing operations.
• The contents of a register can be shifted to the left or right.
• At the same time that the bits are shifted, the first flip-flop receives its
binary information from the serial input.
• During a shift-left operation the serial input transfers a bit into the
right most position.

02/13/14 38
 Shift Microoperations
• During a shift-right operation the serial input transfer a bit into the
leftmost position.
• The information transferred through the serial input determines the
types of shift operation.
• There are three types of shift operations :

a. Logical
b. Circular
c. Arithmetic

02/13/14 39
 Shift Microoperations
Smbolic Designation Description
R  shl R Shift-left register R
R  shr R shift-right register R
R  cil R Circular shif-left reg. R
R  cir R Circular shift-right reg. R
R  ashl R arithmetic shift-left R
R  ashr R arithmetic shift-right R

02/13/14 40
 4-bit combinational circuit shifter
Serial Input Select
(IR)
M1 H0 Select
A0
0 for shift
A1 right (down)
M2 H1
A2 1 for shift left
(up)
A3
M3 H2

Serial Input M4 H3
(IL)

02/13/14 41
 Function Table
• Select Output
S H0 H1 H2 H3
0 IR A0 A1 A2
1 A1 A2 A3 IL

02/13/14 42
 Arithmetic Logic Shift Unit
Ci S2 S3
S1 Di
One Stage of
S0 arithmetic circuit

Ci+1 4X1 Fi
Mux
Ei
One Stage of
Bi Logic circuit
Ai
shr
Ai-1
shl
Ai+1
02/13/14 43
 Arithmetic Logic Shift Unit
Operation Select
S3 S2 S1 S0 Cin Operation Description
0 0 0 0 0 F=A Transfer A
0 0 0 0 1 F=A+1 Increment A
0 0 0 1 0 F=A+B Addition
0 0 0 1 1 F=A+B+1 Add With Carry
0 0 1 0 0 F=A+B Subtract with borrow
0 0 1 0 1 F=A+B+1 Subtraction
0 0 1 1 0 F=A-1 Decrement A

02/13/14 44
 Arithmetic Logic Shift Unit
Operation Select
S3 S2 S1 S0 Cin Operation Description
0 0 1 1 1 F=A Transfer A
0 1 0 0 X F=A^B AND
0 1 0 1 X F=AVB OR
0 1 1 0 X F=A B XOR +
0 1 1 1 X F=A Complements A
1 0 X X X F=shr A Shift right A into F
1 1 X X X F=shl A Shift left A into F
02/13/14 45
 PROBLEMS
1. Show the block diagram of the hardware that implements the
following register transfer statement:
yT2 : R2 ← R1 , R1 ← R2

2. Represent the following conditional control statement by two

Register transfer statements with control functions.
If (P=1) then (R1 ← R2) else if (Q=1) then (R1 ← R3)
3. Draw the block diagram for the hardware that implements
the following statements:
x+yz : AR ← AR + BR
where AR and BR are two n-bit registers and x,y and z are
control variables.
 THANK YOU!!

Saturday, May 24, 2025

47