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

1、数学公式的DFT还有经过计算才能吃完现实。DFT的计算方法优劣直接影响信号处理的速度。1离散傅里叶变换简写为当n和k从0N-1变化时，旋转因子WNkn 都在极坐标上绕单位圆旋转。X(k)和x(n)的计算形式相同。2)1(0 )(1)()1(0 )()(1010NnWkXNnxNkWnxkXNkknNNnknN5.1.1 直接计算频谱（1）不考虑旋转因子设旋转因子事先算好，并存在计算机存储器中。信号x(n)是N个复数的数组。计算全部频谱需复数乘N2次。计算全部频谱需复数加N(N-1)次。还有，每个k的X(k)都要用到全部x(n)；在算出全部X(k)前，x(n)要用2N个存储单元；X(k)要用2N

2、个存储单元；整个计算过程至少需要4N个存储单元。3（2）考虑旋转因子计算离散傅里叶变换需要旋转因子计算全部频谱需计算NN个旋转因子。旋转因子要计算余弦和正弦。从极坐标看，旋转因子是周期序列。利用周期性，计算离散傅里叶变换时，只需计算旋转因子的N个独立值。4)2sin()2cos()10,10(2knNjknNNnNkeWknNjknN5.1.2 直接计算卷积设信号x(n)和系统h(n)的长等于N，则系统的输出它的长度2N-1。直接计算卷积需乘N(2N-1)次，加(N-1)(2N-1)次。510)()()()()(Niinhixnhnxny利用卷积定理也能计算y(n)，条件是循环卷积的长2N-1

3、。当循环卷积的长=2N-1时，y(n)的频谱若先算好H(k)，用卷积定理求解y(n)的运算量是：6)220()()()(NkkHkXkY复数乘4N(2N-1)次，复数加2(2N-1)(2N-2)次。相比之下，直接卷积优于卷积定理。例5.1 设语音信号的采样率为6kHz，记录时间为1s，计算机复数乘1次需3s，复数加1次需1s。请问：该信号均分为6段，直接计算其频谱要多少时间？若分为3段，要多少时间？7解 总样本为6000，信号分为6段，直接计算频谱的时间为若把信号分为3段，则直接计算频谱的时间为若信号样本逐秒连续输入，这两种算法不能实时分析。8s24s)1999100031000(62s48s

4、)11999200032000(32直接按定义计算离散傅里叶变换，工作量与N2成正比，还与旋转因子的独立值有关。这是一种启示：缩短DFT长度和减少旋转因子独立值，可以降低DFT的计算量。如果把N点DFT的长度缩短一半，变成两个N/2点DFT的组合，那么，DFT的复乘可从N2变成N2/2，复加可从N(N-1)N2变成约N2/2次。常用的分解有：1、按时序的奇偶数将序列分成两段，2、按时序的前后将序列分为两段。9时域抽取的基本做法是，按时序的奇数和偶数分解序列成两段长度相同的子序列。这种算法要求序列的长度N满足5.3.1 时域抽取的原理基本时域抽取法分两步：第一，将序列分成两段；第二，整理频谱表达

5、式。（1）分解序列 按时序n的偶奇数将N点序列x(n)分解成两个子序列，10)(2是自然数MNM用x0(m)和x1(m)组成x(n)的N点DFT，11)12()()2()()(10mnnxmnnxnx)10()()()()()(1012/02/112/02/0NkkXWkXWmxWWmxkXkNNmkmNkNNmkmN（2）整理频谱为使X0(k)和X1(k)满足N/2点DFT的规定，同时又能反映X(k)的N个值，需对X(k)修改。当k=0N/2-1时，当k=N/2N-1时，r=0N/2-1。12)12/0()()()(10NkkXWkXkXkN)2/()2/()2/(12/0rNXWrNXrN

6、XrNN利用旋转因子的周期和对称性，并将符号r换为k，得到 修改后的DFT基本分解式该式的好处：k值减半，DFT的乘加法都减半，旋转因子也减半。13)12/0()()()2/(10NkkXWkXkNXkN)12/0()()()2/()()()(1010NkkXWkXkNXkXWkXkXkNkN5.3.2 原理的推广对N/2点X0(k)和X1(k)继续分解。将X0(k)分解为两个N/4点DFT，同理，X1(k)分解为两个N/4点DFT，14)14/0()()()4/()()()(102/000102/000NkkXWkXkNXkXWkXkXkNkN)14/0()()()4/()()()(112/

7、011112/011NkkXWkXkNXkXWkXkXkNkN为了方便分解，将分解公式变为信号流图，称蝶形图。有更简洁的形式，一个碟形运算需复乘1次复加2次。15例5.2 有一个8点离散傅里叶变换，请用蝶形图表示其时域抽取算法。解 遵循时域抽取法则，8点DFT可分解3次。16蝶形运算有两个重要特点。（1）反序输入序列的时序等于1点长DFT的下标，下标用二进制表示。它按从左到右递增的二进制顺序，称反序。（2）原位运算蝶形的输入数据在后面的蝶形都不再出现，蝶形运算结果的位置和输入的位置相同。称为原位运算，它能够节省计算机的存储器。17运用反序和原位运算，蝶形运算图的中间过程符号可略，变为这种时序的

8、奇偶分解DFT方法称时域抽取基2快速傅里叶变换，简称时域抽取快速傅里叶变换185.3.3 时域抽取的计算量把每次分解DFT当作一级，时域抽取的蝶形运算共有M级，每级有N/2个蝶，每个蝶复数乘1次复数加2次。所以，时域抽取算法需复数乘MN/2次，复数加MN次。比直接计算法的N2 少许多。19例5.3 设语音信号的采样率为6kHz，记录时间为1s，计算机复数乘1次需3s，复数加1次需1s。请问：该信号均分为6段，用时域抽取法计算频谱要多少时间？若分为3段，要多少时间？解 因时域抽取法要求N=2M，当信号分为6段时，每段有1000个样本，故取N=210。这时计算机的耗时20s15.0s)110241

