l07.html

multiplier and divider verilog codes

//
// Radix-2 Booth multiplier.  Unlike signed multiplier, does not
// require time or hardware for taking absolute value of operands.
</font>
<font size="+0" color="#000080">module</font> <font size="+1" color="#000000" face="Arial,Helvetica"><b>imult_Booth</b></font>(product,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">product</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">ready</font>;

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

   <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="#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     = 16;
        product = { <font size="+0" color="#999999">16'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[0],lostbit} )
          <font size="+0" color="#999999">2'b</font>01: product[31:16] = product[31:16] + multiplicand;
          <font size="+0" color="#999999">2'b</font>10: product[31:16] = product[31:16] - multiplicand;
        <font size="+0" color="#4169e1">endcase</font>

        lostbit = product[0];
        product = { product[31], product[31:1] };
        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="+2" color="#000000" face="Arial,Helvetica"><b>Binary Division Algorithm</b></font><font size="+0" color="#b22222">
</font>
<font size="+0" color="#b22222">// :PH: 4.7
</font>
<font size="+0" color="#b22222">// Binary Version of Longhand Division Technique
//
// 11 divided by 3:
//
// 11 (1011) is dividend.
//  3 (0011) is divider.
//
//  """"""""|
//     1011 |
// -0011    |
//  """"""""|    0  Difference is negative: copy dividend and put 0 in quotient.
//     1011 |
//  -0011   |
//  """"""""|   00  Difference is negative: copy dividend and put 0 in quotient.
//     1011 |
//   -0011  |
//  """"""""|  001  Difference is positive: use difference and put 1 in quotient.
//     0101 |
//    -0011 |
//  """"""""| 0011  Difference is positive: use difference and put 1 in quotient.
//       10 | 
//
// Quotient, 3 (0011); remainder 2 (10).
</font>

<font size="+0" color="#b22222">////////////////////////////////////////////////////////////////////////////////
/// </font><font size="+2" color="#000000" face="Arial,Helvetica"><b>Division Hardware (Simple and Streamlined)</b></font><font size="+0" color="#b22222">
</font>
<font size="+0" color="#b22222">// :PH: 4.7
</font>
 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Division Hardware</b></font><font size="+0" color="#b22222">
//
// Simple Divider
//   See :PH: Figure 4.36
//   A straightforward translation of binary division algorithm into hardware.
//   Cost of n-bit divider:
//      Proportional to n.
//      Uses 5n bits of register storage.
//   Speed of n-bit divider:
//      Quotient in n clock cycles.
//
// Streamlined Divider
//   See :PH: Figure 4.41
//   Less storage needed.
//   Cost of n-bit divider:
//      Proportional to n.
//      Uses 2n bits of register storage.
//   Speed of n-bit divider:
//      Quotient in n clock cycles.
</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">
//
// Simple divider.
// Based on :PH: Figure 4.36
</font>
<font size="+0" color="#000080">module</font> <font size="+1" color="#000000" face="Arial,Helvetica"><b>simple_divider</b></font>(quotient,remainder,ready,dividend,divider,start,clk);
   
   <font size="+0" color="#4169e1">input</font> [15:0]  <font size="+0" color="#b8860b">dividend</font>,<font size="+0" color="#b8860b">divider</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">quotient</font>,<font size="+0" color="#b8860b">remainder</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">ready</font>;

<font size="+0" color="#b22222">//  """"""""|
//     1011 |  &lt;----  dividend_copy
// -0011    |  &lt;----  divider_copy
//  """"""""|    0  Difference is negative: copy dividend and put 0 in quotient.
//     1011 |  &lt;----  dividend_copy
//  -0011   |  &lt;----  divider_copy
//  """"""""|   00  Difference is negative: copy dividend and put 0 in quotient.
//     1011 |  &lt;----  dividend_copy
//   -0011  |  &lt;----  divider_copy
//  """"""""|  001  Difference is positive: use difference and put 1 in quotient.
//            quotient (numbers above)   
</font>

   <font size="+0" color="#a020f0">reg</font> [15:0]    <font size="+0" color="#b8860b">quotient</font>;
   <font size="+0" color="#a020f0">reg</font> [31:0]    <font size="+0" color="#b8860b">dividend_copy</font>, <font size="+0" color="#b8860b">divider_copy</font>, <font size="+0" color="#b8860b">diff</font>;
   <font size="+0" color="#a020f0">wire</font> [15:0]   <font size="+0" color="#000000"><b>remainder </b></font>= dividend_copy[15: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="#000080">initial</font> bit = 0;

   <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 = 16;
        quotient = 0;
        dividend_copy = {<font size="+0" color="#999999">16'd</font>0,dividend};
        divider_copy = {<font size="+0" color="#999999">1'b</font>0,divider,<font size="+0" color="#999999">15'd</font>0};

     <font size="+0" color="#0000cd">end</font> <font size="+0" color="#4169e1">else</font> <font size="+0" color="#0000cd">begin</font>

        diff = dividend_copy - divider_copy;

        quotient = quotient &lt;&lt; 1;

        <font size="+0" color="#4169e1">if</font>( !diff[31] ) <font size="+0" color="#0000cd">begin</font>

           dividend_copy = diff;
           quotient[0] = <font size="+0" color="#999999">1'd</font>1;

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

        divider_copy = divider_copy &gt;&gt; 1;
        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">
//
// Streamlined divider.  
// Based on :PH: Figure 4.41
//
// Uses less register storage than simple divider.
</font>
<font size="+0" color="#000080">module</font> <font size="+1" color="#000000" face="Arial,Helvetica"><b>streamlined_divider</b></font>(quotient,remainder,ready,dividend,divider,start,clk);
   
   <font size="+0" color="#4169e1">input</font> [15:0]  <font size="+0" color="#b8860b">dividend</font>,<font size="+0" color="#b8860b">divider</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">quotient</font>,<font size="+0" color="#b8860b">remainder</font>;
   <font size="+0" color="#4169e1">output</font>        <font size="+0" color="#b8860b">ready</font>;

   <font size="+0" color="#a020f0">reg</font> [31:0]    <font size="+0" color="#b8860b">qr</font>;
   <font size="+0" color="#a020f0">reg</font> [16:0]    <font size="+0" color="#b8860b">diff</font>;

<font size="+0" color="#b22222">//
//              0000 1011
//  """"""""|
//     1011 |   0001 0110     &lt;- qr reg
// -0011    |  -0011          &lt;- divider (never changes)
//  """"""""|           
//     1011 |   0010 110o     &lt;- qr reg
//  -0011   |  -0011
//  """"""""|
//     1011 |   0101 10oo     &lt;- qr reg
//   -0011  |  -0011
//  """"""""|   0010 1000     &lt;- qr reg before shift
//     0101 |   0101 0ooi     &lt;- after shift
//    -0011 |  -0011
//  """"""""|   0010 ooii
//       10 |   
//
// Quotient, 3 (0011); remainder 2 (10).
</font>
   
   <font size="+0" color="#a020f0">wire</font> [15:0]   <font size="+0" color="#000000"><b>remainder </b></font>= qr[31:16];
   <font size="+0" color="#a020f0">wire</font> [15:0]   <font size="+0" color="#000000"><b>quotient </b></font>= qr[15: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="#000080">initial</font> bit = 0;

   <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 = 16;
        qr = {<font size="+0" color="#999999">16'd</font>0,dividend};

     <font size="+0" color="#0000cd">end</font> <font size="+0" color="#4169e1">else</font> <font size="+0" color="#0000cd">begin</font>

        diff = qr[31:15] - {<font size="+0" color="#999999">1'b</font>0,divider};

        <font size="+0" color="#4169e1">if</font>( diff[16] )
          qr = {qr[30:0],<font size="+0" color="#999999">1'd</font>0};
        <font size="+0" color="#4169e1">else</font>
          qr = {diff[15:0],qr[14:0],<font size="+0" color="#999999">1'd</font>1};
        
        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="+2" color="#000000" face="Arial,Helvetica"><b>"Real" Arithmetic Circuits</b></font><font size="+0" color="#b22222">
</font>
<font size="+0" color="#b22222">// :HP: Appendix A
</font>
 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Adders</b></font><font size="+0" color="#b22222">
//
// Multiple-level CLA covered in class reasonably close to adders used
// in processors.
//
// Other fast adder techniques also used. (See :PH: problems.)
</font>
 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Multipliers</b></font><font size="+0" color="#b22222">
//
// The multiplication hardware presented above is much slower than
// the hardware used in real processors.
//
// "Real" n-bit Multiplier Features
//
//   Multiplication done in one or two cycles (assume one cycle).
//   Uses higher-radix (say 4) Booth recoding or something similar.
//   Enough adders are provided so that product computed in one cycle.
//   These adders can add n numbers quickly without the cost of n CLA's.
//     Cost may be something like 3/2 n ripple adders plus 1 CLA.
//     Delay through each adder is only a handful of gates.
//   Adders may be connected as a tree, so that number of adders
//     from input to output is proportional to log n (rather than n).
</font>
 <font size="+0" color="#b22222">/// </font><font size="+0" color="#b22222" face="Arial,Helvetica"><b>Dividers</b></font><font size="+0" color="#b22222">
//
// The division hardware presented above is slower than hardware used
// in real processors.
//
// Division trickier than multiplication because result of step i
// needed for i+1.  This precludes the tree structures used in
// fast multipliers.
//
// FP Dividers in general-purpose processors typically take 10-20 cycles.
//
// Several division techniques used.  Examples:
//   SRT: Sweeney, Robertson, Tocher
//   Newton Iteration
//   Goldschmidt's Algorithm
//
</font></pre>
  </body></html>