/// LSU EE 3755 --- Computer Organization

/// LSU EE 3755 --- Fall 2009 Computer Organization

/// Verilog Notes 9 -- Integer Multiply and Divide

/// Contents

// Unsigned multiplication

// Booth Algorithm

// Division

/// References

// :P: Palnitkar, "Verilog HDL"

// :Q: Qualis, "Verilog HDL Quick Reference Card Revision 1.0"

// :PH: Patterson & Hennessy, "Computer Organization & Design"

////////////////////////////////////////////////////////////////////////////////

/// Unsigned multiplication

/// Long Hand Procedure Review

// Multiply 5 times 12 in binary:

// 0101 Multiplicand

// 1100 Multiplier

// """"

// 0000

// 0101

// """""""

// 0111100 Product

// :Example:

// Simple Unsigned Combinational Multiplier

// This is a straightforward coding of the longhand multiplication

// technique.

module simple_combinational_mult(product,multiplier,multiplicand);

input [15:0] multiplier, multiplicand;

output product;

reg [31:0] product;

integer i;

always @( multiplier or multiplicand )

begin

product = 0;

for(i=0; i<16; i=i+1)

if( multiplier[i] == 1'b1 ) product = product + ( multiplicand <<

i );

end

endmodule

////////////////////////////////////////////////////////////////////////////////

// Two modules below implement add/shift algorithm

//(it is called the sequential add/shift algorithm at our notes)

// for unsigned multiplication(presented in class).

// Cycles usually mean clock cycles.

// but cycles at our notes mean steps.

// Module below is combinational multiplier

// It implements add/shift algorithm without clock.

// Combinational multiplier produces result immediately

//(without any time delay)

// Sequential multiplier produces result after certain

// number of clock cycles(actual time depends on clock period).

module combinational_mult(product,multiplier,multiplicand);

input [15:0] multiplier, multiplicand;

output product;

reg [31:0] product;

reg c;

reg [15:0] m;

integer i;

always @( multiplier or multiplicand )

begin

//initialize

product[31:16] = 16'd0;

product[15:0] = multiplier;

m = multiplicand;

c = 1'd0;

//add,shift algorithm for unsigned multiplication.

//following the notes.

for(i=0; i<16; i=i+1)

begin

if(product[0])

begin

{c,product[31:16]} = product[31:16] + m ;

//shift

product[31:0] = {c,product[31:1]};

c = 0;

end

else

begin

product[31:0] = {c,product[31:1]};

c = 0;

end

//better way of doing is....

// if(product[0]) {c,product[31:16]} = product[31:16] + m ;

// product[31:0] = {c,product[31:1]};

// c = 0;

end //end of for loop..

end

endmodule

//Module below is sequetial multiplier.

//Handshaking signals are added to command

//multiplier to start and to indicate when finished.

//ready is an output of the module which tells the module is not busy,

//ready to accept inputs.

//start is an input signal to the module which tells

//the module start to process.

module sequential_mult(product,ready,multiplier,multiplicand,start,clk);

input [15:0] multiplier, multiplicand;

input start,clk;

output product;

output ready;

reg [4:0] bit;

wire ready = !bit;

reg [31:0] product;

reg c;

reg [15:0] m;

initial bit = 0;

always @( posedge clk )

if( ready && start) begin

//initialize

bit = 16;

product[31:16] = 16'd0;

product[15:0] = multiplier;

m = multiplicand;

c = 1'd0;

end else if(bit) begin

//add,shift algorithm for unsigned multiplication.

//following the notes.

if(product[0])

begin

{c,product[31:16]} = product[31:16] + m ;

//shift

product[31:0] = {c,product[31:1]};

c = 0;

end

else

begin

product[31:0] = {c,product[31:1]};

c = 0;

end

//better way of doing is....

// if(product[0]) {c,product[31:16]} = product[31:16] + m ;

// product[31:0] = {c,product[31:1]};

// c = 0;

bit = bit -1;

end

endmodule

////////////////////////////////////////////////////////////////////////////////

//Booth multipliers

//We will present two bits, three bits, and four bits examination.

////////////////////////////////////////////////////////////////////////////////

module two_bits_Booth(product,ready,multiplicand,multiplier,start,clk);

input [15:0] multiplicand, multiplier;

input start, clk;

output product;

output ready;

reg [31:0] product;

reg [4:0] bit;

wire ready = !bit;

reg d;

initial bit = 0;

always @( posedge clk )

if( ready && start ) begin

bit = 16;

