第5章-信号处理的效率-《数字信号处理》课件.ppt

《第5章-信号处理的效率-《数字信号处理》课件.ppt》由会员分享，可在线阅读，更多相关《第5章-信号处理的效率-《数字信号处理》课件.ppt（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数字信号处理数字信号处理Enjoy ScienceEnjoy Science 一一种种理理论不不应只只停停留留在在是是否否能能运运用用上上，还应讲究究它它应用的效率。用的效率。DFT也是也是这样。5.1 直接直接计算算DFT的代价的代价 为了方便后面的方法探了方便后面的方法探讨，现在将离散傅里叶在将离散傅里叶变换写成更写成更简单的的形式，即形式，即第第5章章 信号信号处理的效率理的效率1数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.1.1 直接直接计算算频谱的代价的代价 现在在按按分分析析方方程程来来评估估，直直接接计算算离离散散傅傅里里叶叶变换的代价。的代价

2、。（1）不考）不考虑旋旋转因子因子 假假设设各各旋旋转转因因子子事事先先已已经经算算好好，并并存存储储在在计计算算机机的的存存储储器器中中。如如果果信信号号x(n)是是N个个复复数数的的数数组，计算算一一个个k的的频谱时，需需要要复复数数乘乘法法N次次；计算算全全部部k的的频谱时，需要的复数乘法次数，需要的复数乘法次数为 计算算一一个个k的的频谱时，需需要要复复数数加加法法N-1次次；计算算全部全部k的的频谱时，需要的复数加法次数是，需要的复数加法次数是(5.3)(5.4)2数字信号处理数字信号处理Enjoy ScienceEnjoy Science（2）考）考虑旋旋转因子因子 计算离散傅里叶

3、算离散傅里叶变换少不了少不了旋旋转因子因子因因为时序序n有有N个个值、频序序k也也有有N个个值，所所以以计算算全全部部k的的频谱时，需要，需要计算算NN=N2个旋个旋转因子。因子。如果从极坐如果从极坐标的表达式和的表达式和图形形来看，旋来看，旋转因子明因子明显是周期序列。是周期序列。利用旋利用旋转因子的周期特点，在因子的周期特点，在计算算离散傅里叶离散傅里叶变换时，只需，只需计算旋算旋转因子的因子的N个独立个独立值。(5.5)3数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.1.2 直接直接计算卷算卷积的代价的代价 假假设信信号号x(n)和和系系统h(n)的的长

4、度度都都等等于于N，则系系统的的输出出它的它的长度等于度等于2N-1。如如果果直直接接按按照照定定义计算算卷卷积，那那么么计算算n=02N-2的的y(n)需要的乘法运算量需要的乘法运算量同同时，需要的加法运算量，需要的加法运算量(5.8)(5.9)(5.10)4数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy Science复数加法次数复数加法次数复数的加法要由实数的加法组成。复数的加法要由实数的加法组成。相相比比之之下下，直直接接计计算算卷卷积的的方方法法优优于于用用卷卷积积定定理理来来计算卷算卷积的方的

5、方法。法。还还有有，直直接接计计算算卷卷积积和和利利用用卷卷积积定定理理来来计计算算卷卷积积，它它们们都有一个共同的特点，就是都有一个共同的特点，就是计计算量都与算量都与N2成正比。成正比。(5.13)图图5.26数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.2 离散傅里叶离散傅里叶变换计变换计算效率的提高算效率的提高 如如5.1.1所所述述，直直接接按按定定义来来计算算离离散散傅傅里里叶叶变换，这种种方方法法的的工工作作量量与与信信号号长度度N的的平平方方成成正正比比，还还与与旋旋转转因子的独立因子的独立值值有关。有关。不不过，这两两个个特特点点也也提提醒醒

6、我我们：缩短短DFT的的长长度度和和减减少少旋旋转转因因子子的的独独立立值值，可可以以降降低低离离散散傅傅里里叶叶变换的的计算量。算量。如如果果把把N点点离离散散傅傅里里叶叶变换的的长度度缩短短一一半半，即即变成成两两个个N/2点点DFT的的组组合合，那那么么，离离散散傅傅里里叶叶变变换换的的复复乘乘次次数数就就可可以以从从N2次次变变成成N2/2次次，复复加加次次数数可可以以从从N(N-1)N2次次变变成成约约N2/2次次。这这说说明明，把把离离散散傅傅里里叶叶变变换换分分解解成成较较短短的的离离散散傅傅里里叶叶变变换换，有有可可能能减减少少约一一半半的乘法次数和加法次数。的乘法次数和加法次

