Abstract:
A cascaded multiplier is configured for multiplying an input value by one of a predetermined set of coefficients. Each multiplier stage performs a set of elementary operations, including shifting, signal selection, addition, and subtraction. Each multiplier stage is responsive to at least one input control signal to control at least one elementary operation for selecting the coefficient. The cascaded multiplier may include a right-shift register.

Description:
BACKGROUND  
       [0001]     1. Field of the Invention  
         [0002]     This invention relates to programmable logic devices configured to perform multiplication.  
         [0003]     2. Discussion of the Related Art  
         [0004]     Certain digital signal processing applications require multiplication of a variable by one of a set of constants. A common prior-art technique employs a full multiplier circuit with a constant read-only memory (ROM). The efficiency of this approach is impeded by the necessity for a large multiplier circuit and a large ROM.  
         [0005]     Another prior-art technique uses a multi-constant canonic signed digit pattern search (such as described in V. Lèfevre, “Multiplication by an Integer Constant,” INRIA Report No. 4192, May 2001, Viller-Les-Nancy, France) in which a multiplier circuit simultaneously produces results for all constants and selects one of the results. This approach is inherently inefficient, since only one result needs to be produced.  
         [0006]     Finite impulse response filters, as well as other digital signal-processing applications that perform large numbers of multiplications can benefit from a technique that improves the efficiency of multiplications.  
       SUMMARY OF THE INVENTION  
       [0007]     Embodiments of the present invention relate to computer-implemented multiplication using elementary operations, such as shifts (i.e., multiplication by a power of two), additions, and subtractions. Embodiments of the invention may provide for smaller, faster, and/or less power-consuming circuits.  
         [0008]     In one embodiment of the invention, a sequential multiplication means is configured for performing a plurality of sequential multiplication operations. The sequential multiplication means may include, by way of example, but without limitation, a plurality of multipliers arranged to operate sequentially. Each multiplier typically comprises at least one elementary operation, such as shifting, addition, sign selection, and/or subtraction. Furthermore, each multiplier is configured to be responsive to at least one input control signal for controlling the at least one elementary operation. An input control signaling means is coupled to the sequential multiplication means to produce the at least one input control signal for each multiplier. The input control signaling means may include, by way of example, but without limitation, any signal generation circuitry or any signal selection circuitry configured to produce the at least one input control signal for selecting a predetermined coefficient to multiply an input value.  
         [0009]     In another embodiment, the sequential multiplication means further comprises a right-shifting means configured for right shifting an output of the sequential multiplication means. The right-shifting means may include, by way of example, but without limitation, a right-shift register.  
         [0010]     In yet another embodiment, the sequential multiplication means comprises a mapping means, such as a circuit configured to perform at least one of a set of mapping functions, including reordering coefficients and rejecting coefficients. For example, coefficients may be reordered to produce a set of ascending (or descending) coefficients, and duplicate coefficients may be removed.  
         [0011]     Various functional elements, separately or in combination, depicted in the figures may take the form of a microprocessor, digital signal processor, application specific integrated circuit, field programmable gate array, or other logic circuitry programmed or otherwise configured to operate as described herein. Accordingly, embodiments may take the form of programmable features executed by a common processor or discrete hardware unit.  
         [0012]     These and other embodiments of the invention are described with respect to the figures and the following description of the preferred embodiments. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]     Embodiments according to the present invention are understood with reference to schematic block diagrams of  FIGS. 1, 2 ,  5 ,  6 , and  7 , and plots of  FIGS. 3 and 4 .  
         [0014]      FIG. 1  is a block diagram of an n th  multiplier stage of a plurality N of cascaded multiplier stages in accordance with an embodiment of the present invention.  
         [0015]      FIG. 2  is a block diagram of a cascade of N multiplier stages in accordance with an embodiment of the invention.  
         [0016]      FIG. 3  is a plot showing the quantization match of coefficients related to values of s n  and q n  selected by an exhaustive search to have the smallest maximum error relative to a predetermined function.  
         [0017]      FIG. 4  is a plot of coefficients as a function of a control parameter c n  prior to deleting duplicate coefficients and reordering.  
         [0018]      FIG. 5  is a block diagram of an n th  multiplier stage in accordance with an alternative embodiment of the present invention.  
         [0019]      FIG. 6  is a block diagram of a cascade of N multiplier stages in accordance with an alternative embodiment of the invention.  
         [0020]      FIG. 7  shows an alternative embodiment of a multiplier stage. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0021]     The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art.  
         [0022]      FIG. 1  is a block diagram of an n th  multiplier stage of a plurality N of cascaded multiplier stages in accordance with an embodiment of the present invention. The n th  multiplier stage is configured to multiply an input value x by one of two predetermined constants p n . An input signal x is processed by a left-shift register configured to effectively multiply the input signal x by 2 q     n   . The input signal x may also be operated upon by a sign value s n . An input selector value c n  and the signed input signal are input to an AND gate. The AND gate&#39;s output is summed with the left-shift register&#39;s output by a summer (e.g., a binary adder) to produce an output p n x.  
         [0023]     The constant p n  has an associated left-shift value q n , which represents the bit spacing for the two canonic signed digits in the constant pair associated with the n th  multiplier stage. The sign value s n  sets the sign of the less significant of the two digits. An input control signal, such as the input selector value c n , may include a binary value that selects the constant by which the stage will multiply. The sequence of selector inputs c n , n=0, . . . , N−1 forms a binary number c used to select one of the constants for multiplication by the cascaded multiplier. The sign value s n  may be hard coded or it may be an input control signal.  
         [0024]      FIG. 2  is a block diagram of a cascade of N multiplier stages. At the output, a shift right by Q bits may be performed, such as to provide for fractional multiplication. The output of the cascaded multiplier is expressed as  
       y   =       (       2     -   Q       ⁢       ∏     n   =   o       N   -   1       ⁢           ⁢     (       2     q   n       +       s   n     ⁢     c   n         )         )     ⁢   x           
 In one embodiment, the parameters q n  and s n  may be pre-set, such as predetermined by a particular hardware configuration. In this case, the input selector values c n  select the constant used for multiplication from a set of 2 N  constants. Values for s n  and q n  may be selected by employing numerical optimization or exhaustive search. 
 
         [0025]     A selection algorithm can reduce some error in the coefficient set associated with s n  and q n  values with respect to a desired set of coefficients or coefficient span coverage. For example,  FIG. 3  shows the quantization match of coefficients related to values of s n  and q n  selected by an exhaustive search to have the smallest maximum error relative to a predetermined function. In this exemplary case, the function (and thus, the set of coefficients) may be used to select soft weights for symbol estimates in a CDMA receiver.  
         [0026]      FIG. 4  is a plot of coefficients as a function of control parameter c n  prior to deleting duplicate coefficients and reordering. In this exemplary case, the multiplier had parameter values Q=9 and q=[3 2 1 0 0]. The coefficients for the cascaded multiplier are not necessarily a monotonic function of c, nor is it necessarily possible for them all to fit in the range of interest. They also may not be unique. For some embodiments, it may be advantageous to precede the c input with a mapping circuit to reorder coefficients and reject those that are not desired. If 2 N  possible coefficients are desired, it may be necessary to use N+1 multiplier stages and reject the undesired coefficients.  
         [0027]     Embodiments of the invention may employ multiplier stages having alternative configurations. For example, with no increase in hardware complexity, an alternative embodiment of the invention may increase the possible number of coefficient sets for a given stage count N by splitting the input to the multiplier, such as shown in  FIG. 5 . These two-input stages may be connected in a feed-forward network of various topologies chosen to minimize an error criterion. One such configuration is shown in  FIG. 6 , which has a benefit of providing no increase in hardware complexity with respect to the embodiment shown in  FIG. 2 . Other benefits and advantages may be provided by the embodiments described herein and their variations.  
         [0028]      FIG. 7  shows an alternative embodiment of a multiplier stage further comprising a multiplexer in the upper path of the multiplier stage to permit dynamic selection of the left shift. This alternative embodiment balances the combinatorial delay of the AND gate with that of the multiplexer and is of minimal additional complexity. As described in previous embodiments, the sign selector s n  may be changed from a hard parameter to a dynamic selection.  
         [0029]     Those skilled in the art should recognize that method and apparatus embodiments described herein may be implemented in a variety of ways, including implementations in hardware, software, firmware, or various combinations thereof. Examples of such hardware may include Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs), general-purpose processors, Digital Signal Processors (DSPs), and/or other circuitry.  
         [0030]     The method and system embodiments described herein merely illustrate particular embodiments of the invention. It should be appreciated that those skilled in the art will be able to devise various arrangements, which, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope. Furthermore, all examples and conditional language recited herein are intended to be only for pedagogical purposes to aid the reader in understanding the principles of the invention. This disclosure and its associated references are to be construed as applying without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure.