FFT 快速傅立叶变换(任意点)
这个月几乎都在搞保研的事情…结果没拿到资格…算了…也算经历过了…
心血来潮想搞搞FFT玩玩…
虽然在数字信号处理课上有比较详细的讲过…不过是基2的,对于不是2^N点的FFT只能补零吗…
本来是想做做图像的FFT看看…但是图像的边不是2^N点的…而且补零可能也不方便…做滤波估计还会被补的0影响…
不管怎么样…还是先看看基2的FFT怎么做吧…
稍微看了下Wiki上的…貌似还有不少别的方法的FFT…
还是先看看经典的Cooley Tukey算法吧…
离散傅立叶变换的定义式大约是这个样子的
这里用W方便表示,W(a,n)表示极角是a/n个360度的角度,这里关于角度的性质W也有
作为例子,展开个n=8的情况
为了计算右边那一列n个数,直接算要n^2级别的计算量
现在将黄色和绿色的部分分别取出来
X_e和X_o分别是原数列的偶数项和奇数项的离散傅立叶变换,递归的子结构出现了
放到原式中就变成了
这样,只要分别计算出X_e和X_o并附加2*n级别的计算量,就能完成原本要n^2级别的计算量才能完成的运算了
不过毕竟是最基础的方法…代码的运行效率还有很多优化的余地
虽然说是基2的,但是实际上只是个特例
实质上这个方法并不是对分成2份才有效
比如以n=6作为例子,既可以分成2份:
也可以分成3份:
而且依然满足递归的子结构的要求
也就是,n=a*b的情况下,可以分成a份,计算a个长度为b的子序列的离散傅立叶变换值,附加a*n的级别的运算量,就可以完成n点的离散傅立叶变换了
这样,对任意的n都可以做快速傅立叶变换了:分解质因数
可惜n是质数的时候,貌似只能用定义式了…
基2,4,8的情况下,在代码级别上还可以有很好的优化
因为这时会让中间很多步骤中有关W的复数运算简化很多,不用复数乘法,而用实部虚部做较少的加减法来完成
浮点数真是功不可没啊…用很小的精度代价让一个浮点数包含了原序列每个数的一部分信息…就像全息照相一样呢…
RSS订阅