(From Shaums DSP outline, 2nd edition, page 248, problem 6.21)

Book says, evaluate the Sum:

$$ S = \sum^{N-1}_{n=0} \Bigg( x_1[n] \ x^{*}_2[n] \Bigg) $$


$$ \begin{aligned} x_1[n] = \cos\left( \frac{2\pi n k_1}{N} \right) \\ \\ x_2[n] = \cos\left( \frac{2\pi n k_2}{N} \right) \end{aligned} $$

using Property:

$$ \sum^{N-1}_{n=0} \Bigg( x_1[n]\ x^{*}_2[n] \Bigg) = \frac{1}{N} \sum^{N-1}_{k=0} \Bigg( X_1[k]\ X_2^{*}[k]\Bigg) $$

I start by converting cosines into complex exponentials:

$$ x_1[n] = \cos\left( \frac{2\pi n k_1}{N} \right) $$

$$ x_1[n] = 0.5e^{j2\pi n k_1 / N} + 0.5e^{-j 2\pi n k_1 / N} $$

Applying Definition of DFT to find: $$ X_1[k] = \sum_{n=0}^{N-1} \Bigg( 0.5e^{j2\pi n k_1 / N} + 0.5e^{-j 2\pi n k_1 / N} \Bigg) e^{-j2\pi nk/N} $$

$$ X_1[k] = \sum_{n=0}^{N-1} \Bigg( 0.5e^{-j(2\pi n/N)(k- k_1)} + 0.5e^{-j(2\pi n/N)(k+ k_1)} \Bigg) $$

From this I determine that sum over one period of a complex exponential is zero, except when k is selected to cancel out exponential function input to zero, such as when $k=k_1$ and $k=-k_1$. Thus:

$$ X_1[k] = \begin{cases} \frac{N}{2}&(k=k_1)\ or\ (k=-k_1) \\ 0 & else \end{cases} $$

By similar means: $$ X_2[k] = \begin{cases} \frac{N}{2}&(k=k_2)\ or\ (k=-k_2) \\ 0 & else \end{cases} $$

Here's where I get lost:

Books says, therefore:

$$ \sum^{N-1}_{n=0} x_{1}[n] x^{*}_{2}[n] = \frac{1}{N}\Bigg[ \frac{N^2}{4} + \frac{N^2}{4} \Bigg] = \frac{N}{2} $$

Where does: $$ \frac{N^2}{4} + \frac{N^2}{4} $$ come from?


1 Answer 1


Actually you have quite done it, but lets indicate.

When the frequencies of both sinusoidal signals $x_1[n]$ and $x_2[n]$ are the same; i.e., $k_1 = k_2 = m$, then the impulses in the corresponding N-point DFT sequences $X_1[k]$ and $X_2[k]$ will occur at the same index $k=m$ and $k=-m$ (or $N-m$) with a weight of $N/2$.

Hence multiplication of $X_1[k]$ with $X_2[k]$ will be $N/2 * N/2 + N/2 * N/2 = N^2/2$, as there are two impulses in the DFT of a cosine signal...

Finally dividing by $N$ yields the result as $N/2$ when the frequencies are the same and $0$ when not.

  • $\begingroup$ would it be: $(1/N)\sum^{N-1}_{k=0}X_{1}[k]X^{*}_{2}[k] = (1/N)(X_{1}[k_1{]}X^{*}_{2}[k_{1}] + X_1[k_{2}]X^{*}_{2}[k_{2}])$ $\endgroup$ Jan 27, 2019 at 22:08
  • $\begingroup$ $X_1[k_1] = N/2$, and $X_2[k_2] = N/2$, when I plug in... I get a mysterious $X_{1}^{*}[k_2]$ and $X_{2}^{*}[k_1]$ that has a value that is not nice and clean.. $\endgroup$ Jan 27, 2019 at 22:14
  • $\begingroup$ actually, $X^*_1[k_2]$ should equal zero for $k_2$? no idea.. its a mystery $\endgroup$ Jan 27, 2019 at 22:20
  • $\begingroup$ assuming $k_1 \ne k_2$ … or maybe its required that $k_1 = k_2$ $\endgroup$ Jan 27, 2019 at 22:26
  • 1
    $\begingroup$ ahh...ok...that's the answer... the product is zero unless $k_1 = k_2$... some type of frequency correlation problem... $\endgroup$ Jan 27, 2019 at 22:27

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.