Subversion Repositories socgen

////////////////////////////////////////////////////////////////////////////////

/// Booth Recoding for Higher-Radix and Signed Multiplication

// :PH: 4.6  Only describes Radix-2 Booth Recoding

 /// Basic Idea

//

// Rather than repeatedly adding either 0 or 1 times multiplicand,

// repeatedly add 0, 1, -1, 2, -2, etc. times the multiplicand.

//

 /// Benefits

//

// Performs signed multiplication without having to first compute the

// absolute value of the multiplier and multiplicand.

//

// Improved performance (when radix higher than 2).

 /// Multipliers Described Here

//

// 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.

 /// Ordinary Radix-4 Multiplier Idea

//

// 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

 // 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.

// :Example:

//

// A Radix-4 multiplier.  Takes unsigned numbers.

module imult_ord_radix_4 #(parameter width=16)

(

   input   wire               clk,

   input   wire               reset,

   input   wire               start,

   input   wire [width-1:0]   multiplicand,

   input   wire [width-1:0]   multiplier,

   output  wire [2*width-1:0] prod,

   output  wire               ready

);

   reg   [width+1:0]          pp;

   reg   [width-1:0]          bit_cnt;

   reg   [2*width:0]          product;

   wire  [width+1:0]          multiplicand_X_1 = {2'b00,multiplicand};

   wire  [width+1:0]          multiplicand_X_2 = {1'b0,multiplicand,1'b0};

   wire  [width+1:0]          multiplicand_X_3 =  multiplicand_X_2 + multiplicand_X_1;

   assign   prod  =  product[2*width-1:0];

   assign   ready = ~ ( | bit_cnt);

   always @(*)

     begin

        case ( {product[1:0]} )

          2'd0: pp = {2'b0, product[2*width-1:width] };

          2'd1: pp = {2'b0, product[2*width-1:width] } + multiplicand_X_1;

          2'd2: pp = {2'b0, product[2*width-1:width] } + multiplicand_X_2;

          2'd3: pp = {2'b0, product[2*width-1:width] } + multiplicand_X_3;

        endcase

     end

   always @( posedge clk )

    if(reset)

        begin

        bit_cnt <= 'b0;

        product <= 'b0;

        end

    else

    begin

     if( ready && start )

        begin

        bit_cnt     <= width/2;

        product     <= {1'b0, {width{1'b0}}, multiplier };

        end

     else if( !ready )

        begin

        product     <= { 1'b0,pp, product[width-1:2] };

        bit_cnt     <= bit_cnt - 1;

        end

    end

endmodule