数字信号处理离散傅里叶变换DFT及其快速算法学习教案.pptx

《数字信号处理离散傅里叶变换DFT及其快速算法学习教案.pptx》由会员分享，可在线阅读，更多相关《数字信号处理离散傅里叶变换DFT及其快速算法学习教案.pptx（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数字信号处理数字信号处理(xn ho ch l)离散傅里叶变离散傅里叶变换换DFT及其快速算法及其快速算法第一页，共92页。n n傅 里 叶 变 换：建 立 以 时 间t 为 自 变 量 的“信 号”与 以 频 率 f为 自 变 量 的“频 率 函 数”(频谱)之 间 的 某 种 变 换 关 系.n n 所 以“时 间”或“频 率”取 连 续 还 是 离 散 值,就 形 成 各 种 不 同 形 式 的 傅 里 叶 变 换 对。傅里叶变换傅里叶变换(binhun)(binhun)的几种形式的几种形式第2页/共92页第二页，共92页。3.1 离散离散(lsn)傅里叶傅里叶变换的定义及物理意

2、变换的定义及物理意义义 模拟(mn)域 FT、LT 数字域 FT、ZT 数字域 DFT 时间(shjin)域 t:连续 频率域、s:连续 时间域 n:离散 频率域 k：离散 频率域、z：连续返回返回第3页/共92页第三页，共92页。DFT 的的图图形形(txng)解解释释第4页/共92页第四页，共92页。Z变换(binhun)、DTFT、DFT 的取值范围第5页/共92页第五页，共92页。四种四种(s zhn)傅立叶变傅立叶变换换第6页/共92页第六页，共92页。离散傅立叶变换（DFT）实现了信号(xnho)首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实

3、用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。因而具有重要的理论意义和应用价值，是本课程学习的一大重点。本节主要介绍返回返回(fnhu)p定义(dngy)p与ZT、FT、DFS的关系p的矩阵表示第7页/共92页第七页，共92页。定义定义定义定义(dngy)(dngy)设序列x(n)长度为M，定义(dngy)x(n)的N点DFT为式中，N称为离散傅里叶变换区间长度，要求N M。为书写简单，令 ，因此通常将N点DFT表示为定义(dngy)X(k)的N点离散傅里叶逆变换(IDFT)为长度(chngd)为N的离散序列返回返回回到本节回到本节第8页/共92页第八页，共92页。例3.1

4、：，分别(fnbi)计算x(n)的8点、16点DFT。解:x(n)的8点DFT为 x(n)的16点DFT为返回返回(fnhu)回到本节回到本节第9页/共92页第九页，共92页。是是是是 在频率区间在频率区间在频率区间在频率区间(q jin)(q jin)上的等间隔采样上的等间隔采样上的等间隔采样上的等间隔采样返回返回(fnhu)回到本节回到本节第10页/共92页第十页，共92页。与与与与ZTZT、FTFT、DFSDFS的关系的关系的关系的关系(gun x)(gun x)DFT有明确的物理意义，我们可以通过比较序列的DFT、FT、ZT，并将DFT与周期序列的DFS联系起来(q li)，得到DFT

5、的物理意义。DFT和FT、ZT之间的关系 假设序列的长度为M，NM将N点DFT和FT、ZT的定义重写如下 返回返回(fnhu)回到本节回到本节第11页/共92页第十一页，共92页。比较前面三式，得到 ，k=0,1,2,N-1 ，k=0,1,2,N-1 结论：(1)序列的N点DFT是序列傅里叶变换在频率区间(q jin)0，2上的N点等间隔采样，采样间隔为2/N。(2)序列的N点DFT是序列的Z变换在单位圆上的N点等间隔采样，频率采样间隔为2/N。返回返回(fnhu)回到本节回到本节第12页/共92页第十二页，共92页。DFT与z变换(binhun)X(ej)X(k)o1234567(N-1)k

6、=0 DFT与DTFT变换(binhun)序列序列x(n)的的N点点DFT是是 x(n)的的Z变换在单位变换在单位(dnwi)圆上的圆上的N点等间隔采样；点等间隔采样；X(k)为为x(n)的傅立叶变换的傅立叶变换 在区间在区间 上的上的N点点等间隔采样。这就是等间隔采样。这就是DFT的物理意义。的物理意义。第13页/共92页第十三页，共92页。变量(binling)周期(zhuq)分辨率返回返回(fnhu)回到本节回到本节第14页/共92页第十四页，共92页。DFT和和DFS之间的关系之间的关系(gun x)：周期延拓周期延拓 取主值取主值 有限长序列有限长序列 周期序列周期序列 主值区序列主

