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

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.