基2时域频域FFT算法.ppt

* 重点： 1.基2时域FFT流图算法 2.基2频域FFT流图算法 难点： 1.利用FFT流图计算IFFT 2.利用 N点复序列FFT，计算2N点实序列 3.利用N点复序列FFT算法计算两个N点实序列 快速Fourier变换(FFT) 4点序列{2，3，3，2} DFT的计算复杂度 复数加法 N(N-1) 复数乘法 N 2 如何提高DFT的运算效率? 问题的提出 一般性 DFT: 直接计算的计算量： N-1 复数乘法 N 对N个不同X[m] 复数加法 N(N-1) 复数乘法 N2 对一固定的m 复数加法 如计算1024点DFT： 复数乘法次数： N2 =10242 = 220 = 1048576 解决问题的思路 1.将长序列DFT分解为短序列的DFT 2.利用旋转因子 的周期性、对称性、可约性。 1)周期性(periodicity) 2)复共轭对称性(complex conjugate) 3)当N是偶数时 的性质 解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。 基2时间抽取(Decimation in time)FFT算法 基2频率抽取(Decimation in frequency)FFT算法 3.1 基2时域抽取FFT算法 算法推导: N=2M时域抽取(Decimation in time) ] a ] [ 1 k x ] [ 2 l x ] [ ] [ 2 1 l x k x a + [ ] [ 2 1 l x k x a - -1 (一)算法原理 基本蝶形(butterfly) 算法推导: N=2M时域抽取 例： ] 0 [ X ] 1 [ X -1 1 ] 0 [ x ] 1 [ x 2点FFT流图 N=2基2时域FFT流图的推导 N=4时域基2FFT流图的推导 -1 X[2] X[3] -1 2点 DFT 2点 DFT x[0] x[3] x[1] x[2] X[0] X[1] 2点DFT 0 4 W 1 4 W x[0] x[3] x[1] x[2] X[3] X[1] X[2] X[0] -1 -1 -1 -1 N=8基2时域FFT流图的推导 0 8 W 1 8 W 2 8 W 3 8 W 4点 DFT 4点 DFT X[0] X[3] X[1] X[2] X[4] X[5] X[6] X[7] x[0] x[6] x[2] x[4] x[1] x[3] x[5] x[7] -1 -1 -1 -1 0 8 W 1 8 W 2 8 W 3 8 W X[0] X[3] X[1] X[2] X[4] X[5] X[6] X[7] x[0] x[6] x[4] x[2] x[1] x[5] x[3] x[7] 0 4 W 1 4 W 0 4 W 1 4 W -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8点FFT流图 第三级 第一级 第二级 (二 ) 算法工作量 a ] [ 1 k x ] [ 2 l x ] [ ] [ 2 1 l x k x a + ] [ ] [ 2 1 l x k x a - -1 一个蝶形计算量： 复数乘法 1，复数加法 2 复数乘法: N， N N M 2 log 2 2 = 复数加法： N=2M时，分解级数为 M，每级蝶形数 N/2 计算1024点复数乘法次数： DFT： N 2 =1024 2 = 220 = 1048576 ；FFT： (三) 流图规律 1) 原位运算(In-place Computations) a ] [ 1 k x ] [ 2 l x ] [ ] [ 2 1 l x k x a + ] [ ] [ 2 1 l x k x a - -1 优点：节省存储空间 (三) 流图规律 第二级的蝶形系数为 ，蝶形节点的距离为2。 第一级的蝶形系数均为 ，蝶形节点的距离为1。 第三级的蝶形系数为 ，蝶形节点的距离为4。 第M级的蝶形系数为 ，蝶形节点的距离为N/2。 2)FFT算法流图旋转因子 规律 3)倒序规律 k 0 k 1 k 2 x [ k 2 k 1 k 0 ] x [00 0] x [10 0] x [01 0] 0 1 0 1 1] 1 2 x [ k k 0] x [ k 2 k 1 0 1 x [11 0] x [001 ] x [101 ] x [01 0] x [111 ] 0 1 0 1 0 1 0 1 例：试利用N=4基2时间抽取的FFT流图计算 8点序列x[k]={1, -1, 1, -1, 2, 1, 1, 2}的DF