《数字信号处理教学课件作者第2版陈树新第4章节离散傅里叶变换课件》由会员分享，可在线阅读，更多相关《数字信号处理教学课件作者第2版陈树新第4章节离散傅里叶变换课件（59页珍藏版）》请在金锄头文库上搜索。
1、第4章 离散傅里叶变换及其快速算法,4.1 DFT的定义及物理意义 4.2 离散傅里叶变换的性质 4.3 频域采样定理 4.4 快速傅里叶变换(FFT) 4.5 FFT算法的特点和改进措施 4.6 FFT的应用举例,2019/6/20,2,4.1 DFT的定义及物理意义,4.1.1 DFT的定义 设x(n)是一个长度为M的有限长序列，定义x(n)的N点离散傅里叶变换（DFT）为 与上式相对应，X(k)的离散傅里叶逆变换为 式中 ，那么,2019/6/20,3,N称为DFT变换区间长度，可以证明离散傅里叶变换具有唯一性。 4.1.2 DFT和Z变换的关系 设序列x(n)的长度为N，其Z变换、DF
2、T和傅里叶变换分别可以表示为,2019/6/20,4,上式表明序列x(n)的N点离散傅里叶变换X(k)是其Z变换X(z)在单位圆上N点等间隔采样，或表明X(k)为序列x(n)傅里叶变换X(ej)在区间0，2上的N点等间隔采样，这就是DFT的物理意义。 基于上述分析，DFT的变换区间长度N不相同，表示对X(ej)在区间0，2上采样间隔和点数不同，所以DFT得到的变换结果就不同。,2019/6/20,5,4.1.3 DFT的线性和周期性 1、线性特性 如果x1(n)和x2(n)的长度分别为N1和N2，且 y(n)=ax1(n)+bx2(n) 取N = maxN1，N2，则y(n)的N点DFT为 2
3、、周期性 x(n)与X(k)均为有限长序列，x(n)与X(k)均具有周期性，且周期都是N。,2019/6/20,6,实际上，任何周期为N的周期序列 都可以看作是长度为N的有限长序列x(n)的周期延拓，而x(n)则是 中的一个周期，即,2019/6/20,7,为了方便起见，周期序列 和有限长序列x(n)之间的关系也可以表示成为 可以证明一个周期为N的周期序列，它的离散傅里叶级数的分析与综合，可以表示为 式中,2019/6/20,8,4.2 离散傅里叶变换的性质,离散傅里叶变换除了具有线性和周期性这两种基本特性以外，根据离散傅里叶变换的特点，它还具有以下特性和定理。 4.2.1 循环移位性质 1、
4、序列的循环移位 设x(n)为有限长序列，其长度为N，则序列x(n)的循环移位可以定义为,2019/6/20,9,2019/6/20,10,2、时域循环移位定理 设x(n)是长度为N的有限长序列，y(n)为x(n)的循环移位，即 则 3、频域循环移位定理 如果 则,2019/6/20,11,4.2.2 循环卷积定理 1、时域循环卷积定理 如果x1(n)和x2(n)的长度分别为N1和N2，取N= maxN1，N2，如果 X(k)= X1(k) X2(k) 可以证明 上式运算为x1(n)和x2(n)的循环卷积积分，简称循环卷积。,2019/6/20,12,进一步观察可以发现，上式还可以写为 计算循环
5、卷积过程也分为以下几步：,2019/6/20,13,2、频域循环卷积定理 如果 x (n)=x1(n)x2(n) 可以证明 合理地应用时域和频域循环卷积定理，可以较好的回避复杂的循环卷积运算，对于提高系统运算效率，简化系统结构非常有效。,2019/6/20,14,4.2.3 DFT的对称性 1、复共轭序列的DFT 设x*(n)是x(n)的复共轭序列，序列长度为N，且 ，则 利用同样的方法还可以证明,2019/6/20,15,2、时域有限长序列的共轭对称性 共轭对称和共轭反对称序列定义如下： 当N为偶数时，将上式中的n换成N/2-n可得到,2019/6/20,16,可以证明，任何有限长序列x(n
6、)都可以表示成为它的共轭对称分量和共轭反对称分量之和，即,2019/6/20,17,3、DFT的共轭对称性 如果将序列x(n)分解为实部和虚部两部分，即 那么，可以推导出,2019/6/20,18,结合式xep(n)和xop(n)的DFT可以分别表示为,2019/6/20,19,4.3 频域采样定理,4.3.1 频域采样过程 设任意序列x(n)的Z变换为 X(z)收敛域包含单位圆，则存在傅里叶变换。那么，在单位圆上对X(z)等间隔N点采样，可以得到 X(k)可以看作长度为N的有限长序列xN(n)的DFT,2019/6/20,20,离散傅里叶级数的系数和离散傅里叶变换的关系，可以表示为 将X(k
7、)，带入上式得 可以证明 所以,2019/6/20,21,可以由频域采样值X(k)恢复出原序列x(n)的条件是：在频域区间0，2的范围内，采样点数N必须大于等于序列长度M，否则就会在时域上产生混叠现象。这就是所谓的频域采样定理。 xN(n) = IDFTX(k) = x(n)，0 n N-1 4.3.2 利用频域采样信号恢复原始信号 对于有限长序列x(n)，当满足频域采样定理时，N点频域采样X(k)就足以不失真地表示序列的特征。也就是说，由N点X(k)可内插恢复出X(z)或X(ej)。,2019/6/20,22,设序列x(n)长度为M，在频域区间0，2中等间隔采样N点，NM，则有 由于满足频域
8、采样定理，则有 将上式代入，得,2019/6/20,23,上式 进一步化简得 其中内插函数 设X(z)的收敛域包含单位圆，则可以利用z= ej从而得到x(n)傅里叶变换X(ej)的内插函数和内插公式为,2019/6/20,24,4.4 快速傅里叶变换(FFT),4.4.1 从DFT到FFT 直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。自从1965年图基(J.W.Tuky)和库利(T.W.Coody)在计算机数学杂志上发表了著名的“机器计算傅里叶级数的一种算法”论文以后，桑德(G.Sand)-图基等快速算法相继出现，后经人们进一步改进，很快形成一套高效运算方法，这就是现
9、在的快速傅里叶变换(简称FFT)。,2019/6/20,25,对于长度为N的序列x(n)，它的DFT可以写为 对某一个k值，直接按上式计算X(k)值需要N次复数乘法和(N-1)次复数加法。计算全部N点X(k)值，则需要N2次复数相乘和N(N-1)次复数加法。 快速傅里叶变换算法的基本思想：分解成短序列；利用旋转因子具有的周期性和对称性。 4.4.2 时域抽取法基2FFT算法 按n的奇偶取值不同，把x(n)分解为两个N/2点的子序列,2019/6/20,26,则x(n)的DFT可以表示为,2019/6/20,27,由于 所以 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT
10、，根据DFT的周期特性，则X1(k)= X1(k+N/2)，X2(k)= X2(k+N/2)，且,2019/6/20,28,所以X(k)可以表示成为： 上面的两个式的运算可以用流图符号表示如下 中间以一个小圆点表示加减运算，右上支路为相加后的输出，右下支路为相减后的输出。,2019/6/20,29,采用这种运算符，当N=23=8时 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即,2019/6/20,30,那么，X1(k)又可表示为 同理，由X3(k)和X4(k)的周期性和的对称性，最后得到,2019/6/20,31,同样将x2(r)按奇偶分解成两个N/
11、4长的子序列x5(l)和x6(l)，做类似x3(l)和x4(l)的N/4点DFT，由X5(k)和X6(k)的周期性和的对称性，最后得到,2019/6/20,32,依此类推，经过M-1次分解，最后将N点DFT分解成为N/2个2点DFT。,2019/6/20,33,4.4.3 频域抽取法基2FFT算法 DIFFFT算法不是按偶数、奇数将序列x(n)分解，而是按前后对半分解，这样可将N点的DFT写成前后两部分。即,2019/6/20,34,按式中k的不同取值，可以将X(k)分解成偶数组与奇数组，当k取偶数时，有 当k取奇数时，有,2019/6/20,35,令 将x1(n)和x2(n)分别代入上式，可
12、以得到 x1(n)和x2(n)同x(n)的关系也可以用蝶形运算流图,2019/6/20,36,结合蝶形运算流图可以得到N = 8的一次分解运算流图 由于N =2M，N/2仍然是偶数，继续将N/2点DFT分解成偶数组与奇数组，这样每N/2点DFT又可以由两个N/4点DFT形成。,2019/6/20,37,2019/6/20,38,4.5 FFT算法的特点和改进措施,4.5.1 FFT算法的规律与特点 1、与DFT比较极大减小了运算量 全部N点的FFT运算共有蝶形单元数为 需要复数相乘次数为 需要复数加法次数为,2019/6/20,39,通常计算一次相乘的时间要远远大于计算一次加法的时间，因此，在
13、分析算法运算量时也仅统计相乘的次数。 2、原位计算 经过某一级蝶形运算后的结果可以存放在原来存贮该输入数据同一地址的单元中。原位计算的结构可以节省大量内存，从而使设备成本降低。 3、序列的倒序 DITFFT算法的输入序列排序为码位倒序，DIFFFT算法的输出序列排序为码位倒序。,2019/6/20,40,由于序列长度N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。所谓码位倒序，就是将二进制数从最高到最低有效位的位序进行颠倒放置，即(n0n1n M-2n M-1)，从而实现码位倒序。 4、旋转因子的变化规律 DITFFT运算流图从左到右，旋转因子也有不同，用L表示从左到右的
14、运算级(L=1，2，M)，当N=23=8时的各级旋转因子可以表示如下： L=1时， L=2时， L=3时，,2019/6/20,41,而DIFFFT算法的旋转因子从左到右排列顺序与DITFFT算法正好相反，当N=23=8时，M=3，各级旋转因子可以表示如下： L=1时， L=2时， L=3时， 4.5.2 改进FFT算法措施 以提高程序的复杂度为代价换取计算量的进一步减少措施。,2019/6/20,42,1、多类蝶形单元运算 综合起来分析，在FFT算法，对于旋转因子取1和j的情况都不需要乘法运算，这些旋转因子包括 、 和 。 在FFT算法还存在一些特殊的复数运算，例如旋转因子为 的情况。可以表
15、示为 这样一次复数乘法就简化为两次实数加法和两次实数乘法运算，可减少一半的运算量。,2019/6/20,43,若包含所有旋转因子，也就是对所有有关旋转因子的乘法，都按照复乘处理，则称该算法为一类蝶形单元运算； 若取掉 的旋转因子，则称该算法为二类蝶形单元运算； 若取掉 的旋转因子，则称该算法为三类蝶形单元运算； 若取掉 的旋转因子，则称该算法为四类蝶形单元运算；通常将二类、三类和四类蝶形单元运算称为多类蝶形单元运算。,2019/6/20,44,2、旋转因子的生成 在实际计算时通常将所需要的旋转因子，事先计算好，存放在一个旋转因子表中，在程序运行过程中，直接从表中查取所需要的旋转因子，这样运算速
16、度快，但需要一定数量的内存开销。 3、实序列的FFT算法 可以采用以下办法来提高FFT的运算效率： (1)用一个N点的FFT计算两个N点实序列的FFT，一个实序列作为FFT的实部，另一个实序列作为FFT的虚部，计算完FFT以后，根据DFT的共轭对称性，由输出X(k)分别得到两个实序列的N点DFT。,2019/6/20,45,(2)用N/2点的FFT计算一个N点实序列的DFT，其思路是将x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，则 。 对y(n) 进行N/2点的FFT计算，则Y(k)=DFTy(n)，同样根据DFT的共轭对称性，有 根据DIT-FFT的思路，可得,2019/6/20,46,由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为 这样x(n)的N点实序列的DFT就全部计算完成
