《数字信号处理》课件2第3章 (3).ppt

分两种情况讨论如下：（1）x(n)与h(n)点数差不多。例如，M=L，则N=2M-1≈2M，则这样可得下表：M=L8163264128256512102420484096Km0.5720.9411.62.785.928.821629.2453.999.9当M=8时，FFT法的运算量大于直接法；当M=32时，二者相当；当M=512时，FFT法运算速度可快16倍；当M=4096时，FFT法约快100倍。可以看出，当M=L且M超过32以后，M越长，FFT法的好处越明显。因而将圆周卷积称为快速卷积。（2）当x(n)的点数很多时，即当LM。通常不允许等x(n)全部采集齐后再进行卷积;否则，使输出相对于输入有较长的延时。此外，若N=L+M-1太大，h(n)必须补很多个零值点，很不经济，且FFT的计算时间也要很长。这时FFT法的优点就表现不出来了，因此需要采用分段卷积或称分段过滤的办法。即将x(n)分成点数和h(n)相仿的段，分别求出每段的卷积结果，然后用一定方式把它们合在一起，便得到总的输出，其中每一段的卷积均采用FFT方法处理。有两种分段卷积的办法:重叠相加法和重叠保留法。2．重叠相加法设h(n)的点数为M，信号x(n)为很长的序列。我们将x(n)分解为很多段，每段为L点，L选择成和M的数量级相同，用xi(n)表示x(n)的第i段：iL≤n≤(i+1)L-1其他ni=0,1,…（3-68）则输入序列可表示成（3-69）这样，x(n)和h(n)的线性卷积等于各xi(n)与h(n)的线性卷积之和，即（3-70）每一个xi(n)*h(n)都可用上面讨论的快速卷积办法来运算。由于xi(n)*h(n)为L+M-1点，故先对xi(n)及h(n)补零值点，补到N点。为便于利用基-2FFT算法，一般取N=2m≥L+M-1，然后作N点的圆周卷积：N由于xi(n)为L点，而yi(n)为（L+M-1）点（设N=L+M-1），故相邻两段输出序列必然有（M-1）个点发生重叠，即前一段的后（M-1）个点和后一段的前（M-1）个点相重叠，如图3-27所示。按照式（3-70），应该将重叠部分相加再和不重叠的部分共同组成输出y(n)。图3-28重叠相加法图形和上面的讨论一样，用FFT法实现重叠相加法的步骤如下:?①计算N点FFT，H(k)=DFT［h(n)］；②计算N点FFT，Xi(k)=DFT［xi(n)］；③相乘，Yi(k)=Xi(k)H(k)；④计算N点IFFT，yi(n)=IDFT［Yi(k)］；⑤将各段yi(n)（包括重叠部分）相加， 。重叠相加的名称是由于各输出段的重叠部分相加而得名的。3．重叠保留法此方法与上述方法稍有不同。先将x(n)分段，每段L=N-M+1个点，这是相同的。不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值，组成L+M-1点序列xi(n)，如图3-29(a）所示。如果L+M-12m，则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。图3-29重叠保留法示意图为了说明以上说法的正确性，我们来看一看图3-29。任一段xi(n)（为N点）与h(n)（原为M点，补零值后也为N点）的N点圆周卷积N（3-71）由于h(m)为M点，补零后作N点圆周移位时，在n=0,1,…,M-2的每一种情况下，h((n-m))NRN(m)在0≤m≤N-1范围的末端出现非零值，而此处xi(m)是有数值存在的，图3-29（c），（d）为n=0,n=M-2的情况，所以在0≤n≤M-2这一部分的yi(n)值中将混入xi(m)尾部与h((n-m))N·RN(m)尾部的乘积值，从而使这些点的yi(n)不同于线性卷积结果。但是从n=M-1开始到n=N-1，h((n-m))NRN(m)=h(n-m)（如图3-29（e），（f）所示），圆周卷积值完全与线性卷积值一样，yi(n)就是正确的线性卷积值。因而必须把每一段圆周卷积结果的前(M-1)个值去掉，如图3-29（g）所示。?因此，为了不造成输出信号的遗漏，对输入分段时，就需要使相邻两段有M-1个点重叠（对于第一段，即x0(n)，由于没有前一段保留信号