Guia

University of Rhode Island Department of Electrical and Computer Engineering ELE 436: Communication Systems

FFT Tutorial
1 Getting to Know the FFT

What is the FFT? FFT = Fast Fourier Transform. The FFT is a faster version of the Discrete Fourier Transform (DFT). The FFT utilizes some clever algorithms to do the same thing as the DTF, but in much less time. Ok, but what is the DFT? The DFTis extremely important in the area of frequency (spectrum) analysis because it takes a discrete signal in the time domain and transforms that signal into its discrete frequency domain representation. Without a discrete-time to discrete-frequency transform we would not be able to compute the Fourier transform with a microprocessor or DSP based system. It is the speed and discrete nature of theFFT that allows us to analyze a signal’s spectrum with Matlab or in real-time on the SR770

2

Review of Transforms

Was the DFT or FFT something that was taught in ELE 313 or 314? No. If you took ELE 313 and 314 you learned about the following transforms:
∞

Laplace Transform: Continuous-Time Fourier Transform: z Transform: Discrete-Time Fourier Transform:

x(t) ⇔ X(s) x(t) ⇔ X(jω) x[n]⇔ X(z) x[n] ⇔ X(ejΩ )

where X(s) = where X(jω) =

x(t)e−st dt
−∞ ∞

x(t)e−jωt dt
−∞ ∞

where X(z) = where X(ejΩ ) =
n=−∞ ∞

x[n]z −n x[n]e−jΩn
n=−∞

The Laplace transform is used to to find a pole/zero representation of a continuous-time signal or system, x(t), in the s-plane. Similarly, The z transform is used to find a pole/zero representation of a discrete-time signal orsystem, x[n], in the z-plane. The continuous-time Fourier transform (CTFT) can be found by evaluating the Laplace transform at s = jω. The discrete-time Fourier transform (DTFT) can be found by evaluating the z transform at z = ejΩ .

1

3

Understanding the DFT

How does the discrete Fourier transform relate to the other transforms? First of all, the DFT is NOT the same as the DTFT. Bothstart with a discrete-time signal, but the DFT produces a discrete frequency domain representation while the DTFT is continuous in the frequency domain. These two transforms have much in common, however. It is therefore helpful to have a basic understanding of the properties of the DTFT. Periodicity: The DTFT, X(ejΩ ), is periodic. One period extends from f = 0 to fs , where fs is the samplingfrequency. Taking advantage of this redundancy, The DFT is only defined in the region between 0 and fs . Symmetry: When the region between 0 and fs is examined, it can be seen that there is even symmetry around the center point, 0.5fs , the Nyquist frequency. This symmetry adds redundant information. Figure 1 shows the DFT (implemented with Matlab’s FFT function) of a cosine with a frequency one tenththe sampling frequency. Note that the data between 0.5f s and fs is a mirror image of the data between 0 and 0.5fs .

12

10

8

6

4

2

0

0

0.1

0.2

0.3

0.4

0.5 frequency/f

0.6

0.7

0.8

0.9

1

s

Figure 1: Plot showing the symmetry of a DFT

2

4

Matlab and the FFT

Matlab’s FFT function is an effective tool for computing the discreteFourier transform of a signal. The following code examples will help you to understand the details of using the FFT function.

Example 1: The typical syntax for computing the FFT of a signal is FFT(x,N) where x is the
signal, x[n], you wish to transform, and N is the number of points in the FFT. N must be at least as large as the number of samples in x[n]. To demonstrate the effect of changing thevalue of N, sythesize a cosine with 30 samples at 10 samples per period.
n = [0:29]; x = cos(2*pi*n/10);

Define 3 different values for N. Then take the transform of x[n] for each of the 3 values that were defined. The abs function finds the magnitude of the transform, as we are not concered with distinguishing between real and imaginary components.
N1 N2 N3 X1 X2 X3 = = = = = = 64; 128; 256;...