第九章 离散傅里叶变换.ppt

1、第九章 离散傅里叶变换,前言：引入DFT的原因,计算机应用于信号处理的基本条件： 1. 连续函数转变为离散数据(时域与频域)； 2. 计算范围从无限宽收缩到一个有限区间。 离散傅里叶变换研究内容： 1. 如何在频域进行离散化？ 2. 时域上的样本与频域上的样本之间的数学关系是怎样的？,主要内容,离散傅里叶级数（DFS） 离散傅里叶变换（DFT） 快速傅里叶变换（FFT）,一.DFT是重要的变换 1.分析有限长序列的有用工具。 2.在信号处理的理论上有重要意义。 3.在运算方法上起核心作用，谱分析、 卷积、相关都可以通DFT在计算机上 实现。, 9-1引 言,二.DFT是现代信号处理桥梁 DFT

2、要解决两个问题： 一是离散与量化， 二是快速运算。,信号处理,DFT(FFT),傅氏变换,离散量化,FT 傅立叶变换,时域：连续、非周期，频域：非周期、连续,9.2 傅里叶变换的几种可能形式,FS 傅立叶级数,时域：连续、周期，频域：非周期、离散,1,1,1,1,1,1,1,1,1,1,DTFT,时域：离散、非周期 频域：周期、连续,时域 频域,连续非周期 非周期连续 傅里叶变换,连续周期 非周期离散 傅里叶级数,离散非周期 周期连续 序列的傅里叶变换,离散周期 周期离散 离散傅里叶级数,傅里叶变换形式,傅里叶变换的4种形式,但是，前三种傅里叶变换对都不适于计算机上运算，因为它们至少在一个域（

3、时域或频域）中函数是连续的。 因此，我们感兴趣的是时域和频域都是离散的情况。,时域：离散、周期，频域：周期、离散,9.3 DFS与DFT,连续周期信号: 抽样（抽样周期为T，一个周期 内抽样N个点）,得周期序列,一、离散傅里叶级数,是周期为N的周期序列,1、DFS的引入,将 两端乘 再从 n=0到N-1求和，,则：,2、 的求取,3、将定标因子1/N移到 表达式中。,保持与Z变换相同的形式？,设 则离散傅氏级数表示为：,正变换：,反变换：,4、离散傅氏级数的表示：,DFS的图示说明,5、 函数的几个性质：,1.共轭对称性：,2.周期性：,i为整数,3.可约性：,4.正交性：,i为整数,二、 离

4、散傅里叶变换,在进行DFS分析时，时域、频域序列都是无限长的周期序列 周期序列实际上只有有限个序列值有意义 长度为N的有限长序列可以看成周期为N的周期序列的一个周期（主值序列） 借助DFS变换对，取时域、频域的主值序列可以得到一个新的变换DFT，即有限长序列的离散傅里叶变换,另一种表示,其中 表示对 n 取模N 运算(或模 N的余数)。,则,若,1、周期序列与主值序列的关系,举例：设周期为 N=6。则有周期序列和求余运算： 这是因为： (19=36+1) 同理 这是因为： (-2=-16+4),同样：X(k)也是一个N点的有限长序列,2、DFT的定义,3、DFT的矩阵形式,其中：,4、离散傅里

5、叶变换(DFT)的特点,序列x(n)在时域是有限长的(长度为N)，它的离散傅里叶变换X(k)也是离散、有限长的(长度也为N)。 n为时域变量，k为频域变量。 离散傅里叶变换与离散傅里叶级数没有本质区别，DFT实际上是离散傅里叶级数的主值，DFT也隐含有周期性。 离散傅里叶变换(DFT)具有唯一性。,例1、计算 (N=12)的N点DFT. 解：,9.4 离散傅里叶变换的性质,1、线性,这里，序列长度及DFT点数均为N 若不等，分别为N1，N2，则需补零使两序列长度相等，均为N，且,若,则,有限长序列的圆周移位导致频谱线性相移，而对频谱幅度无影响。,(1)圆周移位,2、时移特性,(2)时移特性,从

6、图中两虚线之间的主值序列的移位情况可以看出： 当主值序列左移m个样本时，从右边会同时移进m个样本 好像是刚向左边移出的那些样本又从右边循环移了进来 因此取名“循环移位”。 显然，循环移位不同于线性移位,3、频移特性,时域序列的调制等效于频域的圆周移位,eg：,4、时域圆周卷积,设,则,(1)定理,圆周卷积步骤： 1）翻褶 2）圆周移位 3）相乘 4）相加,(2) 圆周卷积的计算,0,m,0,m,0,m,0,m,最后结果：,1）.线性卷积 的长度为 的长度为,2）圆周卷积,（3）线性卷积与圆周卷积的关系,3) 关系,补0 加长,x(n)的N点DFT是 x(n)的z变换在单位圆上的N点等间隔抽样；

7、 x(n)的DTFT在区间0,2上的N点等间隔抽样。,一.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N.,9-6 FFT的应用,DFT与IDFT运算特点,当N很大时,运算量将是惊人的,如N=1024, 要完成1048576 次(一百多万次)运算.这样, 难以做到实时处理.,二.改进的途径,1. 的对称性和周期性,对称性:,周期性:,2、N点DFT 2个N/2点DFT,利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘

