详解快速傅里叶变换FFT算法

快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法，只有FFT才能在现实中有实际应用的意义。虽然许多学过数字信号处理这门课的同学都知道DFT和FFT，但实际上真正理解其算法原理的屈指可数，绝大部分同学知其然而不知其所以然，况且限于高校课程教学体制，课堂上不可能把这些原理和算法讲得明明白白的。为此，特意以本文讲解FFT算法的原理与实际应用，给欲往电子信息类专业进修和发展的同学一些课外参考。

N点有限长序列x(n)的DFT为

X(k) x(n)W 其中W

nkN

n 0N 1

nkN

e

j

2 nkN

其逆变换IDFT为

1N 1 nk

x(n) X(k)WN

Nn 0

正逆变换的运算量都是相同的。x(n)和X（k）都是复数序列，计算一个X(k)值，需要N次复数乘法和N-1次复数加法。X(k)有N个点，所以总共需要N*N次复数乘法和N(N-1)次复数加法。复数运算实际上是通过实数运算来完成的。上式可以写成：

nknk

X(k) Re x(n) jIm x(n) Re WN jIm WN

n 0

N 1

nknknknk Re x(n) Re W Imx(n)ImW jRex(n)ImW Imx(n)ReW NNNN

n 0

N 1

由此可见，一次复数乘法需要4次实数乘法和2次实数加减法。一次复数加法需要2次实数加

法。所以每一个X（k）计算需要4N次实数乘法以及2N+2(N-1)=2(2N-1)次实数加法。整个DFT运算总共需要4N*N次实数乘法和N*2(2N-1)=2N(2N-1)次实数加法。当N足够大，N>>1时，直接计算DFT的乘法次数和加法次数都是和N的平方成正比。当N=1024时，DFT的运算量为1048576次，即一百多万次复乘运算，一块嵌入式32位处理器的最高速度为105百万指令每秒，那么它要完全计算这个DFT的时间最快也要1秒，期间还是独占CPU所有运算资源且不能有任何其他的中断请求。这样计算量太庞大，计算速递太慢了，谈不上实时性，根本没有实用意义。

所以，我们就要利用DFT的系数的固有特性来简化计算，减少运算量。特性如下：

nk nk

1. 共轭对称性：(WN )* WN

nk(n N)kn(k N)2. 周期性： WN WN WNnknmknk/m

WN WN3. 可约性： WN/m

得出：

(k N/2)kn(N k)(N n)k nk

WNWN WN WN WNN/2 1 WN

利用上述这些系数性质就可以合并DFT某些项的计算从而减少计算量。下面仅给出按时间抽选