Method and apparatus for implementing a digital filter employing coefficients expressed as sums of 2 to an integer power
AssigneeMonolith Technologies Corporation
InventorKun Lin
Life of this patent
Estimating the term…
Abstract
Method and apparatus for implementing a digital filter employing coefficients expressed as sums of 2 to an integer power. Coefficients expressed as sums of powers of 2 may be algebraically manipulated such that higher order terms are replaced by an equivalent group of lower order terms. In the context of a shift-and-add algorithm, the lower order terms require fewer shifting operations and less total hardware to effect multiplication than the corresponding higher order terms.
Claims20
An apparatus for generating indicia of the product of a data word x and a binary coefficient b, the coefficient b being expressible as a sum of L terms each of the form f2.sup.-p, where f=+1, -1, or o and p is a positive integer, said apparatus comprising:
- a coefficient memory configured to store indicia of said coefficient b;
- a shifter comprising shifter input means for loading data into said shifter, said shifter being coupled to said coefficient memory to selectively shift the contents of said shifter in accordance with one of said terms;
- a feedback link disposed to apply data output from said shifter to said shifter input means;
- and
- summing means configured to receive data output from said shifter, for successively summing L data values output from said shifter to thereby generate said indicia of said product of said data word x and said coefficient b.
A method of effecting the shift-and-add operation of a binary data word x in accordance with a binary coefficient b expressible as a sum of terms each of the form f2.sup.-p, where f=+1, or o and p is an integer, the method comprising the steps of:
- loading said data word x into a shifter;
- shifting said data word x in accordance with a first one of said terms comprising said coefficient b to produce a first shifted value;
- feeding said first shifted value back into said shifter;
- shifting said first shifted value in accordance with a second one of said terms comprising said coefficient b;
- summing a plurality of values output from said shifter to thereby generate indicia of the product of data word x and coefficient b.
A method of generating indicia of the product of a data word x and a coefficient b, wherein said coefficient b is expressible as a sum of L terms of the form b=f.sub.1 2.sup.-p(1) ;
- is in +f.sub.2 2.sup.-p(2) . . . f.sub.L 2.sup.-p(L), wherein f.sub.L =+1, -1, or 0 p(i) is an integer for i=1 to L, said method comprising the steps of:
- loading said data word x into a shifter;
- thereafter for each of said (L-1) of said terms, shifting the contents of said shifter in accordance with a respective one of said terms, outputting a shifted value from said shifter, and loading said shifted value into said shifter;
- and
- summing said shifted values to form said indicia of said product.
Dependencies are inferred from the claim text.