《离散傅立叶变换》由会员分享，可在线阅读，更多相关《离散傅立叶变换（115页珍藏版）》请在金锄头文库上搜索。
1、第五章 傅立叶变换 离散傅立叶变换DFT,离散傅里叶变换,四种常用的傅立叶变换,时域,频域,离散,连续,离散时间傅立叶变换,连续,连续,连续时间傅立叶变换,离散,离散,离散傅立叶变换,连续,离散,连续时间傅立叶级数,信号与系统,数字信号处理,3/155,信号与系统与数字信号处理区别,数字信号处理,信号与系统,问题 分析系统 求系统,FT vs FS,DTFT vs DFT,FS vs DFT,连续时间傅立叶变换(FT),正变换 分解(提取),反变换 合成(还原),帕斯瓦尔定理，Parseval,物理意义：信号在时域的总能量等于信号在频域的总能量,非周期连续时间信号非周期连续频率函数,常见信号频
2、谱,连续时间傅立叶级数(FS),周期,正变换,反变换,收敛性 抽样定理,周期连续时间信号非周期离散频谱函数,常见信号频谱,离散时间傅里叶变换(DTFT),正变换,反变换,非周期离散信号周期连续频率函数,常见信号频谱,N点有限长序列,离散傅立叶变换 Discrete Fourier Transform DFT,定义,性质,IDFT证明,证明:,证明：,N2,N*(N-1),DFT、IDFT复数乘法 DFT、IDFT复数加法,例：,Xk的DFT频谱,yn与xn的关系？,频域采样,离散,连续,采样点数 M 信号长度 N,M N,对时域信号进行M点周期延拓,例：,对xn的DTFT 进行8点均匀抽样,求
3、其逆变换,若做4点抽样,其逆变换,解：,混叠,频域采样率不够，时域信号会发生混叠,离散,连续,插值,如何从离散频率点求任一频率？,插值公式,插值公式：由离散点计算连续频谱,33/155,等价于:FIR、卷积、 低通滤波、时域采样恢复,等价于?,DFT用于DTFT的数值估算,补零,M大小对Xk的影响?,M:采样点数 N:信号长度,解:,16点序列,32点序列,补零,以上序列DFT变换的结果？,16点序列DFT,补零至256点DFT,32点序列的DFT？ 256点序列的DFT？,0k 31, k=6,k=26； 0k 255,k=96,k=416;,当M足够大时，| Xk|的包络可逼近| X(ej
4、)|曲线。,DFT,DTFT,增大N可以提高信号DFT的频率分辨率,N越大越好,N大小与信号周期的关系,N=128和N=129时的DFT频谱,N为周期的整数倍频谱的尖峰为正弦的频率,N不是周期的整数倍出现模糊,单频模拟信号DFT宽频DFT频谱,原因？,129点,128点,时域上看,波形的突变产生多种频率分量,频域上看,结论,44/155,DFT 变换区间长度N不同，变换结果Xk不同。 当N确定后，Xk与xn是一一对应的。,2)当N足够大时，|Xk|的包络可逼近 | X(ej)|曲线。可用DFT逼近DTFT。,结论,3）| Xk|表示k=(2/N)k频点的幅度谱线。如果xn是一模拟信号的采样，采
5、样间隔为Ts，=Ts=2f/fs，则与k相对应的模拟频率fk为,1/NTs：频率分辨率,序列的循环移位,DFT的性质 : 有限长序列的运算,移位与循环移位,例：hn=2 2 1 1 , 0 n 3,h4=?, 2 1 1 2 ,h4=?,1 1 2 2 ,性质,证明,有限长序列的分类,共轭对称：,共轭反对称：,任意复序列可分解为共轭对称和共轭反对称部分,共轭对称部分,共轭反对称部分,特例：实序列,偶对称：,奇对称：,任意实序列可分解为偶对称和奇对称部分,偶对称部分,奇对称部分,圆周共轭对称：,圆周共轭反对称：,N点序列可分解为圆周共轭对称和圆周共轭反对称部分,圆周共轭对称部分,圆周共轭对称部分
6、,几何对称：,几何反对称：,DFT的对称关系,复序列DFT的对称关系,序列,DFT频谱,实序列DFT的对称关系,DFT频谱 对称关系,序列,DFT频谱,为何实序列有这样的对称关系？,xn=cos(0.1n)的DFT频谱,例：xn=cos(0.1n)的DFT频谱,DFT的性质,已知,线性：,循环时移,时移,DTFT,DFT,幅度(功率)谱不变，仅影响相位谱,DFT对偶：,N*N,N*(N-1),DFT、IDFT复数乘法 DFT、IDFT复数加法,快速傅立叶变换FFT,63/155,64/155,约需1800万次的16位加法 当初计算机的运算速度每秒几千次(取5千次) 不计移位等运算也约需1小时,
7、计算机诞生初期，利用计算机 做一个1024点16位DFT需要多久？,一幅1024*1024卫星图片(100万像素) ： 1024次 1024点 DFT需要42天 1次 100万点 DFT需要上百年,如何缩短计算时间？,65/155,2010诺贝尔物理学奖,2000诺贝尔物理学奖,1965年，J.W.Cooley 和 J.W.Tukey 首次提出了DFT运算的一种快速算法此后相继出现了各种用于计算机平台的改进FFT 算法FFT使DFT的运算时间可缩短一、二个数量级，使DFT的运算可以应用到实际中,67/155,算法优化：如何减少计算次数？,一次加法 两次乘法,一次加法 一次乘法,按时间抽取法,D
8、FT,N/2点DFT,时间抽取法蝶形运算,一次乘法，两次加法,偶部,奇部,按时间抽取蝶形FFT算法,最简单的蝶形计算单元：2点DFT,72/155,NL/2 * NL +,L = log2N,例：8点DFT分解过程第1层分解,73/155,74/155,8点DFT分解过程第2层分解,N=8 按时间抽取的FFT运算流图,75/155,8点DFT分解过程第3层分解,每层N/2个蝶型，逐渐变大,时间抽取FFT的时序特点：,观察上例中N=8，三层分解FFT算法的时序,二进制 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1,二进制 0 0 0 1 0 0
9、0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1,76/155,有何规律？,比特逆序,时间抽取法流程,两根谱线联合计算 时序抽乱 频序正常,比特逆序,例：N=8,输入顺序 0 1 2 3 4 5 6 7,二进制码 000 001 010 011 100 101 110 111,码位倒读 000 100 010 110 001 101 011 111,输出顺序 0 4 2 6 1 5 3 7,原位运算：,按时间抽取蝶形算法小结,运算量 加法运算次数 减少（N-1)/log2N 倍 乘法运算次数 减少 2N/log2N 倍时频序列的顺序 时域序会变乱 频谱的序正常,频率抽取法
10、,按k的奇偶将Xk分为两部分,偶序,奇序,频率抽取法蝶形运算,N=8按频率抽取的FFT算法过程,84/155,每层N/2个蝶形，逐渐变小,频率抽取法中的比特逆序,例：N=8,二进制 0 00 0 01 0 10 0 11 1 00 1 01 1 10 1 11,二进制 00 0 10 0 01 0 11 0 00 1 10 1 01 1 11 1,85/155,频域比特逆序,频率抽取法流程(蝶形变小、频域比特逆序),N=8 按时间抽取的FFT运算流图,87/155,无需另外存储空间,N=8 按频率抽取的FFT算法过程,88/155,无需另外存储空间,IFFT算法,IDFT,DFT,IFFT,运
11、算量分析：,乘法 加法DFT N2 N(N+1) FFT (N/2)log2N Nlog2N改善比 2N/log2N (N+1)/log2N,例：,DFT FFT 乘法 加法 乘法 加法128 16384 16512 448 896256 65536 65792 1024 2048516 2.7*105 2.7*105 2304 46081024 1.0*106 1.0*106 5120 10240,乘法、加法、浮点、定点,线性卷积的快速运算,N点线性卷积运算复杂度：乘法 N*N加法 N*(N-1),运算复杂度？,有无快速方法？,圆周卷积,回顾：N点序列的线性卷积,yLn的长度？,N点序列的圆
12、周卷积,yCn的长度？,线性卷积与圆周卷积的关系,线性卷积,圆周卷积,L=M+N-1点 圆周卷积 = 线性卷积,两个有限长序列的线性卷积,用DFT计算线性卷积,基本思想：线性卷积圆周卷积 DFT,IDFT计算,有限长序列与无限长序列的线性卷积,基本思想：无限长卷积有限长卷积之和,1. 重叠相加法,与hn 做L=M+N-1 点圆周卷积,2个 (M+N-1)点 DFT,2. 重叠保留法,与hn 做L=N3 圆计算量 线计算量 N=128 圆计算量 = 8% 线计算量,线性卷积,103/155,两个实序列DFT的计算,实序列DFT的计算,基本思想：利用DFT的对称性,2N点实序列DFT的计算,2N点实序列vn,歌曲：Dreams,分析其频谱特性，一次分析？,短时分析 短时(加窗)傅立叶变换,基音周期不同,语谱图 三维短时功率谱,声音 九色鹿,清音频谱能量分布在整个频率段内、无明显衰减,浊音频谱能量集中在低频率区、衰减较快,基于语谱图的清浊音分析,静音频谱能量很小,频率与乐谱,乐音：发音物体有规律地振动而产生的具有固定音高的音,112/155,五线谱与短时傅立叶分析,频谱,五线谱与短时傅立叶分析,小结,DTFT DFT FFT,
