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`

filters
the data in vector ` = `

fftfilt(b,x)`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`

uses ` = `

fftfilt(b,x,n)`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 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 http://www.mathworks.com/products/parallel-computing/requirements.html 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*.

[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?