3.6 BOOTH MULTIPLIER

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.

Booth algorithm gives a procedure for multiplying binary integers in signed –2’s complement representation.
Step 1: 

Making the Booth table

I. From the two numbers, pick the number with the smallest difference between a series of consecutive numbers, and make it a multiplier.

II. Let X is multiplier, Let Y is multiplicand and take the 2’s complement of Y and call it –Y

III. Load the X value in the table.

IV. Load 0 for X-1 value it should be the previous first least significant bit of X

V. Load 0 in U and V rows which will have the product of X and Y at the end of Operation.

VI. Make four rows for each cycle; this is because we are multiplying four bits
Numbers.

Step 2: 

Booth Algorithm

Booth algorithm requires examination of the multiplier bits, and shifting of the partial product. Prior to the shifting, the multiplicand m a y be added to partial product, subtracted from the partial product, or left unchanged according to the following rules: Look at the first least significant bits of the multiplier “X”, and the previous least significant bits of the multiplier “X - 1”.

0 0  Shift only
1 1  Shift only

0 1 Add Y to U, and shift
1 0 Subtract Y from U, and shift or add (-Y) to U and shift

II Take U & V together and shift arithmetic right shift which preserves the sign bit of 2’s complement number. Thus a positive number remains positive, and a negative number remains negative.

III Shift X circular right shift because this will prevent us from using two registers for the X value.

For designing this algorithm we can use any adders which are discussed above.

 

 DIAGRAM:


PROGRAM:

MAIN:
 

module booth(prod, busy, mc, mp, clk, start);

output [15:0] prod;

output busy;

input [7:0] mc, mp;

input clk, start;

reg [7:0] A, Q, M;

reg Q_1;

reg [3:0] count;

wire [7:0] sum, difference;

always @(posedge clk)

begin

if (start)

begin A <= 8'b0;

M <= mc;

Q <= mp;

Q_1 <= 1'b0;

count <= 4'b0;

end

else

begin

case ({Q[0], Q_1})

2'b0_1 : {A, Q, Q_1} <= {sum[7], sum, Q};

2'b1_0 : {A, Q, Q_1} <= {difference[7], difference, Q};

default: {A, Q, Q_1} <= {A[7], A, Q};

endcase count <= count + 1'b1;

end

end

adder8 adder (sum, A, M, 1'b0);

adder8 subtracter (difference, A, ~M, 1'b1);

assign prod = {A, Q};

assign busy = (count < 8);

endmodule