16767dft的快速算法——fft

16767dft的快速算法——fft内容摘要：

kX1 kX2   kXWkX kN 21    kXWkX kN 21    kXWkX kN 21    kXWkX kN 21 上式可由图 621的蝶形流图表示。 由流图可见，每个蝶形有一次复乘，两次复加。 例 的一次分解如图 622所示。 1NW2NW0NW3NW5x1x3x7x0x 2x 4x6x 6X 0X 5X1X 3X 2X 4X 7XDFTN点2DFTN点2共有 2/N 个碟形  01X11X 21X 31X 02X12X 22X 32X一个 8点 DFT分解为两个 4点 DFT，如图 622所示。 4222 NN24222 NN222 NNm F 2N22N1N若 次复乘； 计算量： N/2点 DFT要 次复乘； 两个 N/2点 DFT要 N/2个蝶形合成要 N/2次复乘； 共需 几乎减少了一半。 比直接计算的运算量 4/N        lxlxlxlxrx41311 122 14,.1,0  Nl     rkNNrWrxkX 2/11201        klNNllkNNlWlxWlx 12 2/114022/1140122      lkNNlkNlkNNlWlxWWlx 4/41402/4/3140       kXWkXkXWkX kNkN 42342/3 14,.1,0  Nk  kX1  kX (2)将 再分解为两个 点的 DFT运算     kNXkX433     kNXkX444kNNkN WW  4/2/142/24/2/  jNNjNN eeWkNNkN WW  2/4/N 2/N  kX1 kX3  kX 4由 点 合成为 、 点的 要用  kX3  kX 到 的周期性、对称性。 周期 对称     kNXkX41114,.1,0  Nk    kXWkXkNX kN 42/31 2       kXWkXkX kN 42/31  kX1 kX1分为前后两部分： 将 及 前 N/4点 后 N/4点  0x 2x 4x 6xDFT点N /4DFT点N /40NW2NW 01X11X 21X 31X 03X13X 04X14X8N  kX1 的流图如图 623所示。 例 时  kX2  kX5  kX6同理 再分解为两个 N/4点的 DFT 、。 00 4/ NN WW      040 30 4/ XxWx N      140 30 4/ XxWx N 8N 0x 4x如法炮制，一直分解到最后的 2点 DFT。  0x  4x 组成的 2点 DFT的蝶形如图 例 时由 、 625所示。                                          ,11,7,3341122,。