Double-accumulator implementation of the convolution function

• US 5,511,015 A
• Filed: 11/30/1993
• Issued: 04/23/1996
• Est. Priority Date: 11/30/1993
• Status: Expired due to Term

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Loral Vought Systems Corporation (Martin Marietta Corporation)
• Inventors: Flockencier, Stuart W.
• Primary Examiner(s): Gordon, Paul P.
• Assistant Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US08/158,757
• Time in Patent Office: 875 Days
• Field of Search: 364/728.01, 364/728.02, 364/728.03, 364/728.07, 364/735, 364/729, 364/604, 364/819
• US Class Current: 708/420
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: H03H 17/0229 reducing the number of taps

Abstract

A Finite Impulse Response (FIR) digital signal processing circuit uses a double-accumulator technique to drastically reduce the number of multiply-accumulate operations which are necessary per sample of input data. The amount of reduction is dependent upon the shape of the filter function to be convolved. A double-accumulator (D-A) can be implemented by first providing a set of D-A coefficients, which are derived from the filter coefficient stream (FCS). Each D-A coefficient is multiplied by a separate input data sample. The products are summed together along with the result of a previous multiplication of the same D-A coefficients with different input data samples. This first sum is added to another number to form a second sum. The other number is the previous value of the second sum. The second sum is the result.

The derived D-A coefficients are fewer and simpler than that required by the conventional FIR implementation. Since multipliers are complex, costly, bulky and limited in speed, the D-A method can lessen these constraints.

Claims

1. A circuit for convolving or correlating two functions comprising:

a plurality of multipliers each having an input and an output, each of said multipliers configured to multiply an input data sample by a non-zero coefficient, each of said coefficients being proportional to a derivative of at least one of said two functions;

a first accumulator having a plurality of inputs and an output, said first accumulator receiving the outputs of said multipliers; and

a second accumulator receiving the output of said first accumulator.

2. The circuit of claim 1 wherein each of said coefficients is proportional to a second derivative of at least one of said two functions.

3. A circuit for convolving or correlating two functions comprising:

a multiply-accumulator for multiplying a coefficient by an input data sample, said multiply-accumulator having a plurality of inputs and an output, said coefficient being proportional to a derivative of at least one of said two functions;

a memory for holding said coefficient and input data samples, said memory having an input to receive said input data samples, an output for providing the coefficient and the input data samples to the multiply-accumulator, and an input to receive address information for determining what information to place on said output;

an address generator having an output for providing information to said memory; and

an accumulator having an input for receiving the output of said multiply-accumulator and an output for providing a result.

4. The circuit of claim 3 wherein said coefficient is proportional to a second derivative of at least one of said two functions.

5. A method of correlating or convolving two functions using a first memory and a second memory, comprising the steps of:

multiplying a number of input data samples by an equal number of coefficients, said coefficients derived from a derivative of at least one of the two functions, to produce a number of products;

storing in said first memory the sum of said number of products and an output of said first memory; and

storing in said second memory the sum of the output of said first memory and an output of said second memory.

6. The method of claim 5 wherein said coefficients are proportional to a second derivative of at least one of said two functions.

7. A circuit for convolving or correlating two functions comprising:

a plurality of multipliers each having an input and an output, each of said multipliers configured to multiply an input data sample by a coefficient, said coefficient derived from a derivative of at least one of the functions; and

an accumulation circuit having a first accumulator including a first accumulating output and a second accumulator including a second accumulating output, the accumulation circuit adding the outputs of said multipliers with the first accumulating output to provide a summed output, and adding the summed output with the second accumulating output to provide a convolved or correlated output.

8. The circuit of claim 7 wherein said coefficients are proportional to a second derivative of at least one of said two functions.

9. The circuit of claim 7 wherein said first accumulator and said second accumulator are arranged in series.