离散傅立叶变换及其快速算法.pptx

《离散傅立叶变换及其快速算法.pptx》由会员分享，可在线阅读，更多相关《离散傅立叶变换及其快速算法.pptx（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、DFT是现代信号处理桥梁从傅立叶变换到离散傅立叶变换，及其应用要解决两个问题：离散与量化，离散与量化，快速运算。快速运算。傅氏变换频域离散量化DFT(FFT)信号处理第1页/共83页 一连续时间、连续频率的傅立叶一连续时间、连续频率的傅立叶 变换变换0正变换：反变换：0t第2页/共83页对称性时域信号时域信号频域信号频域信号连续的连续的非周期的非周期的非周期的非周期的连续的连续的时域连续，则频域非周期。反之亦然。时域连续，则频域非周期。反之亦然。第3页/共83页二二.连续时间、离散频率傅里叶变换连续时间、离散频率傅里叶变换 傅立叶级数傅立叶级数0t-0第4页/共83页时域信号时域信号频域信号频

2、域信号连续的连续的周期的周期的非周期的非周期的离散的离散的时域：连续、周期（周期为时域：连续、周期（周期为T Tp p）频域：非周期、离散（谱线间隔频域：非周期、离散（谱线间隔2 2/T/Tp p）第5页/共83页三离散时间、连续频率的傅氏变换 序列的傅立叶变换x(nT)-T 0T 2Tt-2T第6页/共83页如果把序列看成是模拟信号的抽样，利用如果把序列看成是模拟信号的抽样，利用关系：关系：第7页/共83页时域信号时域信号频域信号频域信号离散的离散的非周期的非周期的周期的周期的连续的连续的时域：非周期、离散（取样间隔为时域：非周期、离散（取样间隔为T T）频域：连续、周期（周期为频域：连续、

3、周期（周期为 ）第8页/共83页0tt-T0T 2Tt-0第9页/共83页四离散时间、离散频率的傅立叶四离散时间、离散频率的傅立叶变换变换DFTDFT第10页/共83页由上述分析可知，要想在时域和频域都是离散的，由上述分析可知，要想在时域和频域都是离散的，那么两个域必须是周期的。那么两个域必须是周期的。时域信号时域信号频域信号频域信号离散的离散的周期的周期的周期的周期的离散的离散的第11页/共83页 对称关系时域周期性频域离散性时域离散性频域周期性时域非周期频域连续性 时域连续性频域非周期第12页/共83页 2.1 离散傅里叶变换（DFT）一、离散傅里叶级数（DFS）1、DFS的引入一个周期为

4、N的周期序列，即，k为任意整数，N为周期周期序列不能进行Z变换，因为其在n=-到+都周而复始永不衰减，即 z 平面上没有收敛域。但是，正象连续时间周期信号可用傅氏级数表达，周期序列也可用离散的傅氏级数来表示，也即用周期为N的正弦序列来表示。第13页/共83页周期为N的正弦序列其基频成分为：K次谐波序列为：但离散级数所有谐波成分中只有N个是独立的，这是与连续傅氏级数的不同之处，即因此第14页/共83页将周期序列展成离散傅里叶级数时，只需取k=0到(N-1)这N个独立的谐波分量，所以一个周期序列的离散傅里叶级数只需包含这N个复指数，2、利用正弦序列的周期性可求解系数。将上式两边乘以，并对一个周期求

5、和第15页/共83页第16页/共83页上式中部分显然只有当k=r时才有值为1,其他任意k值时均为零,所以有或写为1)可求N次谐波的系数2）也是一个由N个独立谐波分量组成的傅立叶级数3）为周期序列，周期为N。第17页/共83页时域上周期序列的离散傅里叶级数在频域上仍是一个周期序列。第18页/共83页是一个周期序列的离散傅里叶级数(DFS)变换对，这种对称关系可表为：3、DFS的表示习惯上：记，第19页/共83页DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列实际上只有N个序列值的信息是有用的，

