| Signal Processing Toolbox | Help Desk |
fft
One-dimensional fast Fourier transform.
y = fft(x) y = fft(x,n)
fft computes the discrete Fourier transform of a vector or matrix. This function implements the transform given by
where WN = e-j(2
/N) and N = length(x). Note that the series is indexed as n + 1 and k + 1 instead of the usual n and k because MATLAB vectors run from 1 to N instead of from 0 to N-1.
y = fft(x)
is the discrete Fourier transform of vector x, computed with a fast Fourier transform (FFT) algorithm. If x is a matrix, y is the FFT of each column of the matrix. The fft function employs a radix-2 fast Fourier transform algorithm if the length of the sequence is a power of two, and a slower algorithm if it is not; see the "Algorithm" section for details.
y = fft(x,n)
is the n-point FFT. If the length of x is less than n, fft pads x with trailing zeros to length n. If the length of x is greater than n, fft truncates the sequence x. If x is an array, fft adjusts the length of the columns in the same manner.
fft is part of the standard MATLAB environment.
A common use of the Fourier transform is to find the frequency components of a time-domain signal buried in noise. Consider data sampled at 1000 Hz. Form a signal consisting of 50 Hz and 120 Hz sinusoids and corrupt the signal with zero-mean random noise:
t = 0:0.001:0.6; x = sin(2*pi*50*t) + sin(2*pi*120*t); y = x + 2*randn(1,length(t)); plot(y(1:50))It is difficult to identify the frequency components by studying the original signal. Convert to the frequency domain by taking the discrete Fourier transform of the noisy signal
y using a 512-point fast Fourier transform (FFT):
Y = fft(y,512);The power spectral density, a measurement of the energy at various frequencies, is
Pyy = Y.*conj(Y) / 512;Graph the first 256 points (the other 256 points are symmetric) on a meaningful frequency axis:
f = 1000*(0:255)/512; plot(f,Pyy(1:256))See the
psd function for details on calculating spectral density.
Sometimes it is useful to normalize the output of fft so that a unit sinusoid in the time domain corresponds to unit amplitude in the frequency domain. To produce a normalized discrete-time Fourier transform in this manner, use
Pn = abs(fft(x))*2/length(x)
fft is a built-in MATLAB function. When the sequence length is a power of two, fft uses a high-speed radix-2 fast Fourier transform algorithm. The radix-2 FFT routine is optimized to perform a real FFT if the input sequence is purely real; otherwise it computes the complex FFT. This causes a real power-of-two FFT to be about 40% faster than a complex FFT of the same length.
When the sequence length is not an exact power of two, a separate algorithm finds the prime factors of the sequence length and computes the mixed-radix discrete Fourier transforms of the shorter sequences.
The execution time for fft depends on the sequence length. If the length of a sequence has many prime factors, the function computes the FFT quickly; if the length has few prime factors, execution is slower. For sequences whose lengths are prime numbers, fft uses the raw (and slow) DFT algorithm. For this reason it is usually better to use power-of-two FFTs, if this is supported by your application. For example, on one machine a 4096-point real FFT takes 2.1 seconds and a complex FFT of the same length takes 3.7 seconds. The FFTs of neighboring sequences of length 4095 and 4097, however, take 7 seconds and 58 seconds, respectively.
Suppose a sequence x of N points is obtained at a sample frequency of 
. Then, for up to the Nyquist frequency, or point n = N/2 + 1, the relationship between the actual frequency and the index k into x (out of N possible indices) is
Filter data with a recursive (IIR) or nonrecursive (FIR) filter. |
|