5-离散傅里叶变换与快速傅里叶变换

2020/4/27大连理工大学1PartII数字信号处理大连理工大学硕士研究生校管课程信号处理与数据分析电子信息与电气工程学部邱天爽2015年11月2020/4/27大连理工大学2第5章离散傅里叶变换与快速傅里叶变换大连理工大学硕士研究生校管课程信号处理与数据分析电子信息与电气工程学部邱天爽2015年11月内容概要•§5.1引言•§5.2离散傅里叶变换（DFT）•§5.3DFT理论与应用中若干问题•§5.4二维傅里叶变换简介•§5.5快速傅里叶变换（FFT）•§5.6FFT的主要应用2020/4/27大连理工大学4§5.1引言2020/4/27大连理工大学5•为什么要学习离散傅里叶变换（DFT）？–数字信号处理，要求信号是数字化的，也希望信号的频谱或系统的频率响应也是数字化的。–实际应用中的信号总是有限时宽的、且为非周期的。希望信号频谱也是有限频宽、且非周期的。–考察前面介绍的4种傅里叶级数或傅里叶变换，没有任何一种能够满足这种需求。–因此，发展新的傅里叶变换方法以适应数字信号处理实际应用的要求称为数字信号处理理论的一个重要任务。–这就为DFT的发展提供了需求和动力。2020/4/27大连理工大学6§5.2离散傅里叶变换（DFT）5.2.1已有傅里叶变换的简要回顾（1）FS：连续、周期；离散、非周期；大连理工大学7()xtka002jj2jj11()ed()ed()eektktTkTTktktTkkkkaxttxttTTxtaa2020/4/27大连理工大学8（2）DFS：离散、周期；离散、周期；（3）FT：连续、非周期；连续、非周期；–ka()xn002jj2jj11()e()e()eeknknNknNnNknknNkkkNkNaxnxnNNxnaa()xt(j)Xjj(j)()ed1()(j)ed2ttXxttxtX2020/4/27大连理工大学9（4）DTFT：离散、非周期；连续、周期；()xnj(e)Xjjjj2(e)()e1()(e)ed2nnnXxnxnX5.2.2由DFS到DFT•（1）DFT的导出与定义–由上节分析，在已给出的4种傅里叶级数与变换中，只有DFS在时域和频域都是离散的，且均为周期性的。–定义新符号：和分别表示周期性信号和频谱。–定义矩形序列符号和为–有限长序列和可以认为是周期性序列和的一个周期。大连理工大学10()xnka()NRn()NRk1,011,01()()0,0,NNnNkNRnRknk或其它其它()xnka()xnka2020/4/27大连理工大学11–再定义：–式中，（或）表示对取余数（或对取余数）。–这样，有：()()(())NxnxnNxn模()()NkkkNaaa模(())Nn()NknNkN()()()(())()NNNxnxnRnxnRn()()()NkkNkNaaRkaRk2020/4/27大连理工大学12•分析：–注意到，在DFS中，时间序列是周期性的，周期为N。–另一方面，周期为N的序列只有N点独立样本，其余的都重复。–DFS中，实际上只用了的N点数据。–这样，可以把N点长的非周期序列看成周期为N的序列的一个周期。()xn()xn2020/4/27大连理工大学13•离散傅里叶变换（DFT）•【假设】–设为有限长序列，点数为N，可将其看作周期为N的周期序列的一个周期；而把看作是的周期延拓，即：–称是的主值序列。–记为：–表示“对取余数”，或对取模值。()xn()xn()xn()xn()01()0xnnNxnn，（主值），其他()xn()xn()()(())NxnxnNxn模(())NxnnnNN()()rxnxnrN2020/4/27大连理工大学14•【例】–设为周期的序列，求两数对的余数。•【解】–因为：，故：–因为：，故：–这样：()xn9NN25,5nn25297n9((25))75(1)94n9((5))499(25)((25))(7)(5)((5))(4)xxxxxx2020/4/27大连理工大学15•DFT的定义：式中，211j00211j00()DFT[()]()e(),0,1,,111()IDFT[()]()e(),0,1,,1NNknknNNnnNNknknNNkkXkxnxnxnWkNxnXkXkXkWnNNN2jeNNW()xn()Xk22jje,eknknknknNNNNWW002jj2jj11()e()e()eeknknNknNnNknknNkkkNkNaxnxnNNxnaaDFS：离散、非周期；离散、非周期2020/4/27大连理工大学16–利用加窗函数–则DFT定义式改写为：–即DFT是DFS的一个周期。101101()()00NNnNkNRnRknk，，或，其它，其它1010()()()()()1()()()()()NnkNNNnNnkNNNkXkxnWRkXkRkxnXkWRnxnRnN2020/4/27大连理工大学17•（2）DFT的图形解释2020/4/27大连理工大学18•说明（参考上页图）–(a)长度为T的连续时间信号，其频谱为。–(b)时域采样信号：，其频谱仍为同周期脉冲序列。–(c)采样，连续时间信号离散化，频谱周期性延拓。–(d)频域采样信号。–(e)频域采样的结果，频谱离散化，信号周期性延拓。–(j)X()()SSnptTtnT2020/4/27大连理工大学19•DFT与DTFT及z变换的关系–设长为N点，则：其中：定义在整个z平面；仅在z平面单位圆上取值；是单位圆上N个等间距点上取值是的主值周期。()xnj11j001jje021jj20()()()(e)(e)()e()()()e(e)NNnnnnNnznNnkNknNXzxnzxnrXxnXzXkxnX()Xzj(e)X()Xk()Xkka()()kNXkaRk2020/4/27大连理工大学20•【例5.1】020406080100120140160180200-2-1012n幅度三个正弦信号的混合0204060801001201401601802000100200300f/Hz幅度混合信号的频谱5.2.3离散傅里叶变换的性质•DFT的性质大连理工大学212020/4/27大连理工大学22•DFT的性质（续）2020/4/27大连理工大学23•【线性性质】–若：–则：•【序列的圆周位移性质】–将延拓为，将位移，取主值区间上的序列值。即：–圆周位移：–若：–则：1122DFT()(),DFT()()xnXkxnXk1212DFT()()()()axnbxnaXkbXk()xn()xn()xn()(())()()()mNNNxnxnmRnxnmRn()DFT()()mkmmNXkxnWXkDFT()()xnXk2020/4/27大连理工大学24•【圆周位移的图形解释】左移=顺时针旋转右移=逆时针旋转2020/4/27大连理工大学25•【对偶性】–若：–则：•【帕色伐尔定理】–若：–则：DFT()()xnXkDFT()(())()(())()NNNNXnNxkRkNxNkRkDFT()()xnXk11**001()()()()NNnnxnynXkYkN2020/4/27大连理工大学26•【圆周共轭对称性】•若：•则：DFT()DFTRe()jIm()xnxnxn******ep*op*1DFT()(())()=(())()2DFT(())()()13DFTRe()()(())(())()214DFTjIm()()(())(())()25()(())(),()NNNNNNNNNNNNNNxnXkRkXNkRkxnRnXkxnXkXkXNkRkxnXkXkXNkRkXkXNkRkxn若*real6()(())()()imagenaryNNXkXNkRkxn，若2020/4/27大连理工大学27•【满足圆周共轭对称性的序列】2020/4/27大连理工大学28•【圆周卷积和性质】–若：–若：–则：1122DFT()(),DFT()()xnXkxnXk12()()()YkXkXk11201210()IDFT()()(())()()(())()NNNmNNNmynYkxmxnmRnxmxnmRn2020/4/27大连理工大学29–【圆周卷积和图示】把主值周期左边一个周期的数据反折到主值区间。右移，最右边的移至最左边2020/4/27大连理工大学30•【圆周相关性质】–若：–若：–则：DFT()(),DFT()()xnXkynYk*()()()xyRkXkYk1*01*0()IDFT()()(())()()(())()NxyxyNNnNNNnrmRkynxnmRmxnynmRm2020/4/27大连理工大学31•有限长序列的线性卷积和圆周卷积–（1）线性卷积–非零值区间：，其中和分别为两序列的长度。–其中，的非0区间为；–的非0区间为–线性卷积的长度：1112120()()()()()Nlmmynxmxnmxmxnm120,2NN121NNN1N2N1()xm101mN2()xnm201nmN2020/4/27大连理工大学32–（2）圆周卷积–将看成L点序列，，不足补0.–则–结论：•L点圆周卷积是线性卷积以L为周期的周期延拓序列的主值序列。•若，则L点圆周卷积能代表线性卷积。12()()()ynxnxn12(),()xnxn12,LNLN11221212(),01(),01(),()0,10,1xnnNxnnNxnxnNnLNnL1120()()(())()()()LLLlLmrynxmxnmRnynrlRn()yn121LNN2020/4/27大连理工大学33•离散傅里叶变换的逆变换–逆变换与正变换的区别：•有系数•指数有负号–具体应用时：10101IDFT()()DFT()()NnkNkNnkNnxnXkXkWNXkxnxkW1/NnknkNNWW*1***011()DFT()NnkNnxnXkWXkNN2020/4/27大连理工大学34§5.3DFT理论与应用中若干问题2020/4/27大连理工大学35•采样定理：–若采样定理不满足，则产生混叠，即频率响应周期延拓分量互相重叠。–若信号的频谱无限宽，则需要抗混叠滤波器进行预处理。–可选占信号能量98%左右的频带宽度的作为信号的最高频率，从而进一步确定采样频率。max2smaxs5.3.1频率混叠问题2020/4/27大连理工大学36•频谱泄漏的含义：截断信号的能量扩散到无穷宽的频带中去，称为频谱泄漏。•频谱泄漏的原因：–在实际应用中，观测信号总是要限制在一定的时间范围内。–这相当于信号与矩形窗函数相乘。–时域乘积对应于频域卷积，卷积的结果使的频