6、因此周期序列与有限长序列有着本质的联系。则DFS变换对可写为DFS离散傅里叶级数变换IDFS离散傅里叶级数反变换。第20页/共83页4、DFS的几个主要特性：假设都是周期为N的两个周期序列，各自的离散傅里叶级数为：1）线性a,b为任意常数第21页/共83页 2）序列移位证因为及都是以N为周期的函数，所以有第22页/共83页由于 与对称的特点，同样可证明第23页/共83页 3）共轭对称性对于复序列其共轭序列满足证证:同理同理:第24页/共83页进一步可得共轭偶对称分量 共轭奇对称分量第25页/共83页4）周期卷积若则或第26页/共83页证：这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里

7、的卷积过程只限于一个周期内（即m=0N-1），称为周期卷积。例：、，周期为N=7,宽度分别为4和3，求周期卷积。结果仍为周期序列，周期为N。第27页/共83页 周 期 卷 积第28页/共83页由于DFS与IDFS的对称性，对周期序列乘积，存在着频域的周期卷积公式，若则第29页/共83页二、离散傅里叶变换（DFT）1、周期序列与有限长序列的关系我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上。一个有限长序列x(n)，长为N，为了引用周期序列的概念，假定一个周期序列，它由长度为N的有限长序列x(n)延拓而成，它们的关系：第30页/共83页2、周期序列的主值区间与主

8、值序列：对于周期序列，定义其第一个周期n=0N-1，为的“主值区间”，主值区间上的序列为主值序列x(n)。x(n)与的关系可描述为：数学表示：RN（n）为矩形序列。符号（n）N是余数运算表达式，表示n对N求余数。第31页/共83页第32页/共83页例：是周期为N=8的序列，求n=11和n=-2对N的余数。因此第33页/共83页3、频域上的主值区间与主值序列：周期序列的离散付氏级数也是一个周期序列，也可给它定义一个主值区间，以及主值序列X(k)。数学表示：第34页/共83页再看周期序列的离散傅里叶级数变换（DFS）公式：这两个公式的求和都只限于主值区间（0N-1），它们完全适用于主值序列x(n)

9、与X(k)，因而我们可得到一个新的定义有限长序列离散傅里叶变换定义。第35页/共83页4、离散傅立叶变换（DFT）长度为N的有限长序列x(n)，其离散傅里叶变换X(k)仍是一个长度为N的有限长序列，它们的关系为：x(n)与X(k)是一个有限长序列离散傅里叶变换对，已知x(n)就能唯一地确定X(k)，同样已知X(k)也就唯一地确定x(n)，实际上x(n)与X(k)都是长度为N的序列（复序列）都有N个独立值，因而具有等量的信息。有限长序列隐含着周期性。第36页/共83页（1）DFT的矩阵方程表示第37页/共83页2、DFT特性：以下讨论DFT的一些主要特性，这些特性都与周期序列的DFS有关。假定x

10、(n)与y(n)是长度为N的有限长序列，其各自的离散傅里叶变换分别为：X(k)=DFTx(n)Y(k)=DFTy(n)11)线性DFTax(n)+by(n)=aX(k)+bY(k),a,b为任意常数第38页/共83页(2)循环移位有限长序列x(n)的循环移位定义为：f(n)=x(n+m)NRN(n)含义：1)x(n+m)N表示x(n)的周期延拓序列的移位：2)x(n+m)NRN(n)表示对移位的周期序列x(n+m)N取主值序列,所以f(n)仍然是一个长度为N的有限长序列。f（n）实际上可看作序列x（n）排列在一个N等分圆周上，并向左旋转m位。第39页/共83页循环移位第40页/共83页圆周移位

11、移位前左移两位后第41页/共83页证：利用周期序列的移位特性：实 际 上，利 用 WN-mk的 周 期 性，将f(n)=x(n+m)NRN(n)代入DFT定义式，同样很容易证明。序列循环移位后的DFT为F（k）=DFTf（n）=X（k）第42页/共83页同样，对于频域有限长序列X(k)的循环移位，有如下反变换特性：IDFTX(k+l)NRN(k)=x（n）第43页/共83页（3）循环卷积若F（k）=X（k）Y（k）则或第44页/共83页证：这个卷积可看作是周期序列卷积后再取其主值序列。将F（k）周期延拓，得：则根据DFS的周期卷积公式：因0mN-1时，x(m)N=x(m)，因此经过简单的换元可

