Performing convolution and filtering in the frequency domain is a useful method of increasing the performance of these functions by using the fact that convolution in the time domain is equivalent to multiplication in the frequency domain.
The down side is that there is increased end-to-end latency due to the requirement to translate between the time and frequency domains (and back again).
Two common methods of performing this task are the Overlap And Add or the Overlap And Save.
These algorithms are summarized in the following document : http://www.numerix-dsp.com/tutorials/DSP/FrequencyDomainFiltering.pdf
Some notes to accompany the presentation :
Looking at the diagrams, lets assign the filter input to Input A and the streaming data to Input B.
The FFT for the filter input can be pre-calculated to reduce the run-time overhead.
The filter length is defined by the system level requirements - pass band ripple, stop band attenuation, transition bandwidth. From this you can then work out what FFT length (> length N+M-1) you require, what dataset length you can support (Input B) and then what overlap you need to use for the FFT algorithms.
If you use Decimation In Frequency algorithms for the forward and inverse FFTs then you can avoid the need to bit reverse re-order the data because all of the frequency domain data will be in bit reversed order.
When using an FFT for an application such as spectrum analysis it is often necessary to window the time domain data to reduce spectral leakage. This is not necessary for the overlap algorithms because the spectral leakage is a linear (convolution) operation caused by the discrete nature of the forward FFT. When you perform the inverse FFT the process is reversed and hence the effect is cancelled
If you have found this solution useful then please do hit the Google (+1) button so that others may be able to find it as well.