7、数。7数字信号处理数字信号处理Enjoy ScienceEnjoy Science 常常用用的的分分解解DFT的的方方法法有有两两种种：第第一一种种是是按按时时序序的的奇奇偶偶数数将将序序列列分分成成两两段段，第第二二种种是是按按时时序序的的前前后后将将序列序列分分割割为为两段。两段。5.3 时域抽取的快速算法域抽取的快速算法 时域域抽抽取取的的基基本本做做法法是是，按按时序序的的奇奇数数和和偶偶数数将将序序列列分分解解成成两两段段长度度相相同同的的子子序序列列。这这种种算算法法要要求求序序列的列的长长度度N必必须满须满足足5.3.1 时域抽取法的原理域抽取法的原理 基基本本的的时域域抽抽取取

8、法法分分两两个个步步骤完完成成：第第一一步步是是将将序序列列分分成成两两段段长度度相相同同的的短短序序列列，第第二二步步是是整整理理短短序序列的列的频谱表达式。表达式。(5.17)8数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy Science上式上式简化后得化后得（2）整理）整理频谱频谱表达式表达式 为为了了使使X0(k)和和X1(k)满满足足N/2点点DFT的的规定定，同同时又又能能反反映映X(k)的的N个个频频谱谱值值，需需要要对对关关系系式式(5.20)做做些些修改。修改。当当0kN/2-1时时，

9、频谱X(k)的的公公式式(5.20)和和原原来来一一样样，即即 当当N/2kN-1时时，令令频序序k=N/2+r，r=0N/2-1，并并将将k=N/2+r代入代入X(k)的公式的公式(5.20)，就能得到，就能得到(5.20)(5.21)(5.22)10数字信号处理数字信号处理Enjoy ScienceEnjoy Science利用旋利用旋转转因子的周期性和反向因子的周期性和反向对对称性，有称性，有用它用它们简们简化公式化公式X(N/2+r)，并将符号，并将符号r换为换为k，就可得就可得 修改公式修改公式(5.20)后，得到后，得到DFT的基本分解公式的基本分解公式它它将将N点点DFT分解分解

10、为为两个两个N/2点点DFT。(5.23)(5.24)(5.25)11数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.3.2 时时域抽取法的域抽取法的应应用用 既既然然，分分解解的的做做法法能能减减少少计算算量量，就就应对N/2=2M-1点离散傅里叶点离散傅里叶变换变换X0(k)和和X1(k)继续继续分解分解。将将X0(k)分分解解为两两个个N/4=2M-2点点的的离离散散傅傅里里叶叶变变换换，即即 同同理理，将将X1(k)分分解解为两两个个N/4=2M-2点点的的离离散散傅傅里里叶叶变

11、换，即，即 第第2次次分分解解使使2个个N/2点点DFT变成成4个个N/4点点DFT，两两个个N/2点的点的DFT的乘法和加法的乘法和加法计算量再减少一半。算量再减少一半。(5.26)(5.27)13数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy Science 例例题题5.2 有有一一个个N=8点点的的离离散散傅傅里里叶叶变换，请用用蝶蝶形形图表示它的表示它的时域抽取基域抽取基2快速傅里叶快速傅里叶变换的算法。的算法。解解 遵遵循循时域域抽抽取取法法的的规律律式式(5.25)，N=8点点长的的DFT需要

12、需要进行行3次分解就可以次分解就可以变成成8个个1点点长的的DFT。图图5.615数字信号处理数字信号处理Enjoy ScienceEnjoy Science 例例题题5.2显显示示，蝶蝶形形运运算算确确实实能能够够将将较较短短的的频频谱谱组组合合成成较较长长的的频频谱谱。除除此此之之外外，蝶蝶形形运运算算还有有两两个个重重要要特点。特点。（1）倒序倒序 输入入序序列列的的时序序等等于于1点点长DFT的的下下标，下下标是是用用二二进制制表表示示的的。这些些二二进制制下下标的的变化化规律律按按照照从从左左到到右右递增增的的二二进制制顺序序，即即在在最最左左边逐逐次次二二进制制加加1 1并并向右向

