Computing M Sample DFT by Hand

[Number2Pencil]

Homework Statement

Compute the M sample DFT of:

f(m) = cos(2*pi*(f*m)) for 0 <= m <= M-1

where M = 128, f = 1/16

This should be done by hand, and the solution will reduce to a very simple form.

Homework Equations

The Attempt at a Solution

I slaved through this problem and got an answer that seems to have the same shape and magnitude as the dft function in MATLAB, but it is not what I'd consider a "very simple form." Could you please check my work and see if there is any major simplifications I missed?

First, we look at the generic formula for the DFT:

<br /> \tilde{x(k)} = \sum_{n=0}^{N-1} x(n) e^{\frac{-j 2 \pi k n}{N}}<br />

where x(k) is the frequency values at normalized frequency k, x(n) is the input sample, and N is the number of samples taken. For this problem, this formula is:
<br /> \tilde{f(k)} = \sum_{n=0}^{M-1} cos(2 \pi f_x n) e^{\frac{-j 2 \pi k n}{M}}<br />


We can utilize Euler's identity:

<br /> cos(x) = \frac {e^{jx}+e^{-jx}}{2}<br />

<br /> \tilde{f(k)} = \sum_{n=0}^{M-1} (\frac{e^{j2 \pi f_x n}+e^{-j 2 \pi f_x n}}{2}) e^{\frac{-j 2 \pi k n}{M}}<br />

Distributing the outside exponential, separating into two summations:

<br /> \tilde{f(k)} <br /> = \sum_{n=0}^{M-1} <br /> <br /> \frac<br /> {e^{j 2 \pi f_x n}e^{-j 2 \pi k \frac{1}{M}n}}<br /> {2}<br /> <br /> +<br /> = \sum_{n=0}^{M-1} <br /> \frac<br /> {e^{-j 2 \pi f_x n}e^{-j2 \pi k \frac{1}{M}n}}<br /> {2}<br /> <br />

Combine terms:

<br /> \tilde{f(k)} <br /> = \sum_{n=0}^{M-1}<br /> \frac{1}{2}<br /> e^{j 2 \pi n (f-\frac{1}{M}k)} <br /> +<br /> = \sum_{n=0}^{M-1}<br /> \frac{1}{2}<br /> e^{-j 2 \pi n (f+\frac{1}{M}k)} <br />

The form of a geometric sum:

<br /> \sum_{n=0}^{M-1} a^n = \frac{1-a^M}{1-a}<br />

In this case:

<br /> a = e^{j 2 \pi (f-\frac{1}{M}k)}<br />

Resulting in:


<br /> \tilde{f(k)} = \frac{1}{2}<br /> \frac<br /> {1 - e^{j2 \pi (f-\frac{1}{M}k)M}}<br /> {1-e^{j2 \pi (f - \frac{1}{M}k)}}<br /> <br /> + \frac{1}{2}<br /> \frac<br /> {1-e^{-j 2 \pi (f+\frac{1}{M}k)M}}<br /> {1-e^{-j 2 \pi (f+\frac{1}{M}k)}}<br />

There is a specific identity to be used:

<br /> \frac{1-e^{jaN}}{1-e^{ja}} = \frac{e^{\frac{ja(N-1)}{2}}sin(\frac{aN}{2})}{sin(\frac{a}{2})}<br />

In our case:

<br /> \tilde{x(k)} = \frac{1}{2}<br /> \frac{<br /> e^{\frac{[j2 \pi (f-\frac{1}{M}k)][M-1]}{2}}<br /> sin(\frac{[2 \pi (f-\frac{1}{M}k)]M}{2})}<br /> {<br /> sin(\frac{2 \pi (f-\frac{1}{M}k)}{2})<br /> } +<br /> <br /> \frac{1}{2}<br /> \frac{<br /> e^{\frac{[-j2 \pi (f+\frac{1}{M}k)][M-1]}{2}}<br /> sin(\frac{[-2 \pi (f+\frac{1}{M}k)]M}{2})}<br /> {<br /> sin(\frac{-2 \pi (f+\frac{1}{M}k)}{2})<br /> }<br />

Plugging in the original values:

<br /> \tilde{f(x)} = \frac{1}{2}e^{127 j \pi (\frac{1}{16}-\frac{1}{128}k)}<br /> \frac<br /> {sin[128 \pi (\frac{1}{16} - \frac{1}{128}k)]}<br /> {sin[\pi (\frac{1}{16} - \frac{1}{128}k)]}<br /> +<br /> \frac{1}{2}e^{-j 127 \pi (\frac{1}{16}+\frac{1}{128}k)}<br /> \frac<br /> {sin[128 \pi (\frac{1}{16}+\frac{1}{128}k)]}<br /> {sin[\pi (\frac{1}{16}+\frac{1}{128}k]}<br />

 

[MisterX]

Return to the sum of the geometric series. Consider the case that f = \frac{\ell}{M} where \ell is an integer.