串行 FFT 递归算法（蝶式递归计算原理）求傅里叶变换摘要 FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的
它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步
设 x(n)为 N 项的复数序列，由 DFT 变换，任一 X（m）的计算都需要 N 次复数乘法和 N-1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出 N 项复数序列的 X（m）,即 N 点 DFT 变换大约就需要 N^2 次运算
当 N=1024 点甚至更多的时候，需要 N2=1048576 次运算，在 FFT 中，利用 WN 的周期性和对称性，把一个 N 项序列（设 N=2k,k 为正整数），分为两个 N/2 项的子序列，每个N/2 点 DFT 变换需要（N/2）^2 次运算，再用 N 次运算把两个 N/2 点的 DFT 变换组合成一个N 点的 DFT 变换
这样变换以后，总的运算次数就变成 N+2（N/2）^2=N+N^2/2
继续上面的例子，N=1024 时，总的运算次数就变成了 525312 次，节省了大约 50%的运算量
而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的 DFT 运算单元，那么 N点的 DFT 变换就只需要 Nlog(2)(N)次的运算，N 在 1024 点时，运算量仅有 10240 次，是先前的直接算法的 1%，点数越多，运算量的节约就越大，这就是 FFT 的优越性
关键字：FFT 蝶式计算 傅里叶变换目录一．题目及要求
