Booth's algorithm part 1

Audio Version available in YouTube Link : www.youtube.com/Aksharam
subscribe the channel

Computer Architecture and Organization
V semester
Anna University
By
Babu M, Assistant Professor
Department of ECE
RMK College of Engineering and Technology
Chennai

1. BOOTH’s ALGORITHM E.g.: Binary Multiplication of two Positive Numbers (+13 X +7)

2. BOOTH’s ALGORITHM Booth's multiplication algorithm  is used to multiply two signed  binary  numbers in  two's complement notation . The algorithm was invented by  Andrew Donald Booth  in 1950. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. It handles both positive and negative multiplier uniformly. Basic Understandings required to learn the topic are: Binary Number Representation Binary Multiplication

3. Explanation with an example Binary Multiplication of two Positive Numbers (+13 X +7) STEP 1: Number Representation Multiplicand + 13 Multiplier + 7 1101 111 Binary Representation 2’s Compliment Representation 01101 00111

4. Binary Multiplication of two Positive Numbers (+13 X +7) STEP 2: Recoding of the Multiplier Multiplier + 7 00111 0 0 1 1 1 Recoded Multiplier Multiplier Multiplicand selected Bit i Bit i-1 0 X Multiplicand 1 +1 X Multiplicand 1 -1 X Multiplicand 1 1 0 X Multiplicand Booth’s Recoding Table i i-1 -1 i i-1 i i-1 +1 i i-1 i i-1

5. Binary Multiplication of two Positive Numbers (+13 X +7) STEP 3: Multiplication Multiplicand 01101 Recoded Multiplier 0+100-1 Note: 1. Multiplication with 0 – 0 (00000) 2. Multiplication with +1 – Multiplicand (01101) 3. Multiplication with -1 – 2’s compliment of Multiplicand (10011) 1 1 1 +1 0 0 -1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

6. Binary Multiplication of two Positive Numbers (+13 X [phone] +13 +7 01101 0+100-1 +13 x +7 1 0 1 1 0 1 1 64 32 16 8 4 2 1 64+16+8+2+1 = 91 +91 STEP 4: Verification