Fast Fourier transform method of computing difference equations and simulating filters

Abstract

Two methods for using the fast Fourier transform to reduce the number of arithmetic operations and, therefore the time required for computing discrete, preformulated, and finite convolutions are listed and justified. Under the idealistic assumption that the impulse response of a preformulated difference equation terminates, a theorem is proved that these two methods can be modified to compute such difference equations. This theorem makes plausible the application of these methods when the impulse response does not terminate, provided that the impulse response decays to a small value. In such cases, the fast Fourier transform can be used to compute approximations to the solutions, although usually this use of the fast Fourier transform offers no reduction in the amount of time required for computing the definition of the difference equation. However, if a filtering operation is specified as a frequency response, the fast Fourier transform can be used to compute the filtering operation directly without need of formulating a difference equation, although this simplification is achieved at the cost of a moderate increase (e.g., twice) in the amount of computation time.