快速Fourier变换

《快速Fourier变换》由会员分享，可在线阅读，更多相关《快速Fourier变换（41页珍藏版）》请在装配图网上搜索。

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

2、FT的多种算法，基本算法是基2-DIT和基2-DIF.l大部分DFT的计算都可以利用其对称性和周期性来消除，而这也是FFT的最主要思想.FFTFFT算法的基本原理算法的基本原理l l1.DFT的计算量l l由离散傅里叶变换分析可知，由离散傅里叶变换分析可知，DFTDFT计算公式为计算公式为l l写成矩阵形式有写成矩阵形式有4 45 5DFT的计算量l l每计算一个X(k)值，需要进行N次复数相乘和N-1次复数相加，若计算X(0),X(1),共N个X(k)值时，则需要计算N2次复数相乘，N(N-1)次复数相加.l l当N增大时，运算工作量迅速增大，如N=10时，需要100次复数相乘，而当N=10

3、24(210)时，需要一百多万次复数乘法运算。6 62.减小计算量的方法l l在W与x(n)相乘过程中是否存在不必要的重复运算？l l设N=4，则矩阵表达式为l l复数乘法：N2=16;加法N(N-1)=12.7 7l l进一步分析可发现，存在不必要的运算：l l(1)(1)WW0 0=1;=1;l l(2)(2)W WN N/2/2=e=e-j2-j2/N N N N/2/2=-1;=-1;l l也存在一些可利用的特性，如：l l(1)(1)WWnknk的周期性，即的周期性，即运用此式，当运用此式，当N N=4=4时，有时，有WW2 2=WW6 6，WW1 1=WW9 9等；等；8 8l l

4、(2)Wnk的对称性，即l l运用此式有运用此式有WW3 3=-=-WW1 1，WW2 2=-=-WW0 0等等.l l运用以上特性，可简化W矩阵如下 9 9二.FFT计算方法对称性对称性周期性周期性Combine Decompositionn FFT算法分类DIT-FFT:Decimation-in-time FFT algorithm 时间抽取FFT算法DIF-FFT:Decimation-in-frequency FFT algorithm 频率抽取FFT算法 returnRadix-2(基2)DIT-FFT算法Radix-2:序列长度N 满足:L 为整数n 时间抽取FFT(DIT-FF

5、T)运作方式l 将N点时域信号分解为 N组信号，每组仅包含一个数据点.每次分解均采用交错分解的方式实现,将偶指数和奇指数样本分离;l 计算与这N组时域信号相对应的N组频谱;l 将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 3 11 7 15084 122 106 141 95 133 117 150 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

6、 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 算法原则l将N点序列x(n)分解为两组N/2点序列 x1(r)和 x2(r)l计算x1(r)和 x2(r)的DFT l计算N点序列x(n)的DFTl“蝶形计算”流程图总共有1次复数乘法和2次复数加法N=4的情形l l此时有1818N/2-pointDFTN/2-pointDFTN-点 DFTN=8时Radix-2 DIT-FFT算法对于2-点点DFT2-点点DFT2-点

7、点DFT2-点点DFT将将2-点点 DFT 合成为合成为 4-点点 DFT将将2-点点 DFT 合成为合成为 4-点点 DFT将将4-点点 DFT 合成为合成为 8-点点 DFT 3-阶合成,每阶合成均包括 N/2次蝶形运算n 计算复杂度Radix-2 DIT-FFT算法当l共有L-阶合成,每一阶包括N/2 蝶形运算.每一次蝶形运算包括一次复数乘法和两次复数加法.l总共的复数乘法数量为:l总共的复数加法数量为:Radix-2 DIF-FFT算法n 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 comput

8、ation 0 1 2 3 0 1 2 3 butterfly computation butterfly computation 0 1 0 1 0 1 0 1butterflybutterflybutterflybutterfly0426153701010101Radix-2 DIF-FFT算法n 算法原则l将N点序列 x(n)划分为两组N/2点序列前N/2点后N/2点l计算N点序列x(n)的DFTRadix-2 DIF-FFT算法l分离奇数和偶数样本X(k)Radix-2 DIF-FFT算法Radix-2 DIF-FFT Algorithml蝶形运算流程图共有1次复数乘法和2次复数加法f

9、orN/2-pointDFTN/2-pointDFTRadix-2 DIF-FFT算法n DIT与DIF差别l 蝶形运算DIT-FFT:先做乘法，再做加法DIF-FFT:先做加法，再做乘法IDFT的快速算法n 算法 1在DFT的FFT流程图中:IDFT的快速算法n 算法 2 returnFFT应用举例l l分析过去300年的太阳黑子活动l l具有周期性，每具有周期性，每1111年有一次最大值出现年有一次最大值出现l l数据：苏黎世太阳黑子相对数，同时记录了太数据：苏黎世太阳黑子相对数，同时记录了太阳黑子的数量和大小。阳黑子的数量和大小。3333 load sunspot.dat year=su

10、nspot(:,1);relNums=sunspot(:,2);plot(year,relNums)title(Sunspot Data)3434l l前50组数据plot(year(1:50),relNums(1:50),b.-);3535l l利用FFT做频域分析 Y=fft(relNums);Y=fft(relNums);Y(1)=;%First component is the sum of data Y(1)=;%First component is the sum of data plot(Y,ro)plot(Y,ro)title(Fourier Coefficients in t

11、he Complex Plane);title(Fourier Coefficients in the Complex Plane);xlabel(Real Axis);ylabel(Imaginary Axis);xlabel(Real Axis);ylabel(Imaginary Axis);3636l l难以理解，考虑其功率(Complex magnitude squared Y)和频率之间的关系，即画出周期图3737 plot(freq(1:40),power(1:40)xlabel(cycles/year)3838period=1./freq;plot(period,power);axis(0 40 0 2e+7);ylabel(Power);xlabel(Period(Years/Cycle);3939hold on;index=find(power=max(power);mainPeriodStr=num2str(period(index);plot(period(index),power(index),r.,MarkerSize,25);text(period(index)+2,power(index),Period=,mainPeriodStr);hold off;40404141