Question

Booth’s Algorithm for integer multiplication gives best performance when the multiplier pattern is

1.   01110111
2.   10101010
3.   00100011

Comments

1.   01110111  give same as 3
2.   10101010 gives worst
3.   00100011 give same as 1

---

How did u calculate?

---

the one which contains less number of 01 or 10 will perform better. hence 3 will give worst performance. because when 00 or 11 pairs are encountered, no addition/subtraction will be performed. but when 01 occurs one add operation and when 10 occurs one subtraction will be performed.

Both 1 and 3 will require 4 arithmetic operations.

---

when # of arthemetic operations are equal then performance will depend on shift operations,

1st has 14 shift operations, wheras 3rd has 13 shift operations, therfore 3rd is somewhat faster than 1st

Answer 1

....

Comments

@hira

suppose we have to find the booth code for (154)10

then what will be the number of shift operations here

because we willc onvert (154)10 as 128  64 32 16 8 4 2 1

                                                           -1 0 +1 0 -1 +1 -1 0

here we will add 128+ 32 + 8 +4 +2  or  take like the above example as

                             1+2+3+5+7 ?

---

A_i_$_h  suppose if booth recording like  0 +1 0 0 0 0 0 -1 then number of shifting : 2⁶ ,2⁰ (6+0)=6,add the value of 2ⁿ add the n values

---

@hira

Is number of shift operations for (154)₁₀= 13 or 18?

---

 see this

---

thank you :)

---

you mean for 0 no ASR performed ryt?

http://www.studytonight.com/computer-architecture/booth-multiplication-algorithm

https://courses.cs.washington.edu/courses/cse378/00sp/Sec5-1.htm

both link saying ASR is perfomed for 00,10,11 and 01

---

@Hira Thakur please provide reference to no of shift operations. 

As per given in Wikipedia, we have to perform shift operations on every occurence of $00,01,10,11$.

---

The booth coding seems to be wrong . since on booth coding to decimal conversion( multiplying with 2^n)

I am getting (-1)*128+(0)*64+(+1)*32+(0)*16+(-1)*8+(+1)*4+(-1)*2+(0)*1= -102

I think this is due to not including the sign bit for booth coding ,when we use that,the booth code becomes

+1-10+10-1+1-10

which on decimal conversion gives 154.Then total shift operations = 26

Please correct me if I am wrong.