calculate fft convolution for an LTI system given its input (in time domain) and its poles and zeros

Question

I have considered taking the fft (MatLab) of the input (x) and create frequency bins for the first half (problems with an odd number of samples, tried solution zero paddings) and evaluate the transfer function in these freq bins. Then apply conjugated symmetry for completing the fft of the Transfer function. This pair of sequences are multiplied term by term and then apply ifft (MatLab). Finally scaled by the sum of the fft signal of the transfer function.

There is something strange/invalid with this procedure? How I can correct it? Bibliographical references are appreciated.

Thanks, again.

Answer 1

In general the filter you want to implement is an infinite impulse response (IIR) filter, unless all poles are at the origin of the complex plane (assuming causality), in which case it is a finite impulse response (FIR) filter.

In the general (IIR) case, your suggested method will not result in an exact implementation of the filter. There are two reasons for this:

1. by using an FFT of the filter's frequency response you actually approximate the infinitely long impulse response by an impulse response of finite length. That impulse response is simply given by the inverse FFT of the sampled frequency response.

2. multiplication of the FFTs implements circular (cyclic) convolution, which is different from linear convolution.

Both errors can be made small. For the first error (FIR approximation of IIR filter), you just need to choose an FFT length that captures a large percentage of the energy of the impulse response. This basically means that you choose an FIR filter of sufficient length to approximate the given IIR filter. For minimizing the second error (circular convolution instead of linear convolution), you need to zero-pad the input sequence and the FIR approximation of the IIR filter.

The question remains why one would want to use an implementation like this. One disadvantage of the proposed solution is that you have to wait for the complete input signal before you can start processing, i.e., you introduce a substantial delay. This problem could be tackled by block processing, like overlap-save or overlap-add in the case of standard fast convolution FIR filtering. The other disadvantage is the increase in memory requirements and computational load. Most practical IIR filters have relatively low orders (lower than $20$), but an FIR filter that provides a reasonable approximation will usually have many hundreds of coefficients, or even more.

There exists an exact method for block processing of IIR filters, in which FFTs can be used to solve certain matrix-vector multiplications. This method is explained in detail in this very accessible book chapter by Selesnick and Burrus: Fast Convolution and Filtering (Section 8.3.1).