2

I'm finding it hard to find a derivation of the DFT from books, was wondering if someone can point me to some resources or attempt to explain it here.

chutsu
  • 276
  • 1
    Derivation... from what? For instance, there is a way to see DFT as an approximation to Fourier series. There's also a way to see DFTs as a special kind of change-of-basis of a finite-dimensional vector space. – Zhen Lin Mar 14 '11 at 19:11
  • I would like the derivation of the DFT as an approximation to the Fourier Series. Thanks – chutsu Mar 18 '11 at 15:06

1 Answers1

2

Sorry. I really can't answer the question on dummies' level. But here is a possible explanation.

A periodic function $f:[0,2\pi]\to \mathbb{R}$ is sampled at $N+1$ equidistant nodes $x_j=j{2\pi\over N},j=0,1,\ldots ,N$: $v_j=f(x_j)$. We try to write $f(x)$ as Fourier series: $f(x)\approx {1\over 2\pi}\sum_{k=-N/2}^{N/2} \hat{v}_k e^{\imath kx}$.

Now I want to show you $\hat{v}_k={2\pi\over N}\sum_{j=1}^N v_j e^{-\imath kx_j}$, which is exactly the discrete Fourier transform.

Take $x=x_j$ and summation of $j$ from $1$ to $N$, then use the discrete orthogonality from here, you will get it.

user33869
  • 1,040