2、用一点FFT计算一个N点实序列的DFT 设x(m)为N点实序列,取x(n)的偶数点和奇数点分别作为新构造的序列 y(n)的实部和虚部,即 x1(m)=x(2n),x(n)=x(2n+1),n=0.1- y(n)=x(n)+x2(n),n=01 对y(n)进行点FFT,输出Y(k),则 X, (k)=DFTLx,(n)=Y(k k=0,1, X2(k)=DFTL,(n)=-yr(K) 根据 DIT-FFT的思想可得 X(k)=X1(k)+Wx2(k),k=01N-1 由于x(m)为实序列,所以X(k)具有共轭对称性,X(k)的另外,点的值为 X(N-k)=x(k=1.2…,-1 相对一般的FFT算法,上述算法的运算效率η 2M 当N=2M=20时 M+1 运算速度提高近一倍。 44分裂基FFT算法 自从基2快速算法出现以来,人们仍不断寻求更快的算法。从理论上讲,用 较大的基数可以进一步减少运算次数,但同时会使计算程序变得更为复杂。所以 取大于8的基数没有多大的实际意义。1984年,法国的杜梅尔和霍尔曼将基2 分解和基4分解糅合在一起,提出了分裂基FFT算法。其运算量比前述几种算 法都有所减少,运算流程却与基2FFT很接近,运算程序也很短。所以说分裂基 FFT算法是一种适用的高效新算法。 44.1分裂基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 算法的运算量