fftfilt (Signal Processing Toolbox)

FFT-based FIR filtering using 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.

If x is a matrix, fftfilt filters its columns. If b is a matrix, fftfilt applies the filter in each column of b to the signal vector x. If b and x are both matrices with the same number of columns, the i-th column of b is used to filter the i-th column of x.

y = fftfilt(b,x,n) uses n to determine the length of the FFT. See the Algorithm section below for information.

fftfilt works for both real and complex inputs.

Comparison to FILTER function

When the input signal is relatively laree, it is advantageous to use fftfilt instead of filter. filter performs N multiplications for each sample in x, where N is the filter length. fftfilt performs 2 FFT operations -- the FFT of the signal block of length L plus the inverse FT of the product of the FFTs -- at the cost of

where L is the block length. It then performs L pointwise multiplications for a total cost of

multiplcations. The cost ratio is therefore

which is approximately log2(L)/N.

Therefore, fftfilt becomes advantageous when log2(L) is less than N.

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, where L must be greater than the filter length N.

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, dfilt.fftfir, filter, filtfilt

References

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

fft2 fftshift