13、右进位，位，这种种规律称律称为倒序倒序。（2）原位运算原位运算 每每个个蝶蝶形形图图的的输输入入数数据据在在后后面面的的蝶蝶形形运运算算中中都都不不再再出出现现，并并且且蝶蝶形形运运算算运运算算结结果果的的位位置置和和其其输输入入数数据据的的位位置置相相同同。这个个特特点点称称为原原位位运运算算，它它能能够节省省计算机的存算机的存储器。器。反反序序和和原原位位运运算算的的特特点点在在计计算算机机中中很很容容易易实实现现，因它已被集成因它已被集成电电路路设计师设计师所考所考虑虑，实际的蝶形运用的蝶形运用16数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数

14、字信号处理Enjoy ScienceEnjoy Science5.3.3 时时域抽取法的运算量域抽取法的运算量 把把每每次次分分解解DFT当当作作一一级级来来看看待待，可可得得时时域域抽抽取取快速傅里叶快速傅里叶变换变换的运算特点：的运算特点：（1）每每级级的的蝶蝶形形个个数数都都是是N/2，时时域域抽抽取取法法的的分分解解共共有有M级级；（2）每个蝶形需要复数乘法）每个蝶形需要复数乘法1次，复数加法次，复数加法2次。次。根根据据这这两两个个运运算算特特点点，全全部部蝶蝶形形需需要要的的复复数数乘乘法法和复数加法的次数是和复数加法的次数是它它们比直接比直接计算法的算法的计算量算量N2少了少了许

15、多。多。(5.28)18数字信号处理数字信号处理Enjoy ScienceEnjoy Science 例例题题5.3 假假设计算算机机的的一一次次复复数数乘乘法法需需要要3微微秒秒，一一次次复复数数加加法法需需要要1微微秒秒；用用这台台计算算机机来来计算算一一个个1000点点序序列列的的频谱。请问采采用用直直接接计算算法法和和时域域抽抽取取快速算法快速算法进行行频谱计算，哪个方法比算，哪个方法比较快？快？解解 已已知知序序列列的的长度度是是1000点点，只只要要满足足频率率采采样定定理理，频率率采采样数数量量N1000，用用N点点离离散散傅傅里里叶叶变换就可以正确分析序列的就可以正确分析序列的

16、频谱。（1）直接直接计算法算法 为为了了减减少少计计算算量量，我我们们取取N=1000。按按照照公公式式(5.3)和和(5.4)，直接，直接计计算算频谱频谱的的时间时间是是(5.29)19数字信号处理数字信号处理Enjoy ScienceEnjoy Science（2）时域抽取法域抽取法 为为了了满满足足时时域域抽抽取取法法的的长长度度条条件件N=2M，我我们们取取N=1024=210。按按照照公公式式(5.28)，时时域域抽抽取取快快速速算算法法的的计计算算时间时间是是 比比较公公式式(5.29)和和(5.30)的的结果果，40.0256156，快速算法比直接算法快快速算法比直接算法快155

17、倍。倍。值得得强调一一下下，这里里介介绍的的时域域抽抽取取基基2快快速速傅傅里里叶叶变换并并不不是是什什么么新新的的傅傅里里叶叶变换，而而是是计算算离离散散傅傅里叶里叶变换的一种技巧。的一种技巧。(5.30)20数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.4 频频域抽取的快速算法域抽取的快速算法 频频域域抽抽取取快快速速算算法法的的基基本本做做法法是是，将将整整串串时间信信号号的的序序列列从从中中间切切开开，分分成成长度度相相等等的的两两段段子子序序列列。这这种算法要求序列的种算法要求序列的长长度度N必必须满须满足足5.4.1 频频域抽取法的原理域抽取法的原

