/// 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

//    0000

//   0101

//  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;

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

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

//the module start to process.

input [15:0]  multiplier, multiplicand;

input         start,clk;

output        product;

reg [4:0]     bit;

reg [31:0]    product;

reg           c;

reg [15:0]    m;

initial bit = 0;

always @( posedge clk )

//initialize

bit = 16;

product[31:16] = 16'd0;

product[15:0] = multiplier;

m = multiplicand;

c = 1'd0;

end else if(bit) begin

//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

end

endmodule

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

//Booth multipliers

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

//

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

input [15:0]  multiplicand, multiplier;

input         start, clk;

output        product;

reg [31:0]    product;

reg [4:0]     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....

//

input [15:0]  multiplicand, multiplier;

input         start, clk;

output        prod;

reg [32:0]    product;

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

reg [3:0]     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:

input [14:0]  multiplicand, multiplier;

input         start, clk;

output        prod;

reg [31:0]    product;

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

reg [2:0]     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

//

input [31:0]  dividend;

input [15:0]  divisor;

input         start, clk;

output [15:0] quotient,remainder;

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

req           c;

quotient =  q;

remainder = r;

reg [4:0]     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

end

bit = bit - 1;

end

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

endmodule