# How to do DFT of this signal

I am trying to get $$X[k]$$ when $$x[n]$$ is equal to

$$x[n] = \cos\left(\tfrac{\pi}{4}n-\tfrac{\pi}{4}\right)$$

I'm using this equation:

$$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j \frac{2 \pi}{N}kn}$$

but I'm really getting stuck. So far I have done Euler on the cosine and I am now trying to multiply the two exponents I get from this with the exponent on the right hand side of the equation that I have included above but I cannot get it into any form that I can convert using the DFT.

Does anyone know what I can do?

## 2 Answers

A large share of such questions are addressed via known sum of series. With trigonometrics arguments like $$\cos(\alpha n+\beta)$$, one solution is to use Euler/De Moivre formulae:

$$\cos(\alpha n+\beta) = \frac{e^{j(\alpha n+\beta)}+e^{-j(\alpha n+\beta)}}{2}$$

and recognize, under the Fourier sum, two geometric series:

$$\sum_{n=0}^{N-1} \frac{e^{j(\alpha n+\beta)}+e^{-j(\alpha n+\beta)}}{2}e^{-j2\pi kn/N}$$ with terms like :

$$\sum_{n=0}^{N-1}\left( e^{j(\pm\alpha -j2\pi k/N)}\right)^n$$ whose sum is well-known. For a given $$k$$, you have:

\begin{align} \sum_{n=0}^{N-1} e^{\pm j(\alpha n+\beta)}e^{-j2\pi kn/N} &= & e^{\pm j\beta}\sum_{n=0}^{N-1} e^{\pm j\alpha n-j2\pi kn/N}\\ &= & e^{\pm j\beta}\sum_{n=0}^{N-1} e^{j(\pm \alpha -2\pi k/N)n}\\ &= & e^{\pm j\beta}\sum_{n=0}^{N-1} \left(e^{j(\pm \alpha -2\pi k/N)}\right)^n\\ \end{align} and then, noting

$$\rho = e^{j(\pm \alpha -2\pi k/N)}$$ you can get:

$$\sum_{n=0}^{N-1}\rho^n =\begin{cases}N \textrm{ when } \rho=1, \\\frac{1-\rho^N}{1-\rho} \textrm{ when } \rho\neq 1.\end{cases}$$

• Thanks for your answer! Would you be able to tell me how you got from the second to the third equation? – CoderEH Oct 29 '18 at 15:39
• I have combined the above with the $\pm$ sign – Laurent Duval Mar 1 at 20:41

The nature of the DFT values will depend on whether $$N$$ is a multiple of 8. If it is, you will have a whole number of cycles and all the DFT values will be zero except at $$N/4$$ and $$3N/4$$. [Correction: $$N/8$$ and $$7N/8$$]

You can find the math for the exact calculation in my blog article DFT Bin Value Formulas for Pure Real Tones. I use slightly different terminology and a $$1/N$$ normalized DFT, but you should be able to follow along.

In your case $$\alpha = \pi / 4$$ and $$\phi = -\pi / 4$$. You can jump to equations (23)-(25) if $$N$$ is not a multiple of 8, otherwise use equation (19).

Yes, this approach uses Euler's equation and the geometric summation formula so you were on the right approach.

• Thanks for your response! How come N should be a multiple of 8 for this to be true? Did you deduce this from something in my question or is it always the case? – CoderEH Oct 29 '18 at 15:57
• @CoderEH, It is because $\pi / 4$ is one eighth the way around the unit circle. Thus, your signal is periodic at 8 samples. A DFT of a pure tone with a whole number of cycles in the sample frame is qualitatively different than a fractional number of cycles. It is a special case. – Cedron Dawg Oct 29 '18 at 16:22
• Thanks, so if I had $\pi / 5$ then I would be looking to see if N=10? – CoderEH Oct 29 '18 at 16:29
• @CoderEH, Correct, or a multiple of 10. The key is if there are a whole number of cycles in the sample frame. – Cedron Dawg Oct 29 '18 at 16:35