l07.html

multiplier and divider verilog codes

        bit     = bit - 1;

        <font size="+0" color="#4169e1">if</font>( lsb ) product[31:15] = product[30:15] + abs_multiplicand;

        <font size="+0" color="#4169e1">if</font>( !bit &amp;&amp; multiplicand[15] ^ multiplier[15] ) product = -product;

     <font size="+0" color="#0000cd">end</font>

<font size="+0" color="#000080">endmodule</font>


<font size="+0" color="#b22222">////////////////////////////////////////////////////////////////////////////////
/// </font><font size="+2" color="#000000" face="Arial,Helvetica"><b>Booth Recoding for Higher-Radix and Signed Multiplication</b></font><font size="+0" color="#b22222">
</font>
<font size="+0" color="#b22222">// :PH: 4.6  Only describes Radix-2 Booth Recoding
</font>
 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Basic Idea</b></font><font size="+0" color="#b22222">
//
// Rather than repeatedly adding either 0 or 1 times multiplicand,
// repeatedly add 0, 1, -1, 2, -2, etc. times the multiplicand.
//
</font> <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Benefits</b></font><font size="+0" color="#b22222">
//
// Performs signed multiplication without having to first compute the
// absolute value of the multiplier and multiplicand.
//
// Improved performance (when radix higher than 2).
</font>
 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Multipliers Described Here</b></font><font size="+0" color="#b22222">
//
// Ordinary Radix-4 Unsigned Multiplier
//   Presented for pedagogical reasons, Booth multipliers better.
//   Twice as fast as earlier multipliers.
//   Uses more hardware than Booth multipliers below.
//
// Booth Recoding Radix-4 Multiplier
//   Multiplies signed numbers.
//   Twice as fast as earlier multipliers.
//
// Booth Recoding Radix-2 Multiplier
//   Multiplies signed numbers.
//   Uses about the same amount of hardware than earlier signed multiplier.
</font>

 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Ordinary Radix-4 Multiplier Idea</b></font><font size="+0" color="#b22222">
//
// Review of Radix-2 Multiplication
//
//  Multiply 5 times 12.  Radix-2 multiplication (the usual way).
//
//     0101  Multiplicand
//     1100  Multiplier
//     """"
//     0000  0 x 0101
//    0000   0 x 0101
//   0101    1 x 0101
//  0101     1 x 0101
//  """""""
//  0111100  Product
//
// Radix-4 Multiplication
//   Let "a" denote the multiplicand and b denote the multiplier.
//   Pre-compute 2a and 3a.
//   Examine multiplier two bits at a time (rather than one bit at a time).
//   Based on the value of those bits add 0, a, 2a, or 3a (shifted by
//     the appropriate amount).
//
//   Uses n/2 additions to multiply two n-bit numbers.
//
// Two Radix-4 Multiplication Examples
//
//  Multiply 5 times 12.  Radix-4 multiplication (the faster way).
//
//     Precompute: 2a: 01010,  3a: 01111
//
//     0101  Multiplicand
//     1100  Multiplier
//     """"
//    00000  00 x 0101  
//  01111    11 x 0101
//  """""""
//  0111100  Product
//
//  Multiply 5 times 9.  Radix-4 multiplication (the faster way).
//
//     0101  Multiplicand
//     1001  Multiplier
//     """"
//    00101  01 x 0101
//  01010    10 x 0101
//  """""""
//  0101101  Product
</font>
 <font size="+0" color="#b22222">// Ordinary Radix-2^d Multiplier
//
// This is a generalization of the Radix-4 multiplier.
//
//   Let "a" denote the multiplicand and b denote the multiplier.
//   Pre-compute 2a, 3a, 4a, 5a, ..., (2^d-1)a
//   Examine multiplier d bits at a time.
//   Let the value of those bits be v.
//   Add v shifted by the appropriate amount.
//
//   Uses n/d additions to multiply two n-bit numbers.
</font>

