分享小程序-快速傅里叶变换

从零开始

1.标题党了，此贴不分享程序，分享采样数为2^n的快速傅里叶算法。
2.傅里叶变换可写成矩阵形式，此矩阵又可以分解为多个（稀疏）矩阵乘积，根据这些稀疏矩阵的规律可以得到高效的“迭代式”（iterative)FFT和IFFT算法。（递归式FFT的程序写起来简洁，但多次重复调用函数，比较耗电脑资源（函数式编程语言除外）。
3.分享自己编制(copy)的8-points,16-points, 2^n points DIF FFT矩阵，和8点，16点 DIF FFT的蝶形图
4.实在写不出来的话，还有个笨办法，将这些矩阵写出来，以稀疏矩阵格式（比如csr,csc形式）存储在电脑里，计算FFT时依次读取这些矩阵，依次做乘法。效率也很高，只是多了几次文件读取。不便之处是不同的采样数，不同的矩阵。
5.要注意的是，FFT写法分为  DIF-FFT（频域抽取）法和DIT-FFT（时域抽取）法。DIF-FFT算法，输入（也就是时间项）是自然顺序，结果（也就时频率项）的次序是“位反”（bit-reversed）的，DIT-FFT算法，输入（也就是时间项）的次序是“位反”的，结果是自然顺序。
6. 分享的pdf文档里有fft算法的部分数学基础，不包括完整的推导，主要用于帮助理解和记忆。Key Words：DFT，FFT，IFFT， DIF-FFT，DIT-FFT， Sparse Matrix, Bit-reverse