product = { 16'd0, multiplier };

d = 0;

end else if( bit ) begin

case ( {product[0],d} )

2'b01: product[31:16] = product[31:16] + multiplicand;

2'b10: product[31:16] = product[31:16] - multiplicand;

endcase

d = product[0];

product = { product[31], product[31:1] };

bit = bit - 1;

end

endmodule

//examing three bits booth....

module three_bit_Booth(prod,ready,multiplicand,multiplier,start,clk);

input [15:0] multiplicand, multiplier;

input start, clk;

output prod;

output ready;

reg [32:0] product;

wire [31:0] prod = product[31:0];

reg [3:0] bit;

wire ready = !bit;

reg d;

initial bit = 0;

wire [16:0] multsx = {multiplicand[15],multiplicand};

always @( posedge clk )

if( ready && start ) begin

bit = 8;

product = { 17'd0, multiplier };

d = 0;

end else if( bit ) begin

case ( {product[1:0],d} )

3'b001: product[32:16] = product[32:16] + multsx;

3'b010: product[32:16] = product[32:16] + multsx;

3'b011: product[32:16] = product[32:16] + 2 * multiplicand;

3'b100: product[32:16] = product[32:16] - 2 * multiplicand;

3'b101: product[32:16] = product[32:16] - multsx;

3'b110: product[32:16] = product[32:16] - multsx;

endcase

d = product[1];

product = { product[32], product[32], product[32:2] };

bit = bit - 1;

end

endmodule

//examing four bits..

// :Example:

module four_bit_Booth(prod,ready,multiplicand,multiplier,start,clk);

input [14:0] multiplicand, multiplier;

input start, clk;

output prod;

output ready;

reg [31:0] product;

wire [29:0] prod = product[29:0];

reg [2:0] bit;

wire ready = !bit;

reg d;

initial bit = 0;

wire [16:0] multsx = {multiplicand[14], multiplicand[14],multiplicand};

wire [16:0] multsx2 = {multiplicand[14], multiplicand,1'd0};

always @( posedge clk )

if( ready && start ) begin

bit = 5;

product = { 17'd0, multiplier };

d = 0;

end else if( bit ) begin

case ( {product[2:0],d} )

4'b0001: product[31:15] = product[31:15] + multsx;

4'b0010: product[31:15] = product[31:15] + multsx;

4'b0011: product[31:15] = product[31:15] + multsx2;

4'b0100: product[31:15] = product[31:15] + multsx2;

4'b0101: product[31:15] = product[31:15] + 3 * multiplicand;

4'b0110: product[31:15] = product[31:15] + 3 * multiplicand;

4'b0111: product[31:15] = product[31:15] + 4 * multiplicand;

4'b1000: product[31:15] = product[31:15] - 4 * multiplicand;

4'b1001: product[31:15] = product[31:15] – 3 * multiplicand;

4'b1010: product[31:15] = product[31:15] - 3 * multiplicand;

4'b1011: product[31:15] = product[31:15] – multsx2;

4'b1100: product[31:15] = product[31:15] – multsx2;

4'b1101: product[31:15] = product[31:15] - multsx;

4'b1110: product[31:15] = product[31:15] - multsx;

endcase

d = product[2];

product = { product[31], product[31], product[31], product[31:3]};

bit = bit - 1;

end

endmodule

////////////////////////////////////////////////////////////////////////////////

/// Division

// Module below shows the division algorithm presented in class

module seq_divider(quotient,remainder,ready,dividend,divisor,start,clk);

input [31:0] dividend;

input [15:0] divisor;

input start, clk;

output [15:0] quotient,remainder;

output ready;

reg [15:0] b,r,q;

req c;

quotient = q;

remainder = r;

reg [4:0] bit;

wire ready = !bit;

initial bit = 0;

always @( posedge clk )

if( ready && start ) begin

bit = 16;

//initialization;

b = divisor;

{r,q} = dividend;

c = 1’b0;

end else if(bit) begin

//1-st cycle;

if(bit == 16 ) begin

{r,q}={r[14:0],q[15:0],1’b0};

{c,r} = r- b;

q[0] =c;

end

//repeat n-1(15) times

else begin

if(c==0) begin

{r,q}={r[14:0],q[15:0],1’b0};

{c,r} = r + b;

q[0] =c;

end

else begin

{r,q}={r[14:0],q[15:0],1’b0};

{c,r} = r- b;

q[0] =c;

end;

end

bit = bit - 1;

end

if(c == 0) {c,r} = r+b;//restore..

endmodule