快速卷积中嵌套算法的设计与实现.rar

快速卷积中嵌套算法的设计与实现

摘 要

离散富里叶变换(DFT)和卷积计算在图象、数字信号处理中起着重要的作用，

因此对快速算法的研究早就引起人们足够的重视。针对卷积算法的计算进行深入

研究，发现在离散卷积计算过程中的计算量会随着输入信号序列的长度而急速增

加，传统的卷积计算算法已不能满足要求，本文研究了如何将一维卷积变换成二

维卷积或多维卷积，而多维卷积中由包含简单的一维卷积，从而进行嵌套计算。

important role in the image, a digital signal processing, and therefore the study of fast

algorithms have attracted enough attention. Through the In-depth study of the

convolution algorithm, we find the calculation of the convolution calculation will

increases with the length of the rapid of the input signal sequence. Conventional

convolution calculation algorithm can’t meet the requirements. This paper studies

how the one-dimensional convolution transform into a multi-dimensional convolution

or two-dimensional, and multi-dimensional convolution include simple

one-dimensional convolution. Using short convolution calculate long convolution,

and finally achieving 16 points nested circular convolution algorithm, significantly

1.1 课题研究背景 .................................................1

1.2 快速卷积算法的发展历史 .......................................3

1.3 课题研究内容 .................................................4

第二章 快速卷积算法运算中的问题 .....................................5

2.1 数字信号处理中的计算问题 .....................................5

2.2 算法序列 ....................................................11

第三章利用短卷积嵌套计算长卷积算法原理简介 .........................13

3.1 二维卷积与多维卷积 ..........................................13

3.2 Agarwal-Cooley 卷积算法 .....................................19

信号处理技术已得到广泛应用。然而在许多具体的应用场合需要处理的数据量和

计算量都是巨大的，特别是在某些实时性要求较高的应用领域，对信号的处理速

度是苛刻的。当然可以设计研制速度更快的处理器来满足要求，但研制新的处理

器需要较大的投入和较长的研制时间，况且还有赖于技术的进步。

正是出现了著名的离散傅里叶变换（DFT）的快速算法（FFT）后，数字信号处理

技术才迅速发展起来并走向实用的。

然而这种表达方式计算起来并不高效，需要用较多的乘法和加法次数；另外一种

表示方法就是从计算效率的角度来表示一个算法，但这种表达方法往往又会使得

表达式变得让人难于理解。

(1-1)

(1-3)

把它们写成

(1-4)

得复杂。如果 c 和 d 都是常数，那么

和

可以预先计算好，这样只需要 3

次乘法和 3 次加法。这个复数乘法也可用矩阵表示

(1-5)

(1-6)

(1-7)

M 为一对角阵，它代表了算法中的所有乘法运算；C 则称后加矩阵。

，

，其中 F 为某一数域，则 C 的元素

次乘法和

次加法，因此

总共需要

次乘法和

次加法。现在我们来改进这个算法，使得乘法次