第6章IIR滤波器的设计.ppt

所以 因此 如果不考虑因子1/2，只要增加2N次实数加法运算就能由DHT求出DFT。 3. DHT的快速算法（FHT） 仿照快速DFT的分解方法，可通过时域的抽取或频域抽取方式实现快速DHT。将N=2M点的实序列 进行奇偶抽取 则 根据三角公式 令 ， ，根据DHT的周期性，在 时 类似于DIT基-2FFT分解的同址运算思想，可用 、 、 和 四个点同址运算得出 、 、 和 。这种运算构成了一个运算蝶形，称为“哈特曼蝶形”。 设 将上式中k分别取k、N/2+k、N/2-k和N-k四个值，并考虑 和 以N/2为周期，当 时，得到 上述的运算可用哈德曼蝶形表示如图4.5.1所示 四点的FHT的蝶形图如图4.5.2所示。 图4.5.3显示了8点的DIT基-2FHT流图。 运算量 乘法次数 加法次数 4.6 线性卷积和线性相关的FFT算法 4.6.1 线性卷积的FFT算法 设 y(n)是x(n)（n=0~L-1）和h(n)（n=0~M-1）的线性卷积： 由于每一个x(n)的输入值都必须和全部的h(n)相乘一次，因而总共需要LM次乘法。 用FFT算法也就是用圆周卷积来代替线性卷积时，为了不产生混叠，其必要条件是使x(n)，h(n)都补零值，补到至少N=M+L-1，即 然后计算圆周卷积 这时，y(n)就能代表线性卷积的结果。  利用FFT进行线性卷积的步骤如下： 1.将序列x(n)和h(n)补零延长，使其长度 若采用基-2FFT，还应使N等于 2的最小整数次幂。 2.做x(n)和h(n)的长为N点的FFT得到X(k)和Y(k)，求它们的积Y(k)=X(k)H(k) 3.求Y（k）的IFFT并取前N点获得线性卷积的结果为 N≥L+M-1 整个过程中，共需要进行三次FFT运算，共需 次相乘，还有步骤（2）的N次相乘，因此共需相乘次数为 可以用线性相位FIR滤波器来比较直接计算线性卷积和FFT法计算线性卷积这两种方法的乘法次数。 代表直接线性卷积所用的乘法次数，则比值为 （1）x(n)与h(n)点数差不多 例如，设M=L，则 ，则 当M＝8，16，32时，圆周卷积的运算量大于线性卷积；当M=64时，二者相当（圆周卷积稍好）；当M=512时，圆周卷积运算速度可快8倍；当M=4096时，圆周卷积约可快50倍。可以看出，当M=L且M超过64以后，M越长圆周卷积的好处越明显。因而将圆周卷积称为快速卷积。 （2）当x(n)的点数很多时 1.重叠相加法 h(n)长度为M，x(n)长度为L0，且L0 》M， x(n)与y(n)的卷积为 重叠相加法的步骤如下： 3.计算 ，并求长为L的反变换，即 4.将 的重叠部分相加，最后得到结果为 1.将 补零延长到L =M+ N -1，并计算长为L的FFT， 得到 2.分别将 补零延长到L =M+ N -1，并计算长为L的FFT，得到 （补充）重叠保留法 序列分段的方法： 重叠保留法 分段方法 示意图 输入的每段序列重叠N-1点，而每段的循环 卷积的输出去掉前面N-1点只保留后面M点， 4.6.2线性相关的FFT算法 设x(n)为L点，y(n)为M点，则线性相关 利用FFT法求线性相关是用圆周相关代替线性相关，选择 ，且 （r为整数），令 其计算步骤如下： （1）用FFT算法求 ，N点； （2）用FFT算法求 ，N点； （3）求乘积 （4）用IFFT算法求 * 4.2.5 DIT基-2FFT的软件编程思想 由DIT基-2FFT算法原理及特点，不难看出，FFT计算程序主要包括变址和M级递推计算两大部分。 1.变址（倒序）运算 在实际运算中，一般总是按自然顺序将输入序列存入存储单元，故为实现DIT基-2FFT首先必须将输入序列x(n)按二