7、值区序列有限长序列有限长序列周期序列周期序列主值区间序列主值区间序列返回返回(fnhu)回到本节回到本节第15页/共92页第十五页，共92页。返回返回(fnhu)回到本节回到本节第16页/共92页第十六页，共92页。周期序列DFS:有限长序列的DFT:对比二者发现(fxin)：是 的主值区序列，条件NM返回返回(fnhu)回到本节回到本节第17页/共92页第十七页，共92页。DFSDFT返回返回(fnhu)回到本节回到本节第18页/共92页第十八页，共92页。DFTDFT与与与与DFSDFS之间的关系之间的关系之间的关系之间的关系(gun x):(gun x):有限长序列x(n)的DFT变换(

8、binhun)X(k)，就是x(n)的周期延拓序列 的DFS系数的主值序列返回返回(fnhu)回到本节回到本节第19页/共92页第十九页，共92页。DFSDFS与与与与FTFT之间的关系之间的关系之间的关系之间的关系(gun x):(gun x):n n周期延拓序列 的频谱特性由其傅里叶级数的n n系数 确定，幅度相差一个常数因子(ynz)。n nDFT的 是 的主值区序列，所以x(n)的n nDFT表示的是 周期序列的频谱特性。返回返回(fnhu)回到本节回到本节第20页/共92页第二十页，共92页。的矩阵的矩阵的矩阵的矩阵(j(j zhn)zhn)表示表示表示表示周期序列 的DFS以及有限

9、长序列x(n)的DFT如下可以发现它们右边的函数形式一样，但k的定义域不同，X(k)只是 的主值区序列，或者说X(k)以N为周期进行(jnxng)周期延拓即是 ，用后面两式表示二者的关系：返回返回(fnhu)回到本节回到本节第21页/共92页第二十一页，共92页。式说明了DFT和DFS之间的关系。这些关系式成立的条件是N M，即DFT的变换区间N不能小于x(n)的长度M。如果该条件不满足，按照式将x(n)进行延拓时，中将发生时域混叠，由式得到的X(k)不再(b zi)是x(n)的DFT，这时以上讲的DFS和DFT之间的关系不再(b zi)成立。返回返回(fnhu)回到本节回到本节第22页/共9

10、2页第二十二页，共92页。也可以(ky)表示成矩阵形式式中，X是N点DFT频域序列向量:x是时域序列向量:DN称为N点DFT矩阵，定义为返回返回(fnhu)回到本节回到本节第23页/共92页第二十三页，共92页。也可以(ky)表示为矩阵形式:称为N点IDFT矩阵，定义为从式和式，我们可以(ky)发现返回返回(fnhu)回到本节回到本节第24页/共92页第二十四页，共92页。3.2 DFT的主要的主要(zhyo)性质性质与序列的FT类似，DFT也有许多重要的性质。其中一些性质本质上与FT的相应性质相同，但是某些其他性质稍微有些(yuxi)差别。返回返回(fnhu)p 线性性质线性性质 p DFT

11、的隐含周期性的隐含周期性 p 循环移位性质循环移位性质 p 复共轭序列的复共轭序列的DFT p DFT的共轭对称性的共轭对称性 p 循环卷积定理循环卷积定理p 离散巴塞伐尔定理离散巴塞伐尔定理第25页/共92页第二十五页，共92页。线性性质线性性质 设有限长序列设有限长序列(xli)的长度分别为的长度分别为 ，a和和b为常数。为常数。则则式中式中 ，。返回返回(fnhu)回到本节回到本节第26页/共92页第二十六页，共92页。DFT的隐含周期性的隐含周期性 在第一节中，在第一节中，DFT和和IDFT只只定义了定义了X(k)和和x(n)在变换区间在变换区间上上的的N个值。如果个值。如果(rgu)

12、使使DFT中中k的取值域为的取值域为-，就会，就会发现发现X(k)是以是以N为周期的，即为周期的，即 X(k+mN)=X(k)称称X(k)的这一特性为的这一特性为DFT的隐的隐含周期性。含周期性。物理意义：物理意义：X(k)为为 在区间在区间 上的上的N点等间隔采样。点等间隔采样。以以2为周期，为周期，X(k)以以N为周为周期。期。返回返回(fnhu)回到本节回到本节第27页/共92页第二十七页，共92页。循环移位性质循环移位性质(xngzh)有限长序列的循环移位有限长序列的循环移位 设序列设序列x(n)的长度为的长度为M，对，对x(n)以以N（N M）为周期进）为周期进行周行周期延拓，得到期

