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

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.

• Paz: poles and zeros – OscarArcila Jun 18 at 18:33
• If you share a specific example of input signal and the zeros and poles we can show you a full answer. – Royi Jun 18 at 20:06

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).

• Hello @MattL, I really appreciate your help. I have a file of zeros and poles and I need to calculate the convolution of the signal with this transfer function. This signal is a synthetic seismic signal and I need to compare with the available registers that are instrumental records (convolved). I have very little experience in Signal Processing but I read that I can make convolution multiplying the FFT of the signal with the values of the transfer function calculated in the appropriate frequency bins but I don´t know how to make this exactly. Again I am very grateful. – OscarArcila Jun 20 at 0:09
• @OscarArcila: Just implement the filter using Matlab's filter() function. You can obtain the required filter coefficients a and b from the poles and zeros using the function zp2tf(). – Matt L. Jun 20 at 9:25
• Thanks, I going to make as you say. Maybe you have some interest in other of my questions link. – OscarArcila Jun 21 at 5:57