In applications such as acoustic echo cancellation the impulse response of the system often reaches over 100ms in length. This would require an adaptive FIR filter with over 1000 coefficients. The linear convolution and the update of the adaptive filter with this length creates a significant computational burden for applications that require low power processors. For example, the order of computational complexity of the affine projection algorithm is O(2NL2), where L is the length of the adaptive filter and N is the order of the affine projection. The application of the adaptive IIR filters often fail to produce the desired results despite their reduced complexity is because the adaptation of the IIR filter contains many local minima and instabilities. As the efficiency of Fast Fourier Transforms (FFTs) have improved, block processing and frequency domain adaptive filters (FDAF) have become realizable on low power DSPs.
FDAF provide several advantages over its time domain counterpart. Besides being able to perform the filter convolution by a multiplication in frequency domain, also the length of the adaptive filter are effectively decimated by the transformation. Thus, the computational complexity of the adaptive algorithm is reduced. In addition, to reduced computational complexity, FDAF can also provide an increased convergence speed. This is a result from the decreased eigenvalue spread of the autocorrelation matrix of the signals in the filter update.
These advantages of the FDAF ultimately come with a tradeoff. The main costs of FDAF are increased latency and an increased memory requirement. The latency cost comes from the need to delay the desired signal (or microphone signal in echo cancellation) by the delay through the frequency domain filter. This results in an increased memory storage over time domain approaches because both the excitation and desired signals need to be stored. Early approaches of the FDAF made the order of the FFT approximately the same size as the impulse response. But as mentioned earlier, applications such as acoustic echo cancellation can have long echo paths, resulting in a large delay and memory requirement. This disadvantage can be overcome by methods such as the multidelay adaptive filters. In this approachthe block size can be smaller than the required time domain adaptive filter, and adaptive filters in each frequency bins can be applied instead of a single coefficient. Therefore, the disadvantages of FDAF can be mitigated, while maintaining the decreased computational complexity and increased convergence speed.