《华侨大学自动化专业数字信号处理》-公开·课件.ppt

x[k], h[k]是实序列， 将其构成复序列y[k]=x[k]+j h[k] DFT{x[k]+j h[k]}=DFT{y[k]}=Y [m] （1）利用N点复序列的FFT算法 计算两个N点实序列DFT 例3-1 已知两个4点实序列分别为x[k]={1,2,0,1}, h[k]={2,2,1,1}，试利用4点序列FFT算法同时计算两个实序列的DFT X[m]和H[m]。 构造复数序列y[k] 计算复数序列的4点FFT Y[m]，并计算 由前面的公式得到X[m]和H[m] y[k]是一个长度为2N的序列 问题：如何利用N点FFT，计算4N点序列的FFT？ （2）利用N点复序列的FFT 计算2N点实序列的DFT 如果y[k]是实序列，则可由实序列x1[k]和x2[k]构成一个N点复序列，计算该N点复序列的DFT同时得到X1[m]和X2[m] 2. IDFT的快速计算方法 （1）类似FFT流图方法计算IFFT （2）直接由FFT计算IFFT （1）类似FFT流图方法计算IFFT 将系数 换成 最后一级乘以常数1/N 步骤：① 将X [m]取共轭。 ③ 对步骤②中结果取共轭并除以N。 （2）直接由FFT计算IFFT ② 用FFT流图计算DFT{X*[m]} 例3-2 已知某4点序列x[k]的DFT为X[m]={1+2j,2+3j,3+4j,4+5j}，试利用基2时间抽取FFT流图计算其对应的序列x[k]，并通过IDFT定义公式验证计算结果。 四、基4时间抽取FFT算法 将N点时间序列分解为4个N/4点的时间短序列 4个N/4点序列的频谱可通过下式 合成N点序列的频谱 利用DFT的周期性以及旋转因子的特性,可得 基2时间抽取FFT算法的基本关系 基3时间抽取FFT算法的基本关系 基4时间抽取FFT算法的基本关系 基p时间抽取FFT算法的基本关系 序列x[k]长度为N=pq,将其按时间抽取方式分解为p个q点序列 由于Xp[m]隐含以q为周期，故可得 q点序列可以按照q=uv方式进一步分解 五、混合基FFT算法 各级分解的基可以不同 可以减少序列补0的个数，提高FFT算法的效率 本章小结 一、基2时间抽取FFT算法 基2时间抽取FFT算法原理 基2时间抽取FFT算法流图 基2时间抽取FFT算法的计算复杂度 基2时间抽取FFT算法结构特点 二、基2频率抽取FFT算法 基2频率抽取FFT算法原理 基2频率抽取FFT算法流图 频率抽取与时间抽取的比较 三、FFT算法的实际应用 实序列的DFT计算 IDFT的快速计算方法 四、基4时间抽取FFT算法 五、混合基FFT算法 FFT: Fast Fourier Transform * * 将频域序列X[m]分成越来越短的子序列 * 一、基2时间抽取FFT算法 二、基2频率抽取FFT算法 三、FFT算法的实际应用 四、基4时间抽取FFT算法 五、混合基FFT算法 问题的提出 N点序列DFT的计算复杂度 复数加法 N(N-1) 复数乘法 N 2 如何提高DFT的运算效率？ 解决问题的思路 1. 将长序列DFT分解为短序列的DFT，再将短序列的DFT合成为长序列的DFT 2. 利用旋转因子 的周期性、对称性、可约性。 旋转因子 的性质 (1) 周期性 (2) 对称性 (3) 可约性 一、基2时间抽取FFT算法 基2时间抽取FFT算法原理 基2时间抽取FFT算法流图 基2时间抽取FFT算法的计算复杂度 基2时间抽取FFT算法结构特点 1. 基2时间抽取FFT算法原理 （1）分解 将长度为N的时域序列x分解为两个长度为N/2的短序列x1、x2 偶数点序列 奇数点序列 这两个短序列的N/2点DFT为 （2）合成 2. 基2时间抽取FFT算法流图 基2时间抽取蝶形运算的信号流图 X1[m] X2[m] X[m] X[m+N/2] -1 2点序列DFT运算流图 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算法流图 x[0] x[2] x[1] x[3] X1[0] X1[1] X2[0] X2[1] -1 -1 -1 -1 X [0] X [1] X [2] X [3] 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]