<font size="+0" color="#b22222">// </font><font size="+0" color="#999999">:</font><font size="+0" color="#228b22"><b>Example</b></font><font size="+0" color="#999999">:</font><font size="+0" color="#b22222">
//
// A Radix-4 multiplier.  Takes unsigned numbers.
</font>
<font size="+0" color="#000080">module</font> <font size="+1" color="#000000" face="Arial,Helvetica"><b>imult_ord_radix_4</b></font>(prod,ready,multiplicand,multiplier,start,clk);

   <font size="+0" color="#4169e1">input</font> [15:0]  <font size="+0" color="#b8860b">multiplicand</font>, <font size="+0" color="#b8860b">multiplier</font>;
   <font size="+0" color="#4169e1">input</font>         <font size="+0" color="#b8860b">start</font>, <font size="+0" color="#b8860b">clk</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">prod</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">ready</font>;

   <font size="+0" color="#a020f0">reg</font> [32:0]    <font size="+0" color="#b8860b">product</font>;
   <font size="+0" color="#a020f0">wire</font> [31:0]   <font size="+0" color="#000000"><b>prod </b></font>= product[31:0];

   <font size="+0" color="#a020f0">reg</font> [4:0]     <font size="+0" color="#b8860b">bit</font>; 
   <font size="+0" color="#a020f0">wire</font>          <font size="+0" color="#000000"><b>ready </b></font>= !bit;

   <font size="+0" color="#a020f0">reg</font> [17:0]    <font size="+0" color="#b8860b">pp</font>;
   
   <font size="+0" color="#000080">initial</font> bit = 0;

   <font size="+0" color="#a020f0">wire</font> [17:0]   <font size="+0" color="#000000"><b>multiplicand_X_1 </b></font>= {<font size="+0" color="#999999">1'b</font>0,multiplicand};
   <font size="+0" color="#a020f0">wire</font> [17:0]   <font size="+0" color="#000000"><b>multiplicand_X_2 </b></font>= {multiplicand,<font size="+0" color="#999999">1'b</font>0};
   <font size="+0" color="#a020f0">wire</font> [17:0]   <font size="+0" color="#000000"><b>multiplicand_X_3 </b></font>= multiplicand_X_2 + multiplicand_X_1;

   <font size="+0" color="#000080">always</font> <font size="+0" color="#da70d6">@</font>( <font size="+0" color="#9400d3">posedge</font> clk )

     <font size="+0" color="#4169e1">if</font>( ready &amp;&amp; start ) <font size="+0" color="#0000cd">begin</font>

        bit     = 8;
        product = { <font size="+0" color="#999999">16'd</font>0, multiplier };
        
     <font size="+0" color="#0000cd">end</font> <font size="+0" color="#4169e1">else</font> <font size="+0" color="#4169e1">if</font>( bit ) <font size="+0" color="#0000cd">begin</font>

        <font size="+0" color="#4169e1">case</font> ( {product[1:0]} )
          <font size="+0" color="#999999">2'd</font>0: pp = {<font size="+0" color="#999999">2'b</font>0, product[31:16] };
          <font size="+0" color="#999999">2'd</font>1: pp = {<font size="+0" color="#999999">2'b</font>0, product[31:16] } + multiplicand_X_1;
          <font size="+0" color="#999999">2'd</font>2: pp = {<font size="+0" color="#999999">2'b</font>0, product[31:16] } + multiplicand_X_2;
          <font size="+0" color="#999999">2'd</font>3: pp = {<font size="+0" color="#999999">2'b</font>0, product[31:16] } + multiplicand_X_3;
        <font size="+0" color="#4169e1">endcase</font>

        product = { pp, product[15:2] };
        bit     = bit - 1;

     <font size="+0" color="#0000cd">end</font>

<font size="+0" color="#000080">endmodule</font>


 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Booth Recoding</b></font><font size="+0" color="#b22222">
//
// Goal: Reduce the number of pre-computed multiples of the multiplicand.
// Bonus: Handles signed numbers.
//
// Idea: Use something like carries.
//
// Why It's Called Recoding
//   Numbers like 3 are recoded into 4-1, avoiding the need to deal with 3.
//
// Consider need to compute multiplicand_X_3 for radix-4 multiplier.
// Instead:
//   Subtract multiplicand and add 4 times multiplicand.
//   The subtraction is done in the "current" step.
//   The addition is done in the "next" step.
</font>
<font size="+0" color="#b22222">//  Multiply 5 times 3.  Booth radix-4 multiplication.
//
//     0101  Multiplicand
//     0011  Multiplier
//  """""""
//  1111011  -1      x 0101  Multiplier bits 11 -&gt; -1 + 4 -&gt; -1 now, +1 next step
//  00101     (00+1) x 0101  Multiplier bits 00 -&gt; 0 (now) + 1 (from last step)
//  """""""
//  0001111  Product
</font>

