DFTLX,(1) X,(1) DFT 图4.2.3N点DFT的第二次时域抽取分解图(N=8) A(0) xX(1) X(2) X(5) 图4.2.4N点DI一FT运算流图(N=8) 423 DIT-FFT算法与直接计算DFT运算量的比较 1、 DIT-FFT算法的运算量 由 DIT-FFT算法的分解过程可见,N=2M时,其运算流图应有M级蝶形, 每一级都由N2次复数城和N次复数加(每个蝶形需要两次复数加),所以,M 级运算总共需要的复数乘次数为 N C(2 复数加次数为 CA(2)=NM=Nlog? 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 时
log2,从而, DIT-FFT算法比直接计算DFT的运算次数大大减少 3、举例说明 例如:N=20=1024时, 10048567 =204.8 5120 直接计算 512 FHT算法 612825651 N(取样点数) 图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线 424 DIT-FFT的运算规律及编程思想 1、原位计算 N=2M点的FFT共进行M级运算,每级由N2个蝶形运算组成。同一级中, 每个蝶形的两个输入数据只对计算本蝶形有用,而且每个蝶形的输入、输出数据 节点又同在一条水平线上,这就意味着计算完一个蝶形后,所得的输出数据可立 即存入原输入数据所占的存储单元。这样,经过M级运算后,原来存放输入序 列数据的N个存储单元中便依次存放X(k)的N个值。这种利用同一存储单元存 储蝶形计算输入、输出数据的方法称为原位计算 原位计算可节省大量内存。 旋转因子的变化规律 N点 DIT-FFT运算流图中,每级都有N2个蝶形。每个蝶形都要乘以因子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