《数字信号处理 教学课件 ppt 作者 杨毅明 2013版 第5章 信号处理的效率》由会员分享，可在线阅读，更多相关《数字信号处理 教学课件 ppt 作者 杨毅明 2013版 第5章 信号处理的效率（46页珍藏版）》请在金锄头文库上搜索。
1、一种理论不应只停留在是否能运用上，还应当讲究应用的效率。 5.1 直接计算离散傅里叶变换的代价 为了方便后面的方法探讨，现在将离散傅里叶变换写成较简单的形式，即,第5章 信号处理的效率,(5.1),(5.2),5.1.1 直接计算频谱的代价 现在按照分析方程评估直接计算离散傅里叶变换的代价。 （1）不考虑旋转因子 假设旋转因子事先已经算好，存储在计算机的存储器中。如果信号x(n)是N个复数的数组，计算全部k的频谱时，需要的复数乘法次数是 需要的复数加法次数是,(5.3),(5.4),（2）考虑旋转因子 计算离散傅里叶变换少不了旋转因子 因为时序n有N个值、频序k也有N个值，所以计算全部k的频谱
2、需要计算NN=N2个旋转因子。 如果从极坐标的表达方式和图形来看旋转因子，旋转因子是周期序列。利用旋转因子的周期特点，在计算离散傅里叶变换时，只需计算旋转因子的N个独立值。,(5.5),5.1.2 直接计算卷积的代价 假设信号x(n)和系统h(n)的长度都是N，则系统的输出 如果直接按照卷积公式计算，需要的乘法运算量 需要的加法运算量,(5.8),(5.9),(5.10),如果运用DFT的卷积定理，取循环卷积的长度为2N-1，并利用表4.5的卷积定理，就可以得到系统的输出频谱 在事先计算好系统频谱H(k)的条件下，用卷积定理求解y(n)的运算量是：复数乘法次数 复数加法次数 直接计算卷积和利用
3、卷积定理计算卷积的计算量都与N2成正比。相比之下，直接计算法优于卷积定理法。,(5.11),(5.12),(5.13),5.2 离散傅里叶变换计算效率的提高 直接按定义来计算离散傅里叶变换，这种方法的工作量与信号长度N的平方成正比，还与旋转因子的独立值有关。 这两个特点暗示：缩短DFT的长度和减少旋转因子的独立值，可以降低离散傅里叶变换的计算量。 如果把N点离散傅里叶变换的长度缩短一半，即变成两个N/2点DFT的组合，那么，离散傅里叶变换的复乘次数就可以从N2次变成N2/2次，复加次数可以从N(N-1)N2次变成约N2/2次。这说明，把离散傅里叶变换分解成较短的离散傅里叶变换，能减少约一半的乘
4、法和加法次数。,常用的分解DFT的方法有两种：第一种是按时序的奇偶数将序列分成两段，第二种是将序列切割为前后两段。 5.3 时域抽取的快速算法 时域抽取的基本做法是按时序的奇数和偶数将序列分解成两段长度相同的子序列。这种算法要求序列的长度N必须满足 5.3.1 时域抽取法的原理 基本的时域抽取法分两个步骤完成：第一步是将序列分成两段长度相同的短序列，第二步是整理短序列的频谱表达式。,(5.17),（1）按时序的奇偶分解序列 按时序n的奇偶数字将N点长的序列x(n)分解成两个子序列x0(r)和x1(r)，即 用两个子序列x0(m)和x1(m)组成序列x(n)的N点DFT，,(5.18),(5.2
5、0),（2）整理频谱表达式 为了使X0(k)和X1(k)满足N/2点长的规定，同时又能反映X(k)的k个频谱值，需要对X(k)的关系式做些修改。 当0kN/2-1时，频谱X(k)的公式和原来一样，即 当N/2kN-1时，令频序k=N/2+r，r=0N/2-1，并将k=N/2+r代入X(k)的公式，就能得到,(5.20),(5.21),(5.22),利用旋转因子的周期性和反向对称性，有 用它们简化公式X(N/2+r)，并将符号r换为k，得到 修改公式X(k)后，得到基本的DFT分解公式,(5.23),(5.24),(5.25),这个公式是为计算机而写的，计算X(k)的前N/2个频谱值时，使用上面
6、的式子，计算X(k)的后N/2个频谱值时，采用下面的式子。 公式(5.25)这么做的好处是：k值的数量减少一半，离散傅里叶变换的乘法计算量和加法计算量都减少一半，旋转因子的计算量也跟着减少一半。你或许要问：公式(5.25)下面的式子的负号是否会增加计算量？不会的，因为计算机的加法和减法所用的时间相同。,5.3.2 时域抽取法的应用 既然分解的做法能减少计算量，我们就该对N/2=2M-1点离散傅里叶变换X0(k)和X1(k)继续分解。将X0(k)分解为N/4=2M-2点的离散傅里叶变换， 同理，将X1(k)分解为N/4=2M-2点的离散傅里叶变换， 第2次分解使2个N/2点DFT变成4个N/4点
7、DFT，两个N/2点的DFT的乘法和加法计算量再减少一半。,(5.26),(5.27),为了深入理解和方便应用分解公式，让我们将分解公式转化成信号流图，这种流图叫蝶形图。 它有更简洁的交叉线形式，规定交叉线左边为参加运算的信号，右边为蝶形运算的结果；右上角输出的是进入交叉节点的两个信号之和，右下角输出的是进入交叉节点的两个信号之差。,图5.4,图5.5,例题5.2 有一个N=8点的离散傅里叶变换，请用蝶形图表示它的时域抽取基2快速傅里叶变换的算法。 解 遵循时域抽取法的规律(5.25)，N=8点长的DFT需要进行3次分解就可以变成1点长的DFT。,图5.6,例题5.2显示，蝶形运算确实能够将较
8、短的频谱组合成较长的频谱。除此之外，蝶形运算有两个重要特点。 （1）倒序 输入序列的时序等于1点长DFT的下标。下标变化的规律按照从左到右递增的二进制顺序，即在最左边逐次二进制加1并向右进位。 （2）原位运算 每个蝶形图的输入数据在后面的蝶形运算中都不再出现，并且其运算结果的位置和输入数据的位置相同，这个特点能够节省计算机的存储器。 反序和原位运算的特点在计算机中很容易实现。,运用倒序和原位运算的特点，前面的蝶形运算图可简化为,图5.7,5.3.3 时域抽取法的运算量 把每次分解DFT当作一级来看待，得到时域抽取快速算法的运算特点： （1）每级的蝶形个数都是N/2，时域抽取法的分解共有M级；
9、（2）每个蝶形需要复数乘法1次，复数加法2次。 根据这两个运算特点，全部蝶形需要的复数乘法和复数加法的次数是 它们比直接计算法的计算量N2少了许多。,(5.28),例题5.3 假设计算机的一次复数乘法需要3微秒，一次复数加法需要1微秒；用这台计算机来计算一个1000点序列的频谱。请问采用直接计算法和时域抽取快速算法进行频谱计算，哪个方法比较快？ 解 已知序列的长度是1000点，只要满足频率采样定理，频率采样数量N1000，用N点离散傅里叶变换就可以正确分析序列的频谱。 （1）直接计算法 为了减少计算量，我们取N=1000。按照公式(5.3)和(5.4)，直接计算频谱的时间是,(5.29),（2
10、）时域抽取法 为了满足时域抽取法的长度条件(5.17)，我们取N=1024=210。按照公式(5.28)，时域抽取快速算法的计算时间是 比较公式(5.29)和(5.30)的结果，40.0256156，快速算法比直接算法快155倍。 值得强调一下，这里介绍的时域抽取基2快速傅里叶变换并不是什么新的傅里叶变换，而是计算离散傅里叶变换的一种技巧。,(5.30),5.4 频域抽取的快速算法 频域抽取快速算法的基本做法是，将序列从中间切开，分成长度相同的两段子序列。这种算法要求序列的长度N必须满足 5.4.1 频域抽取法的原理 频域抽取法的基本做法分为两步：第一步是将序列按时序先后分成两部分，第二步是整
11、理短序列的频谱表达式。 （1）按时序的前后分解序列 将n按自然顺序分成前半部分和后半部分，相应地，序列x(n)就变成两段长度相等的短序列，这样一来，x(n)的DFT是,(5.31),（2）整理频谱表达式 让我们将频序k按偶数和奇数分类，那么，偶数频序的个数和奇数频序的个数就变成N/2，长频谱就可以变成短频谱。 利用旋转因子的周期性，公式(5.32)的偶数频序的频谱是,(5.32),同理，利用旋转因子的反向对称性(5.16)，公式(5.32)的奇数频序组成的频谱是 现在，公式(5.33)和(5.34)都是真正意义的N/2点DFT，因为它们的n和k都是N/2点。,(5.33),(5.34),为了将
12、公式(5.33)和(5.34)两个N/2点DFT的样式变得更简洁，突出频域抽取法的规律，令 这就是频域抽取法的基本分解公式，它能够将N点DFT分解为N/2点DFT。将公式(5.35)分别代入公式(5.33)和(5.34)，并重新排列它们的偶数频序和奇数频序，形成简洁的N/2点DFT，即,(5.35),(5.36),5.4.2 频域抽取法的应用 既然公式(5.35)表示的N/2点长序列能够减少离散傅里叶变换的运算量，我们就有理由对N/2=2M-1点的X0(k)和X1(k)继续第2次同样的分解，将它们变成N/4=2M-2点的离散傅里叶变换。 频域抽取法的分解公式也可以用蝶形图表示，蝶 形图的左边是
13、输入，右边是输出，右上角是信号之和，右下角是信号之差。 蝶形图比用公式分解的方法更加简明扼要。,图5.8,例题5.4 有一个N=8点的离散傅里叶变换，请你用频域抽取法的蝶形图来描述它的频域抽取基2快速傅里叶变换的计算过程。 解 根据频域抽取法的规律(5.35)，N=8的DFT需要3次分解就能缩短为1点的DFT。,图5.9,由于每次分解DFT时，对频序的分解都是按偶奇数进行的，即按二进制频序的最低位0和1来分类；所以，当分解进行到1点长的DFT时，短序列的下标等于频谱的二进制频序，它们按反序从上到下排列。 在知道蝶形图的原位运算特点的情况下，图5.9中反映分解过程的序列符号可以省略，频域抽取法的
14、蝶形运算图可以简化为,图5.10,5.4.3 频域抽取法的运算量 频域抽取法的傅里叶变换运算量和时域抽取法的傅里叶变换运算量是相同的，对比两者的蝶形运算图就可明白。完成全部蝶形运算需要的复数乘法和复数加法的次数是 5.4.4 两种快速算法的相似之处 频域抽取和时域抽取这两种方法减少DFT运算量的主导思想是一样的，都是缩短DFT。 不管是时域抽取算法还是频域抽取算法，都会发生输入或者输出序列的倒序排列。这个问题，集成电路工程师在开发DSP芯片时，已经充分考虑。,(5.37),5.5 离散傅里叶逆变换的快速算法 离散傅里叶变换的用途很多，例如频谱分析，信息提取、快速卷积、信号压缩等；应用离散傅里叶
15、变换时，往往还需要对离散傅里叶变换做逆变换。在设计产品时，该如何给离散傅里叶逆变换编写计算程序呢？ 5.5.1 仿效快速傅里叶变换 只要按照前面介绍的两种快速傅里叶变换法，缩短离散傅里叶逆变换的长度，就可以减少逆变换的计算量。对比离散傅里叶正变换的定义，,(5.38),和反变换的定义 它们的累加符号内的运算过程是相同的，所不同的是：前面的系数1/N和旋转因子的指数符号。 5.5.2 取旋转因子的复共轭 抽去公式(5.38)的x(n)和公式(5.39)的X(k)的具体内容，它们就都是数据，它们与旋转因子的乘法都是相同的，只是两种旋转因子的指数符号正好相反。而不管指数符号如何，这些旋转因子都具有相同的周期性和反向对称性。 只要我们在原来快速运算的基础上增加一个取,(5.39),WNkn的复数共轭的子程序，就可以利用原有的快速傅里叶变换程序，对数据X(k)进行反变换的运算。 5.5.3 取频谱的复共轭 这是个负负得正的道理，即 这说明，只要增添两个取复数
