0.8 Lab 6b - discrete fourier transform and fft (part 2)  (Page 2/3)

In the following, you will compute the DTFT samples of $x\left(n\right)$ using both $N=50$ and $N=200$ point DFT's. Notice that when $N=200$ , most of the samples of $x\left(n\right)$ will be zeros because $x\left(n\right)=0$ for $n\ge 50$ . This technique is known as “zero padding”, and may be used toproduce a finer sampling of the DTFT.

For $N=50$ and $N=200$ , do the following:

1. Compute the vector x containing the values $x\left(0\right),\cdots ,x(N-1)$ .
2. Compute the samples of $X\left(k\right)$ using your function DTFTsamples .
3. Plot the magnitude of the DTFT samples versus frequency in rad/sample.

The fast fourier transform algorithm

We have seen in the preceding sections that the DFT is a very computationally intensiveoperation. In 1965, Cooley and Tukey ( [link] ) published an algorithm that couldbe used to compute the DFT much more efficiently. Various forms of their algorithm,which came to be known as the fast Fourier transform (FFT), had actually been developed much earlier by other mathematicians (even dating back toGauss). It was their paper, however, which stimulated a revolution in the field of signal processing.

It is important to keep in mind at the outset that the FFT is not a new transform. It is simply a very efficient way to compute an existingtransform, namely the DFT. As we saw, a straight forward implementation of the DFT canbe computationally expensive because the number of multiplies grows as the square of the input length (i.e. $N^2$ for an $N$ point DFT). The FFT reduces this computation using two simple but importantconcepts. The first concept, known as divide-and-conquer,splits the problem into two smaller problems. The second concept, known as recursion, applies this divide-and-conquermethod repeatedly until the problem is solved.

Consider the defining equation for the DFT and assume that $N$ is even, so that $N/2$ is an integer:

Here we have dropped the subscript of $N$ in the notation for $X\left(k\right)$ . We will also use the notation

to denote the $N$ point DFT of the signal $x\left(n\right)$ .

Suppose we break the sum in [link] into two sums, one containing all the terms for which $n$ is even, and one containing all the terms for which $n$ is odd:

We can eliminate the conditions “ $n$ even” and “ $n$ odd” in [link] by making a change of variable in each sum. In the first sum, we replace $n$ by $2m$ . Then as we sum $m$ from 0 to $N/2-1$ , $n=2m$ will take on all even integer values between 0 and $N-2$ . Similarly, in the second sum, we replace $n$ by $2m+1$ . Then as we sum $m$ from 0 to $N/2-1$ , $n=2m+1$ will take on all odd integer values between 0 and $N-1$ . Thus, we can write

Next we rearrange the exponent of the complex exponential in the first sum, and split and rearrange the exponent in the second sum to yield

Now compare the first sum in [link] with the definition for the DFT given by [link] . They have exactly the same form if we replace $N$ everywhere in [link] by $N/2$ . Thus the first sum in [link] is an $N/2$ point DFT of the even-numbered data points in the original sequence. Similarly, the second sumin [link] is an $N/2$ point DFT of the odd-numbered data points in the original sequence. To obtain the $N$ point DFT of the complete sequence, we multiply the DFT of the odd-numbered data pointsby the complex exponential factor $e^{-j2\pi k/N}$ , and then simply sum the two $N/2$ point DFTs.