Fast convolution multiplier

Abstract

The present invention provides a method and apparatus for performing finite impulse response (FIR) type filtering of 2N points of real-only input data using fewer multiplication elements than traditionally required. A filter multiplexer segregates or divides the input data into even and odd data values which are transferred to the "real" and "imaginary" inputs of a fast Fourier Transformation (FFT) or DFT element which selectively performs N-point transformations according to a preselected FFT algorithm. The transformed data output by the FFT transformer is divided into even and odd transformed, frequency domain, data. The even and odd transformed data is transferred to a multiplier where it is multiplied by a preselected weighting matrix of coefficients and the DFT of the desired filter response. The resulting data is divided into even and odd transformed data functions which are recombined to provide the transform of the multiplier input data function. Data thus transformed is transferred to an IFFT transformer where it is transformed to the time domain and subsequently de-multiplexed into a filtered data output. The frequency domain multiplication is obtained using N/2 multiplier section each employing twelve multipliers. The resulting filter or fast convolution apparatus is optimized in terms of multiplications per point making it more efficient than previous filter devices.

Dependencies are inferred from the claim text.