第5章 信号处理的效果.ppt

第5章 信号处理的效率 一种理论不应只停留在是否能运用上，还应当讲究应用的效率。 5.1 直接计算离散傅里叶变换的代价 为了方便后面的方法探讨，现在将离散傅里叶变换写成较简单的形式，即 5.1.1 直接计算频谱的代价 现在按照分析方程评估直接计算离散傅里叶变换的代价。 （1）不考虑旋转因子 假设旋转因子事先已经算好，存储在计算机的存储器中。如果信号x(n)是N个复数的数组，计算全部k的频谱时，需要的复数乘法次数是 需要的复数加法次数是 （2）考虑旋转因子 计算离散傅里叶变换少不了旋转因子 因为时序n有N个值、频序k也有N个值，所以计算全部k的频谱需要计算N×N=N2个旋转因子。 如果从极坐标的表达方式和图形来看旋转因子，旋转因子是周期序列。利用旋转因子的周期特点，在计算离散傅里叶变换时，只需计算旋转因子的N个独立值。 5.1.2 直接计算卷积的代价 假设信号x(n)和系统h(n)的长度都是N，则系统的输出 如果直接按照卷积公式计算，需要的乘法运算量 需要的加法运算量 如果运用DFT的卷积定理，取循环卷积的长度为2N-1，并利用表4.5的卷积定理，就可以得到系统的输出频谱 在事先计算好系统频谱H(k)的条件下，用卷积定理求解y(n)的运算量是：复数乘法次数 复数加法次数 直接计算卷积和利用卷积定理计算卷积的计算量都与N2成正比。相比之下，直接计算法优于卷积定理法。 5.2 离散傅里叶变换计算效率的提高 直接按定义来计算离散傅里叶变换，这种方法的工作量与信号长度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点长的规定，同时又能反映X(k)的k个频谱值，需要对X(k)的关系式做些修改。 ① 当0≤k≤N/2-1时，频谱X(k)的公式和原来一样，即 ② 当N/2≤k≤N-1时，令频序k=N/2+r，r=0~N/2-1，并将k=N/2+r代入X(k)的公式，就能得到 利用旋转因子的周期性和反向对称性，有 用它们简化公式X(N/2+r)，并将符号r换为k，得到 修改公式X(k)后，得到基本的DFT分解公式 这个公式是为计算机而写的，计算X(k)的前N/2个频谱值时，使用上面的式子，计算X(k)的后N/2个频谱值时，采用下面的式子。 公式(5.25)这么做的好处是：k值的数量减少一半，离散傅里叶变换的乘法计算量和加法计算量都减少一半，旋转因子的计算量也跟着减少一半。你或许要问：公式(5.25)下面的式子的负号是否会增加计算量？不会的，因为计算机的加法和减法所用的时间相同。 5.3.2 时域抽取法的应用 既然分解的做法能减少计算量，我们就有理由对N/2=2M-1点的离散傅里叶变换X0(k)和X1(k)继续第2次分解。将X0(k)分解为N/4=2M-2点的离散傅里叶变换， 同理，将X1(k)分解为N/4=2M-2点的离散傅里叶变换， 第2次分解使2个N/2点DFT变成4个N/4点DFT，两个N/2点的DFT的乘法和加法计算量再减少一半。 为了深入理解和方便应用分解公式，让我们将分解公式转化成信号流图，这种流图叫做蝶形图。 它有更简洁的交叉线形式，规定交叉线左边为参加运算的信号，右边为蝶形运算的结果；右上角输出的是进入交叉节点的两个信号之和，右下角输出的是进入交叉节点的两个信号之差。 例题5.2 有一个N=8点长的离散傅里叶变换，请你用蝶形图表示它的时域抽取基2快速傅里叶变换的算法。 解 遵循时域抽取法的规律(5.25)，N=8点长的DFT需要进行3次分解就可以变成1点长的