文件名重复-167674

文件名重复-167674内容摘要：

上述计算量要小得多。 下面 讨论基 4 FFT算法。       nkNNNnnkNNnWnxWnxkX 12/4/14/0    nkNNNnnkNNNnWnxWnx 14/314/32/不过，当 N=4M ，即以 4为基（类推基 8，基 16）的 首先将 N=4M点 DFT分解为四个 N/4点的 DFT          kXWkXWkXWkXkX kNkNkN 332210    kXWkX llkNl30式中 X0(k), X1(k) ,X2(k) ,X3(k)均为 N/4点的 DFT。 由四个 N/4点的 DFT合成 N点 DFT，要利用 N/4点 DFT的周期性，即 Xl(k) N/4点的 DFT 这样， N点 DFT为 X1(k)= X1(k +N/4) =X1(k +N/2) =X1(k +3N/4) X2(k)= X2(k +N/4) =X2(k +N/2) =X2(k +3N/4) X4(k)= X4(k +N/4) =X4(k +N/2) =X4(k +3N/4) X0(k)= X0(k +N/4) =X2(k +N/2) =X3(k +3N/4)          kXWkXWkXWkXkX kNkNkN 332210       kXWkXNkX NkN 1404/       kXWkXNkX NkN 1202/       kXWkXNkX NkN 14304/3     kXWkXWNkNNkN 343242      kXWkXWNkNNkN 323222      kXWkXW NkNNkN 34332432    基 4的基本蝶形如图 642所示  4/2 NkNW kNW3kNW2kNW 4/NkNW  4/3 NkNW  2/NkNW  2/2 NkNW  2/3 NkNW  4/3NkNW  4/33 NkNW  4/32 NkNW 4 jNNW 14jWnNN的对称性，即 4/NNW 4/NNW基 4计算式中的乘法系数与 有关，注意到 具有 ，且 4/NNW而 177。 j ， 177。 1都不必作乘法运算，所以利用 的对 称性，上式简化为          kXWkXWkXWkXkX kNkNkN 332210           kXjWkXWkXjWkXNkX kNkNkN 3322104/           kXWkXWkXWkXNkX kNkNkN 3322102/           kXjWkXWkXjWkXNkX kNkNkN 3322104/3 简化后基 4的蝶形如图 643所示。 kNW31 1 1 j 1 j j j kNW2kNW分解会有相同的运算量减少。 与基 2一样 N越大，效率 越高。 比较后，可知基 4计算量比基 2还少。 同理，基 16运算量 基 实乘数 实加数 2 89,924 139,266 4 57,348 126,978 16 48,132 125,442 8 49,156 126978 上式是 N=4M一级分解的结果。 以此类推，后面的各级 基 16有类似的结果。 例 N =4096=212时，比较基 由表 64可见，随着基数上升运算效率提高并不多。 而基 数的增加会使算法结构复杂。 并且基越大，蝶形结构越 复杂。 运算量的减少是以程序（或硬件）复杂为代价， 基太大往往得不偿失。 所以有人认为取大于 8的基数没有 多大实际意义。 上世纪八十年代法国人提出了将基 2分解 与基 4分解结合的分裂基算法，其运算量比基 2少，运算 流图与基 2FFT接近，运算程序也不长，是一种实用高效 算法，有兴趣的读者可以参考有关教材。 加意味着计算量的增加，是低效的算法。 补零的方法增加点数，可以提高频谱密度，但 N的增。