fftfilt (Signal Processing Toolbox)

FFT-based FIR filtering using the overlap-add method

Syntax

y = fftfilt(b,x)
y = fftfilt(b,x,n)

Description

fftfilt filters data using the efficient FFT-based method of overlap-add, a frequency domain filtering technique that works only for FIR filters.

y = fftfilt(b,x) filters the data in vector x with the filter described by coefficient vector b. It returns the data vector y. The operation performed by fftfilt is described in the time domain by the difference equation:

An equivalent representation is the z-transform or frequency domain description:

By default, fftfilt chooses an FFT length and data block length that guarantee efficient execution time.

y = fftfilt(b,x,n) uses an FFT length of nfft = 2^nextpow2(n) and a data block length of nfft - length(b) + 1.

fftfilt works for both real and complex inputs.

Examples

Show that the results from fftfilt and filter are identical:

b = [1 2 3 4];
x = [1 zeros(1,99)]';
norm(fftfilt(b,x) - filter(b,1,x))

ans = 
    9.5914e-15

Algorithm

fftfilt uses fft to implement the overlap-add method [1], a technique that combines successive frequency domain filtered blocks of an input sequence. fftfilt breaks an input sequence x into length L data blocks

and convolves each block with the filter b by

y = ifft(fft(x(i:i+L-1),nfft).*fft(b,nfft));

where nfft is the FFT length. fftfilt overlaps successive output sections by n-1 points, where n is the length of the filter, and sums them.

fftfilt chooses the key parameters L and nfft in different ways, depending on whether you supply an FFT length n and on the lengths of the filter and signal. If you do not specify a value for n (which determines FFT length), fftfilt chooses these key parameters automatically:

If length(x)is greater than length(b), fftfilt chooses values that minimize the number of blocks times the number of flops per FFT.
If length(b) is greater than or equal to length(x), fftfilt uses a single FFT of length

```
2^nextpow2(length(b) + length(x) - 1)
```

This essentially computes
- ```
y = ifft(fft(B,nfft).*fft(X,nfft))
```

If you supply a value for n, fftfilt chooses an FFT length, nfft, of 2^nextpow2(n)and a data block length of nfft - length(b) + 1. If n is less than length(b), fftfilt sets n to length(b).

See Also

conv, filter, filtfilt

References

[1] Oppenheim, A.V., and R.W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989.

fft2 fftshift