/// 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;
//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
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
end
bit
= bit - 1;
end
if(c
== 0) {c,r} = r+b;//restore..
endmodule