3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • 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
    Commented Oct 29, 2018 at 15:39
  • $\begingroup$ I have combined the above with the $\pm$ sign $\endgroup$ Commented Mar 1, 2021 at 20:41
0
$\begingroup$

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.

$\endgroup$
4
  • $\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
    Commented Oct 29, 2018 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$ Commented Oct 29, 2018 at 16:22
  • $\begingroup$ Thanks, so if I had $\pi / 5$ then I would be looking to see if N=10? $\endgroup$
    – CoderEH
    Commented Oct 29, 2018 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$ Commented Oct 29, 2018 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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