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 DFT is 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 …ver más…

We then normalize the scale so that it extends from 0 to 1 −
F1 = [0 : F2 = [0 : F3 = [0 : N1 - 1]/N1; N2 - 1]/N2; N3 - 1]/N3;
1 N.

Plot each of the transforms one above the other. subplot(3,1,1) plot(F1,X1,’-x’),title(’N = 64’),axis([0 1 0 20]) subplot(3,1,2) plot(F2,X2,’-x’),title(’N = 128’),axis([0 1 0 20]) subplot(3,1,3) plot(F3,X3,’-x’),title(’N = 256’),axis([0 1 0 20])

Upon examining the plot (shown in figure 2) one can see that each of the transforms adheres to the same shape, differing only in the number of samples used to approximate that shape. What happens if N is the same as the number of samples in x[n]? To find out, set N1 = 30. What does the resulting plot look like? Why does it look like this?

3

N = 64 20 15 10 5 0 20 15 10 5 0 20 15 10 5 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 N = 256 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 N = 128 0.6 0.7 0.8 0.9 1

Figure 2: FFT of a cosine for N = 64, 128, and 256

Example 2: In the the last example the length of x[n] was limited to 3 periods in length.
Now, let’s choose a large value for N (for a transform with many points), and vary the number of repetitions of the fundamental period. n = [0:29]; x1 = cos(2*pi*n/10); % 3 periods x2 = [x1 x1]; % 6 periods x3 = [x1 x1 x1]; % 9 periods N = 2048; X1 = abs(fft(x1,N)); X2 = abs(fft(x2,N)); X3 = abs(fft(x3,N)); F = [0:N-1]/N; subplot(3,1,1) plot(F,X1),title(’3 periods’),axis([0 1 0 50]) subplot(3,1,2) plot(F,X2),title(’6