快速付立叶变换(FFT) X1(m)和X2(m)是N1点的DFT,它们的计算又可 以用类似方法化为两个更短的N2=N1/2点的DFT, 一直分解下去，直到2为止，这就构成了上述 FFT的全部运算图。 。 粗算其中每一根线条代表一次乘法，线条的合 成点代表一次加法。则每一级要N次乘法和加 法。N=8时，需10g28=3级，故共要24次乘法和 加法。原来要N2=64次。若N=1024,需要10242 次乘法，而用FFT,需分解为log21024=9级，只 需1024×9次乘法，加快了100多倍。 1313 快速付立叶变换(FFT) • X1(m)和X2(m)是N1点的DFT，它们的计算又可 以用类似方法化为两个更短的N2=N1/2点的DFT, 一直分解下去，直到2为止，这就构成了上述 FFT的全部运算图。 • 粗算其中每一根线条代表一次乘法，线条的合 成点代表一次加法。则每一级要N次乘法和加 法。N=8时，需log28=3级，故共要24次乘法和 加法。原来要N2=64次。若N=1024，需要10242 次乘法，而用FFT, 需分解为log21024=9级，只 需1024×9次乘法，加快了100多倍