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.

Fast Fourier transform

`Y = fft(X)`

`Y = fft(X,n)`

`Y = fft(X,n,dim)`

computes
the discrete
Fourier transform (DFT) of `Y`

= fft(`X`

)`X`

using a fast
Fourier transform (FFT) algorithm.

If

`X`

is a vector, then`fft(X)`

returns the Fourier transform of the vector.If

`X`

is a matrix, then`fft(X)`

treats the columns of`X`

as vectors and returns the Fourier transform of each column.If

`X`

is a multidimensional array, then`fft(X)`

treats the values along the first array dimension whose size does not equal 1 as vectors and returns the Fourier transform of each vector.

returns
the `Y`

= fft(`X`

,`n`

)`n`

-point DFT. If no value is specified, `Y`

is
the same size as `X`

.

If

`X`

is a vector and the length of`X`

is less than`n`

, then`X`

is padded with trailing zeros to length`n`

.If

`X`

is a vector and the length of`X`

is greater than`n`

, then`X`

is truncated to length`n`

.If

`X`

is a matrix, then each column is treated as in the vector case.If

`X`

is a multidimensional array, then the first array dimension whose size does not equal 1 is treated as in the vector case.

The execution time for

`fft`

depends on the length of the transform. The time is fastest for powers of two and almost as fast for lengths that have only small prime factors. The time is typically several times slower for lengths that are prime, or which have large prime factors.For most values of

`n`

, real-input DFTs require roughly half the computation time of complex-input DFTs. However, when`n`

has large prime factors, there is little or no speed difference.You can potentially increase the speed of

`fft`

using the utility function,`fftw`

. This function controls the optimization of the algorithm used to compute an FFT of a particular size and dimension.

The FFT functions (`fft`

, `fft2`

, `fftn`

, `ifft`

, `ifft2`

, `ifftn`

)
are based on a library called FFTW [1] [2].

[1] FFTW (`http://www.fftw.org`

)

[2] Frigo, M., and S. G. Johnson. “FFTW: An Adaptive Software Architecture for the FFT.” Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. Vol. 3, 1998, pp. 1381-1384.