基于重叠保留法圆周卷积的FFT实现.doc

1 理论分析 1.1线性卷积的FFT算法 我们以FIR滤波器为例，因为它的输出等于有限长冲激响应h(n)与有限长输入信号x(n)的离散线性卷积。 设x(n)为L点，h(n)为M点，输出为 y(n)也是有限长序列，其点数为L+M-1点。下面讨论线性卷积的运算量。由于每一个x(n)的输入值都必须和全部的h(n)值相乘一次，因而总共需要LM次乘法运算，以md表示为 md=LM 对于线性相位FIR滤波器，满足 h(n)=h(M-1-n) 其运算结构如教材第五章所示，加权系数少了一半，因而相乘次数可以减少一半，即 Md=LM/2 用FFT法也就是用圆周卷积来代替线性卷积时，为了不产生混叠，其必要条件是使x(n)、h(n)都补零点，补到至少N=M+L-1，然后计算圆周卷积 y(n)=x(n)h(n) 这时，y(n)就能够代表线性卷积的结果。 用FFT计算y(n)值的步骤如下： 求H(k)=DFT[h(n)],N点； 求X(k)=DFT[x(n)],N点； (3)计算Y(k)=H(k)X(k)； (4)求y(n)=IDFT[Y(k),N点； 步骤(1)、(2)、(4)都可以用FFT来完成。此时的工作量如下：上次FFT运算共 需Nlog2N次相乘，还有步骤(3)的N次相乘，因此共需相乘次数为： mF=Nlog2N+N 这样，我们就可以用线性相位FIR滤波器来比较直接计算线性卷积和FFT算法就是线性卷积这两种算法的乘法次数。设mF和 md的比值为Km，则 Km= 分两种情况讨论如下： x(n)与h(n)点数差不多。例如，设M=L,则N=2M-1，则 Km = 这样可以得到下表： M=L 8 32 64 128 256 512 1024 2048 4096 Km 0.286 0.80 1.39 2.46 4.41 8 14.62 26.95 49.95 当M=8，16，32时，圆周卷积的运算量大于线性卷积；当M=64时，二者相当（圆周卷积稍好）；当M=512时，圆周卷积运算速度可快8倍；当M=4096时，圆周卷积约可以快50倍。可以看出，当M=L且M超过64以后，M越长圆周卷积的好处越明显。因而将圆周卷积称为快速卷积。 当x(n)的点数很多时，即当 LM 则 N=L+M-1=L 这时 Km=M/（2+log2L) 于是，当L太大时，会使 Km下降，圆周卷积的优点就体现不出来了，因此需要采用分段卷积或成为分段过滤的方法。 1.2重叠保留法原理 下面讨论一个短的有限长序列与一个长序列的卷积，如图1所示。例如，当x(n)是很长的序列，利用圆周卷积时，h(n)必须补很多个零值点，很不经济。因而必须将x(n)分成点数和h(n)相仿的段，分别求出每段的卷积结果，然后用一定的方式把他们合在一起，从而得到总的输出。对于每一段的卷积都采用FFT算法处理，通常有两种分段卷积的办法，一种是重叠相加法，另一种是重叠保留法，在此，只介绍重叠保留法。 图1 长序列分段滤波示意图 先将x(n)分段，每段L=N-M+1个点，因此要在每段前面补上数值使之成为N点的序列，重叠保留法采取的处理措施是在每一段的前边补上前一段的保留下来的M-1个输入序列值，组成L+M-1点序列xi(n)，如图2所示。如果L+M-12m，则可以在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前面M-1个点的值不等于线性卷积值，必须舍去。 图2 重叠保留法示意图a 图3 重叠保留法示意图b 为了说明以上说法的正确性，我们来看一看图3任意段xi(n)（为N点）与h(n)(原为M点，补零值点后也为N点）的N点圆周卷积为 yi(n)=xi(n)h(n)= 由于h(m)为M点，补零后作N点圆周位移时，在n=0，1，…，M-2的每种情况下h((n-m))NRN(m)在 范围内的末端出现非零值，而此处xi(m)是有数值存在的，当n=0，M-2的情况，所以在