论文导读：本文对两种实信号快速卷积算法进行了分析和对比，找到了一种快速有效的算法。为以后的快速卷积研究指明了方向。
关键词：快速卷积，二维卷积，分段卷积
0 引言
在数字信号处理中，卷积占有很重要的地位。正是卷积将输入信号、输出信号和系统的单位脉冲响应三者联系起来。但是卷积的计算量较大，因此，要实现信号的实时处理，卷积速度是最关键的。实际中，经常用有限长单位脉冲响应（FIR）滤波器来处理信号，且信号多以实信号的形式存在。因此，本文讨论的是实信号的快速卷积算法。以下就对两种卷积算法进行分析。
1 两种卷积算法
我们知道，卷积的定义式为： ，其中 代表FIR滤波器的单位脉冲响应， 为待处理的信号，则 就是处理后的输出结果。如果直接用定义式来计算卷积，需要的数乘次数为： 。这里， 为的长度， 为的长度。
1.1二维卷积算法
用一维多项式分别表征，：
则
当和有公因子 时，和可以写成：
 ，
记： （1）
其中 。
将（1）式代入 和 的表征多项式有：
 (2)
记： （3）
这样就可以把一维多项式和写成如下二维形式：
 （4）
它们的积为二维多项式
 （5）
整个算法的运算量为：
数乘次数：Prod=
数加次数：Add=
1.2 FFT算法
FFT算法利用了有限长序列的离散傅立叶变换（DFT）的快速算法和圆周卷积与线性卷积的关系。其计算步骤如下：
1） 求 ，L点；
2） 求 ，L点；
3） 计算 ；
4） 求 ，L点。
其中步骤1）、2）、4）都可以用FFT来实现。这样FFT算法的运算量为：
数乘次数：
为了实现信号的实时处理，当输入信号点数很多时，就不能等全部采集后再进行卷积了，否则会使输出有较长的延时。这就需要采用分段卷积的方法。即将分成点数和相仿的段，分别求出每段的卷积结果，然后用重叠相加法或重叠保留法将它们结合在一起得到总的输出 。这种算法的运算量为每一段的运算量乘以总段数。
1/2 1 2 下一页 尾页 |