18、理 频域域抽抽取取法法的的基基本本做做法法分分为两两步步：第第一一步步是是将将序序列列按按时时序序先先后后分分成成两两段段，第第二二步步是是整整理理短短序序列列的的频谱表达式。表达式。（1）按）按时时序的前后分解序列序的前后分解序列 将将n按按自自然然顺序序分分成成前前半半部部分分和和后后半半部部分分，相相应地地，序序列列x(n)就就变成成两两段段长度度相相等等的的短短序序列列，这样一一来，来，x(n)的的DFT是是(5.31)21数字信号处理数字信号处理Enjoy ScienceEnjoy Science（2）整理）整理频谱频谱表达式表达式 让让我我们们将将频频序序k k按按偶偶数数和和奇奇

19、数数分分类类，那那么么，偶偶数数频频序序的的个个数数和和奇奇数数频频序序的的个个数数就就变变成成N/2，长长频频谱谱就就可可以以变变成短成短频谱频谱。利利用用旋旋转转因因子子的的周周期期性性，公公式式(5.32)的的偶偶数数频序序的的频谱是是(5.32)22数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy Science 为为了了将将公公式式(5.33)和和(5.34)两两个个N/2点点DFT的的样样式式变变得更得更简洁简洁，突出，突出频频域抽取法的域抽取法的规规律，令律，令这这就就是是频频域域抽抽取取法法

20、的的基基本本分分解解公公式式，它它能能够够将将N点点DFT分解分解为为两个两个N/2点点DFT。将将公公式式(5.35)分分别别代代入入公公式式(5.33)和和(5.34)，并并重重新新排排列列它它们们的的偶偶数数频频序序和和奇奇数数频频序序，就就形形成成简简洁洁的的N/2点点DFT，即，即(5.35)(5.36)29节节24数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.4.2 频频域抽取法的域抽取法的应应用用 既既然然公公式式(5.35)表表示示的的N/2点点长长序序列列能能够够减减少少离离散散傅傅里里叶叶变变换换的的运运算算量量，我我们们就就有有理理由由对

21、对N/2=2M-1点点的的X0(k)和和X1(k)继继续续第第2次次同同样样的的分分解解，用用式式(5.35)将将X0(k)和和X1(k)变变成四个成四个N/4=2M-2点的离散傅里叶点的离散傅里叶变换变换。频频域抽取法的分解公式也可以用蝶形域抽取法的分解公式也可以用蝶形图图表示，表示，蝶蝶形形图的的左左边是是输入入信信号号，右右边是是输出出信信号号，右右上上角角是是输入信号之和，右下角是入信号之和，右下角是输入信号之差。入信号之差。用用蝶蝶形形图来来分分解解DFT比比用用公公式式来来分分解解DFT更更加加简简明扼要明扼要。下面来看蝶形下面来看蝶形图的的应用。用。图图5.825数字信号处理数字

22、信号处理Enjoy ScienceEnjoy Science 例例题题5.4 有有一一个个N=8点点的的离离散散傅傅里里叶叶变换，请用用频域域抽抽取取法法的的蝶蝶形形图来来描描述述它它的的频域域抽抽取取基基2快快速速傅傅里里叶叶变换的的计算算过程。程。解解 根根据据频频域域抽抽取取法法的的规规律律式式(5.35)，N=8的的DFT需需要要3次分解就能次分解就能缩缩短短为为8 8个个1点的点的DFT。图图5.926数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.4.3 频频域抽取法的运算量

23、域抽取法的运算量 频频域域抽抽取取法法的的DFT运运算算量量和和时时域域抽抽取取法法的的DFT运运算算量量相相同同，对对比比两两者者的的蝶蝶形形运运算算图图就就可可明明白白。频频域域抽抽取取法法完完成成全全部部蝶蝶形形运运算算需需要要的的复复数数乘乘法法和和复复数数加加法法的的次数是次数是5.4.4 两种快速算法的相似之两种快速算法的相似之处处 频频域域抽抽取取和和时时域域抽抽取取这这两两种种方方法法减减少少DFT运运算算量量的主的主导导思想是一思想是一样样的，都是的，都是缩缩短短DFT。不不管管是是时时域域抽抽取取算算法法还还是是频频域域抽抽取取算算法法，都都会会发发生生输输入入或或者者输输

