Transformada Rapida De Fourier

Chapter 8. Fourier Analysis

We should point out that this is not the only notation for the finite Fourier transform in common use. The minus sign in the definition of ω after the first equation sometimes occurs instead in the definition of ω used in the inverse transform. ¯ √ The 1/n scaling factor in the inverse transform is sometimes replaced with 1/ n scaling factors in both transforms. InMatlab, the Fourier matrix F can be generated for any given n by omega = exp(-2*pi*i/n); j = 0:n-1; k = j’ F = omega.^(k*j) The quantity k*j is an outer product, an n-by-n matrix whose elements are the products of the elements of two vectors. However, the built-in function fft takes the finite Fourier transform of each column of a matrix argument, so an easier, and quicker, way to generate F is

TheGUI fftgui allows you to investigate properties of the finite Fourier transform. If y is a vector containing a few dozen elements, fftgui(y) produces four plots. real(y) real(fft(y)) imag(y) imag(fft(y))

You can use the mouse to move any of the points in any of the plots, and the points in the other plots respond. Please run fftgui and try the following examples. Each illustrates some propertyof the Fourier transform. If you start with no arguments, fftgui all four plots are initialized to zeros(1,32). Click your mouse in the upper lefthand corner of the upper left-hand plot. You are taking the fft of the zeroth unit vector, with one in the first component and zeros elsewhere. This should produce Figure 8.6. The real part of the result is constant and the imaginary part is zero.
Thetones generated by a touch-tone telephone and the Wolfer sunspot index are two examples of periodic time series, that is, functions of time that exhibit periodic behavior, at least approximately. Fourier analysis allows us to estimate the period from a discrete set of values sampled at a fixed rate. The following table shows the relationship between the various quantities involved in this analysis.8.6. Fast Finite Fourier Transform y Fs n = length(y) t = (0:n-1)/Fs dt = 1/Fs Y = fft(y) abs(Y) abs(Y).^2 f = (0:n-1)*(Fs/n) (n/2)*(Fs/n) = Fs/2 p = 1./f data samples/unit-time number of samples total time time increment finite Fourier transform amplitude of FFT power frequency, cycles/unit-time Nyquist frequency period, unit-time/cycle

13

The periodogram is a plot of the FFT amplitudeabs(Y), or power abs(Y).^2, versus the frequency f. You only need to plot the first half because the second half is a reflection of the first half about the Nyquist frequency.

8.6

Fast Finite Fourier Transform

One-dimensional FFTs with a million points and two-dimensional 1000-by-1000 transforms are common. The key to modern signal and image processing is the ability to do these computationsrapidly. Direct application of the definition
n−1

Yk =
j=0

ω jk yj , k = 0, . . . , n − 1,

requires n multiplications and n additions for each of the n components of Y for a total of 2n2 floating-point operations. This does not include the generation of the powers of ω. A computer capable of doing one multiplication and addition every microsecond would require a million seconds, or about11.5 days, to do a million-point FFT. Several people discovered fast FFT algorithms independently and many people have since contributed to their development, but it was a 1965 paper by John Tukey of Princeton University and John Cooley of IBM Research that is generally credited as the starting point for the modern usage of the FFT. Modern fast FFT algorithms have computational complexity O(n log2n) instead of O(n2 ). If n is a power of 2, a one-dimensional FFT of length n requires fewer than 3n log2 n floating-point operations. For n = 220 , that’s a factor of almost 35,000 faster than 2n2 . Even if n = 1024 = 210 , the factor is about 70. With Matlab 6.5 and a 700 MHz Pentium laptop, the time required for fft(x) if length(x) is 220 = 1048576 is about 1 s. The built-in fft function is...