13、延拓，得到定义定义x(n)的循环移位序列为的循环移位序列为上式表示将序列上式表示将序列x(n)以以N为周为周期进行周期延拓，再左移期进行周期延拓，再左移m个个单位并取主值序列，单位并取主值序列，就得到就得到x(n)的循环移位序列的循环移位序列y(n)。下图中下图中(a)、(b)、(c)和和(d)分分别描述了别描述了x(n)、k k 和和y(n)。图中。图中M=6，N=8，m=2。返回返回(fnhu)回到本节回到本节第28页/共92页第二十八页，共92页。序列(xli)的循环移位过程示意图返回返回(fnhu)回到本节回到本节第29页/共92页第二十九页，共92页。n n 循环移位性质 n n设序

14、列x(n)长度为M，x(n)的循环移位序列为n n ，N Mn n则 n n复共轭序列的DFT n n假设用 表示(biosh)x(n)的复共轭序列，长度为N，n n且 ，则n n ，k=0,1,2,N-1 n n式中，。n n同样：返回返回(fnhu)回到本节回到本节第30页/共92页第三十页，共92页。DFT的共轭对称性的共轭对称性上一章介绍上一章介绍(jisho)了序列了序列FT的共轭对称性，的共轭对称性，DFT也有类似也有类似的共轭的共轭对称性质。但对称性质。但FT中的共轭对中的共轭对称是指对坐标原点的共轭对称是指对坐标原点的共轭对称，在称，在DFT中指的是对变换区中指的是对变换区间的

15、中心，即间的中心，即N/2点的共轭对点的共轭对称。称。有限长共轭对称序列和共有限长共轭对称序列和共轭反对称序列轭反对称序列 k k假设有限长序列假设有限长序列 满足下式满足下式l l ，n=0,1,2,N-1 mm则称则称 为共轭对称序列。为共轭对称序列。n n假设有限长序列假设有限长序列 满足下式满足下式o o ，n=0,1,2,N-1 p p则称其为共轭反对称序列。则称其为共轭反对称序列。返回返回(fnhu)回到本节回到本节第31页/共92页第三十一页，共92页。任一有限长序列x(n)都可以用它的共轭对称分量和共轭反对称分量之和表示，即将上式中的n用N-n代替(dit)，并两边取共轭，得到

16、 由上面两式得到 和 与原序列x(n)的关系为 返回返回(fnhu)回到本节回到本节第32页/共92页第三十二页，共92页。DFT的共轭对称性质(xngzh)假设序列x(n)长度为N，其N点DFT用X(k)表示。将序列x(n)分成实部和虚部，相应x(n)的DFT分成共轭对称和共轭反对称两部分。即式中，则 返回返回(fnhu)回到本节回到本节第33页/共92页第三十三页，共92页。将序列x(n)分成共轭对称和共轭反对称两部分(b fen)，相应x(n)的DFT分成实部和虚部两部分(b fen)，即式中，则返回返回(fnhu)回到本节回到本节第34页/共92页第三十四页，共92页。实信号DFT的特

17、点设x(n)是长度为N的实序列，其N点DFT用X(k)表示(biosh)，我们从的结论可知道X(k)具有共轭对称性质，即如果将X(k)写成极坐标形式 ，由共轭对称性质，说明X(k)的模关于 k=N/2点偶对称 ，利用DFT的共轭对称性质可以减小实序列的DFT计算量：a)利用计算一个复序列的N点DFT，很容易求得两个不同 的实序列的N点DFT；b)实序列的2N点DFT，可以用复序列的N点DFT得到。返回返回(fnhu)回到本节回到本节第35页/共92页第三十五页，共92页。a)设 是实序列，长度均为N，用它们构成一个复序列 对上式进行(jnxng)N点DFT，得到利用的结论可以得到这样只计算一个

18、N点DFT，得到X(k)，用上面两式容易得到两个实序列的N点DFT。()返回返回(fnhu)回到本节回到本节第36页/共92页第三十六页，共92页。b)通过复序列的N点DFT得到实序列的2N点DFT。设 是一个长度为2N的实序列，首先分别用 中的偶数点和奇数点形成两个长度为N的新序列 ，即 再由 构造长度为N的复序列x(n)，即计算x(n)的N点DFT，因为 均是实序列，利用(lyng)式和式得到 。最后由 以得到实序列v(n)的2N点DFT，即V(k)。返回返回(fnhu)回到本节回到本节第37页/共92页第三十七页，共92页。实序列实序列实序列实序列(xli)2N(xli)2N点的点的点的

19、点的DFTDFT，拆分重组为，拆分重组为，拆分重组为，拆分重组为NN点复序点复序点复序点复序列列列列(xli)DFT(xli)DFT例如例如例如例如 是实序列，长度是实序列，长度是实序列，长度是实序列，长度(chngd)(chngd)为为为为2N2N拆分拆分拆分拆分重组重组重组重组NN点点点点DFTDFT返回返回(fnhu)回到本节回到本节第38页/共92页第三十八页，共92页。循环卷积定理循环卷积定理时域循环卷积定理是时域循环卷积定理是DFT中很中很重要的定理，具有很强的实用重要的定理，具有很强的实用性。已知系统输入性。已知系统输入(shr)和和系统的单位脉冲响应，计算系系统的单位脉冲响应，

