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`