9、032/102410(6若将信号分为3段，每段有2000个样本，故取N=211。这时计算机的耗时两种算法都能实时分析频谱。21s17.0s)120481132/204811(3例5.4 设计算机1次乘需3s，1次加需1s；用它计算1000点序列的频谱。请比较直接计算和时域抽取计算频谱的时间。解 若按DFT的定义直接计算频谱，取N=1000，这时计算机耗时22s 16s)12(9991000s)1234(10002若用时域抽取法计算频谱，取N=210，这时计算机的耗时两种结果相比，16/0.092174，时域抽取比直接计算快173倍。23ms 92s)12(101024s)1234(2/1010

10、24频域抽取的基本做法是：将离散傅里叶变换的序列从中间分解为等长的两段序列。这种算法要求序列的长5.4.1 频域抽取的原理频域抽取分两步：1、将序列按时序分两段，2、是整理短序列的频谱。（1）分解序列24)(2是自然数指数MNM12/02/12/0)2/(12/0)2/()()2/()()(NnknNkNNNnnNkNNnknNWWnNxnxWnNxWnxkX（2）整理频谱为了得到N/2点DFT，根据k的偶奇数将X(k)分解为两部分。偶数k的频谱 这时n和k都是N/2点，故X(2k)是真正的N/2点DFT。2512/02/12/022/2)2/()()2/()()2(NnknNNnknNkNN

11、WnNxnxWWnNxnxkX它们都是N/2点DFT，运算量比X(k)的运算量少近一半。5.4.2 原理的推广对N/2点的X0(k)和X1(k)继续分解，可得N/4点离散傅里叶变换。不过用图来表示比较简洁直观。26)12/0()()12()()()2()(12/02/1112/02/00NkWnxkXkXWnxkXkXNnknNNnknN例5.5 有个8点离散傅里叶变换，请用频域抽取法的蝶形图描述计算过程。解 根据频域抽取法则，8点DFT可分解3次。27根据蝶形图的原位运算，分解过程的序列符号可省略，频域抽取法的蝶形运算图可简化为285.4.3 频域抽取的计算量 频域抽取法的运算量和时域抽取法

12、的运算量相同。它全部蝶形运算需复数乘和复数加次数是5.4.4 两种算法的异同时域抽取法的输入倒序，频域抽取法的输出倒序；前者的蝶形先乘后加，后者的蝶形先加后乘；前者的蝶由小到大，后者的蝶由大到小。29)2(2/addmulMNNMNNMN离散傅里叶变换的用途很多，例如频谱分析，信息提取、快速卷积、信号压缩等；应用离散傅里叶变换时，往往还要离散傅里叶变换反变换。在设计产品时，该如何给离散傅里叶反变换编写有效的计算程序呢？5.5.1 仿效正变换因离散傅里叶变换的正变换为30)10()()(10NkWnxkXNnknN反变换为两者的计算方式除了系数1/N，其它相同。5.5.2 旋转因子共轭抽去x(n

13、)和X(k)的具体内容，剩下都是数字，它们的乘法相同，只是两种旋转因子的正负相反。它们不影响旋转因子的周期和反向对称。31)10()(1)(10NnWkXNnxNkknN只要我们在原来快速运算的基础上增加一个取WNkn的复共轭子程序，并乘1/N，就可以利用原有快速傅里叶变换程序，对数据X(k)进行反变换。5.5.3 频谱共轭对反变换公式取两次共轭，即32*)(*1*)(1)(1010NkknNNkknNWkXNWkXNnx为了程序的通用性，快速傅里叶变换大多按复数序列编写。怎样快速计算实数序列的频谱？5.6.1 直接运用把实数序列当作是虚部为0的复数序列，用现成的快速傅里叶变换程序对这个复数序

14、列进行计算。但计算机不是人，它不知道实数序列的虚部为0，0是不用算的。如果考虑计算机对这种复数序列的虚部运算量和存储器的需要，这种开销很大。335.6.2 合二为一先用两个同长实数序列x1(n)和x2(n)构建新序列，然后，运用快速傅里叶变换程序计算X(k)；最后，根据DFT的共轭对称性，这种分离只需复数加N次。34)10()()()(21Nnnjxnxnx)10(2)(*)()(2)(*)()(21NkjkXkXkXkXkXkXNN5.6.3 一分为二先将N点实数x(n)按n的奇偶分成x0(r)=x(2r)和x1(r)=x(2r+1)，r=0N/2-1，并组成y(r)=x0(r)+jx1(r

15、)；然后，将y(n)送入快速傅里叶变换程序，得Y(k)，k=0N/2-1，并用DFT的共轭对称性获取35)12/0(2)(*)()(2)(*)()(2/12/0NkjkYkYkXkYkYkXNN最后，根据时域抽取分解式，得x(n)的频谱因y(n)比x(n)长度减半，故这种算法的运算量比直接快速计算X(k)的运算量减少近一半。36)12/0()()()2/()()()(1010NkkXWkXkNXkXWkXkXkNkN离散傅里叶变换是分析和综合序列的理论，快速傅里叶变换是计算离散傅里叶变换的策略。5.7.1 信号分析例5.6 设导弹的最高时速v=2000km/h，雷达发射的微波x(t)=cos(

16、2f0t)，目标的反射波y(t)=cos2f0(t-r)。求y(t)的采样频率。若每3s发射一次0.1ms宽的微波脉冲x(t)，每3ms记录一段2ms长的y(t)，计算机复乘1次需20ns，复加1次需10ns。求直接计算和快速计算能否实时频谱分析。37解（1）采样频率确定采样频率前要知道x(t)的带宽。设雷达和目标的距离为d(t)，用泰勒级数表示为 38tddtdtddtd)0()0(!2)0(!1)0()0()(2d(0)和d(0)为导弹t=0时的距离和速度。信号往返的时间r=2d(t)/c，c=3108m/s为电磁波传播速度，所以，根据v=2000km/h，最大频偏f=2d(0)f0/c

17、111.2kHz。考虑fH=f0+f和f0=30000.2MHz，为满足带通采样定理fH=2nf，取f=200kHz可让n为整数，故采样频率fs=800kHz。39)/)0(4)/)0(21(2cos()/)0()0(2(2cos()(000cfdtcdfctddtfty（2）频谱分析因2ms的信号样本有1600个，根据频域采样定理，取N=1600，得按定义直接计算频谱的时间约76.8ms，它大于3ms间隔，故不能实时分析反射信号。按快速傅里叶变换计算频谱时，取N=211，其频谱计算的时间约0.45ms，小于3ms间隔，故可实时分析频谱。405.7.2 线性卷积线性卷积是系统加工信号的工具，若

18、信号x(n)和系统h(n)长2M，则它们卷积y(n)的长为2M+1-1，需实数乘加各需约22M+1次。例5.7 设信号x(n)和系统h(n)的长度N=1024=210，计算机乘1次要10ns，加1次要5ns。求计算机直接卷积和用快速卷积的时间。解（1）直接卷积因线性卷积的非0值长为2210-1，故计算卷积需乘约2220次，加约2220次，共耗时31.5ms。41（2）快速卷积先给序列x(n)和h(n)尾部添加零，延长它们到2N=211。h(n)的频谱可事先算好，存在计算机里，这样一来，快速卷积耗时约1.7ms。快速卷积比直接卷积快18倍。42信号长度往往比系统长很多时，快速卷积要分解序列。1.重叠相加法将输入信号分段，相邻段不重叠，每段分别与系统卷积，直接组合这些卷积即得输出。432.重叠保留法将输入信号分段，各段信号的首部为前段信号的尾部，各段信号与系统卷积后，连接起来就是输出。44用来连接的是N点循环卷积的后N-Lh+1点，这部分没有混叠失真。45