2、用二点FFT计算一个N点实序列的DFT。 设x(m)为N点实序列,取x(n)的偶数点和奇数点分别作为新构造的序列 y(n)的实部和虚部,即 x(n)=x(2n),x2(m)=x(2n+1),n=01 y(n)=x(n)+x2(n),n=0,1 对y(m)进行,点FFT,输出Y(k),则 X1(k)=DFT[x(m)]=() x:(k)=D[x()]=-mn() k=0,1, 2 根据 DIT-FFT的思想可得 X(k)=X1(k)+WX2(k),k=01 由于x(m)为实序列,所以X(k)具有共轭对称性,X(k)的另外点的值为 (N-k)=x^(k),k 相对一般的FFT算法,上述算法的运算效率η 2M n=1,运算速度提高近一倍。 44分裂基FFT算法 自从基2快速算法出现以来,人们仍不断寻求更快的算法。从理论上讲,用 较大的基数可以进一步减少运算次数,但同时会使计算程序变得更为复杂。所以 取大于8的基数没有多大的实际意义。1984年,法国的杜梅尔和霍尔曼将基2 分解和基4分解糅合在一起,提出了分裂基FFT算法。其运算量比前述几种算 法都有所减少,运算流程却与基2FFT很接近,运算程序也很短。所以说分裂基 FFT算法是一种适用的高效新算法。 441分裂基FFT算法原理 442分裂基FFT算法的运算量2、用 2 N 点 FFT 计算一个 N 点实序列的 DFT。 设 x n( ) 为 N 点实序列，取 x n( ) 的偶数点和奇数点分别作为新构造的序列 y n( ) 的实部和虚部，即 1 2 ( ) (2 , 2 1 , 0,1, , 1 ) ( ) ( ) 2 N x n x n x n x n n = = + = − ( ) 1 2 ( ) ( ), 0,1, , 1 2 N y n x n jx n n = + = − 对 y n( ) 进行 2 N 点 FFT，输出 Y k( ) ，则 ( ) ( ) ( ) ( ) ( ) ( ) 1 1 2 2 , 0,1, , 1 2 ep op X k DFT x n Y k N k X k DFT x n jY k = =        = − = = −      根据 DIT-FFT 的思想可得 ( ) 1 2 ( ) ( ), 0,1, , 1 2 k N N X k X k W X k k = + = − 由于 x n( ) 为实序列，所以 X k( ) 具有共轭对称性， X k( ) 的另外 2 N 点的值为 ( ) ( ) * , 1,2, , 1 2 N X N k X k k − = = − 相对一般的 FFT 算法，上述算法的运算效率 2 1 M M  = + ，当 10 2 2 M N = = 时， 20 11  = ，运算速度提高近一倍。 4.4 分裂基 FFT 算法 自从基 2 快速算法出现以来，人们仍不断寻求更快的算法。从理论上讲，用 较大的基数可以进一步减少运算次数，但同时会使计算程序变得更为复杂。所以 取大于 8 的基数没有多大的实际意义。1984 年，法国的杜梅尔和霍尔曼将基 2 分解和基 4 分解糅合在一起，提出了分裂基 FFT 算法。其运算量比前述几种算 法都有所减少，运算流程却与基 2FFT 很接近，运算程序也很短。所以说分裂基 FFT 算法是一种适用的高效新算法。 4.4.1 分裂基 FFT 算法原理 4.4.2 分裂基 FFT 算法的运算量