20、计算系统的输统的输出，以及出，以及FIR滤波器用滤波器用FFT实实现等，都是该定理的重要应用。现等，都是该定理的重要应用。1.两个有限长序列的循环卷积两个有限长序列的循环卷积 k k设序列设序列h(n)和和x(n)的长度分别的长度分别为为N和和M。h(n)与与x(n)的的L点循点循l l环卷积定义为环卷积定义为mm式中，式中，L称为循环卷积的长度，称为循环卷积的长度，LmaxN，M。n n为了区别线性卷积，用为了区别线性卷积，用 表示表示循环卷积，用循环卷积，用 表示表示L点循点循o o环卷积，即环卷积，即 x(n)。LL返回返回(fnhu)回到本节回到本节第39页/共92页第三十九页，共92

21、页。有限长序列循环卷积的矩阵形式上式中右边第一个矩阵称为x(n)的L点循环矩阵，它的特点(tdin)是：(a)第一行是x(n)的L点循环倒相。x(0)不动，后面其它反转180放在他的后面。(b)第二行是第一行向右循环移一位；(c)第三行是第二行向右循环移一位；依次类推。返回返回(fnhu)回到本节回到本节第40页/共92页第四十页，共92页。例3.2：计算下面(xi mian)给出的两个长度为4的序列h(n)与x(n)的4点和8点循环卷积。解:按照式写出h(n)与x(n)的4点循环卷积矩阵形式为 返回返回(fnhu)回到本节回到本节第41页/共92页第四十一页，共92页。h(n)与x(n)的8

22、点循环(xnhun)卷积矩阵形式为 返回返回(fnhu)回到本节回到本节第42页/共92页第四十二页，共92页。2.DFT的时域循环卷积定理 设h(n)和x(n)长度分别为N和M，yc(n)为序列h(n)和x(n)的L点循环卷积，即 x(n)则 式中时域循环卷积定理表明，DFT将时域循环卷积关系，变换成频域的相乘关系。用时域循环卷积定理计算两个(lin)序列循环卷积运算的方框图如下图所示 图用DFT计算两个(lin)有限长序列L点循环卷积运算的方框图 L返回返回(fnhu)回到本节回到本节第43页/共92页第四十三页，共92页。3.DFT的频域循环卷积定理设h(n)和x(n)长度分别(fnbi

23、)为N和M，并且 ，则 式中，LmaxN,M。DFT：时域循环卷积 频域乘积离散巴塞伐尔定理 设长度为N的序列x(n)的N点DFT为X(k)，则 L返回返回(fnhu)回到本节回到本节第44页/共92页第四十四页，共92页。3.3 频域采样频域采样(ci yn)时域和频域的对偶原理时域和频域的对偶原理 对对时间序列时间序列x(n)x(n)的连续频谱的连续频谱函数在频域等间隔采样，则采样函数在频域等间隔采样，则采样得到的离散频谱对应的时域得到的离散频谱对应的时域序列必然是原时间序列序列必然是原时间序列x(n)x(n)的周的周期延拓序列。期延拓序列。而且仅对时域有限而且仅对时域有限(yuxin)(

24、yuxin)长序列，当满足频域采用定理长序列，当满足频域采用定理时，才时，才能由频域离散采样恢复原来的连能由频域离散采样恢复原来的连续频谱函数（或原时间序续频谱函数（或原时间序列）。列）。时域采样时域采样 频域周期延拓频域周期延拓 时域周期延拓时域周期延拓 频域采样频域采样本节讨论：频域采样定理、频率本节讨论：频域采样定理、频率采样条件、频域内插公式。采样条件、频域内插公式。返回返回(fnhu)第45页/共92页第四十五页，共92页。1.1.频域采样频域采样(ci yn)与频域采与频域采样样(ci yn)定理定理2.2.设任意序列设任意序列x(n)的的Z变换为变换为3.3.而且而且X(z)的收