24、出出序序列列的的倒倒序序排排列列。这这个个问问题题，集集成成电电路工程路工程师师在开在开发发DSP芯片芯片时时，已，已经经充分考充分考虑虑。(5.37)28数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.5 离散傅里叶离散傅里叶反反变换的快速算法的快速算法 离离散散傅傅里里叶叶变变换换的的用用途途很很多多，例例如如频频谱谱分分析析，信信息息提提取取、快快速速卷卷积积、信信号号压压缩缩等等；应应用用离离散散傅傅里里叶叶变变换换时时，往往往往还还需需要要对对离离散散傅傅里里叶叶变变换换做做反反变换。在在设设计计产产品品时时，该该如如何何给给离离散散傅傅里里叶叶反反变

25、变换换编编写写有有效效的的计计算程序呢？算程序呢？5.5.1 仿效快速傅里叶仿效快速傅里叶变换变换 只只要要按按照照前前面面介介绍绍的的两两种种快快速速傅傅里里叶叶变变换换法法，缩缩短短离离散散傅傅里里叶叶反反变换的的长度度，就就可可以以减减少少反反变换的的计算量。算量。对比离散傅里叶正比离散傅里叶正变换的定的定义，(5.38)29数字信号处理数字信号处理Enjoy ScienceEnjoy Science数字信号处理数字信号处理Enjoy ScienceEnjoy ScienceWNkn的的复复数数共共轭的的子子程程序序，就就可可以以利利用用原原有有的的快快速速傅傅里叶里叶变换程序，程序，对

26、数据数据X(k)进进行反行反变换变换的运算。的运算。5.5.3 取取频谱频谱的复共的复共轭轭 这这是个是个负负负负得正的道理，即得正的道理，即这这说说明明，只只要要增增添添两两个个取取复复数数共共轭的的子子程程序序，并并添添加加一一个个乘乘1/N的的子子程程序序，快快速速傅傅里里叶叶变换的的程程序序就就可可用用来来计算离散傅里叶反算离散傅里叶反变换。(5.40)31数字信号处理数字信号处理Enjoy ScienceEnjoy Science 值值得得说说明的是，理明的是，理论论和和实际实际是有差是有差别别的。的。理理论论上上，X(k)的的反反变变换换得得到到的的结结果果是是x(n)；如如果果x

27、(n)是是实实数数序序列列，反反变变换换得得到到的的结结果果也也应应该该是是实实数数序序列。列。实实际际上上，由由于于计计算算机机的的计计算算存存在在误误差差，如如果果x(n)是是实实数数序序列列，X(k)的的反反变变换换得得到到的的结结果果就就不不一一定定是是实实数序列，而是虚部不数序列，而是虚部不为为零的复数序列。零的复数序列。怎怎么么解解决决这这个个问问题题呢呢？解解决决的的方方法法是是：取取这这个个X(k)反反变换变换的的复数序列的复数序列的实实部当作部当作x(n)。32数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.6 实实数序列的快速傅里叶数序列的快

28、速傅里叶变换变换 为为了了考考虑虑通通用用性性，前前面面介介绍绍的的离离散散傅傅里里叶叶变变换换的的快快速速算算法法没没有有规规定定参参加加变变换换的的序序列列是是实实数数还还是是复复数数。快速傅里叶快速傅里叶变换变换的程序大多是按复数序列的程序大多是按复数序列编编写的。写的。由由于于许许多多信信号号或或序序列列都都是是实实数数，怎怎样样利利用用为为复复数数序序列列编编写写的的快快速速傅傅里里叶叶变变换换程程序序，快快速速计计算算实实数数序序列列的的频谱频谱呢？呢？5.6.1 直接运用直接运用 这这种种方方法法是是把把实实数数序序列列当当作作是是虚虚部部为为0的的复复数数序序列列，用用现现成成

