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

To summarize, we will rewrite [link] according to this interpretation.First, we define two new $N/2$ point data sequences $x_0\left(n\right)$ and $x_1\left(n\right)$ , which contain the even and odd-numbered datapoints from the original $N$ point sequence, respectively:

where $n=0,...,N/2-1$ . This separation of even and odd points is called decimation in time . The $N$ point DFT of $x\left(n\right)$ is then given by

where $X_0\left(k\right)$ and $X_1\left(k\right)$ are the $N/2$ point DFT's of the even and odd points.

While [link] requires less computation than the original $N$ point DFT, it can still be further simplified.First, note that each $N/2$ point DFT is periodic with period $N/2$ . This means that we need to only compute $X_0\left(k\right)$ and $X_1\left(k\right)$ for $N/2$ values of $k$ rather than the $N$ values shown in [link] . Furthermore, the complex exponential factor $e^{-j2\pi k/N}$ has the property that

These two facts may be combined to yield a simpler expression for the $N$ point DFT:

where the complex constants defined by $W_N^k=e^{-j2\pi k/N}$ are commonly known as the twiddle factors .

[link] shows a graphical interpretation of [link] which we will refer to as the “divide-and-conquer DFT”. We start on the left side with the data separated intoeven and odd subsets. We perform an $N/2$ point DFT on each subset, and then multiply the output of the odd DFT by the required twiddlefactors. The first half of the output is computed by addingthe two branches, while the second half is formed by subtraction.This type of flow diagram is conventionally used to describe a fast Fourier transform algorithm.

Implementation of divide-and-conquer dft

In this section, you will implement the DFT transformationusing [link] and the illustration in [link] . Write a Matlab function with the syntax

X = dcDFT(x)

where x is a vector of even length $N$ , and X is its DFT. Your function dcDFT should do the following:

1. Separate the samples of x into even and odd points.
   Hint The Matlab command x0 = x(1:2:N) can be used to obtain the “even” points.
2. Use your function DFTsum to compute the two $N/2$ point DFT's.
3. Multiply by the twiddle factors $W_N^k=e^{-j2\pi k/N}$ .
4. Combine the two DFT's to form $X$ .

Test your function dcDFT by using it to compute the DFT's of the following signals.

1. $x\left(n\right)=\delta \left(n\right)$ for $N=10$
2. $x\left(n\right)=1\text{for}N=10$
3. $x\left(n\right)=e^{j2\pi n/N}$ for $N=10$

Inlab report

1. Submit the code for your function dcDFT .
2. Determine the number of multiplies that are required in this approach to computing an $N$ point DFT. (Consider a multiply to be one multiplication ofreal or complex numbers.)
   HINT Refer to the diagram of [link] , and remember to consider the $N/2$ point DFTs.

Recursive divide and conquer

The second basic concept underlying the FFT algorithm is that of recursion. Suppose $N/2$ is also even. Then we may apply the same decimation-in-timeidea to the computation of each of the $N/2$ point DFT's in [link] . This yields the process depicted in [link] . We now have two stages of twiddle factorsinstead of one.

How many times can we repeat the process of decimating the input sequence? Suppose $N$ is a power of 2, i.e. $N=2^p$ for some integer $p$ . We can thenrepeatedly decimate the sequence until each subsequence contains only two points.It is easily seen from [link] that the 2 point DFT is a simple sum and difference of values.

[link] shows the flow diagram that results for an 8 point DFT when we decimate 3 times.Note that there are 3 stages of twiddle factors (in the first stage, the twiddle factors simplify to “1”).This is the flow diagram for the complete decimation-in-time 8 point FFT algorithm.How many multiplies are required to compute it?

Write three Matlab functions to compute the 2, 4, and 8 point FFT's using the syntax

X = FFT2(x)

X = FFT4(x)

X = FFT8(x)

The function FFT2 should directly compute the 2-point DFT using [link] , but the functions FFT4 and FFT8 should compute their respective FFT's using the divide and conquer strategy.This means that FFT8 should call FFT4 , and FFT4 should call FFT2 .

Test your function FFT8 by using it to compute the DFT's of the following signals. Compare these results to the previous ones.

1. $x\left(n\right)=\delta \left(n\right)$ for $N=8$
2. $x\left(n\right)=1\text{for}N=8$
3. $x\left(n\right)=e^{j2\pi n/8}$ for $N=8$

Inlab report

1. Submit the code for your functions FFT2 , FFT4 and FFT8 .
2. List the output of FFT8 for the case $x\left(n\right)=1$ for $N=8$ .
3. Calculate the total number of multiplies by twiddle factors required for your 8 point FFT. (A multiply is a multiplication by a real or complexnumber.)
4. Determine a formula for the number of multiplies required for an $N=2^p$ point FFT. Leave the expression in terms of $N$ and $p$ . How does this compare to the number of multiplies requiredfor direct implementation when p=10?

If you wrote the FFT4 and FFT8 functions properly, they should have almost the exact same form. The only difference between them is the length of the input signal,and the function called to compute the (N/2)-pt DFTs. Obviously, it's redundant to write a separate function for each specificlength DFT when they each have the same form. The preferred method is to write a recursive function, which means that the function calls itself within the body. It is imperative that a recursive function has a condition for exiting withoutcalling itself, otherwise it would never terminate.

Write a recursive function X=fft_stage(x) that performs one stage of the FFT algorithm for a power-of-2 length signal.An outline of the function is as follows:

1. Determine the length of the input signal.
2. If N=2, then the function should just compute the 2-pt DFT as in [link] , and then return.
3. If N>2, then the function should perform the FFT steps described previously (i.e. decimate, compute (N/2)-pt DFTs, re-combine),calling fft_stage to compute the (N/2)-pt DFTs.

Note that the body of this function should look very similar to previous functions written in this lab.Test fft_stage on the three 8-pt signals given above, and verify that it returns the same results as FFT8 .