数字信号处理杨毅明电子课件2014版第5章节信号处理的效率.ppt

第5章 信号处理的效率 一种理论不应只停留在是否能运用上，还应讲究它应用的效率。DFT也是这样。 5.1 直接计算DFT的代价 为了方便后面的方法探讨，现 在将离散傅里叶变换写成更简单的 形式，即 5.1.1 直接计算频谱的代价 现在按分析方程来评估，直接计算离散傅里叶变换的代价。 （1）不考虑旋转因子 假设各旋转因子事先已经算好，并存储在计算机的存储器中。如果信号x(n)是N个复数的数组，计算一个k的频谱时，需要复数乘法N次；计算全部k的频谱时，需要的复数乘法次数为 计算一个k的频谱时，需要复数加法N-1次；计算全部k的频谱时，需要的复数加法次数是 （2）考虑旋转因子 计算离散傅里叶变换少不了旋转因子 因为时序n有N个值、频序k也有N个值，所以计算全部k的频谱时，需要计算N×N=N2个旋转因子。 如果从极坐标的表达式和图形 来看，旋转因子明显是周期序列。 利用旋转因子的周期特点，在计算 离散傅里叶变换时，只需计算旋转 因子的N个独立值。 5.1.2 直接计算卷积的代价 假设信号x(n)和系统h(n)的长度都等于N，则系统的输出 它的长度等于2N-1。 如果直接按照定义计算卷积，那么计算n=0~2N-2的y(n)需要的乘法运算量 同时，需要的加法运算量 如果利用卷积定理来计算该卷积，取循环卷积的长度为2N-1，并根据表4.5的DFT卷积定理，就可以得到系统的输出频谱 在事先计算好系统频谱H(k)的条件下，如图5.2所示，用卷积定理求解y(n)的复数运算量是： （1）复数乘法次数 考虑实现复数运算的实数运算的话，其运算量更大。 复数加法次数 复数的加法要由实数的加法组成。 相比之下，直接计算卷积的方法优于用卷积定理来计算卷积的方法。 还有，直接计算卷积和利用卷积定理来计算卷积，它们都有一个共同的特点，就是计算量都与N2成正比。 5.2 离散傅里叶变换计算效率的提高 如5.1.1所述，直接按定义来计算离散傅里叶变换，这种方法的工作量与信号长度N的平方成正比，还与旋转因子的独立值有关。 不过，这两个特点也提醒我们：缩短DFT的长度和减少旋转因子的独立值，可以降低离散傅里叶变换的计算量。 如果把N点离散傅里叶变换的长度缩短一半，即变成两个N/2点DFT的组合，那么，离散傅里叶变换的复乘次数就可以从N2次变成N2/2次，复加次数可以从N(N-1)≈N2次变成约N2/2次。这说明，把离散傅里叶变换分解成较短的离散傅里叶变换，有可能减少约一半的乘法次数和加法次数。 常用的分解DFT的方法有两种：第一种是按时序的奇偶数将序列分成两段，第二种是按时序的前后将序列分割为两段。 5.3 时域抽取的快速算法 时域抽取的基本做法是，按时序的奇数和偶数将序列分解成两段长度相同的子序列。这种算法要求序列的长度N必须满足 5.3.1 时域抽取法的原理 基本的时域抽取法分两个步骤完成：第一步是将序列分成两段长度相同的短序列，第二步是整理短序列的频谱表达式。 （1）按时序的奇偶分解序列 按时序n的奇偶数字将N点长的序列x(n)分解成两个子序列x0(r)和x1(r)，即 用这两个序列x0(m)和x1(m)组成序列x(n)的N点DFT，即 上式简化后得 （2）整理频谱表达式 为了使X0(k)和X1(k)满足N/2点DFT的规定，同时又能反映X(k)的N个频谱值，需要对关系式(5.20)做些修改。 ① 当0≤k≤N/2-1时，频谱X(k)的公式(5.20)和原来一样，即 ② 当N/2≤k≤N-1时，令频序k=N/2+r，r=0~N/2-1，并将k=N/2+r代入X(k)的公式(5.20)，就能得到 利用旋转因子的周期性和反向对称性，有 用它们简化公式X(N/2+r)，并将符号r换为k，就可得 修改公式(5.20)后，得到DFT的基本分解公式 它将N点DFT分解为两个N/2点DFT。 这个公式是为计算机而写的，计算X(k)的前N/2个频谱值时，使用式(5.25)上面的式子，计算X(k)的后N/2个频谱值时，使用式(5.25)下面的式子。 公式(5.25)这么做的好处是：k值的数量减少一半，离散傅里叶变换的乘法计算量和加法计算量都减少一半，旋转因子的计算量也跟着减少一半。 你或许要问：公式(5.25)下面的式子的负号是否会增加计算量？不会的，因为计算机的加法和减法所用的时间相同。 5.3.2 时域抽取法的应用 既然，分解的做法能减少计算量，就应对N/2=