25、敛域包含单位圆。的收敛域包含单位圆。以以2/N为采样为采样(ci yn)间隔，间隔，在单在单4.4.位圆上对位圆上对X(z)进行等间隔采样进行等间隔采样(ci yn)得到得到 5.5.实质上，实质上，是对是对x(n)的频谱函的频谱函数数 的等间隔采样的等间隔采样(ci yn)。因因6.6.为为 以以2 为周期，所以为周期，所以 是是以以N为周期的频域序列。为周期的频域序列。返回返回(fnhu)回到本节回到本节第46页/共92页第四十六页，共92页。根据离散傅里叶级数理论，必然是一个周期序列(xli)的DFS系数。经推导，我们能够得到上式说明频域采样 所对应 的时域周期序列(xli)是原序列x(

26、n)的周期延拓序列(xli)，延拓周期为N。根据DFT与DFS之间的关系知道，分别截取 和 的主值序列(xli)则 和 构成一对DFT 返回返回(fnhu)回到本节回到本节第47页/共92页第四十七页，共92页。式表明 是对X(z)在单位圆上的N点等间隔采样，即对 在频率区间0，2上的N点等间隔采样。式式说明，对应的时域有限长序列 就是原序列x(n)以N为周期的周期延拓序列的主值序列。综上所述，可以总结出频域采样定理:如果原序列x(n)长度为M，对 在频率区间0，2上等间隔采样N点，得到 ，则仅当采样点数NM时，才能由频域采样 恢复 ，否则将产生时域混叠失真，不能由 恢复原序列x(n)。定理告

27、诫我们，只有当时域序列x(n)为有限长时，以适当的采样间隔对其频谱函数 采样，才不会丢失(dis)信息。返回返回(fnhu)回到本节回到本节第48页/共92页第四十八页，共92页。返回返回(fnhu)回到本节回到本节第49页/共92页第四十九页，共92页。2.频域内插公式频域内插公式 所谓所谓(suwi)频域内插公式，就是频域内插公式，就是用频域采样用频域采样 表示表示X(z)和和 。频域内插公式是频域内插公式是FIR数字滤波器的数字滤波器的频率采样结构和频率采样频率采样结构和频率采样设计法的理论依据。设计法的理论依据。设序列设序列x(n)的长度为的长度为M，在，在Z平面平面单位圆上对单位圆上

28、对X(z)的采样点数的采样点数为为N，且满足频域采样定理，且满足频域采样定理（NM）。则有）。则有 返回返回(fnhu)回到本节回到本节第50页/共92页第五十页，共92页。将式代入式得到(d do)式中，。令则所以(suy)返回返回(fnhu)回到本节回到本节第51页/共92页第五十一页，共92页。式和式称为用 表示X(z)的z域内插公式。称为z域内插函数。将 带入(c)式并化简，得到用 表示 的内插公式和内插函数 :式和式将用于FIR数字滤波器的频率采样设计(shj)法的误差分析。返回返回(fnhu)回到本节回到本节第52页/共92页第五十二页，共92页。l保证了各采样点上的保证了各采样点

29、上的值与原序列值与原序列(xli)的频谱相同；的频谱相同；l采样点之间为采样值采样点之间为采样值与对应点的内插公式与对应点的内插公式相乘，并叠加而成。相乘，并叠加而成。返回返回(fnhu)回到本节回到本节第53页/共92页第五十三页，共92页。3.4 DFT的快速的快速(kui s)算法算法快速快速(kui s)傅里叶变换傅里叶变换(FFT)l lDFT使计算机在频域处理信号成为可能，但是当N很大时，直接计算N点DFT的计算量非常大。l l快速傅里叶变换（FFT，Fast Fourier Transform）可使实现DFT的运算量下降几个数量级，从而使数字信号处理的速度大大提高，工程应用成为可

30、能。l l人们已经(y jing)研究出多种FFT算法，它们的复杂度和运算效率各不相同。l l 本章主要介绍最基本的基2 FFT算法及其编程方法。返回返回(fnhu)第54页/共92页第五十四页，共92页。直接计算直接计算直接计算直接计算(j sun)DFT(j sun)DFT的特点及减少运算量的的特点及减少运算量的的特点及减少运算量的的特点及减少运算量的基本途径基本途径基本途径基本途径DFT计算量：计算量：长度为长度为N的序列的序列(xli)x(n)的的N点点DFT为为 计算计算X(k)的每一个值需要计算的每一个值需要计算N次复数乘法和次复数乘法和N-1次复数次复数加法，那么计算加法，那么计

