FFT快速傅里叶算法

学习数字信号处理时学到如果直接对有限长的序列进行N点DFT，那么其需要进行 N 2 N^2 N2次的复数乘以及复数加运算，其算法复杂度十分高，将会浪费大量时间在计算过程中。为此研究了FFT（快速傅里叶算法）这里给大家介绍两种：时域抽取法(DIT-DFT)和频域抽取法（DIF-FFT）。

时域抽取法：设有一序列 x ( n ) x(n) x(n)的长度为N，且满足 N = 2 M N=2^M N=2M,M为自然数。按 n n n的奇偶性分成两个 N / 2 N/2 N/2的子序列。 x 1 ( r ) = x ( 2 r ) r = 0 , 1 , 2 … N / 2 − 1 x_1(r)=x(2r) r=0,1,2…N/2-1 x1​(r)=x(2r)r=0,1,2…N/2−1 x 1 ( r ) = x ( 2 r − 1 ) r = 0 , 1 , 2 … N / 2 − 1 x_1(r)=x(2r-1) r=0,1,2…N/2-1 x1​(r)=x(2r−1)r=0,1,2…N/2−1 则 x ( n ) x(n) x(n)的DFT为 再将其中的 X 1 ( k ) X_1(k) X1​(k)和 X 2 ( k ) X_2(k) X2​(k)拆分出来，显然可以得到。 并且我们可以得到奇偶序列都是以 N / 2 N/2 N/2为周期的，且根据旋转因子的对称性可以得到 W N k + N / 2 = − W N k W_N^{k+N/2}=-W_N^k WNk+N/2​=−WNk​ 那么 X ( k ) X(k) X(k)可以表示为 这样就可以简单的将N点的DFT分为N/2点的DFT。 这里需要引进一种计算符号：蝶形运算符

显然可以看出：一次蝶形运算需要一次复数乘与两次复数加来合成。

回到上文我们已经明白如何把N点DFT拆分成2个N/2点DFT运算了。以此类推我们可以知道最简单的是：将N点DFT经过M次（ M = l b N M=lbN M=lbN）拆分可以获得最效率的运算方式。这里可以用蝶形图十分直观的表现出来。（我会在另一篇文章上详细的解析如何绘画蝶形运算流图）。

因此我们可以得到经过DIT-FFT处理后只需要进行N/2M次复数乘以及NM次复数加相比DFT快速许多。