Note: This page has been translated by MathWorks. Click here to see

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

FFT-based FIR filtering using overlap-add method

`y = fftfilt(b,x)`

y = fftfilt(b,x,n)

y = fftfilt(d,x)

y = fftfilt(d,x,n)

y = fftfilt(gpuArrayb,gpuArrayX,n)

`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:

$$y(n)=b(1)x(n)+b(2)x(n-1)+\cdots +b(nb+1)x(n-nb)$$

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

$$Y(z)=\left(b(1)+b(2){z}^{-1}+\cdots +b(nb+1){z}^{-nb}\right)X(z)$$

By default, `fftfilt`

chooses an FFT length
and a 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 Algorithms for information.

`y = fftfilt(d,x)`

filters the data in vector `x`

with
a `digitalFilter`

object, `d`

.
Use `designfilt`

to generate `d`

based
on frequency-response specifications.

`y = fftfilt(d,x,n)`

uses `n`

to
determine the length of the FFT.

`y = fftfilt(gpuArrayb,gpuArrayX,n)`

filters the data in the `gpuArray`

object, `gpuArrayX`

, with the FIR filter
coefficients in the `gpuArray`

, `gpuArrayb`

. See
Establish Arrays on a GPU (Parallel Computing Toolbox) for details on gpuArray
objects. Using `fftfilt`

with `gpuArray`

objects
requires Parallel
Computing Toolbox™ software and a CUDA-enabled NVIDIA GPU with compute capability 1.3 or
above. See GPU System Requirements for details. The filtered data,
`y`

, is a gpuArray object. See Overlap-Add Filtering on the GPU for example of overlap-add filtering on
the GPU.

`fftfilt`

works for both real and complex inputs.

`filter`

functionWhen the input signal is relatively large, it is advantageous
to use `fftfilt`

instead of `filter`

,
which 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

½*L*log_{2}*L*

where *L* is the block length. It then performs *L* point-wise
multiplications for a total cost of

*L* + *L*log_{2}*L* = *L*(1 + log_{2}*L*)

multiplications. The cost ratio is therefore

*L*(1+log_{2}*L*) / (*N**L*) = (1 + log_{2}*L*)/*N*

which is approximately log_{2}*L* / *N*.

Therefore, `fftfilt`

becomes advantageous when
log_{2}*L*is less than *N*.

`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 length2^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)`

.

[1] Oppenheim, Alan V., Ronald W. Schafer, and John R. Buck. Discrete-Time Signal Processing. 2nd Ed. Upper Saddle River, NJ: Prentice Hall, 1999.

`conv`

| `designfilt`

| `digitalFilter`

| `filter`

| `filtfilt`

Was this topic helpful?