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

for $k=0,1,...(N-1)$ in [link] , we find that

In short, the DFT values result from sampling the DTFT of the truncated signal.

Windowing effects

Download DTFT.m for the following section.

We will next investigate the effect of windowing when computing the DFT of the signal $x\left(n\right)=cos\left(\frac{\pi }{4},n\right)$ truncated with a window of size $N=20$ .

1. In the same figure, plot the phase and magnitude of $W\left(e^{j\omega }\right)$ , using equations [link] and [link] .
2. Determine an expression for $X\left(e^{j\omega }\right)$ (the DTFT of the non-truncated signal).
3. Truncate the signal $x\left(n\right)$ using a window of size $N=20$ and then use DTFT.m to compute $X_{\mathrm{tr}}\left(e^{j\omega }\right)$ . Make sure that the plot contains a least 512 points.
   Hint Use the command [X,w] = DTFT(x,512) .
4. Plot the magnitude of $X_{\mathrm{tr}}\left(e^{j\omega }\right)$ .

Inlab report

1. Submit the plot of the phase and magnitude of $W\left(e^{j\omega }\right)$ .
2. Submit the analytical expression for $X\left(e^{j\omega }\right)$ .
3. Submit the magnitude plot of $X_{\mathrm{tr}}\left(e^{j\omega }\right)$ .
4. Describe the difference between $|X_{\mathrm{tr}}\left(e^{j\omega }\right)|$ and $\left|X\right(e^{j\omega }\left)\right|$ . What is the reason for this difference?
5. Comment on the effects of using a different window for $w\left(n\right)$ . For example, what would you expect your plots to look like if youhad used a Hamming window in place of the truncation (rectangular) window?(See [link] for a plot of a Hamming window of length 20 and its DTFT.)

The discrete fourier transform

Computing the dft

We will now develop our own DFT functions to help our understanding of how the DFT comes from the DTFT.Write your own Matlab function to implement the DFT of equation [link] . Use the syntax

X = DFTsum(x)

where x isan $N$ point vector containing the values $x\left(0\right),\cdots ,x(N-1)$ and X is the corresponding DFT.Your routine should implement the DFT exactly as specified by [link] using for-loops for $n$ and $k$ , and compute the exponentials as they appear.Note: In Matlab, "j" may be computed with the command j=sqrt(-1) . If you use $j=\sqrt{-1}$ , remember not to use j as an index in your for-loop .

Test your routine DFTsum by computing $X_N\left(k\right)$ for each of the following cases:

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

Plot the magnitude of each of the DFT's. In addition, derive simple closed-form analytical expressions for theDFT (not the DTFT!) of each signal.

Inlab report

1. Submit a listing of your code for DFTsum .
2. Submit the magnitude plots.
3. Submit the corresponding analytical expressions.

Write a second Matlab function for computing the inverse DFT of [link] . Use the syntax

x = IDFTsum(X)

where X is the $N$ point vector containing the DFT and x is the corresponding time-domain signal. Use IDFTsum to invert each of the DFT's computed in the previous problem. Plot the magnitudes of the inverted DFT's,and verify that those time-domain signals match the original ones. Use abs(x) to eliminate any imaginary parts which roundoff error may produce.

Inlab report

1. Submit the listing of your code for IDFTsum .
2. Submit the four time-domain IDFT plots.

Matrix representation of the dft

The DFT of [link] can be implemented as a matrix-vector product. To see this, consider the equation

where $\mathbf{A}$ is an $N\times N$ matrix, and both $X$ and $x$ are $N\times 1$ column vectors. This matrix product is equivalent to the summation

where ${\mathbf{A}}_{kn}$ is the matrix element in the $k^{th}$ row and $n^{th}$ column of A .By comparing [link] and [link] we see that for the DFT,

The $-1$ 's are in the exponent because Matlab indices start at 1, not 0. For this section, we need to:

• Write a Matlab function A = DFTmatrix(N) that returns the NxN DFT matrix A.
  Remember that the symbol $*$ is used for matrix multiplication in Matlab, and that ${.}^{\text{'}}$ performs a simple transpose on a vector or matrix. An apostrophe without the period is a conjugate transpose.
• Use the matrix A to compute the DFT of the followingsignals. Confirm that the results are the same as in the previous section.
  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. Print out the matrix $\mathbf{A}$ for $N=5$ .
2. Hand in the three magnitude plots of the DFT's.
3. How many multiplies are required to compute an $N$ point DFT using the matrix method?(Consider a multiply as the multiplication of either complex or real numbers.)

As with the DFT, the inverse DFT may also be represented as a matrix-vector product.

For this section,

1. Write an analytical expression for the elements of the inverse DFT matrix $\mathbf{B}$ , using the form of [link] .
2. Write a Matlab function B = IDFTmatrix(N) that returns the NxN inverse DFT matrix B.
3. Compute the matrices $\mathbf{A}$ and $\mathbf{B}$ for $N=5$ . Then compute the matrix product $\mathbf{C}=\mathbf{B}\mathbf{A}$ .

Inlab report

1. Hand in your analytical expression for the elements of $\mathbf{B}$ .
2. Print out the matrix $\mathbf{B}$ for $N=5$ .
3. Print out the elements of $\mathbf{C}=\mathbf{B}\mathbf{A}$ . What form does $\mathbf{C}$ have? Why does it have this form?

Computation time comparison

Click here for help on the cputime function.

Although the operations performed by DFTsum are mathematically identical to a matrix product, the computation times for these two DFT's in Matlab are quite different.(This is despite the fact that the computational complexity of two procedures is of the same order!)This exercise will underscore why you should try to avoid using for loops in Matlab, and wherever possible, try to formulate your computations using matrix/vector products.

To see this, do the following:

1. Compute the signal $x\left(n\right)=cos(2\pi n/10)$ for $N=512$ .
2. Compute the matrix $\mathbf{A}$ for $N=512$ .
3. Compare the computation time of X = DFTsum(x) with a matrix implementation X = A*x by using the cputime function before and after the program execution. Do not include the computation of A in your timing calculations.