31、算X(k)的的N个值需个值需要要N2次复数乘法和次复数乘法和(N-1)N次复数加法运算。当次复数加法运算。当N1时，时，N点点DFT的复数乘法和复数加的复数乘法和复数加法运算次数均与法运算次数均与N2成正比。成正比。返回返回(fnhu)回到本节回到本节第55页/共92页第五十五页，共92页。减少运算量方法：减少运算量方法：长序列分为短序列：长序列分为短序列：由于由于NN点点DFTDFT的运算量随的运算量随N2N2增长，因此，当增长，因此，当NN较大时，较大时，减少运算量的途径之一就是将减少运算量的途径之一就是将NN点点DFTDFT分解为几个较分解为几个较 短的短的DFTDFT进行进行(jnxn

32、g)(jnxng)计算，计算，则可大大减少其运算量。则可大大减少其运算量。旋转因子的周期性和对称性：旋转因子的周期性和对称性：的周期性：的周期性：的对称性：的对称性：返回返回(fnhu)回到本节回到本节第56页/共92页第五十六页，共92页。快速傅里叶变换就是不断地将长序列的DFT分解为短序列的DFT，并利用(lyng)的周期性和对称性及其一些特殊值来减少DFT运算量的快速算法。时间域抽取：频率域抽取：基基2时间时间(shjin)抽取抽取(Decimation in time)DIT-FFT算法算法基基2频率频率(pnl)抽取抽取(Decimation in frequency)DIF-FFT

