8
$\begingroup$

If $x[k]$ and $X[r] $ are the pair of discrete time Fourier sequences, where $x[k]$ is the discrete time sequence and $X[r]$ is its corresponding DFT. Prove that the energy of the aperiodic sequence $x[k]$ of length $N$ can be expressed in terms of its $N$-point DFT as follows:

$$E_x=\sum_{k=0}^{N-1}|x[k]|^2=\frac{1}{N}\sum_{r}^{N-1}|X[r]|^2.$$

Could anyone one help me with this prove? Thanks.

$\endgroup$
  • $\begingroup$ Note that the DFT is an unitary transformation. $\endgroup$ – chaohuang Mar 31 '13 at 0:56
  • $\begingroup$ In the middle expression, replace one of the $x[k]$ by the weighted sum of $X[r]$'s as specified in the inverse DFT formula. Then, interchange order of summation. For details of this idea for Fourier transforms (where integrals instead of sums are involved), see this answer. $\endgroup$ – Dilip Sarwate Mar 31 '13 at 3:09
11
$\begingroup$

The proof is straightforward. Assume that $X$ and $x$ are related as follows:

$$X[r] = \sum_{k=0}^{N-1} x[k]\, e^{i 2 \pi k r /N}$$

Then

$$|X[r]|^2 = \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k-k') r /N}$$

and

$$\begin{align}\sum_{r=0}^{N-1}|X[r]|^2 &= \sum_{r=0}^{N-1} \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k-k') r /N} \\ &= \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, \sum_{r=0}^{N-1} e^{i 2 \pi (k-k') r /N} \end{align}$$

The inner sum is a geometric series and has the value

$$\sum_{r=0}^{N-1} e^{i 2 \pi (k-k') r /N} = \frac{e^{i 2 \pi (k-k')}-1}{e^{i 2 \pi (k-k')/N}-1}$$

Note that the RHS is zero unless $k=k'$; in that case, you should be able to see that the sum is simply $N$. We then write

$$\sum_{r=0}^{N-1} e^{i 2 \pi (k-k') r /N} = N \delta_{kk'}$$

where $\delta_{kk'}$ is $0$ when $k \ne k'$ and $1$ when $k=k'$. Therefore

$$\sum_{r=0}^{N-1}|X[r]|^2 = N \sum_{k=0}^{N-1} |x[k]|^2$$

and Parseval's theorem follows.

$\endgroup$
  • $\begingroup$ why $$|X[r]|^2 = \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k-k') r /(N-1)}$$, but not $$|X[r]|^2 = \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k+k') r /(N-1)}$$? Thanks. $\endgroup$ – Cheung Apr 2 '13 at 0:00
  • $\begingroup$ Because of the complex conjugation. $\endgroup$ – Ron Gordon Apr 2 '13 at 0:06
  • $\begingroup$ Thank you Ron. You help me a lot. $\endgroup$ – Cheung Apr 2 '13 at 0:53
  • $\begingroup$ Isn't the relationship $X[r]=\sum\limits_{k=0}^{N-1}x[k]e^{-i2\pi kr/N}$? $\endgroup$ – Alejandro May 10 '16 at 6:31
  • $\begingroup$ @Alejandro: it doesn't matter. $\endgroup$ – Ron Gordon May 10 '16 at 7:05

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.