离散傅里叶变换公式推导

先抛变换公式：
$F_m=\sum_{n=0}^{N-1}f_ne^{-2\pi imn/N}\leftrightarrow f_n=\frac{1}{N}\sum_{m=0}^{N-1}F_me^{2\pi imn/N}$
式中的N是数据点个数
讲道理一开始完全看不懂公式这么来的，一顿百度后我学到了很多，但就是没学到怎么推公式。好吧只能自己推。
先来看一下DFT的物理意义： DFT示意图
（图我网上随便下的）
离散傅里叶变换是把周期性离散信号变换到频域上，大家知道，周期信号变到频域上是离散的。离散就是在个别点 ${x_n\}$ 有值。我是学物理的，物理里面离散的可以这么表示：
$f(x)=\sum_{n=0}^{N-1}f_n\delta(x-x_n)$
$\delta(x)$ 是个在 $x = 0$ 处无穷大，其余位置为0且全空间积分为1的函数 $\int_{-\infty}^{\infty}\delta(x)dx=1$

周期性信号变到频域上，那不就是傅里叶级数吗。自然有公式
$\begin{aligned} F_m &= \int_{-T}^{T}\sum_{n=0}^{N-1}f_n\delta(x-x_n)e^{-ixk_m}dx \\&=\sum_{n=0}^{N-1}\int f_n\delta(x-x_n)e^{-ixk_m}dx \\&=\sum_{n=0}^{N-1}f_ne^{-ix_nk_m} \end{aligned}$
接下来我们假设 $d x, d k$ 分别是 ${x_n\}$ , ${k_n\}$ 的间距，那么：
$x_n=ndx,\qquad k_m = mdk$
代入上式：
$\begin{aligned} F_m &=\sum_{n=0}^{N-1}f_ne^{-ix_nk_m} \\&=\sum_{n=0}^{N-1}f_ne^{-imndxdk} \end{aligned}$
是不是和最上面的式子很接近了？还差最后一步，确定 $d x d k$ 的值。
下面我懒得写了，只说一下做法吧

先写出 $F_m$ 到 $f_n$ 的逆变换，
$f_n = c\sum_{n=0}^{N-1}F_me^{imndxdk}$
$c$ 是个系数，之后应该能计算出是 $1 / N$
把上面的 $F_m$ 表达式带进去,就能得到用 $f_{n’}$ 求和表达的 $f_n$ ,这要求 $d x d k$ 满足一定关系，其实就是满足 $\frac{2\pi}{N}$
最后把公式里的 $d x d k$ 替换就完事了