数学实现信号分析[5]: 快速傅里叶变换FFT

封面来自百度百科

上一期(一个月前), 我讲了离散傅里叶变换并且用算法实现了, 但是在实际应用中就不会使用这个算法的, 为什么呢?

效率慢, 在长度为n的数据中, 做一次DFT需要至少计算n^2次复数乘法和n^2次复数加法, (在我的算法里还有附带n^2次复数指数运算,  没有化简真的非常对不起)

那么有没有效率比较快的算法呢  (没有的话我发这个专栏干什么)

快速傅里叶变换 (Fast FT)

以下使用  x_n 表示输入数据,  f_n  表示FFT后的结果,  n  表示数据长度

上次我们说过的DFT表达式是这个

假设我们的数据集是偶数个,  那么把偶数和奇数分开,  得:

化简后得:

然后我们再假设偶部奇部的长度都为偶数 ,即总数据长度可以被4整除, 重复上述步骤, 得:

为了让算式更简洁一些,  我自己创造了一种表示方法:

所以在这种表示方法中,  上面很长的式子就变成了:

然后我们再假设我们的数据长度可以被8整除, 得:

这时候应该可以发现规律了

在一个内层括号里,  结构都是统一的   {8, i} + [4] {8, i+4},   而在上一步,可以观察到   {4, i} + [4] {4, i+2}    这样的结构

所以这是一个非常有规律的一种算法

这里有一个普遍的计算方法:

假设数据长度恰好为  2^n  ,     然后创造一种记法:  记  x_i  为  {2^n,  i}  ,对下列算式进行迭代:

最后得到 {0,0} 就是FFT的结果了

在上一篇DFT中,  观察ω取不同数值时的复平面,   我们可以看到ω以4为中心, 左右的图像是完全对称的

在经过一定量的计算后, 会得到一种非常神奇的计算过程     (在不存在的附章内)

以下定义   蝶形节点    :

并且定义单位虚根:

那么在长度为4的数据中, FFT就可以用下面的蝴蝶节点图来进行计算

而8个数据可以这样计算

那么问题来了, 左边的输入排列有什么规律呢

以8个数据为例,  原数据排列为 [0, 1, 2, 3, 4, 5, 6, 7],  而输入排列为 [0, 4, 2, 6, 1, 5, 3, 7] , 看上去好像完全没有规律

但是写成二进制的话,  原数据排列为  [000, 001, 010, 011, 100, 101, 110, 111],   而输入排列为  [000, 100, 010, 110, 001, 101, 011, 111]   

可以看到把每个原排列的二进制左右对称地换一下, 就得到了输入排列

上面说的是一种叫做  "基-2  快速傅里叶变换 (bias-2 FFT)",   因为我们这里是按偶部奇部对输入数据进行分割,  所以是"基-2"的

同理如果按照  "对3取余,  结果有0, 1, 2"  这样进行分割也是可以的, 这种就叫做 "基-3快速傅里叶变换",   同理可以创造各种 "基- [质数]  FFT",  为什么是质数呢

事实上,  单独一个蝴蝶节点才是真正的 "b-2 FFT", 而后面说到的4个, 8个数据的其实是"b-4 FFT"和"b-8 FFT".   而且运算顺序对结果不会产生影响 (如封面和后面的"b-8FFT", 顺序不同结果一样)

事实上, 对一个数据长度为  (p0*p1*p2* ... *pn) (p为质数) 的序列, 我们可以按照顺序作 "b-p0 FFT", "b-p1 FFT", "b-p2 FFT", ..., "b-pn FFT", 最后得到的结果是和DFT的结果一模一样的

***  FFT不需要专门推导逆算法,  直接按照蝶形节的结构反向计算就可以了 ***

那么说了一大堆, FFT真的有比DFT快吗,     我们可以直接写程序看看用时  FFT的程序太复杂了, 这篇专栏是半夜赶出来的, 没有找到精力去写,  才不是我想咕哦

或者最直接的分析复杂度

在DFT中,  长度为n的数据需要进行n^2次 (复数加法和复数乘法)   的计算, 所以DFT的复杂度为  n^2

在FFT中, 长度为n的数据需要进行  n*log2(n)+3次 (复数加法和复数乘法)   的计算, 所以FFT的复杂度为  n*log2(n)

那就是快多少呢,  我们可以画一个图像来看看他们的区别

可以看到随着n的增大,  DFT和FFT之间的差距是按几何倍数增长的,  所以

FFT万岁