# GATE2006-IT-38

5.4k views

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

1. $2Y$ and $Y$
2. $-2Y$ and $2Y$
3. $-2Y$ and $0$
4. $0$ and $Y$

edited
3

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 !!
1
correct ans is c....
19

Memorize the following table,

(or) understand the logic from the following link:
http://www.geoffknagge.com/fyp/booth.shtml

17

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

1

@blackcloud

How did you get 2-bit Booth code and 3-bit Booth code for this? Please can you elaborate this.

2

@ayushsomani

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

0
it is like step function

It is like sine wave

0 zero

00 one

00 one

000 two

000 -two

00 -one

00 -one

0 zero

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.

edited
21

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 101, 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

thank you @ Puja Mishra

0
same logic @Ayush sir
2

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

0
Can u suggest reference link for this topic?
10
i read from Computer organisation by carl hamechar text book.

http://pages.cs.wisc.edu/~david/courses/cs552/S10/handouts/booth.html
0
what is Y here?
0

@Aspi R Osa  Read the question yaar

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.

## Related questions

1
13.6k views
For each of the four processes $P_1, P_2, P_3,$ and $P_4$. The total size in kilobytes $(KB)$ and the number of segments are given below.$\small \begin{array}{|c|c|c|}\hline \textbf{Process} & \textbf{Total size (in KB)} & \textbf{Number of segments} \\\hline \text{$ ... the above four processes? $\text{P < S < T}$ $\text{S < P < T}$ $\text{S < T < P}$ $\text{T < S < P}$
Consider a Boolean function $f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle$ ... $wx\overline{y} \overline{z}, xz, w\overline{x}yz$ $wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz$
The majority function is a Boolean function $f(x, y, z)$ that takes the value 1 whenever a majority of the variables $x,y,z$ are 1. In the circuit diagram for the majority function shown below, the logic gates for the boxes labeled P and Q are, respectively, XOR, AND XOR, XOR OR, OR OR, AND
The boolean function for a combinational circuit with four inputs is represented by the following Karnaugh map. Which of the product terms given below is an essential prime implicant of the function? $\text{QRS}$ $\text{PQS}$ $\text{PQ'S'}$ $\text{Q'S'}$