12、证明：第45页/共83页这一卷积过程与周期卷积比较，过程是一样的，只是这里只取结果的主值序列，由于卷积过程只在主值区间0mN-1内进行，所以实际上就是y（m）的圆周移位，称为“循环卷积”，习惯上常用符号“”表示循环卷积，以区别于线性卷积。第46页/共83页1）由有限长序列 x(n)、y(n)构造周期序列循环卷积过程:2）计算周期卷积 3）卷积 结果取主值第47页/共83页同样，若f(n)=x(n)y(n)，则第48页/共83页（4）有限长序列的线性卷积与循环卷积（循环卷积的应用）实际问题的大多数是求解线性卷积，如信号x（n）通 过 系 统 h（n），其 输 出 就 是 线 性 卷 积 y（n）

13、=x（n）*h（n）。而循环卷积比起线性卷积，在运算速度上有很大的优越性，它可以采用快速傅里叶变换（FFT）技术，若能利用循环卷积求线性卷积，会带来很大的方便。现在我们来讨论上述x（n）与h（n）的线性卷积，如果x（n）、h（n）为有限长序列，则在什么条件下能用循环卷积代替而不产生失真。第49页/共83页有限长序列的线性卷积：假定x（n）为有限长序列，长度为N，y（n）为有限长序列，长度为M，它们的线性卷积f（n）=x（n）*y（n）也应是有限长序列。因x（m）的非零区间：0mN-1，y(n-m)的非零区间：0n-mM-1，这两个不等式相加，得：0nN+M-2，在这区间以外不是x（m）=0，就

14、是y（n-m）=0，因而f（n）=0。因此，f（n）是一个长度为N+M-1的有限长序列。第50页/共83页循环卷积：重新构造两个有限长序列x（n）、y（n），长度均为LmaxN,M，序列x（n）只有前N个是非零值，后L-N个为补充的零值；序列y（n）只有前M个是非零值，后L-M个为补充的零值。为了分析x（n）与y（n）的循环卷积，先看x（n），y（n）的周期延拓：第51页/共83页其中f（n）就是线性卷积，也就是说，x（n）、y（n）周期延拓后的周期卷积，是x（n）、y（n）线性卷积的周期延拓，周期为L。它们的周期卷积序列为：第52页/共83页根据前面的分析，f（n）具有N+M-1个非零序列值

15、，因此，如果周期卷积的周期LN+M-1，那么f（n）周期延拓后，必然有一部分非零序列值要重叠，出现混淆现象。只有LN+M-1时，才不会产生交叠，这时f（n）的周期延拓中每一个周期L内，前N+M-1个序列值是f（n）的全部非零序列值，而剩下的L（N+M-1）点的序列则是补充的零值。循环卷积正是周期卷积取主值序列：所以使圆周卷积等于线性卷积而不产生混淆的必要条件是：LN+M-1第53页/共83页比较线性卷积与循环卷积例:设有两个序列，x（n）为N=4矩形序列，y（n）为M=6矩形序列，观察其线性卷积和圆周卷积。由线性卷积定义可直接验证，两者的线性卷积f（n）=x(n)*y(n)具有N+M-1=9个

16、非零值,其结果见下图左半部分(c)，不同L下的圆周卷积结果在图的右半部分。图线性卷积和循环卷积图中（d）、（e）、（f），反映了不同L下循环卷积与线性卷积之间的关系，图（d）中L=6，产生严重的混淆，致使fl(n)与f（n）已完全不同，图（e）中L=8，这时有两点（n=0，n=8）发生混淆失真，只有图（f）中，满足条件LN+M-1=9，循环卷积与线性卷积相同（与图（c）比较）。第54页/共83页（5）共轭对称性设x*（n）为x（n）的共轭复数序列，则DFTx*（n）=X*(N-k)证：DFTx*(n)0kN-1由于因此，DFTx*(n)第55页/共83页说明：当k=0时，应为X*(N-0)=X

