///
LSU EE 3755 --- 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