8、法运算.例如N=1024=210 时， 需要(1024/2)log2 210 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍,三、基2FFT算法的思路,把一个序列分为长度减半的偶序列和奇序列, 原序列的DFT就由这两个N/2序列求得. 进一步把N/2序列分解成两个N/4序列, 一直分解到2点序列.,Eg. N=8的FFT,四.算法原理(基2FFT) 1.先将 按n的奇偶分为两组N/2点作DFT,设N=2M ,不足时,可补些零。 n为偶数时: n为奇数时:,因此,其中, 2.两点结论: (1) G(k),H (k)均为N/2点的DFT。 (2) X(k)=G

9、(k)+W H (k)只能确定出 X(k)的k= 0,1,(N/2-1)时的值； 即前N/2点的结果。,k,N,同理,3.X(k)后N/2个点的确定,*X(k)的后N/2个点，也完全由G(k), H(k)确定 *N点的DFT可由两个N/2点的DFT来计算。,实现上式运算的流图称作蝶形运算,k= 0,1,(N/2-1),4.蝶形运算,（N/2个蝶形),由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算,k= 0,1,(N/2-1),例 N=8 时的FFT:,1、 2个N/2点DFT,（1）将 分成奇偶序列，并计算X(k),其中,g(0)=x(0) g(1)=x(2) N/2点

10、 g(2)=x(4) DFT g(3)=x(6) h(0)=x(1) h(1)=x(3) N/2点 h(2)=x(5) DFT h(3)=x(7),1 2,G(0),G(1),G(2),G(3),H(0),H(1),H(2),H(3),W,N,2,W,N,1,W,N,0,W,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),（2）对X (k)和X (k)进行蝶形运算如下图所示:,2、 4个N/4点DFT,（1）将 分成奇偶序列，并进行DFT,其中,（2）将 分成奇偶序列,并进行DFT,W,N,0,W,N,0,W,N,0,W,0,N,

11、-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),8点DFT的FFT的运算流图如下,1.蝶形运算 蝶形单元 蝶距:2m-1 （第m级蝶形运算）,五. FFT算法的特点,输入数据、中间运算结果和最后输出均用同一存储器。,2.原位运算,W,N,0,W,N,0,W,N,0,W,0,N,-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),3

12、 倒位序运算 FFT运算流程中，输出X(k)按正常顺序排 列在存储单元,而输入是按顺序: 这种顺序称作倒位序,即二进制数 倒位。,是由奇偶分组造成的,以N=8为例说明如下:,倒位序的实现 输入序列先按自然顺序存入存储单元,然后经变址运算来实现倒位序排列。 设输入序列的序号为n,二进制为 (n2 n1 n0 )2 ,倒位序顺序用 表示,其倒位序 二进制为(n0 n1 n2 )2 。,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1

13、1 3 7 1 1 1 1 1 1 7,自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n,2 1 0 0 1 2,码位倒序（N=8）,码位倒序（N=16）,倒位序的变址处理方法,存储单元,自然顺序,变址,倒位序,蝶距为1,蝶距为2,W,N,0,W,N,0,W,N,0,W,0,N,-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),4.WNr 的分布规律 第1级： 第2级： 第i级: 第L级:,5.存储单元 存输入序列 (n),n=0,1, ,N-1

14、, 计N 个单元; 存放系数 , r=0,1, ,N/2-1, 需N/2个存储单元； 共计(N+N/2)个存储单元。,三、FFT运算量,1 N=2 时，共有L=log N级蝶形运算；每一级有N/2个蝶形单元。 2每一级有N个输入中间数据，且每级只用到本级的输入中间数据，适合于迭代运算。 3计算量： 每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N 次复乘法；复加法L*N=Nlog2N 次。与直接DFT定义式运算量相比(倍数) N2/(Nlog2N) 。当 N大时，此倍数很大。,2,L,9-7 DFT的应用,一、利用FFT计算线卷积,1、时域圆周卷积

15、定理,设,则,2、圆周卷积与线卷积的关系,补0 加长,3、方法,N点FFT,N点FFT,IFFT,x,x(n),h(n),y(n),M,L,连续时间 非周期信号,1、时域的离散化与有限化,二、利用DFT逼近连续时间信号的频谱,2、频域的有限化与离散化,3、误差分析 1）.混叠现象 为避免混叠,由抽样定理可知，须满足 其中, 为抽样频率; 为信号的最高频率分量； 或者 其中,T为抽样间隔。,2）.频谱泄漏（截断误差） 在实际应用中，通常将所观测的信号 限制在一定的时间间隔内,也 就是说， 在时域对信号进行截断操作,或称作：加时 间窗,亦即用时间窗函数乘以信号,由卷积定 理可知，时域相乘,频域为卷积,这就造成拖 尾现象,称之为频谱泄漏.,0,n,0,n,n,3）.栅栏效应 用DFT计算频谱时，只是知道为频率 的整数倍处的频谱。在两个谱线之间 的情况就不知道,这相当通过一个栅栏观察 景象一样，故称作栅栏效应。 补零点加大周期 ，可使 变小来提高分辨力，以减少栅栏效应。,频谱分辨力,4.用DFT逼近连续时间信号