17、*(0)，因为按定义X（k）只有N个值，即0kN-1，而XN已超出主值区间，但一般已习惯于把X（k）认为是分布在N等分的圆周上，它的末点就是它的起始点，即XN=X0，因此仍采用习惯表示式DFTx*（n）=X*（N-k）以下在所有对称特性讨论中，XN均应理解为XN=X0，同样，x(N)=x(0)。第56页/共83页利用循环卷积和共轭对称特性，可证明DFT形式下的Parseval定律：当y（n）=x（n）时，即为有限长序列的能量：第57页/共83页2.复序列的实部与虚部的DFT变换以xr（n）和xi（n）表示序列x（n）的实部与虚部即x（n）=xr（n）+jxi（n）则以第58页/共83页则以Xe

18、（k）和X0（K）表示实部与虚部序列的DFT，则第59页/共83页显然，Xe(k)与Xo(k)对称性：故因此,Xe(k)具有共轭对称性，称为X(k)的共轭偶对称分量。第60页/共83页用同样的方法可得到X0(k)=-X*0(N-k)即Xo(k)具有共轭反对称特性，称其为X(k)的共轭奇对称分量。对于纯实数序列x（n），即x（n）=xr（n），X（k）只有共轭偶对称部分，即X（k）=Xe（k），表明实数序列的DFT满足共轭对称性，利用这一特性，只要知道一半数目的 X（k），就可得到另一半的 X（k），这一特点在DFT运算中可以加以利用，以提高运算效率。第61页/共83页根据x（n）与X（k）的对

19、称性，同样可找到X（k）的实部、虚部与x（n）的共轭偶部与共轭奇部的关系。分别以xe（n）及x0（n）表示序列x（n）的圆周共轭偶部与圆周共轭奇部：同样应从圆周意义上理解x（N-0）=x（0）。可证明:DFTxe（n）=ReX（k）DFTx0（n）=jImX（k）第62页/共83页（6）选频性（对0有限制？）对复指数函数进行采样得复序列x（n）0nN-1其 中 q为 整 数。当 0=2/N时，x（n）=ej2nq/N,其离散傅里叶变换为第63页/共83页写成闭解形式 可见，当输入频率为q0时，变换X（K）的N个值中只有 X（q）=N，其余皆为零，如果输入信号为若干个不同频率的信号的组合，经离散

20、傅里叶变换后，不同的k上，X（k）将有一一对应的输出，因此，离散傅里叶变换算法实质上对频率具有选择性。第64页/共83页（7）DFT与Z变换有限长序列可以进行z变换比较z变换与DFT变换，可见，当z=w-kN时，即第65页/共83页图DFT与z变换oooooooooooX（ej）X（k）oRezjImzo第66页/共83页变量周期分辨率第67页/共83页是z平面单位圆上幅角为的点，即将z平面上的单位圆N等分后的第k点。1）X(k)也就是z变换在单位圆上等间隔的采样值。2）X（k）也可看作是对序列付氏变换X（ej）的采样，采样间隔为：N=2/N。即结论：第68页/共83页采样定律告诉我们，一个频

21、带有限的信号，可以对它进行时域采样而不丢失任何信息；DFT变换进一步告诉我们，对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息，这正反应了傅立叶变换中时域、频域的对称关系。它有十分重要的意义，由于时域上的采样，使我们能够采用数字技术来处理这些时域上的信号（序列），而DFT的理论不仅在时域，而且在频域也离散化，因此使得在频域采用数字技术处理成为可能。FFT就是频域数字处理中最有成效的一例。第69页/共83页（8）DFT形式下的Parseval定理第70页/共83页2.2 利用DFT做连续信号的频谱分析 一、利用DFT计算连续信号的频谱分析过程利用利用DFTDFT计算连续

