N2>log,从而,DFT算法比直接计算DFT的运算次数大大减少。 3、举例说明 例如:N=20=1024时, N210048567204.8 5120 直接计算 FFT算法 64128256512 N(取样点数 图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线 4.2.4DII-FFT的运算规律及编程思想 1、原位计算 N=2M点的FFT共进行M级运算,每级由N2个蝶形运算组成。同一级中 每个蝶形的两个输入数据只对计算本蝶形有用,而且每个蝶形的输入、输出数据 节点又同在一条水平线上,这就意味着计算完一个蝶形后,所得的输出数据可立 即存入原输入数据所占的存储单元。这样,经过M级运算后,原来存放输入序 列数据的N个存储单元中便依次存放X(k)的N个值。这种利用同一存储单元存 储蝶形计算输入、输出数据的方法称为原位计算 原位计算可节省大量内存。 2、旋转因子的变化规律 N点DIFT运算流图中,每级都有N/2个蝶形。每个蝶形都要乘以因子W,2 2 log 2 n N N  ，从而，DIT-FFT 算法比直接计算 DFT 的运算次数大大减少。 3、举例说明 例如： 10 N   2 1024 时， 2 2 10048567 204.8 5120 log 2 N N N   图 4.2.5 FFT 算法与直接计算 DFT 所需乘法次数的比较曲线 4.2.4 DIT-FFT 的运算规律及编程思想 1、原位计算 2 M N  点的 FFT 共进行 M 级运算，每级由 N/2 个蝶形运算组成。同一级中， 每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据 节点又同在一条水平线上，这就意味着计算完一个蝶形后，所得的输出数据可立 即存入原输入数据所占的存储单元。这样，经过 M 级运算后，原来存放输入序 列数据的 N 个存储单元中便依次存放 X k  的 N 个值。这种利用同一存储单元存 储蝶形计算输入、输出数据的方法称为原位计算。 原位计算可节省大量内存。 2、旋转因子的变化规律 N 点 DIT-FFT 运算流图中，每级都有 N/2 个蝶形。每个蝶形都要乘以因子 p WN