快速Fourier变换教案.pptVIP

* * * IDFT的快速算法 算法 1 在DFT的FFT流程图中: IDFT的快速算法 算法 2 return FFT应用举例 分析过去300年的太阳黑子活动 具有周期性，每11年有一次最大值出现 数据：苏黎世太阳黑子相对数，同时记录了太阳黑子的数量和大小。 * load sunspot.dat year=sunspot(:,1); relNums=sunspot(:,2); plot(year,relNums) title(Sunspot Data) * 前50组数据 plot(year(1:50),relNums(1:50),b.-); * 利用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); * 难以理解，考虑其功率(Complex magnitude squared Y)和频率之间的关系，即画出周期图 * plot(freq(1:40),power(1:40)) xlabel(cycles/year) * period=1./freq; plot(period,power); axis([0 40 0 2e+7]); ylabel(Power); xlabel(Period (Years/Cycle)); * hold 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; * * * There are several ways to calculate the Discrete Fourier Transform (DFT), such as solving simultaneous linear equations or the correlation method described in Chapter 8. The Fast Fourier Transform (FFT) is another method for calculating the DFT. While it produces the same result as the other approaches, it is incredibly more efficient, often reducing the computation time by hundreds. This is the same improvement as flying in a jet aircraft versus walking! If the FFT were not available, many of the techniques described in this book would not be practical. While the FFT only requires a few dozen lines of code, it is one of the most complicated algorithms in DSP. But dont despair! You can easily use published FFT routines without fully understanding the internal workings. 一次复数乘法需用四次实数乘法和二次实数加法； 一次复数加法需用二次实数加法。 DFT的运算量与N2成正比。 * * 利用对称性可以将DFT运算中的某些项合并 利用对称性、周期性及可约性，可以将长序列的DFT分解为短序列的DFT。由于运算量与N的平方成正比，因此降低N后可以大大降低运算量。 * * * example of the time domain decomposition used in the FFT. The next step in the FFT algorithm is to find the frequency spectra of the 1 poin