4

What is the difference between the 'conv' and 'fftfilt' functions in MATLAB?

I read that conv is done in time-domain, while fftfilt first does FFT using the overlap-add method before doing the multiplication in frequency-domain. However, I'm not sure how these different approaches will affect the results (as I thought that convolution in the time-domain is the same as multiplication in the frequency domain), and when I should use one over the other?

zellus
  • 9,617
  • 5
  • 39
  • 56
wave
  • 103
  • 1
  • 6
  • Convolution in one domain is indeed equivalent to multiplication in the other domain. However, with discrete time, finite length signals, it's *circular* convolution. See http://en.wikipedia.org/wiki/Convolution#Discrete_convolution, http://en.wikipedia.org/wiki/Overlap-add, and http://stackoverflow.com/questions/2929401/dsp-filtering-in-the-frequency-domain-via-fft for more on the theory. `fftfilt` and `conv` should give equivalent results, use `fftfilt` if it will be faster. – mtrw Oct 14 '11 at 05:43
  • Also, you might be interested in http://dsp.stackexchange.com. – mtrw Oct 14 '11 at 06:00
  • @mtrw: thanks for your comments and the links - they helped to clear up the confusion I had with the different implementations. I also noticed that `conv` gave a result that had length `M+L-1`, where `M` is the length of the impulse response and `L` is the length of the input signal. `fftfilt`, on the other hand, gave a result that was of the same length as the input signal. I guess this is related to `fftfilt`'s processing and truncation of the segments of the input signal with the overlap add method. – wave Oct 14 '11 at 13:50
  • That's interesting that `fftfilt` gives an output that's missing samples. In principle, there's no reason that overlap-save or overlap-add can't give exactly the same length output, but the implementation has to add one extra buffer of zeros at one of the input, then trim it appropriately on output. Looks like Mathwork's implementation is a bit sloppy in this regard. – mtrw Oct 14 '11 at 23:38
  • The response of the filter in future (values L+1, L+2...) depend on future inputs and you don't know them so MATLAB is technically correct here and most applications you don't need the extra outputs. If you do then you really need convolution. – kon psych Nov 15 '15 at 07:39

1 Answers1

1

The transformation from time-domain to frequency-domain has its own computational price. Although the result should be the same the timing can be different depending on input length. You can find the following post useful. For more in depth analysis you could read about FFT/Convolution in time and frequency domain.

Xyand
  • 4,470
  • 4
  • 36
  • 63
  • In general, you only have to transform the shorter signal once. Suppose the short signal is `N` long, and the long one is `M` long. Naive convolution will take `N*M` operations. Overlap-save will take `2*N*log(2*N)*(M/(2*N)+1) ~= M*log(2*N)` operations. If `N=M=10`, then the 100 ops of convolution is better. If `N=100, M=10000`, then the ~80000 ops of overlap-save is better, if the implementations are equivalent. It's a shame that Mathworks decided to implement `fftfilt` as an m file. – mtrw Oct 14 '11 at 05:59