# Homework Help: DFT of cosine

1. Jun 4, 2013

### Number2Pencil

1. The problem statement, all variables and given/known data

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.

2. Relevant equations

3. 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:

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

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

We can utilize Euler's identity:

$$cos(x) = \frac {e^{jx}+e^{-jx}}{2}$$

$$\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}}$$

Distributing the outside exponential, separating into two summations:

$$\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}$$

Combine terms:

$$\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)}$$

The form of a geometric sum:

$$\sum_{n=0}^{M-1} a^n = \frac{1-a^M}{1-a}$$

In this case:

$$a = e^{j 2 \pi (f-\frac{1}{M}k)}$$

Resulting in:

$$\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)}}$$

There is a specific identity to be used:

$$\frac{1-e^{jaN}}{1-e^{ja}} = \frac{e^{\frac{ja(N-1)}{2}}sin(\frac{aN}{2})}{sin(\frac{a}{2})}$$

In our case:

$$\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}) }$$

Plugging in the original values:

$$\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]}$$

2. Jun 5, 2013

### MisterX

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