chap4快速傅立叶变换fft(编辑修改稿)

chap4快速傅立叶变换fft(编辑修改稿)内容摘要：

＝ 2r＋ 1 r=0,1,…,N/2 1        112222002 22NNrn rnNNnnNNX k X r x n x n W x n x n W                                 11222120021 22NNrn n rnN N NnnNNX k X r x n x n W x n x n W W                          令：       1222nNNx n x n x nNx n x n x n W    则：       2112021220221NnrNnNnrNnX r x n WX r x n Wr=0,1,2,… ,N/21 可见，上两式均为 N/2点 DFT 167。 （ DIF）的 FFT算法（续） 用蝶形图描述 如下 ：    12,x n x n xn2NxnnNW  0 , 1 , 2 , , 122NNx n x n n     2 nNNx n x n W－ 1 167。 （ DIF）的 FFT算法（续） 上述过程小结如下：  首先形成  计算  分别计算 的 N/2点的 DFT，得到 X（ k）的偶数点和奇数点的输出。    12,x n x n , 2Nx n x n   12,x n x n167。 （ DIF）的 FFT算法（续） 以 N=8为例， DIF FFT算法流图如下： 先蝶形运算，后 FFT： 167。 （ DIF）的 FFT算法（续） 2 , 2rNN仍是偶数 即 可继续分组，使得每一个 N/2点的 DFT由 两个 N/4点的 DFT来得到，以此类推，直至分解到两个 一点序列。    12,x n x n167。 （ DIF）的 FFT算法（续） 例如 N=8时 DIF的 FFT流图如下： 167。 （ DIF）的 FFT算法（续） 可见： 一个 N=8点的 DFT经三级（ N=23）分解后，变为 计算两点的 DFT，而这两点的 DFT实际上只有加 减运算，在每一级运算中，都有 N/2个蝶形参加 运算，其运算量同 DIT FFT。 因此， DIF FFT算法从始至终都是在进行分解，而 DIT FFT算法从始至终都是在进行组合。 167。 （ DIF）的 FFT算法（续） 二、 DIT FFT与 DIF FFT 算法的比较  区别：  输入输出顺序相反，每一种 DIT FFT算法都存在一种 DIF FFT算法，二者互为倒置。  两种算法的蝶形运算存在差异， W因子相乘的位置不同。  相同点：  都有 级运算，每级都有 N/2个蝶形。  运算量相同，即需要 次复乘， 次复加  都是原位运算。 2log2 NN 2logNN2rN 设167。 （ DIF）的 FFT算法（续） 三、 IDFT FFT算法 ——IFFT        1101 ,NN k n k nNNk n ox n X k W X k x n WN两式相比， 相差一个负号，系数相差 ， 故：可用 FFT流图计算 IFFT。 NW1N方法： 输入输出调换 将 FFT流图中的 同 代替。 输出的每一个支路乘以 nNW nNW1N167。 （ DIF）的 FFT算法（续） 例：由 N=8按频率抽取的 FFT流图求 IFFT流图 167。 （ DIF）的 FFT算法（续） 可见，一个按频率抽取地 FFT流图能够实现按 时间抽取地 IFFT流图，同理一个按时间抽取的 FFT流图可以实现按频率抽取地 IFFT流图。 实际上机实现时，可直接用 FFT程序计算 IFFT     101011NknNkNknNkx n X k WNX k WNDIT FFT和 DIF FFT都要求 ，故称为基－ 2FFT. 2rN167。 N为复合数的 FFT算法 对于 情况，可用下述方法提高计算 DFT速度  将序列补最少的零至 ，这种方法不是最简的。  若要求至计算 N点的 DFT，而 N又不能分解成素数的积，则直接计算 DFT—CZT. 若 N是一个复合数，则有快速算法计算 DFT。 利用 FFT的基本思想：将大点数 DFT的运算尽量分解为小点数的运算，提高运算效率。 2rN2r167。 N为复合数的 FFT算法（续） 一、算法原理 设： 长 N=ML M：列 L：行 则：  xn    1010100 , 1 , , 10 , 1 , , 1 ,0 , 1 , , 1 ,NknNnX k x n W k NN M Ln M n n x nnLnM  将 序 列 的 序 号 用 矩 阵 表 示表 示 行 号表 示 列 号例：  1 2 4 3 0 , 1 , 2 , , 1 143N x n nML   ，则 ： 列 行167。 N为复合数的 FFT算法（续） 将 n排成矩阵形式如下： 0n1nn 0 1 2 3 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 L 行 M列 矩阵中的序号 5表示如下： 10105 4 1 10 , 1 , 20 1 2 3n M n nnn      行＝ ， ， ， 列167。 N为复合数的 FFT算法（续） 同理：对于 X(k)， k也可以表示成矩阵形式  10100 , 1 , , 1 ,0 , 1 , , 1 ,k M k k x nkMkL将 序 列 的 序 号 用 矩 阵 表 示表 示 列 号表 示 行 号（与 n表示相反） 01012 4 3430 ,1, 2 , 30 ,1, 2NMLkkk  1则 ：k=3k例： 1k0kn 0 1 2 3 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 167。 N为复合数的 FFT算法（续）               1 0 0010 1 0 0 01010 1 0 0 0010 1 011 0 1 00110001100011000,NknNnMLL k k nNnnMLk L k n k nLkN N N NnnMLk L k n k nN N Nnnn k L k k X kX k X L k k X k k x n Wx n Wx n W W W Wx n W W W     11111Mn1MnMn1Mn1将 n=Mn 代 入 得 ：Mnnn167。 N为复合数的 FFT算法（续）           0 1 0 0 0010 1 0 0 0010 0 1 00100111 0 0001100011 0 00139。 1 0 0 2 0 10,,MLk L k n k nN N NnnML。