0.7 Lab 6a - discrete fourier transform and fft (part 1)

Questions or comments concerning this laboratory should be directedto Prof. Charles A. Bouman, School of Electrical and Computer Engineering, Purdue University, West Lafayette IN 47907;(765) 494-0340; bouman@ecn.purdue.edu

Introduction

This is the first week of a two week laboratory that covers the Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT)methods. The first week will introduce the DFT and associated samplingand windowing effects, while thesecond week will continue the discussion of the DFT and introduce the FFT.

In previous laboratories, we have used the Discrete-Time Fourier Transform (DTFT) extensively foranalyzing signals and linear time-invariant systems.

While the DTFT is very useful analytically, it usually cannot be exactlyevaluated on a computer because [link] requires an infinite sum and [link] requires the evaluation of an integral.

The discrete Fourier transform (DFT) is a sampled version of the DTFT, hence it is better suited for numerical evaluation on computers.

Here $X_N\left(k\right)$ is an $N$ point DFT of $x\left(n\right)$ . Note that $X_N\left(k\right)$ is a function of a discrete integer $k$ , where $k$ ranges from 0 to $N-1$ .

In the following sections, we will study the derivation of the DFT from the DTFT,and several DFT implementations. The fastest and most important implementation is known as the fast Fourier transform (FFT). The FFT algorithmis one of the cornerstones of signal processing.

Deriving the dft from the dtft

Truncating the time-domain signal

The DTFT usually cannot be computed exactly because the sum in [link] is infinite. However, the DTFT may be approximately computedby truncating the sum to a finite window. Let $w\left(n\right)$ be a rectangular window of length $N$ :

Then we may define a truncated signal to be

The DTFT of $x_{\mathrm{tr}}\left(n\right)$ is given by:

We would like to compute $X\left(e^{j\omega }\right)$ , but as with filter design, the truncation window distortsthe desired frequency characteristics; $X\left(e^{j\omega }\right)$ and $X_{\mathrm{tr}}\left(e^{j\omega }\right)$ are generally not equal. To understand the relation between these two DTFT's,we need to convolve in the frequency domain (as we did in designing filters with the truncationtechnique):

where $W\left(e^{j\omega }\right)$ is the DTFT of $w\left(n\right)$ . [link] is the periodic convolution of $X\left(e^{j\omega }\right)$ and $W\left(e^{j\omega }\right)$ . Hence the true DTFT, $X\left(e^{j\omega }\right)$ , is smoothed via convolution with $W\left(e^{j\omega }\right)$ to produce the truncated DTFT, $X_{\mathrm{tr}}\left(e^{j\omega }\right)$ .

We can calculate $W\left(e^{j\omega }\right)$ :

For $\omega \ne 0,\pm 2\pi ,...$ , we have:

Notice that the magnitude of this function is similar to $\text{sinc}(\omega N/2)$ except that it is periodic in $\omega$ with period $2\pi$ .

Frequency sampling

[link] contains a summation over a finite number of terms. However, we can only evaluate [link] for a finite set of frequencies, $\omega$ . We must sample in the frequency domain to compute the DTFT on a computer.We can pick any set of frequency points at which to evaluate [link] , but it is particularly useful to uniformly sample $\omega$ at $N$ points, in the range $[0,2\pi )$ . If we substitute