Why have here been given three columns X(i+1), X(i) and X(i-1) .we recode using just two bits in Booth's algo !!

The Gateway to Computer Science Excellence

+24 votes

When multiplicand $Y$ is multiplied by multiplier $X = x_{n - 1}x_{n-2} \dots x_0$ using bit-pair recoding in Booth's algorithm, partial products are generated according to the following table.

$${\begin{array}{c|ccc|c}\hline

\textbf{Row}& \bf{ x_{i+1}}&\bf { x_i}&\bf{ x_{i-1}}& \textbf{Partial Product} \\\hline

1&0&0&0&0 \\ 2&0&0&1& \text{Y} \\ 3&0&1&0& \text{Y} \\ 4&0&1&1& \text{2Y} \\ 5&1&0&0& \text{?} \\ 6&1&0&1& \text{-Y} \\ 7&1&1&0& \text{-Y} \\ 8&1&1&1& \text{?} \\ \hline

\end{array}}$$

The partial products for rows $5$ and $8$ are

- $2Y$ and $Y$
- $-2Y$ and $2Y$
- $-2Y$ and $0$
- $0$ and $Y$

+1

Somebody answer this question please !!

Why have here been given three columns X(i+1), X(i) and X(i-1) .we recode using just two bits in Booth's algo !!

Why have here been given three columns X(i+1), X(i) and X(i-1) .we recode using just two bits in Booth's algo !!

+14

Memorize the following table,

(or) understand the logic from the following link:

http://www.geoffknagge.com/fyp/booth.shtml

**Answer is (C).**

+4

**no need to remember the table...**

**here's the logic simplified==>**

just 1 example is enough..

lets take 101

check pairs consecutively

we have 10 and 01.

do (right bit - left bit) for each pair

meaning (0-1) and (1-0) i.e. -1 and 1

now interpret -1,1 as a weighted binary number

i.e. -1*2^1 + 1*2^0 = -2+1 = -1

check table 101 is -1

now multiply Y ..๐๐ป๐๐ป

**generalising----------**

1 bit recording for 1010 is (0-1)(1-0)(0-1) i.e. -11-1

2 bit recording for 1010 is -11

3 bit recording for 1010 is -3

0

as far as i know there is no such use of 3 bit code...but you can generalize this..

for 1010 1 bit code is -11-1

for 2 bit we take 3 bit at a time ...i.e. 101 and 010

101 means -11 and using weighted power its

-1*2^1 + 1*2^0= -1

similarly 010 is 1-1 i.e. 1

so 2 bit recording is -11

for 3 bit we take 4 bit at a time .. 1010

-11-1 now again weighted power..

-1*4+1*2+(-1)*1 = -4+2-1 = -3

+6 votes

Best answer

We can have 1 bit or 2 bit Booth codes. This question is about 2 bit Booth codes. In Booth's algorithm, we get partial products by multiplying specific codes with the multiplicand. These partial products are used to get the actual product. We initially calculate 2 bit booth code of the multiplier in this question. Then each bit of the code is multiplied with the multiplicand to get the partial product as shown in the last column of the given table.

Here, multiplicand is Y. So, notice that each row of partial product column is multiplied with Y.

Now, the question is how to get these codes i.e., how to represent a multiplier with 2 bit booth code. For that we need to look at the pair of 3 bits as shown in the table below. To get code Ci, look for 3 bits as shown.

$${\begin{array}{ccc|c}

\bf{x_{i+1}}& \bf{x_i}& \bf{x_{i+1}}&\bf{ Booth code (C_i)}\\\hline

0&0&0&0 \\ 0&0&1&1 \\ 0&1&0&1 \\ 0&1&1&2\\ 1&0&0&-2\\ 1&0&1&-1 \\ 1&1&0&- 1 \\ 1&1&1&0\\

\end{array}}$$

Now, multiply ith code to get partial product.

Therefore, Option C is correct.

Here, multiplicand is Y. So, notice that each row of partial product column is multiplied with Y.

Now, the question is how to get these codes i.e., how to represent a multiplier with 2 bit booth code. For that we need to look at the pair of 3 bits as shown in the table below. To get code Ci, look for 3 bits as shown.

$${\begin{array}{ccc|c}

\bf{x_{i+1}}& \bf{x_i}& \bf{x_{i+1}}&\bf{ Booth code (C_i)}\\\hline

0&0&0&0 \\ 0&0&1&1 \\ 0&1&0&1 \\ 0&1&1&2\\ 1&0&0&-2\\ 1&0&1&-1 \\ 1&1&0&- 1 \\ 1&1&1&0\\

\end{array}}$$

Now, multiply ith code to get partial product.

Therefore, Option C is correct.

+11

I found a logical coherence between the values in table

if value is 000, partial product is 0

if value is 001 partial product is Y

if value is 010 partial product is Y

So similarly if value is 101, value is -Y, we can think of leftmost bit as sign bit and when it's 1, we complement rest of bits and check their partial product

like for **1**01, MSB is 1, so I do complement I get 010 and its PP is Y, so for value 101 PP is -Y.

and similarly for 111, on complementing we get 000, for which PP is 0, so for 111 PP is 0.

0

http://pages.cs.wisc.edu/~david/courses/cs552/S10/handouts/booth.html for more and correct logic check here

+11 votes

Partial product is calculated by using bit pair recording in booths algorithm, which is improvement technique used in booths algorithm. Here we consider 3 bits at a time for getting the partial product. This eliminates the worst case behaviour of normal Booth's algorithm. Partial Product calculation can be seen in the below link:

http://www.geoffknagge.com/fyp/booth.shtml

"100" corresponds to -2M and "111" corresponds to 0

-2 X(i+1) + x (i) + X(i-1)

ANS : C

+9

i read from Computer organisation by carl hamechar text book.

it may help you.

http://pages.cs.wisc.edu/~david/courses/cs552/S10/handouts/booth.html

it may help you.

http://pages.cs.wisc.edu/~david/courses/cs552/S10/handouts/booth.html

0 votes

Please refer to this, it will help you.

https://www.techtud.com/short-notes/basics-booths-multiplication-booth-re-coding

In the given question they just want to know how you are decoding a three-bit number. In each row from the right-hand side, you take three bits and decode it in booth multiplier form(2's complement number) and simply find the weighted decimal equivalent of booth multiplier.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,405 comments

105,169 users