三种实信号快速卷积算法的分析(图文)

根据以上分析结果，我们将直接卷积、二维多项式卷积和FFT算法卷积的运算量进行对比。因为加法比乘法的运算耗时要少很多，所以我们在此仅讨论乘法的运算量。并将对比结果列在表1中。

表1 几种算法乘法运算量的比较

（点）	64	128	1024	1024
（点）	64	64	64	1024	1024	1024
直接卷积	4096	8192	65536	1048576	134217728	1073741824
二维多项式	2979	6051	49059	784899	100661763	805304835
FFT算法	5888	5888	70285	131072	14018027	130023424
分段卷积	5888	11776	94208	131072	16777216	134217728

为了能更清楚的看出对比结果，我们将直接卷积的运算量归一化到1。这样得到表2。

表2归一化的运算量比较

（点）	64	128	1024	1024
（点）	64	64	64	1024	1024	1024
直接卷积	1	1	1	1	1	1
二维多项式	0.7273	0.7386	0.7486	0.7485	0.7499	0.7499
FFT算法	1.4375	0.7188	1.0725	0.1250	0.1044	0.1211
分段卷积	1.4375	1.4375	1.4375	0.1250	0.1250	0.1250

从表2中易得：二维多项式卷积算法，不管两个序列长度差别如何，它的运算量始终是直接卷积的75%左右，而FFT算法和分段卷积算法，随着序列长度的增加，其优势越来越明显，它们的运算量是直接卷积的12%左右。相比之下，FFT算法和分段卷积算法是二维多项式算法的运算量的1/6左右。另外，FFT算法和分段卷积算法是运算量是按照最大情况考虑的，即把每一次乘法都按照四次数乘来计算的，实际上，有些乘法是不需要四次乘法的，只需要一次或两次就可以了。因此，实际运算中FFT算法和分段卷积算法的运算量要更少一些。

3.结论

通过以上分析，我们看出要想提高卷积的运算速度，从而实现信号的实时处理，二维多项式的算法是行不通的，因此，我们以后的研究方向应该是FFT算法和分段卷积算法的改进。Madihally J. Narasimha提出的利用实信号DFT的共轭对称性质的改进算法就很有效。

[1] 杨靓 徐炜 黄士坦 《卷积的一种快速算法分析》 微电子学与计算机 2003.3

[2] 刘顺兰 吴杰 《数字信号处理》 西安电子科技大学出版社 2003.8

[3] Madihally J. Narasimha，Fellow，Modified Overlap-Add andOverlap-Save Convolution Algorithms for Real Signals, IEEE Trans. SignalProcessing,vol.13,no.11, pp.669-671,Nov.2006.

 2/2   首页 上一页 1 2