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 Run MATLAB Functions on a GPU (Parallel Computing Toolbox) for details on `gpuArray`

objects. Using `fftfilt`

with `gpuArray`

objects
requires Parallel
Computing Toolbox™ software. Refer to GPU Support by Release (Parallel Computing Toolbox) to see what GPUs
are supported. 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`