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?

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

$\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$ 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$ 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.