x(4)· DFT X() DFT XD) 4点 DFT 图4.2.3N点DFT的第二次时域抽取分解图(N=8) X(0) A(3) 图4.2.4N点DIT一FFT运算流图(N=8) 42.3 DIT-FFT算法与直接计算DFT运算量的比较 l、DI-FFT算法的运算量 由DI-FFT算法的分解过程可见,N=2"时,其运算流图应有M级蝶形, 每一级都由N2次复数城和N次复数加(每个蝶形需要两次复数加),所以,M 级运算总共需要的复数乘次数为 N 复数加次数为 C4(2)= 根据定义直接计算的运算量 直接计算N点DFT需N2次复数乘,N(N-1)次复数加。当N>1时
N/4点 DFT W N 1 2 W N 1 2 W N 0 W N 1 W N 2 W N 3 X1 (0) X1 (1) X1 (2) X1 (3) X2 (0) X2 (1) X2 (2) X2 (3) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x(0) X3 (0) X3 (1) X4 (0) X4 (1) x(4) x(2) x(6) x(1) x(5) x(3) x(7) N/4点 DFT N/4点 DFT N/4点 DFT W N 0 2 W N 0 2 图 4.2.3 N 点 DFT 的第二次时域抽取分解图(N=8) W N 0 W N 1 W N 2 W N 3 W N 0 W N 2 W N 0 W N 2 W N 0 W N 0 W N 0 W N 0 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0) A(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) 图 4.2.4 N 点 DIT―FFT 运算流图(N=8) 4.2.3 DIT-FFT 算法与直接计算 DFT 运算量的比较 1、DIT-FFT 算法的运算量 由 DIT-FFT 算法的分解过程可见， 2 M N 时，其运算流图应有 M 级蝶形， 每一级都由 N/2 次复数城和 N 次复数加（每个蝶形需要两次复数加），所以，M 级运算总共需要的复数乘次数为 2 2 log 2 2 N M N N C M 复数加次数为 2 2 logN C N M N A 2、根据定义直接计算的运算量 直接计算 N 点 DFT 需 2 N 次复数乘， N N 1 次复数加。当 N>>1 时
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