/// 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 = 1b0;

       

 

     end else if(bit) begin

        //1-st cycle;

         if(bit == 16 ) begin

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

                  {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],1b0};

                        {c,r} = r + b;

                        q[0] =c;

                       end

             else     begin

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

                        {c,r} = r- b;

                        q[0] =c;

                      end;

         end

                

        end

 

       

        bit = bit - 1;

 

     end

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

       

endmodule