[comp.music] FIR filtering using FFT

george@fourier.eedsp.gatech.edu (B. George) (03/22/90)

This is really more DSP-oriented, so I'll keep it short:

It is possible to implement FIR filters very efficiently via
the FFT using a technique called the overlap-add method (A. V. Oppenheim
and R. W. Schafer, "Digital Signal Processing," Prentice-Hall, 1975,
pp. 110-115).  The trick is to carefully choose N, the length of the DFT.

If you have an FIR filter of length M and an input sequence of length L,
then N > M+L is required so that the circular convolution resulting
from multiplying the DFT's is the same as linear convolution.  With this
in mind, you can break up your input signal into subsequences of length L,
perform the convolution on the subsequences, and overlap and add the 
results together.
 
-Bryan George <george@eedsp.gatech.edu>
 Georgia Tech, School of EE, DSP Laboratory
 We will meet or beat any advertised bit rate!