Signal Processing Toolbox

fftfilt

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 nb-1 points, where nb 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	Convolution and polynomial multiplication.
filter	Filter data with a recursive (IIR) or nonrecursive (FIR) filter.
filtfilt	Zero-phase digital filtering.

References

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

fft2

fftshift