29、的的快快速速傅傅里里叶叶变变换换程程序序对对这这个个复复数数序序列列进进行行计计算算。但但是是，计算算机机不不是是人人，它它不不知知道道实数数序序列列的的虚虚部部为0，而而0是是不不用用计算算的的。如如果果考考虑计算算机机对这种种复复数数序序列列的的虚虚部部的的运运算算量量和和存存储器器的的需需要要量量，这种种开开销是很大的。是很大的。33数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.6.2 合二合二为为一一 这这种种方方法法的的基基本本操操作作是是：首首先先，用用两两个个同同样长度度N的的实实数序列数序列x1(n)和和x2(n)构建一个新的序列构建一个新的序

30、列x(n)，然然后后，用用快快速速傅傅里里叶叶变变换换程程序序计计算算x(n)，就就可可以以得得到到两两个个实实数数序序列列的的频频谱谱。不不过过这这种种方方法法还还需需解解决决一一个个问问题题，也也就就是是怎怎样样从从x(n)的的频频谱谱X(k)中中分分离离出出x1(n)的的频频谱谱X1(k)和和x2(n)的的频谱频谱X2(k)。根据公式根据公式(5.41)和表和表4.6的共的共轭对称性，可以得到称性，可以得到(5.41)(5.42)34数字信号处理数字信号处理Enjoy ScienceEnjoy Science按按照照这这对对关关系系式式(5.42)编编写写一一个个子子程程序序，就就可可以

31、以从从X(k)中分离出来两个中分离出来两个实实数序列的数序列的频谱频谱X1(k)和和X2(k)。分分离离X1(k)和和X2(k)只只需需要要N次次加加法法和和N次次减减法法；虚虚数数符符号号j是是不不用用计计算算的的，因因为为在在计计算算机机里里根根本本不不存存在在j，实实数数和和虚虚数数的的区区别别只只是是它它们们所所在在的的存存储储器器位位置置不不同同而已。而已。还还有有，在在DSP芯芯片片的的应应用用中中，公公式式(5.42)中中的的除除以以2不不需需要要作作为为运运算算次次数数考考虑虑，因因为为DSP芯芯片片在在输输出出加加减减法法的的结结果果时时，具具有有自自动动向向左左或或向向右右

32、移移位位的的功功能能，这这种种移移位位丝丝毫毫不不影影响响加加减减法法的的运运算算速速度度，而而移移位位1点点相相当当于于乘乘2或除或除2。计算算X(k)需需要要复复数数乘乘法法NM/2次次，需需要要复复数数加加法法NM次次。合合二二为为一一法法计算算X1(k)和和X2(k)共共需需复复数数乘乘法法NM/2次，需要复数加法次，需要复数加法NM+2N次。次。30节节35数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.6.3 一分一分为为二二 它它的的基基本本做做法法是是：首首先先，将将实数数序序列列x(n)按按时时序序n的奇偶的奇偶分成两半，分成两半，得到两个得到

33、两个N/2点点长的序列，即的序列，即一一半半作作为为实实部部，另另一一半半作作为为虚虚部部，这这样样就就可可以以形形成成一一个比原来序列个比原来序列x(n)短一半的复数序列短一半的复数序列y(n)：然然后后，将将这这个个短短序序列列y(n)送送入入快快速速傅傅里里叶叶变变换换的的应应用用程序程序进进行行计计算，就能得到算，就能得到频谱频谱Y(k)。这种种方方法法虽好好，但但还要要解解决决一一个个问题，即即从从短短序序列列y(n)的的频谱Y(k)中恢复中恢复长序列序列x(n)的的频谱X(k)。(5.43)(5.44)36数字信号处理数字信号处理Enjoy ScienceEnjoy Science

34、 根据表根据表4.6的共的共轭对轭对称性知道，称性知道，利利用用X0(k)是是偶偶时时序序x0(r)的的N/2点点DFT，X1(k)是是奇奇时时序序x1(r)的的N/2点点DFT；并并根根据据时时域域抽抽取取快快速速傅傅里里叶叶变变换换法法的分解公式的分解公式(5.25)，被抽取的，被抽取的长长序列序列x(n)的的频谱频谱是是 相相对Y(k)的的计算算来来说，公公式式(5.45)和和(5.46)的的计算算量量是是不不大大的的：因因为Y(k)需需要要复复乘乘N(M-1)/4次次、复复加加N(M-1)/2次次，X0(k)和和X1(k)共共需需复复加加N次次，X(k)需需要要复复乘乘N/2次次、复复

