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:

[tex]
\tilde{x(k)} = \sum_{n=0}^{N-1} x(n) e^{\frac{-j 2 \pi k n}{N}}
[/tex]

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:
[tex]
\tilde{f(k)} = \sum_{n=0}^{M-1} cos(2 \pi f_x n) e^{\frac{-j 2 \pi k n}{M}}
[/tex]


We can utilize Euler's identity:

[tex]
cos(x) = \frac {e^{jx}+e^{-jx}}{2}
[/tex]

[tex]
\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}}
[/tex]

Distributing the outside exponential, separating into two summations:

[tex]
\tilde{f(k)}
= \sum_{n=0}^{M-1}

\frac
{e^{j 2 \pi f_x n}e^{-j 2 \pi k \frac{1}{M}n}}
{2}

+
= \sum_{n=0}^{M-1}
\frac
{e^{-j 2 \pi f_x n}e^{-j2 \pi k \frac{1}{M}n}}
{2}

[/tex]

Combine terms:

[tex]
\tilde{f(k)}
= \sum_{n=0}^{M-1}
\frac{1}{2}
e^{j 2 \pi n (f-\frac{1}{M}k)}
+
= \sum_{n=0}^{M-1}
\frac{1}{2}
e^{-j 2 \pi n (f+\frac{1}{M}k)}
[/tex]

The form of a geometric sum:

[tex]
\sum_{n=0}^{M-1} a^n = \frac{1-a^M}{1-a}
[/tex]

In this case:

[tex]
a = e^{j 2 \pi (f-\frac{1}{M}k)}
[/tex]

Resulting in:


[tex]
\tilde{f(k)} = \frac{1}{2}
\frac
{1 - e^{j2 \pi (f-\frac{1}{M}k)M}}
{1-e^{j2 \pi (f - \frac{1}{M}k)}}

+ \frac{1}{2}
\frac
{1-e^{-j 2 \pi (f+\frac{1}{M}k)M}}
{1-e^{-j 2 \pi (f+\frac{1}{M}k)}}
[/tex]

There is a specific identity to be used:

[tex]
\frac{1-e^{jaN}}{1-e^{ja}} = \frac{e^{\frac{ja(N-1)}{2}}sin(\frac{aN}{2})}{sin(\frac{a}{2})}
[/tex]

In our case:

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

\frac{1}{2}
\frac{
e^{\frac{[-j2 \pi (f+\frac{1}{M}k)][M-1]}{2}}
sin(\frac{[-2 \pi (f+\frac{1}{M}k)]M}{2})}
{
sin(\frac{-2 \pi (f+\frac{1}{M}k)}{2})
}
[/tex]

Plugging in the original values:

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

 

[MisterX]

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