0
$\begingroup$

This wiki page about the DTFT says that the DFT can be obtained from the DTFT by sampling the latter in one cycle at $N$ points:

When the DTFT is continuous, a common practice is to compute an arbitrary number of samples (${{N}}$) of one cycle of the periodic function (${X_{1/T}}$):\begin{align} \underbrace{X_{1/T}\left(\frac{k}{NT}\right)}_{X_k} &= \sum_{n=-\infty}^\infty x[n]\cdot e^{-i 2\pi \frac{kn}{N}} \quad \quad k = 0, \dots, N-1 \\ &= \underbrace{\sum_{N} x_{_N}[n]\cdot e^{-i 2\pi \frac{kn}{N}},}_{DFT}\quad \scriptstyle{\text{(sum over any }n\text{-sequence of length }N)} \end{align} where $x_{_N}$ is a periodic summation: $$x_{_N}[n]\ \triangleq\ \sum_{m=-\infty}^{\infty} x[n-mN]$$

So we essentially have the following equality $$\sum_{n=-\infty}^\infty x[n]\cdot e^{-i 2\pi \frac{kn}{N}}= \sum_{n=0}^{N-1} \sum_{m=-\infty}^{\infty} x[n-mN] e^{-i 2\pi \frac{kn}{N}}. $$

I didn't manage to prove it, is this a known identity?

Improve this question
$\endgroup$
3
  • $\begingroup$ Be very suspicious of that wiki material. If you go back to the definition of what is a periodic sequence and what is the definition of the DFT, you will realize that is impossible to perform the DFT on a periodic sequence. $\endgroup$ – Richard Lyons Feb 8 '20 at 11:51
  • $\begingroup$ I think you're right, the article shouldn't have labeled the quantity over the bracket as a DFT, the DFT is a sum over $x(n)$, not $x_{N}(n)$. $\endgroup$ – Hilbert Feb 8 '20 at 12:13
  • $\begingroup$ No, actually the article is correct. It is a DFT because as jomegA showed below, $x(n)$ is exactly $x_{N}(n)$ over ${0,1,..., N-1}$. $\endgroup$ – Hilbert Feb 8 '20 at 12:19
1
$\begingroup$

The right hand side is the periodic repetition of the left, tells the last equation.

Starting from Fourier transform $$X(\omega)=\sum_{n=-\infty}^{\infty}x(n)e^{-j\omega n}$$ and $X(\omega)$ is periodic with period $2\pi$. So only the samples in the fundamental frequency range are sufficient.

Now we take $N$ equi-distance samples in the iterval $0\leq\omega\leq 2\pi$, so the spacing will be $\dfrac{2\pi}{N}$

Let $k$ be the sample index and $k=0,1,\dots,N-1$ and we evaluate $\omega$ at $\left(\dfrac{2\pi k}{N}\right)$

$$X\left(\dfrac{2\pi}{N}k\right)=\sum_{n=-\infty}^{\infty}x(n)e^{-j2\pi kn/N}$$

which can be written as

$$X\left(\dfrac{2\pi}{N}k\right)=\sum_{l=-\infty}^{\infty}\sum_{n=lN}^{lN+N-1}x(n)e^{-j2\pi kn/N}$$

Now change the index $n$ to $n-lN$ which results in

$$X\left(\dfrac{2\pi}{N}k\right)=\sum_{n=0}^{N-1}\left[\sum_{l=-\infty}^{\infty}x(n-lN)\right]e^{-j2\pi kn/N}$$

The sequence inside the square brackets is the periodic repetition of $x(n)$ of period $N$

$$x_p(n)=\sum_{l=-\infty}^{\infty}x(n-Nl)$$

Thus $$x_p(n)=\begin{cases} x(n),\;\;\;\;0\leq n \leq N-1\\ \\ 0,\;\;\;\;\;\;\;\;\;\;\; \mathrm{elsewhere}\\ \end{cases}$$

Improve this answer
$\endgroup$
9
  • $\begingroup$ Sorry but the question wasn't about the periodization equation, rather about why this equation is true:$$\sum_{n=-\infty}^\infty x[n]\cdot e^{-i 2\pi \frac{kn}{N}}= \sum_{n=0}^{N-1} \sum_{m=-\infty}^{\infty} x[n-mN] e^{-i 2\pi \frac{kn}{N}}. $$ $\endgroup$ – Hilbert Feb 8 '20 at 10:13
  • 1
    $\begingroup$ The equations on the left and right are the same, one is periodic extension of the other. $\endgroup$ – jomegaA Feb 8 '20 at 11:48
  • $\begingroup$ @jomegaA. Is the "sequence inside the brackets" an infinite-length sequence? $\endgroup$ – Richard Lyons Feb 9 '20 at 16:31
  • $\begingroup$ @RichardLyons The sequence $x(n)$ is finite and $x_p(n)$ is periodic extension of it. The index $0\leq n \leq N-1$ is definitely finite. $\endgroup$ – jomegaA Feb 9 '20 at 19:17
  • $\begingroup$ @jomegaA. Hi. I wasn't asking about $x(n)$ or $x_p(n)$. I asked if the "sequence inside the brackets", the summation of $x(n-lN)$, was an infinite-length sequence? Thanks. $\endgroup$ – Richard Lyons Feb 10 '20 at 14:13

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.