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?


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

  • 1
    $\begingroup$ Thanks for your answer! Would you be able to tell me how you got from the second to the third equation? $\endgroup$ – CoderEH Oct 29 '18 at 15:39
  • $\begingroup$ I have combined the above with the $\pm$ sign $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – CoderEH Oct 29 '18 at 15:57
  • $\begingroup$ @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. $\endgroup$ – Cedron Dawg Oct 29 '18 at 16:22
  • $\begingroup$ Thanks, so if I had $\pi / 5$ then I would be looking to see if N=10? $\endgroup$ – CoderEH Oct 29 '18 at 16:29
  • 1
    $\begingroup$ @CoderEH, Correct, or a multiple of 10. The key is if there are a whole number of cycles in the sample frame. $\endgroup$ – Cedron Dawg Oct 29 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.