fft Página 1 de 6
Contents
fft
Fast Fourier transform
Syntax
Y = fft(x)
Y = fft(X,n)
Y = fft(X,[],dim)
Y = fft(X,n,dim)
Definitions
The functions Y = fft(x) and y = ifft(X) implement the transform and
inverse transform pair given for vectors of length N by:
where
is an Nth root of unity.
Description
Y = fft(x) returns the discrete Fourier transform (DFT) of vector x, computed
with a fast Fourier transform (FFT) algorithm.
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, fft operates on the first nonsingleton
dimension.
file:///C:/Program%20Files/MATLAB/R2013a/help/matlab/ref/fft.html 21/01/2014
fft Página 2 de 6
Y = fft(X,n) returns the n-point DFT. fft(X) is equivalent to fft(X,
n) where n is the size of X in the first nonsingleton dimension. If the length of X is
less than n, X is padded with trailing zeros to length n. If the length of X is greater
than n, the sequence X is truncated. When X is a matrix, the length of the columns
are adjusted in the same manner.
Y = fft(X,[],dim) and Y = fft(X,n,dim) applies the FFT
operation across the dimension dim.
Examples
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)')
file:///C:/Program%20Files/MATLAB/R2013a/help/matlab/ref/fft.html 21/01/2014
fft Página 3 de 6
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)|')
file:///C:/Program%20Files/MATLAB/R2013a/help/matlab/ref/fft.html 21/01/2014
fft Página 4 de 6
The main reason the amplitudes are not exactly at 0.7 and 1 is because of the noise.
Several executions of this code (including recomputation of y) will produce different
approximations to 0.7 and 1. The other reason is that you have a finite length signal.
Increasing L from 1000 to 10000 in the example above will produce much better
approximations on average.
Data Type Support
fft supports inputs of data types double and single. If you call fft with the
syntax y = fft(X, ...), the output y has the same data type as the input X.
More About
Algorithms
The FFT functions (fft, fft2, fftn, ifft, ifft2, ifftn) are based on
a library called FFTW [3],[4]. 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 [1], 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
file:///C:/Program%20Files/MATLAB/R2013a/help/matlab/ref/fft.html 21/01/2014
fft Página 5 de 6
several machine-generated fixed-size "codelets." The codelets in turn use several
algorithms in combination, including a variation of Cooley-Tukey [5], a prime factor
algorithm [6], and a split-radix algorithm [2]. 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 [7]. 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 prime factors.
Note You might be able to increase the speed of fft using the utility
function fftw, which controls the optimization of the algorithm used to
compute an FFT of a particular size and dimension.
References
[1] 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.
[2] 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.
[3] FFTW (http://www.fftw.org)
[4] 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.
file:///C:/Program%20Files/MATLAB/R2013a/help/matlab/ref/fft.html 21/01/2014
fft Página 6 de 6
[5] Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-
Hall, 1989, p. 611.
[6] Oppenheim, A. V. and R. W. Schafer, Discrete-Time Signal Processing, Prentice-
Hall, 1989, p. 619.
[7] 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.
See Also
dftmtx | fft2 | fftn | fftshift | fftw | filter | freqz | ifft
Was this topic helpful? Yes No
file:///C:/Program%20Files/MATLAB/R2013a/help/matlab/ref/fft.html 21/01/2014