35、加加N次次；这说明明，一一分分为为二二法法花花费的的功功夫小，收到的成效大。夫小，收到的成效大。(5.45)(5.46)37数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.7 快速傅里叶快速傅里叶变换变换的的应应用用 准准确确地地说说，离离散散傅傅里里叶叶变变换换是是分分析析序序列列和和综综合合序序列列的的理理论论，快快速速傅傅里里叶叶变变换换是是实实施施离离散散傅傅里里叶叶变变换换的的策策略略。在在快快速速傅傅里里叶叶变变换换的的支支持持下下，离离散散傅傅里里叶叶变变换换才能有效地才能有效地应应用到用到许许多多领领域。域。5.7.1 提高信号分析的提高信号分析

36、的计计算速度算速度 例例题题5.5 设导弹的的最最高高时速速v=2000km/h，雷雷达达发射射的的微微波波信信号号x(t)=cos(2f0t)，f0=30000.2MHz，目目标反反射射的的回回波波信信号号y(t)=cos2f0(t-r)，r是是x(t)从从雷雷达达传播播到到达达目目标再再从从目目标回回到到雷雷达达所所消消耗耗的的时间。请问，对回波信号回波信号y(t)模数模数转换的最低采的最低采样频率率应该取多少？取多少？基于以上条件，用离散傅里叶基于以上条件，用离散傅里叶变换分析回波信号分析回波信号38数字信号处理数字信号处理Enjoy ScienceEnjoy Science中中的的目目

37、标信信息息。如如果果雷雷达达发射射器器每每3秒秒发射射一一次次0.1ms宽的的微微波波脉脉冲冲x(t)，且且雷雷达达接接收收器器每每3ms记录一一批批2ms长的的回回波波信信号号y(t)，计算算机机复复乘乘一一次次需需要要20ns，复复加加一一次次需需要要10ns。请问，直直接接计算算法法和和快快速速计算算法法能能够胜任任实时频谱分析分析吗？解解（1）设计设计采采样频样频率率 微微波波信信号号的的频频率率非非常常高高，按按照照普普通通采采样样定定理理选选择择采采样样频频率率是是不不现现实实的的，应应该该按按照照带带通通采采样样策策略略选选择择采采样频样频率率fs=2B。带宽B可可从从y(t)=

38、cos2f0(t-r)获取取。因因为导弹是是运运动的的，如如图5.11所所示示，所所以以微微波波信信号号的的往往返返时间r会会变化，写化，写为(5.47)39数字信号处理数字信号处理Enjoy ScienceEnjoy Science 时时间间公公式式(5.47)中中的的距距离离d(t)与与目目标标的的运运动动时时间间有有关，关，这个函数个函数d(t)可用可用泰勒泰勒级数展开，即数展开，即其其d0是目是目标静止静止时的距离。的距离。将将距距离离公公式式(5.48)代代入入时间公公式式(5.47)，再再将将r代代入入回回波信号公式中，得到波信号公式中，得到图图5.11(5.48)40数字信号处理

39、数字信号处理Enjoy ScienceEnjoy Science 上上式式表表明明，发射射信信号号x(t)的的原原频频率率f0在在y(t)中中发发生生了了变变化化，原原因因是是导导弹弹的的运运动动速速度度d0，d0使使反反射射信信号号y(t)变成了成了带通信号。通信号。y(t)对于于载载波波频频率率f0的偏移的偏移 考考虑虑到到导导弹弹的的正正反反方方向向，带带通通信信号号y(t)的的最最大大带带宽宽B=2|b|max。将将最最大大速速度度|d0|max=v=2000km/h556m/s和和载载波波频频率率f0=30000200kHz代代入入公公式式(5.50)，可可以以得得到到最最大大频频偏

40、偏(5.49)(5.50)(5.51)41数字信号处理数字信号处理Enjoy ScienceEnjoy Science 根据根据带带通采通采样样条件条件让我我们取取频偏偏|b|max=200kHz。虽然然这么么宽的的频偏偏会会引引入入与与雷雷达达信信号号无无关关的的其其它它频率率成成分分，但但是是这些些问题在在数数字字域域很很好好解解决决，而而且且还能能减减轻模模拟抗抗折折叠叠带通通滤波波器的器的压力。力。按按|b|max=200kHz计计 算算，fL=30000000kHz，B=400kHz，式式(5.52)中中的的m=75000是是整整数数，所所以以，最最低采低采样频样频率率fs=800k

