Fast Fourier transform
Y = fft(x)
Y = fft(X,n)
Y = fft(X,,dim)
Y = fft(X,n,dim)
Y = fft(x) and
y = ifft(X) implement the transform
and inverse transform pair given for vectors of length N by:
is an Nth root of unity.
If the input
X is a matrix,
Y = fft(X) returns the Fourier
transform of each column of the matrix.
If the input
X is a multidimensional array,
on the first nonsingleton dimension.
Y = fft(X,n) returns the
fft(X) is equivalent to
fft(X, n) where
the size of
X in the first nonsingleton dimension.
If the length of
X is less than
padded with trailing zeros to length
n. If the
X is greater than
X is truncated. When
a matrix, the length of the columns are adjusted in the same manner.
Y = fft(X,,dim) and
= fft(X,n,dim) applies the FFT operation across the dimension
A common use of Fourier transforms is to find the frequency components of a signal buried in a noisy time domain signal. Consider data sampled at 1000 Hz. Form a signal containing a 50 Hz sinusoid of amplitude 0.7 and 120 Hz sinusoid of amplitude 1 and corrupt it with some zero-mean random noise:
Fs = 1000; % Sampling frequency T = 1/Fs; % Sample time L = 1000; % Length of signal t = (0:L-1)*T; % Time vector % Sum of a 50 Hz sinusoid and a 120 Hz sinusoid x = 0.7*sin(2*pi*50*t) + sin(2*pi*120*t); y = x + 2*randn(size(t)); % Sinusoids plus noise plot(Fs*t(1:50),y(1:50)) title('Signal Corrupted with Zero-Mean Random Noise') xlabel('time (milliseconds)')
It is difficult to identify the frequency components by looking
at the original signal. Converting to the frequency domain, the discrete
Fourier transform of the noisy signal
y is found
by taking the fast Fourier transform (FFT):
NFFT = 2^nextpow2(L); % Next power of 2 from length of y Y = fft(y,NFFT)/L; f = Fs/2*linspace(0,1,NFFT/2+1); % Plot single-sided amplitude spectrum. plot(f,2*abs(Y(1:NFFT/2+1))) title('Single-Sided Amplitude Spectrum of y(t)') xlabel('Frequency (Hz)') ylabel('|Y(f)|')
The main reason the amplitudes are not exactly at 0.7 and 1
is because of the noise. Several executions of this code (including
y) will produce different approximations
to 0.7 and 1. The other reason is that you have a finite length signal.
L from 1000 to 10000 in the example
above will produce much better approximations on average.
fft supports inputs of data types
If you call
fft with the syntax
fft(X, ...), the output
y has the same
data type as the input
The FFT functions (
are based on a library called FFTW ,. To compute an N-point
DFT when N is composite (that is, when N = N1N2),
the FFTW library decomposes the problem using the Cooley-Tukey algorithm , which first computes N1 transforms
of size N2, and then computes N2 transforms
of size N1. The decomposition
is applied recursively to both the N1-
and N2-point DFTs until
the problem can be solved using one of several machine-generated fixed-size
"codelets." The codelets in turn use several algorithms in combination,
including a variation of Cooley-Tukey , a prime factor algorithm , and a split-radix
The particular factorization of N is chosen heuristically.
When N is a prime number, the FFTW library first decomposes an N-point problem into three (N – 1)-point problems using Rader's algorithm . It then uses the Cooley-Tukey decomposition described above to compute the (N – 1)-point DFTs.
For most 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.
The execution time for
fft depends on the
length of the transform. It is fastest for powers of two. It is almost
as fast for lengths that have only small prime factors. It is typically
several times slower for lengths that are prime or which have large
You might be able to increase the speed of
 Cooley, J. W. and J. W. Tukey, "An Algorithm for the Machine Computation of the Complex Fourier Series,"Mathematics of Computation, Vol. 19, April 1965, pp. 297-301.
 Duhamel, P. and M. Vetterli, "Fast Fourier Transforms: A Tutorial Review and a State of the Art," Signal Processing, Vol. 19, April 1990, pp. 259-299.
 FFTW (
 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.
 Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989, p. 611.
 Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989, p. 619.
 Rader, C. M., "Discrete Fourier Transforms when the Number of Data Samples Is Prime," Proceedings of the IEEE, Vol. 56, June 1968, pp. 1107-1108.