本文的目的不是讲如何实现FFT, 而是讲DFT到底是怎么计算的. 对每一个公式进行解释
DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。
然而对于傅里叶变换的公式,很多人看起来头疼, 周期性与加和公式在一起, 使得很多的人不能真正地理解它, 更没有办法来计算它, 我们编程的人一个习惯, 那就是一个算法, 一般来说是要先能够用一个简单的实例来自己先在纸上能够用笔计算出来, 然后才能实现, 像傅里叶变换, 如果给一个简单的4点序列{2, 3, 3, 2} 我们不能用笔计算出来的话, 更不用说用程序来实现了.
1. 长度为N的有限长序列x(n)的DFT为
2. 旋转因子
的周期性、对称性、可约性。
1) 周期性: 
2) 对称性: 
3) 可约性: 
3. 公式解释:
再根据复变函数论里的欧拉公式
, 我们可以很容易的得到.
比如说4点序列的Wn4 分别为{Wn0,Wn1,Wn2,Wn3}={1, -j, -1, j}, 实际上Wnm其实就是将单位圆(2 pi)等分为N份的点所表示的复数.
4. 简单的举例:
4点序列{2, 3, 3, 2}的DFT的计算:
评论