41、Hz，符合，符合带带通采通采样样的条件。的条件。（2）估算分析信号的估算分析信号的时间时间 若以此采若以此采样样速率速率对对回波信号回波信号进进行分析，行分析，记录记录每一每一(5.52)42数字信号处理数字信号处理Enjoy ScienceEnjoy Science批信号的批信号的样样本数本数R=2msfs=1600个。个。直接直接计算法分析一批信号的算法分析一批信号的频谱需要的需要的时间它它远大大于于3毫毫秒秒的的记录间隔隔，故故直直接接法法不不能能实时分分析析回回波信号。波信号。采采用用快快速速计计算算法法时时，样样本本长长度度N必必须须等等于于2M，N必必须大大于于等等于于R。通通过过

42、在在y(n)后后面面补零零的的方方法法，使使y(n)变为N=211=2048的的长度。度。快速快速计算法分析一批信号的算法分析一批信号的频谱需要的需要的时间它它远小小于于3毫毫秒秒的的记录间隔隔，故故快快速速法法可可以以实时分分析析回回波信号。波信号。(5.53)(5.54)43数字信号处理数字信号处理Enjoy ScienceEnjoy Science5.7.2 提高提高线线性卷性卷积积的的计计算速度算速度 线线性性卷卷积积是是系系统统加加工工信信号号的的数数学学工工具具，它它的的计计算算量量非非常常大大。在在实实时时应应用用中中，要要求求计计算算机机能能及及时时处处理理输输入入信信号号，并

43、并按按输输入入信信号号的的速速度度及及时时输输出出达达到到要要求求的的信信号号。为为了了降降低低设设备备的的成成本本和和减减小小生生产产难难度度，必必须须尽尽可可能地减少卷能地减少卷积积的运算量。的运算量。例例题题5.6 设设信信号号x(n)和和系系统统h(n)的的长长度度N=1024=210，计计算算机机乘乘法法1次次需需要要10纳纳秒秒，加加法法1次次需需要要5纳纳秒秒。请请分分析析计计算算机机直直接接计计算算线线性性卷卷积积的的时时间间和和用用FFT计计算算卷卷积积的的时间时间各是多少？各是多少？解解（1）直接卷直接卷积积44数字信号处理数字信号处理Enjoy ScienceEnjoy

44、Science 根根据据同同等等长长度度序序列列的的直直接接卷卷积积公公式式(5.9)和和(5.10)，计计算算x(n)和和h(n)的卷的卷积积需要的需要的时间时间是是（2）快速卷快速卷积积 先先给给序序列列x(n)和和h(n)的的尾尾部部添添加加零零，延延长长它它们们的的长长度度到到2N=211（为为什什么么？）。系系统统h(n)的的2N点点频频谱谱可可以以事先事先计计算好存放在算好存放在计计算机的存算机的存储储器中，器中，如如图5.12所示，所示，(5.57)图图5.1245数字信号处理数字信号处理Enjoy ScienceEnjoy Science这这么么一一来来，按按照照FFT算算法法

45、计计算算X(k)需需要要复复数数乘乘法法2M+1(M+1)/2次次、复复 数数 加加 法法 2M+1(M+1)次次，Y(k)=X(k)H(k)需需 要要 复复 数数 乘乘 法法 2M+1次次，用用 FFT计 算算y(n)=IDFTX(k)H(k)需需要要复复数数乘乘法法2M+1(M+1)/2次次、复数加法复数加法2M+1(M+1)次次，如此得到如此得到卷卷积积需要的需要的总时间时间是是 有比有比较较才有才有鉴别鉴别，两种方法的，两种方法的计计算算时间时间分分别为别为：T直接直接=31.5ms，T快速快速=1.7ms，快速卷快速卷积的速度比直接卷的速度比直接卷积的速度快的速度快1818倍！倍！(5.58)31节节46