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