3基于MATLAB的FFT算法实现
3.1系统总体流程图
本设计要求对一选定的图片进行FFT算法和IFFT算法分析。在MATLAB环境下编写基2 DIT-FFT算法，利用自己编写的算法对图片进行频谱分析，并与MATLAB数字信号处理工具箱中的FFT函数进行对比研究，验证自编算法的正确性。所以得到系统总体流程图如图3-1所示。
图3-1系统总体流程图
3.2 DIT-FFT算法的基本原理
快速傅里叶变换(FFT)是为提高DFT运算速度而采用的一种算法。 对一个有限长度序列x(n)的N点的DFT为：
所以，要求N点的DFT，需要N2次的复数乘法运算，N*(N-1)次复数乘法运算。随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，如当N=1024时，完成复数乘法和复数加法的次数分别为百万以上，无论是用通用计算机还是用DSP芯片，都需要消耗大量的时间，不能满足实时的要求，不适合于对实时处理要求高的场合。为了能实时处理DFT，要想减少DFT的运算量可以有两个途径：第一是降N，N的值减小了，运算量就减少了；第二是利用