<font size="+0" color="#b22222">// The table below indicates:
//
// MB: Multiplier bits value.
//  C: Carry bit (lostbit in modules) from previous step.
//  x: Amount to multiply multiplicand by.
//  c: Carry bit to next step.
//
// Radix-4 Booth Table
//
//  MB C  |  x      c
//  """""""""""""""""
//  00 0  |  0 + 0  0
//  00 1  |  1 + 0  0
//  01 0  |  1 + 0  0
//  01 1  |  2 + 0  0
//  10 0  | -2 + 4  1
//  10 1  | -1 + 4  1
//  11 0  | -1 + 4  1
//  11 1  |  0 + 4  1
//
// For example above:
// Step 1: MB -&gt; 11,  C -&gt; 0,  lookup reveals  x -&gt; -1,  c -&gt; 1
// Step 2: MB -&gt; 00,  C -&gt; 1,  lookup reveals  x -&gt; 1,  c -&gt; 0
//
// Radix-2 Booth Table
//
//  MB C  |  x      c
//  """""""""""""""""
//  0  0  |  0 + 0  0
//  0  1  |  1 + 0  0
//  1  0  | -1 + 2  1
//  1  1  |  0 + 2  1
</font>

<font size="+0" color="#b22222">// Note:
//  The carry out is the same as the MSB of the multiplier bits examined.
//  That's intentional, so that no special storage or computation is need
//    for the carry.
//
//  The carry out of the last step is not used.
//
//  Construction of higher-radix tables is straightforward.
</font>

<font size="+0" color="#b22222">// </font><font size="+0" color="#999999">:</font><font size="+0" color="#228b22"><b>Example</b></font><font size="+0" color="#999999">:</font><font size="+0" color="#b22222">
//
// A Booth radix-4 multiplier.  This takes signed numbers.
</font>
<font size="+0" color="#000080">module</font> <font size="+1" color="#000000" face="Arial,Helvetica"><b>imult_Booth_radix_4</b></font>(prod,ready,multiplicand,multiplier,start,clk); <font size="+0" color="#b22222">// P
</font>
   <font size="+0" color="#4169e1">input</font> [15:0]  <font size="+0" color="#b8860b">multiplicand</font>, <font size="+0" color="#b8860b">multiplier</font>;
   <font size="+0" color="#4169e1">input</font>         <font size="+0" color="#b8860b">start</font>, <font size="+0" color="#b8860b">clk</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">prod</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">ready</font>;

   <font size="+0" color="#a020f0">reg</font> [32:0]    <font size="+0" color="#b8860b">product</font>;
   <font size="+0" color="#a020f0">wire</font> [31:0]   <font size="+0" color="#000000"><b>prod </b></font>= product[31:0];


   <font size="+0" color="#a020f0">reg</font> [4:0]     <font size="+0" color="#b8860b">bit</font>; 
   <font size="+0" color="#a020f0">wire</font>          <font size="+0" color="#000000"><b>ready </b></font>= !bit;
   <font size="+0" color="#a020f0">reg</font>           <font size="+0" color="#b8860b">lostbit</font>;
   
   <font size="+0" color="#000080">initial</font> bit = 0;

   <font size="+0" color="#a020f0">wire</font> [16:0]   <font size="+0" color="#000000"><b>multsx </b></font>= {multiplicand[15],multiplicand};

   <font size="+0" color="#000080">always</font> <font size="+0" color="#da70d6">@</font>( <font size="+0" color="#9400d3">posedge</font> clk )

     <font size="+0" color="#4169e1">if</font>( ready &amp;&amp; start ) <font size="+0" color="#0000cd">begin</font>

        bit     = 8;
        product = { <font size="+0" color="#999999">17'd</font>0, multiplier };
        lostbit = 0;
        
     <font size="+0" color="#0000cd">end</font> <font size="+0" color="#4169e1">else</font> <font size="+0" color="#4169e1">if</font>( bit ) <font size="+0" color="#0000cd">begin</font>:<font size="+0" color="#3cb371">A</font>

        <font size="+0" color="#4169e1">case</font> ( {product[1:0],lostbit} )
          <font size="+0" color="#999999">3'b</font>001: product[32:16] = product[32:16] + multsx;
          <font size="+0" color="#999999">3'b</font>010: product[32:16] = product[32:16] + multsx;
          <font size="+0" color="#999999">3'b</font>011: product[32:16] = product[32:16] + 2 * multiplicand;
          <font size="+0" color="#999999">3'b</font>100: product[32:16] = product[32:16] - 2 * multiplicand;
          <font size="+0" color="#999999">3'b</font>101: product[32:16] = product[32:16] - multsx;
          <font size="+0" color="#999999">3'b</font>110: product[32:16] = product[32:16] - multsx;
        <font size="+0" color="#4169e1">endcase</font>

        lostbit = product[1];
        product = { product[32], product[32], product[32:2] };
        bit     = bit - 1;

     <font size="+0" color="#0000cd">end</font>

<font size="+0" color="#000080">endmodule</font>


<font size="+0" color="#b22222">// </font><font size="+0" color="#999999">:</font><font size="+0" color="#228b22"><b>Example</b></font><font size="+0" color="#999999">:</font><font size="+0" color="#b22222">