2
$\begingroup$

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.

  • 0
    I would like the derivation of the DFT as an approximation to the Fourier Series. Thanks2011-03-18

1 Answers 1

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.