按频率抽选的基FFT算法.PPTVIP

4 .3 按频率抽选的基-2FFT算法 一、 DIF-FFT 算法原理 按k的奇偶将X(k)分成两部分： 令 N /2仍为偶数，进一步分解：N /2 N /4 逐级分解，直到2点DFT 二、 DIF-FFT算法特点 运算量 3.倒位序 对N=2L点FFT，输入自然序，输出倒位序， 两节点距离：2L-m=N / 2m DIT与DIF的异同 基本蝶形不同 4.4 离散傅里叶反变换(IFFT)的快速算法 比较： * ——电子信息工程 设序列点数N=2L，L为整数。 将X(k)按k的偶奇分组前，先将输入x(n)按n的顺序分成前后两半： 则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N / 2点DFT，记为X1(k)和X2(k) 图4-14 按频率抽选蝶形运算流图符号 N/2点 DFT N/2点 DFT X1(0)=X(0) X2(0)=X(1) X1(1)=X(2) X1(2)=X(4) X1(3)=X(6) X2(1)=X(3) X2(2)=X(5) X2(3)=X(7) x1(0) x1(1) -1 x1(2) x1(3) -1 x2(0) x2(1) -1 x2(2) x2(3) -1 x(0) x(7) x(1) x(2) x(3) x(4) x(5) x(6) N/4点 DFT X3(0)=X1(0)=X(0) X3(1)=X1(2)=X(4) N/4点 DFT X4(0)=X1(1)=X(2) X4(1)=X1(3)=X(6) x3(0) x3(1) -1 -1 x4(0) x4(1) x1(0) x1(1) x1(2) x1(3) 同理： 其中： 图4-16 按频率抽选，将一个N点DFT分解为4个N/4点DFT(N=8) 当N=8时，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1 图4-17 按频率抽选FFT流程图（N=8） -1 L级蝶形运算，每级N/2个蝶形，每个蝶形结构： m表示第m级迭代，k，j表示数据所在的行数 一个蝶形的计算包括一次复数乘法和二次复数加法 复乘次数： 复加次数： L级蝶形运算，每级N/2个蝶形 2．原位运算及存储单元 频率抽选FFT的流图仍是原位运算的，每一级的碟形的输入和输出在运算前后可以存储在同一地址的存储单元中 所以只需要N个存储单元 第m级运算： 第一级有N/2种: 第二级有两组每组有N/4种： DIT: 先复乘后加减 DIF: 先减后复乘 运算量相同 都可原位运算 DIT和DIF的基本蝶形互为转置 -1 IDFT: DFT: 图4-19 IFFT流程图（N=8) 共轭 FFT 共轭 乘1/ N 直接调用FFT子程序计算IFFT的方法： * *