ch3_1基2时间抽取FFT讲解.pptVIP

基4时间抽取FFT算法推导 基4时间抽取FFT算法推导 基4时间抽取FFT算法推导 基4时间抽取FFT算法推导 数字信号处理(Digital Signal Processing) 信号与系统系列课程组 国家电工电子教学基地 离散傅里叶变换快速算法(FFT) 问题的提出 解决问题的思路与方法 基2时间抽取FFT算法 基2频率抽取FFT算法 FFT算法的实际应用—— 实序列的DFT计算 IDFT的快速计算方法 时间抽取FFT 问题的提出 4点序列{2，3，3，2} DFT的计算复杂度 复数加法 N(N-1) 复数乘法 N 2 如何提高DFT的运算效率? 时间抽取FFT 一般性 DFT: 直接计算的计算量： 复数乘法 N 对N个不同X[m]: 复数加法 N(N-1) 复数乘法 N2 对一固定的m: 复数加法 N-1 如计算1024点DFT： 复数乘法次数： N2 =10242 = 220 = 1048576 时间抽取FFT 解决问题的思路 1. 将长序列DFT分解为短序列的DFT 2. 利用旋转因子 的周期性、对称性、可约性。 时间抽取FFT (1)周期性(periodicity) (2)复共轭对称性(complex conjugate) (3)当N是偶数时 旋转因子 的性质 时间抽取FFT 解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。 基2时间抽取(Decimation in time)FFT算法 基2频率抽取(Decimation in frequency)FFT算法 时间抽取FFT 基2时间抽取FFT算法推导 基2时间抽取FFT算法流图 基2时间抽取FFT算法的计算复杂度 基2时间抽取FFT算法流图规律 3.1 基2时域抽取FFT算法 时间抽取FFT 基2时间抽取FFT算法推导 算法推导: N=2M时域抽取(时域按奇偶分组) 时间抽取FFT 因此有: 由于X1[m] 和X2[m]隐含有周期性，可得 可见X1[m]是x[k]偶分量的DFT，X2[m]是x[k]奇分量的DFT. 时间抽取FFT 基2时间抽取FFT算法流图 N=2 x[k]={x[0], x[1]} 4点基2时间抽取FFT算法流图 x[0] x[2] x[1] x[3] X1[0] X1[1] X2[0] X2[1] 2点DFT 2点DFT -1 -1 -1 -1 X [0] X [1] X [2] X [3] 4点基2时间抽取FFT算法流图 2点DFT 8点基2时间抽取FFT算法流图 4点DFT 4点DFT x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] X1[0] X1[1] X1[2] X1[3] X2[0] X2[1] X2[2] X2[3] X [0] X [1] X [2] X [3] X [4] X [5] X [6] X [7] -1 -1 -1 -1 4点DFT 4点DFT x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] X1[0] X1[1] X1[2] X1[3] X2[0] X2[1] X2[2] X2[3] X [0] X [1] X [2] X [3] X [4] X [5] X [6] X [7] -1 -1 -1 -1 8点基2时间抽取FFT算法流图 第一级 第二级 第三级 8点基2时间抽取FFT算法流图 时间抽取FFT 算法的计算复杂度 复乘次数 复乘次数 N N 2 基2时间抽取FFT算法流图 第一级 第二级 第三级 FFT算法流图旋转因子 规律 第二级的蝶形系数为 ，蝶形节点的距离为2。 第一级的蝶形系数均为 ，蝶形节点的距离为1。 第三级的蝶形系数为 ，蝶形节点的距离为4。 第M级的蝶形系数为 ，蝶形节点的距离为N /2。 原位运算 x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7] A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) 输入序列 存储单元 第一级输出 第二级输入 第二级输出 第三级输入 X1[0] X1[1] X2[0] X2[1] X3[0] X3[1] X4[0] X4[1] A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) X5[0] X5[1] X5[2] X5[