Main: Main Lab Page

Lab 5 - The Fast Fourier Transform (FFT)

To be submitted along with Lab 4

Due date Nov 3, 2000

Objectives

The FFT is a fast way of calculating the Discrete Fourier Transform (DFT). The spectral components of the FFT are samples of the continuous DTFT of a signal. In some cases it may be desireable to add zeros to the end of a signal (zero-pad) before taking its FFT. Zero-padding causes the DFT to give more closely spaced samples of the DTFT. While zero-padding does not increase the ability to resolve closely spaced frequencies, it does give a better idea of the true shape of the DTFT of the signal. Failure to zero-pad a signal may give misleading information about its spectrum. This will particularly be the case when the frequency of the sinusoid of the signal falls between DFT samples.

In order to better resolve frequencies in a signal, the length of the window should be increased. In other words, the signal should be examined over a longer period of time.

Another fundamental issue of the FFT is resolution and leakage which is determined by the choice of the truncating window. Resolution is the ability to distinguish between two sinusoids that are very closely spaced in frequency. Leakage is when components at one frequency are spread into other frequencies and affect the components at those frequencies. If a signal contains 2 closely spaced sinusoids, leakage may cause the peak produced by each sinusoid to merge into one if the proper window is not selected to truncate the signal. This will cause the FFT to indicate that a single sinusoid is present instead of 2.

J-DSP

Use J-DSP once again for this lab. The program requires Netscape 4.6 (or higher). Push the ``Start'' button below to begin.

Your browser does not recognize the applet tag.

Problem 1: Real and Imaginary FFT's

In this problem, determine what type of signal of length N will have an N-point FFT whose real or imaginary part is zero.

1. Generate the given signals in J-Dsp and plot the magnitude and phase of the FFT of size N=8 and use a linear scale. Name the plots of X₁[k], X₂[k], X₃[k] and X₄[k] as graph1, graph2, graph3, graph4 respectively.
2. For which of these FFTs is the real (imaginary) part zero? ( Use FFT and Plot block.) Make the plot discrete and look and the real part, then the imaginary part.

Note: In the Signal Generator Dialog Box you find a button, labeled ``Edit''. Pushing the button allows you to specify the input signal. Just enter the index and the desired new value in the dialog window and then push update. The new value is shown in the table.

QUIZ QUESTIONS

1.1 For which of the signals is the real part of the FFT zero?
a) x₁[n]
b) x₂[n]
c) x₃[n]
d) x₄[n]

1.2 For which of the signals is the imaginary part of the FFT zero?
a) x₁[n]
b) x₂[n]
c) x₃[n]
d) x₄[n]

Problem 2: Zero-padding and windowing

In this problem we will take a 128 point FFT of a sinusoidal signal. In one case, the 128 points will be the first 128 points of the sinusoidal signal. In the second case, the first 64 points will be the first 64 of the sinusoid and the last 64 will be zeros. We will compare the results.

While doing this problem, condider the following 2 questions.

• Why is the shape of the FFT different when different length windows are used?
• The DTFT of these 2 signals will have a peak that occurs at different frequencies but has the same magnitude. Will the peaks of the FFT of these two signals also have the same magnitude? To determine this, use the "Values" button in the plot dialog box.

Generate a sine wave of amplitude 1 with (a) and (b) .

Window the sine wave with a

• (i) rectangular window of length 64 samples
• (ii) rectangular window of length 128 samples

and plot the FFT of size N=128 for all four cases (use decibel scaling). Why is the shape of the FFT different?

• (i) for case I. (a) and (i) name the graph as graph5. Use decibel scaling.
• (ii) for case II. (a) and (ii)name the graph as graph6 Use decibel scaling.
• (iii) for case III. (b) and (i) save graph as graph7 Use decibel scaling.
• (iv) for case IV. (b) and (iii) save graph as graph8 Use decibel scaling.

QUIZ QUESTIONS

2.1 Why is the peak of the magnitude of the FFT greater for one of the sinusoids?
a) The peaks of the two are actually exactly the same.
b) The frequency of one of the sinusoids is closer to the nearest DFT frequency than the other.

2.2 When is the peak in the frequency domain higher?
a) When the window length is 64.
b) When the window lenght is 128.

Problem 3:

Generate a triangular pulse with amplitude 1 and length 16 samples. Plot the FFT of size N=8, 16, 32, 64, 128, 256 (use linear magnitude scaling). Observe and explain any differences in the graphs. Consider the following questions:

• What appears to be the maximum value of N at which further increasing N does not provide any new information about the shape of the DTFT?
• What is the minimum value of N for which the trianglar pulse can be recovered?

Name the graphs as follows. Be sure to use linear magnitude scaling.
• N=8 - graph9
• N=16 - graph10
• N=32 - graph11
• N=64 - graph12
• N=128 - graph13
• N=256 - graph14

QUIZ QUESTIONS

3.1 What is the maximum value of N at which further increasing N does not provide any new information about the shape of the DTFT?
a) N=8.
b) N=16.
c) N=32.
d) N=64.

3.2 The triangular signal can be recovered from its 8 point FFT?
a) True
b) False

Problem 4: Resolution and Leakage

The following signal is the sum of two signals which are closely spaced in frequency.

Window x[n] with a

• (i) rectangular window of length 128 samples
• (ii) Hamming window of length 128 samples

and plot the FFT of size N=128 for both cases (use decibel scaling). Save the plot in case (i) as graph15 and the plot in part (ii) as graph16. Why is the shape of the FFT different? Which window would you choose? Is either of these windows able to indicate the presences of 2 sinusoids? Does the spectral leakage due to either one of these windows cause the two spectral peaks to merge into one?

QUIZ QUESTIONS

4.1 Which window is able to resolve the 2 sinusoids?
a) Rectangular
b) Hamming

4.2 Why is the window mentioned in the previous problem able to resolve the two sinusoids?
a) It has smaller side lobes.
b) It has a narrower main lobe.

Main: Main Lab Page

Copyright 2000 Andreas Spanias, MIDL, Arizona State University JDSP and Report Submission Software Developed by ASU-MIDL For questions contact Prof. Spanias spanias@asu.edu.