快速Fourier变换

1、快速Fourier变换目录 引言 FFT Radix-2 DIT- FFT Radix-2 DIF- FFT IDFT的快速算法 FFT一.引言 问题来源虽然DFT是一种可计算的变换，但是直接的实现效率很低，特别当序列长度 N 很大.直接计算 N-点DFT需要 N2 次复数乘法和 N2 N 次复数加法；这就意味着 4N2 实数乘法和 4N2 -2N 次实数加法. 如何降低计算复杂度？1965 J. W. Cooley和 T. W. Tukey提出了快速傅里叶变换的思想，将DFT的计算量减少了几个数量级. FFT的出现使得数字信号处理这门新兴学科得到了快速发展.根据对序列分解和选取方法的不同产生

2、了FFT的多种算法，基本算法是基2-DIT和基2-DIF.大部分DFT的计算都可以利用其对称性和周期性来消除，而这也是FFT的最主要思想.FFT算法的基本原理1. DFT的计算量由离散傅里叶变换分析可知，DFT计算公式为写成矩阵形式有45DFT的计算量每计算一个X(k)值，需要进行N次复数相乘和N-1次复数相加，若计算X(0), X(1),共N个X(k)值时，则需要计算N2次复数相乘，N(N-1)次复数相加.当N增大时，运算工作量迅速增大，如N=10时，需要100次复数相乘，而当N=1024(210)时，需要一百多万次复数乘法运算。62. 减小计算量的方法在W与x(n)相乘过程中是否存在不必要

3、的重复运算？设N=4，则矩阵表达式为复数乘法：N2=16; 加法N(N-1)=12.7进一步分析可发现，存在不必要的运算：(1) W0=1;(2) WN/2 =e-j2/NN/2=-1;也存在一些可利用的特性，如：(1) Wnk的周期性，即运用此式，当N=4时，有W2=W6，W1=W9等；8(2) Wnk的对称性，即运用此式有W3=-W1，W2=-W0等.运用以上特性，可简化W矩阵如下 9二. FFT计算方法对称性周期性Combine Decomposition FFT算法分类DIT - FFT: Decimation-in-time FFT algorithm 时间抽取FFT算法DIF -

4、FFT: Decimation-in-frequency FFT algorithm 频率抽取FFT算法 returnRadix-2(基2) DIT- FFT算法Radix-2: 序列长度N 满足:L 为整数 时间抽取FFT(DIT-FFT)运作方式 将N点时域信号分解为 N组信号，每组仅包含一个数据点. 每次分解均采用交错分解的方式实现, 将偶指数和奇指数样本分离; 计算与这N组时域信号相对应的N组频谱; 将N组频谱合成为一组频率谱.Radix-2 FFT 算法 0 4 8 12 2 6 10 14 1 5 9 13 3 7 11 15 0 8 4 12 2 10 6 14 1 9 5 13

5、 3 11 7 15084122106141 95133117150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 signal of 16 points0 2 4 6 8 10 12 141 3 5 7 9 11 13 152 signals of 8 points4 signals of 4 points8 signals of 2 points16 signals of 1 pointRadix-2 FFT算法 算法原则将N点序列x(n)分解为两组N/2点序列 x1(r)和 x2(r) 计算x1(r)和 x2(r)的DFT 计算N点序列x(n)的DFT“蝶形计

6、算”流程图总共有1次复数乘法和2次复数加法N=4的情形此时有18N/2-pointDFTN/2-pointDFTN-点 DFTN=8时Radix-2 DIT- FFT算法对于2-点DFT2-点DFT2-点DFT2-点DFT将2-点 DFT 合成为 4-点 DFT将2-点 DFT 合成为 4-点 DFT将4-点 DFT 合成为 8-点 DFT 3-阶合成, 每阶合成均包括 N/2次蝶形运算 计算复杂度Radix-2 DIT- FFT算法当共有L-阶合成, 每一阶包括N/2 蝶形运算. 每一次蝶形运算包括一次复数乘法和两次复数加法.总共的复数乘法数量为:总共的复数加法数量为:Radix-2 DIF

7、- FFT算法 DIF-FFT操作流程0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 70 1 2 3 0 1 2 3 butterfly computation 0 1 2 3 0 1 2 3 butterfly computation butterfly computation 0 1 0 1 0 1 0 1butterflybutterflybutterflybutterfly0426153701010101Radix-2 DIF- FFT算法 算法原则将N点序列 x(n)划分为两组N/2点序列前N/2点后N/2点计算N点序列x(n)的DFTRadix-2 DIF- FFT算

8、法分离奇数和偶数样本X(k)Radix-2 DIF- FFT算法Radix-2 DIF- FFT Algorithm蝶形运算流程图共有1次复数乘法和2次复数加法forN/2-pointDFTN/2-pointDFTRadix-2 DIF- FFT算法 DIT与DIF差别 蝶形运算DIT-FFT: 先做乘法，再做加法DIF-FFT: 先做加法，再做乘法IDFT的快速算法 算法 1在DFT的FFT流程图中: IDFT的快速算法 算法 2 returnFFT应用举例分析过去300年的太阳黑子活动具有周期性，每11年有一次最大值出现数据：苏黎世太阳黑子相对数，同时记录了太阳黑子的数量和大小。33 lo

9、ad sunspot.dat year=sunspot(:,1); relNums=sunspot(:,2); plot(year,relNums) title(Sunspot Data) 34前50组数据plot(year(1:50),relNums(1:50),b.-); 35利用FFT做频域分析 Y = fft(relNums); Y(1)=; %First component is the sum of data plot(Y,ro) title(Fourier Coefficients in the Complex Plane); xlabel(Real Axis); ylabel(Imaginary Axis); 36难以理解，考虑其功率(Complex magnitude squared Y)和频率之间的关系，即画出周期图37 plot(freq(1:40),power(1:40) xlabel(cycles/year) 38period=1./freq; plot(period,power); axis(0 40 0 2e+7); ylabel(Power); xlabel(Period (Years/Cycle); 39hold on; index=find(power=max(power);mainPer