33、算法算法返回返回回到本节回到本节第57页/共92页第五十七页，共92页。基基基基2 DIT-FFT 2 DIT-FFT 算法算法算法算法(sun f(sun f)基基2FFT要求要求(yoqi)DFT变换变换区间长度区间长度N=2M，M为自然数。为自然数。DIT-FFT算法算法 序列序列x(n)的的N点点DFT为为 将上面的和式按将上面的和式按n的奇偶性分解的奇偶性分解为为 返回返回(fnhu)回到本节回到本节第58页/共92页第五十八页，共92页。令x1(l)=x(2l),x2(l)=x(2l+1)，因为 ，所以上式可写成上式说明(shumng)，按n的奇偶性将x(n)分解为两个N/2长的序

34、列x1(l)和x2(l)，则N点DFT可分解为两个N/2点DFT来计算。用X1(k)和X2(k)分别表示x1(l)和x2(l)的N/2点DFT，即 返回返回(fnhu)回到本节回到本节第59页/共92页第五十九页，共92页。将式和式代入式，并利用X1(k)、X2(k)的隐含周期性可得到 这样，就将N点DFT的计算分解为计算两个(lin)N/2点离散傅里叶变换X1(k)和X2(k)，再计算式。返回返回(fnhu)回到本节回到本节第60页/共92页第六十页，共92页。蝶形图 蝶形图及运算(yn sun)功能 8点DFT一次时域抽取(chu q)分解运算流图 返回返回(fnhu)回到本节回到本节第6

35、1页/共92页第六十一页，共92页。8点DIT-FFT运算(yn sun)流图 返回返回(fnhu)回到本节回到本节第62页/共92页第六十二页，共92页。2.DIT-FFT的运算(yn sun)效率 DIT-FFT与DFT所需乘法(chngf)次数比较曲线返回返回(fnhu)回到本节回到本节第63页/共92页第六十三页，共92页。由8点DIT-FFT运算流图可见，N=2M时，其DIT-FFT运算流图由M级蝶形构成，每级有N/2个蝶形。因此，每级需要N/2次复数乘法运算和N次复数加法(jif)运算，M级蝶形所需复数乘法次数CM(2)和复数加法(jif)次数CA(2)分别为直接计算N点DFT的复

36、数乘法次数为N2，复数加法(jif)次数为(N-1)N。当N1时，N2/CM(2)1，所以N越大，DIT-FFT运算效率越高。DIT-FFT算法与DFT所需乘法次数与N的关系曲线见前页图示。返回返回(fnhu)回到本节回到本节第64页/共92页第六十四页，共92页。例3.3：N=210=1024时，DIT-FFT的运算(yn sun)效率为而当N=211=2048时有 DFT的乘法(chngf)次数DIT-FFT的乘法(chngf)次数返回返回(fnhu)回到本节回到本节第65页/共92页第六十五页，共92页。3.DIT-FFT的运算规律及编程思想 运算规律：（1）原位计算 （2）旋转(xun

37、zhun)因子的变化规律 （3）蝶形运算规律 （4）序列的倒序 （5）编程思想及程序框图返回返回(fnhu)回到本节回到本节第66页/共92页第六十六页，共92页。（1）原位计算）原位计算观察每个蝶形的两个输入和两观察每个蝶形的两个输入和两个输出个输出蝶形的输出可存入原输入数据蝶形的输出可存入原输入数据所占存储单元所占存储单元利用同一组存储单元存储输入、利用同一组存储单元存储输入、输出数据的方法，称为输出数据的方法，称为(chn wi)原位（址）计算。原位（址）计算。节约内存节约内存节省寻址的时间节省寻址的时间返回返回(fnhu)回到本节回到本节第67页/共92页第六十七页，共92页。（2）旋

38、转因子的变化规律N点DIT-FFT运算(yn sun)流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，p称为旋转因子的指数。由于各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子 与运算(yn sun)级数的关系。用L表示从左到右的运算(yn sun)级数（L=1,2,M）。返回返回(fnhu)回到本节回到本节第68页/共92页第六十八页，共92页。由8点DIT-FFT运算流图可以发现(fxin)，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下:L=1时 L=2时 L=3时 对N=2M的一般情况，第L级的旋转因子为返回返回(fn

39、hu)回到本节回到本节第69页/共92页第六十九页，共92页。由于所以这样，就可按上面(shng min)两个式子确定第L级运算的旋转因子。实际编程序时，L为最外层循环(xnhun)变量返回返回(fnhu)回到本节回到本节第70页/共92页第七十页，共92页。（3）蝶形运算规律）蝶形运算规律 设序列设序列x(n)经时域抽选（倒序）经时域抽选（倒序）后，存入数组后，存入数组A中。中。如果蝶形运算的两个输入数据如果蝶形运算的两个输入数据相距相距B个点，应用原位计个点，应用原位计算，则蝶形运算可表示成如下算，则蝶形运算可表示成如下(rxi)形式形式:式中式中下标下标L表示第表示第L级运算，级运算，A

40、L(J)则则表示第表示第L级运算后数组元素级运算后数组元素A(J)的值（即第的值（即第L级蝶形的输出级蝶形的输出数据）。而数据）。而AL-1(J)表示第表示第L级运算前级运算前A(J)的值（即第的值（即第L级级蝶形的输入数据）。蝶形的输入数据）。返回返回(fnhu)回到本节回到本节第71页/共92页第七十一页，共92页。用实数运算完成上述蝶形运算，可按下面的算法(sun f)进行：设式中，下标R表示取实部，I表示取虚部。则设 则返回返回(fnhu)回到本节回到本节第72页/共92页第七十二页，共92页。（4）序列的倒序）序列的倒序 DIT-FFT算法算法(sun f)的输出的输出X(k)为自然

41、顺序，但为了适应原为自然顺序，但为了适应原位计位计算，其输入序列不是按算，其输入序列不是按x(n)的自然的自然顺序排序，这种经过顺序排序，这种经过M-1次次偶奇抽选后的排序称为序列偶奇抽选后的排序称为序列x(n)的的倒序（倒位）。倒序（倒位）。因此，在运算之前应先对序列因此，在运算之前应先对序列x(n)进行倒序。进行倒序。由于由于N=2M，因此顺序数可用，因此顺序数可用M位二进制数（位二进制数（nM-1nM-2n1n0）表）表示。示。M次偶奇时域抽选过程如次偶奇时域抽选过程如右图所示。第一次按最低位右图所示。第一次按最低位n0的的0和和1将将x(n)分解为偶奇两分解为偶奇两组，第二次又按次低位

42、组，第二次又按次低位n1的的0、1值分别对偶奇组分解；依次值分别对偶奇组分解；依次类推，第类推，第M次按次按nM-1位分解，最位分解，最后得到二进制倒序数。后得到二进制倒序数。形成(xngchng)例序的树状图(N=23)返回返回(fnhu)回到本节回到本节第73页/共92页第七十三页，共92页。不按顺序排列不按顺序排列顺 序倒 序十进制数I二进制数二进制数十进制数 J012345671 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 104261537 按顺序(shnx)输出返回返回(f

43、nhu)回到本节回到本节第74页/共92页第七十四页，共92页。（5）编程思想及程序框图 先从输入端（第1级）开始，逐级进行，共进行M级运算。在进行第L级运算时，依次(yc)求出B=2L-1个不同的旋转因子，每求出一个旋转因子，就计算完它对应的所有2M-L个蝶形。这样，我们可用三重循环程序实现DIT-FFT运算，程序框图如右 程序运行后，数组A中存放的是x(n)的N点DFT，即X(k)=A(k)。图所示。返回返回(fnhu)回到本节回到本节第75页/共92页第七十五页，共92页。4.IDFT的高效算法 上述FFT算法流图也可以用于IDFT。比较DFT和IDFT的运算公式:只要(zhyo)将DF

44、T运算式中的因子改为，最后乘以1/N，就是IDFT的运算公式。所以，只要(zhyo)将上述的DIT-FFT算法中的旋转因子改为，最后的输出再乘以1/N，就可以用来计算IDFT。如果流图的输入是X(k)，则输出就是x(n)。返回返回(fnhu)回到本节回到本节第76页/共92页第七十六页，共92页。我们还可以直接调用FFT子程序计算IFFT：由于对上式两边同时取共轭，得到这样，可以先将X(k)取共轭，然后(rnhu)直接调用FFT子程序，或者送入FFT专用硬件设备进行FFT运算，最后对FFT结果取共轭并乘以1/N得到序列x(n)。返回返回(fnhu)回到本节回到本节第77页/共92页第七十七页，

45、共92页。3.5 DFT(FFT)应用应用(yngyng)举例举例 DFT因为具有快速(kui s)算法FFT，应用非常广泛，限于篇幅，这里仅介绍DFT在线性卷积和频谱分析两方面的应用。本节主要论述：返回返回(fnhu)p用DFT（FFT）计算两个有限长序列的线性卷积p用DFT计算有限长序列与无限长序列的线性卷积p用DFT对序列进行谱分析第78页/共92页第七十八页，共92页。用用用用DFT(FFT)DFT(FFT)计算计算计算计算(j sun)(j sun)两个有限长序两个有限长序两个有限长序两个有限长序列的线性卷积列的线性卷积列的线性卷积列的线性卷积 当h(n)或x(n)序列较长时，直接计

46、算线性卷积的时间(shjin)会很长，满足不了实时处理的要求。可用FFT将时域卷积变换为频域相乘来计算线性卷积，达到快速实时要求。下面求出线性卷积结果和循环卷积结果相等的条件：设h(n)长度为N，x(n)长度为M，yc(n)和y(n)分别表示h(n)与x(n)的L点循环卷积和线性卷积，有L返回返回(fnhu)回到本节回到本节第79页/共92页第七十九页，共92页。在式中 因此将上式与式对比，方括号部分就是移位(y wi)iL的线性卷积 ，因此得到返回返回(fnhu)回到本节回到本节第80页/共92页第八十页，共92页。式说明，L点循环卷积yc(n)等于线性卷积y(n)以L为周期的周期延拓序列的

47、主值序列。由于y(n)长度为N+M-1，所以，只有当LN+M-1时，式给出的周期延拓无混叠，才能使yc(n)=y(n)。LN+M-1是循环卷积结果和线性卷积结果相等(xingdng)的重要条件。只要满足该条件，就可以用下图计算线性卷积。返回返回(fnhu)回到本节回到本节第81页/共92页第八十一页，共92页。循环循环循环循环(xnhun)(xnhun)卷积计算线性卷积的运算量：卷积计算线性卷积的运算量：卷积计算线性卷积的运算量：卷积计算线性卷积的运算量：uu 小于直接计算线性卷积的运算量uu 可预先计算并存储，乘法的 uu 运算次数(csh)可降低：uu 又称快速卷积法返回返回(fnhu)回

48、到本节回到本节第82页/共92页第八十二页，共92页。例例例例3.43.4求求返回返回(fnhu)回到本节回到本节第83页/共92页第八十三页，共92页。用用用用DFTDFT计算有限计算有限计算有限计算有限(y(y uxin)uxin)长序列与无限长长序列与无限长长序列与无限长长序列与无限长序列的线性卷积序列的线性卷积序列的线性卷积序列的线性卷积 用用FFT计算有限长序列与无限长计算有限长序列与无限长序列的线性卷积序列的线性卷积 问题：问题：h(n)为某滤波器的单为某滤波器的单位脉冲响应位脉冲响应,长度有限长度有限 输入信号输入信号 x(n)很长，很长，h(n)要要补许多零再进行计算补许多零再

49、进行计算,计算量有很大的浪费计算量有很大的浪费(lngfi)解决方法：解决方法：重叠相加法重叠相加法 重叠保留法重叠保留法 重叠相加法：重叠相加法：将将x(n)分段，每段长度为分段，每段长度为M，然，然后依次计算各段与后依次计算各段与h(n)的卷积，再由各段的卷积结果得的卷积，再由各段的卷积结果得到到y(n)。返回返回(fnhu)回到本节回到本节第84页/共92页第八十四页，共92页。假设h(n)和x(n)是因果序列(xli)，对x(n)进行分段，每段长为M，则x(n)可以表示为如下形式:的长度为L=N+M-1。按照图用L点FFT和IFFT计算 ,再按式（）求和，得到。返回返回(fnhu)回到

50、本节回到本节第85页/共92页第八十五页，共92页。计算步骤计算步骤:(1)计算并保存计算并保存H(k)=DFTh(n)L，L=N+M-1，i=0；(2)读入读入 并计算并计算 ；(3)；(4)，n=0,1,2,L-1；(5)计算计算(6)i=i+1，返回（，返回（2）。）。说明：一般说明：一般x(n)是因果是因果(yngu)序列，假设初始条件序列，假设初始条件 。返回返回(fnhu)回到本节回到本节第86页/共92页第八十六页，共92页。(1)(1)重叠相加法重叠相加法重叠相加法重叠相加法由分段由分段由分段由分段(fn dun)(fn dun)卷积的各段相加构成总的卷积卷积的各段相加构成总的