【通信原理| DFT】 从数学和代码角度理解离散傅里叶变换

首先， 有DFT公式， 通过欧拉公式 e j x = cos ⁡ ( x ) + j sin ⁡ ( x ) e^{jx} = \cos(x)+j\sin(x) ejx=cos(x)+jsin(x)：

X ( k ) = ∑ n = 0 N − 1 x ( n ) ⋅ e − i 2 π N k n = ∑ n = 0 N − 1 x ( n ) ⋅ [ cos ⁡ ( 2 π N k n ) + i ⋅ sin ⁡ ( 2 π N k n ) ] \begin{aligned} X(k) &=\sum_{n=0}^{N-1} x(n) \cdot e^{-\frac{i 2 \pi}{N} k n} \\ &=\sum_{n=0}^{N-1} x(n) \cdot\left[\cos \left(\frac{2 \pi}{N} k n\right)+i \cdot \sin \left(\frac{2 \pi}{N} k n\right)\right] \end{aligned} X(k)​=n=0∑N−1​x(n)⋅e−Ni2π​kn=n=0∑N−1​x(n)⋅[cos(N2π​kn)+i⋅sin(N2π​kn)]​

先不考虑虚数项， 考察当 k = 1 k=1 k=1时，即 X ( 1 ) = ∑ n = 0 N − 1 x ( n ) ⋅ cos ⁡ ( 2 π N n ) ， X(1) = \sum_{n=0}^{N-1} x(n) \cdot \cos \left(\frac{2 \pi}{N} n\right)， X(1)=n=0∑N−1​x(n)⋅cos(N2π​n)，

也就是说， DFT的本质是将信号对余弦函数做相关（对应每项相乘后相加）。 众所周知， 任何信号波形都可以分解成 各种频率 的余弦波之和， 那么DFT就是用于获取该波形在每种频率上的分量， 也就是相关的结果， 也就是不同 k k k对应的 X ( k ) X(k) X(k)。

再看 X ( K ) X(K) X(K)对应的真实频率。 以最简单的波形 x ( t ) = cos ⁡ ( 2 π f t ) x(t) = \cos(2\pi ft) x(t)=cos(2πft)来研究。设采样周期为 1 1 1秒， 采样点数 也就是DFT公式中的 N N N， 对应采样频率为 N h z N\mathrm{hz} Nhz, 我们假设 N ≥ 2 f N \ge2f N≥2f满足奈奎斯特采样定理。 采样到的点序列为 { cos ⁡ ( 0 ) , cos ⁡ ( 1 N 2 π f ) … , cos ⁡ ( N − 1 N 2 π f ) } \{\cos(0 ), \cos(\frac{1}{N}2\pi f) \dots, \cos(\frac{N-1}{N}2\pi f)\} {cos(0),cos(N1​2πf)…,cos(NN−1​2πf)} (假设刚好从相位为0开采， 后面解释为何可以这么假设）。

显然， 当 k = f k=f k=f时， X ( k ) = ∑ n = 0 N − 1 cos ⁡ ( n N 2 π f ) ⋅ cos ⁡ ( 2 π N n f ) X(k)=\sum_{n=0}^{N-1}\cos(\frac{n}{N}2\pi f) \cdot \cos \left(\frac{2 \pi}{N} nf\right) X(k)=∑n=0N−1​cos(Nn​2πf)⋅cos(N2π​nf)最大， 其余 k < N 2 k < \frac{N}{2} k 2f N>2f， 此时 X ( k ) ( k < N 2 ) X(k) (k