22、信号的频谱计算连续信号的频谱采样截短DFT第71页/共83页 从图中可以看出，这是一次次的近似过程，首先，用离散采样信号的 DTFT 来近似连续信号 的傅立叶变换 ，其次，将x(n)截短，这一过程等效于用一矩形序列RN(n)与x(n)相乘，其DTFT为 最后，再对截短的信号作DFT第72页/共83页二、频谱分析的近似过程出现问题及解决办法1、混叠（1）混叠现象对连续信号x(t)进行数字处理前，要进行采样采样序列的频谱是连续信号频谱的周期延拓，周期为fs，如采样率过低，不满足采样定理，fs2fh，则导致频谱混迭，使一个周期内的谱对原信号谱产生失真，无法恢复原信号，进一步的数字处理失去依据。第73

23、页/共83页（2）解决办法 在采样前利用一模拟低通滤波器将原始信号的上限频率 限制在采样频率的一半，即加一抗混叠滤波器。第74页/共83页2、泄漏（1）产生原因处理实际信号序列x（n）时，一般总要将它截断为一有限长序列，长为N点，相当于乘以一个矩形窗w(n)=RN(n)。矩形窗函数，其频谱有主瓣，也有许多副瓣，窗口越大，主瓣越窄，当窗口趋于无穷大时，就是一个冲击函数。我们知道，时域的乘积对应频域的卷积，所以，加窗后的频谱实际是原信号频谱与矩形窗函数频谱的卷积，卷积的结果使频谱延伸到了主瓣以外，且一直延伸到无穷。当窗口无穷大时，与冲击函数的卷积才是其本身，这时无畸变，否则就有畸变。第75页/共8

24、3页例如，信号为，是一单线谱，但当加窗后，线谱与抽样函数进行卷积，原来在0处的一根谱线变成了以0为中心的，形状为抽样函数的谱线序列，原来在一个周期（s）内只有一个频率上有非零值，而现在一个周期内几乎所有频率上都有非零值，即的频率成份从0处“泄漏”到其它频率处去了。考虑各采样频率周期间频谱“泄漏”后的互相串漏，卷积后还有频谱混迭现象产生。（2）解决办法：增加截短的长度N，以减小泄漏。第76页/共83页第77页/共83页3、栅栏效应（1）栅栏效应的产生N点DFT是在频率区间0，2上对信号频谱进行N点等间隔采样，得到的是若干个离散的频谱点X（k），且它们限制在基频的整数倍上，这就好像在栅栏的一边通过

25、缝隙看另一边的景象一样，只能在离散点处看到真实的景象，其余部分频谱成分被遮挡，所以称之为栅栏效应。（2）减小栅栏效应方法：尾部补零，使谱线变密，增加频域采样点数，原来漏掉的某些频谱分量就可能被检测出来。第78页/共83页4、DFT的分辨率 填补零值可以改变对DTFT的采样密度，人们常常有一种误解，认为补零可以提高DFT的频率分辨率。事实上我们通常规定DFT的频率分辨率为 ，这里的N是指信号x(n)的有效长度，而不是补零的长度。不同长度的x(n)其DTFT的结果是不同的；而相同长度的x(n)尽管补零的长度不同其DTFT的结果应是相同的，他们的DFT只是反映了对相同的DTFT采用了不同的采样密度。

26、第79页/共83页参数选择的一般原则：(1)若已知信号的最高频率 ，为防止混叠，选定采样频率 ；(2)根据频率分辩率 ，确定所需DFT的长度(3)和N确定以后，即可确定相应模拟信号的时间长度这里T是采样周期。第80页/共83页5、周期信号的谱分析 对于连续的单一频率周期信号 ，为信号的频率。可以得到单一谱线的DFT结果，但这是和作DFT时数据的截取长度选得是否恰当有关，截取长度N选得合理，可完全等于 的采样。第81页/共83页051015-1-0.500.51t/Tx(n)0510150246810kX(k)051015-1-0.500.51t/Tx(n)0510150246810kX(k)(a)(b)(c)(d)不同截取长度的正弦信号及其DFT结果第82页/共83页感谢您的观看！第83页/共83页