《快速卷积中嵌套算法的设计与实现说明书.doc》由会员分享，可在线阅读，更多相关《快速卷积中嵌套算法的设计与实现说明书.doc（40页珍藏版）》请在三一办公上搜索。
1、快速卷积中嵌套算法的设计与实现摘 要离散富里叶变换(DFT)和卷积计算在图象、数字信号处理中起着重要的作用，因此对快速算法的研究早就引起人们足够的重视。针对卷积算法的计算进行深入研究，发现在离散卷积计算过程中的计算量会随着输入信号序列的长度而急速增加，传统的卷积计算算法已不能满足要求，本文研究了如何将一维卷积变换成二维卷积或多维卷积，而多维卷积中由包含简单的一维卷积，从而进行嵌套计算。研究了利用短卷积嵌套计算长卷积的算法，最终实现16点循环卷积嵌套算法，大幅度减少了卷积的计算量。关键词：卷积,快速,嵌套Design and implementation of the nested algori
2、thm of fast convolutionAbstractDiscrete Fourier Transform (DFT) and convolution calculation plays an 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
3、the calculation of the convolution calculation will increases with the length of the rapid of the input signal sequence. Conventional convolution calculation algorithm cant meet the requirements. This paper studies how the one-dimensional convolution transform into a multi-dimensional convolution or
4、 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 reducing the computation of convolution.Key Words: convolution;fast
5、,;nested目 录摘 要iAbstractii第一章 绪论11.1课题研究背景11.2快速卷积算法的发展历史31.3课题研究内容4第二章 快速卷积算法运算中的问题52.1数字信号处理中的计算问题52.1.1滤波和相关52.1.2离散傅里叶变换82.2算法序列11第三章利用短卷积嵌套计算长卷积算法原理简介133.1二维卷积与多维卷积133.2 Agarwal-Cooley卷积算法193.3 分裂算法28第四章 快速卷积嵌套算法实现344.1 16点循环卷积算法实现344.2 算法性能分析35第五章 总结37参考文献38本文由闰土服务机械外文文献翻译成品淘宝店整理第一章 绪论1.1课题研究背景
6、随着大规模集成电路、计算机和数字信号处理器（DSP）的快速发展，数字信号处理技术已得到广泛应用。然而在许多具体的应用场合需要处理的数据量和计算量都是巨大的，特别是在某些实时性要求较高的应用领域，对信号的处理速度是苛刻的。当然可以设计研制速度更快的处理器来满足要求，但研制新的处理器需要较大的投入和较长的研制时间，况且还有赖于技术的进步。另一种方案就是设计高效的算法使计算量降到可以接受的水平，实际上也正是出现了著名的离散傅里叶变换（DFT）的快速算法（FFT）后，数字信号处理技术才迅速发展起来并走向实用的。通常我们在表达一个算法的时候是以一种人们容易理解的方式表达出来的，然而这种表达方式计算起来并
7、不高效，需要用较多的乘法和加法次数；另外一种表示方法就是从计算效率的角度来表示一个算法，但这种表达方法往往又会使得表达式变得让人难于理解。例如，我们要计算下面一个表达式的值A (1-1)如果按照这个表达式计算需要4次乘法和3次加法，不难看出上面的表达式也可写成 (1-2)这样只需要1次乘法和2次加法就可以了。另一个典型的例子是计算两个复数的乘积 (1-3)其中 直接计算需要4次乘法和2次加法，如果把它们写成 (1-4)则需要3次乘法和5次加法就可以了，通常DSP计算乘法要比计算加法来得复杂。如果c和d都是常数，那么和可以预先计算好，这样只需要3次乘法和3次加法。这个复数乘法也可用矩阵表示 (1
8、-5)按照第二个算法还可以写成 (1-6)或写成简洁的形式 (1-7)矩阵A与向量相乘只是一些加法运算，因此称A为前加矩阵；矩阵M为一对角阵，它代表了算法中的所有乘法运算；C则称后加矩阵。如果将作为一个系统的输入数据，作为系统的输出数据。那么，这个算法可描述为：首先将输入数据进行一系列的加法运算，然后是一些乘法运算，最后又是一系列的加法运算。今后我们介绍的快速算法大多可以用这种矩阵结构表示，即它的中间是一个对角矩阵表示乘法运算，两边的矩阵元素是1，0，-1等简单的数，表示加法运算。我们再来看两个矩阵相乘的问题设，其中F为某一数域，则C的元素， (1-8)若直接计算，每计算一个C中的元素就需要次
9、乘法和次加法，因此总共需要次乘法和次加法。现在我们来改进这个算法，使得乘法次数几乎减少一半，而加法次数略有增加。利用下面的恒等式 (1-9)则 (1-10)这里假定是偶数，否则可在A中加入一列0，在B中加入一行0。上面的表达式中第一项需要的乘法次数为，每一个元素都需要计算，因此共次乘法；第二项与j无关，每一行只要计算一次，因此共次乘法；而第三项与i无关，每一列只要计算一次，因此共次乘法；这样计算C总共需要次乘法。对每一个元素需要计算的加法次数为次，对每一行或每一列要计算的加法次数为次，因此加法次数总共为次。对于一个大的矩阵乘法次数大约是直接计算的一半。但值得注意的是这种算法对计算误差会比较敏感
10、，特别是采用定点数计算的时候，这是工程技术人员值得注意的问题。但本课程主要讨论快速算法的问题，对计算误差的问题不做进一步的讨论。1.2快速卷积算法的发展历史有限长序列卷积 (1-11)广泛地应用于相关函数和功率谱的计算以及有限长脉冲响应数字滤波器的设计和实现等众多的数字信号处理领域。然而,直接计算(l-11)式所需乘法及加法运算量，当卷积结果长度N较大时，将随着量级增长很大。以致在快速算法提出之前，(l-11)式的应用受到了很大的限制。1960年和1963年Good和Thomas分别发表了他们的快速算法，但并没有引起人们的重视。1965年，Coley和Tukcy提出了一种称之为快速傅里叶变换(
11、FFT)的计算机实现算法。应用该算法计算(l-11)式，其乘法及加法运算量均可降低到。1966年Stockham将它用于卷积的计算，从而也推动的数字信号处理技术的快速发展。Cooley-Tukey算法也被人们广泛第学习和研究，这种算法也就是一般的数字信号教课书中都有介绍的FFT算法；1978年，wiongrad推出WFT算法，使得(l-11)式的运算量进一步得到降低。然而FFT及WFT都存在两点不足，即：需要计算三角函数以及需要施行复数运算，即使输入值为实序列也是如此，而且当卷积结果长度N增大时，所需乘法及加法量仍然很大，难于实现实时相关或实时卷积计算。早在1972年，C.M.Rader在前人
12、关于Galois域上的离散傅里叶变换研究的基础上提出了应用默森变换方法，在取默森M为模的整数环上计算序列卷积的默森变换(MN)T算法闭。接着Agarwal 和Burrsu进行了更深入的研究，奠定了数论变换(NTT)的基础。NTT的应用使得卷积的乘法运算量降低到，并且其算法结构便于硬件实现。然而遗憾的NTT受到字长及变换长度的严格限制，因此在应用上就有很大的局限性。1978年，Nussbaumer提出了快速多项式变换(FPT)算法,虽然解除了字长及变换长度受限的约束，但其乘法及加法运算仍然保持在的量级上，因而更适合于软件实现。1.3课题研究内容(1)研究快速卷积算法的基本原理和实现方法;(2)设
13、计和实现快速卷积算法;(3)设计和推导快速卷积的嵌套算法并对算法性能进行评估;第二章 快速卷积算法运算中的问题2.1数字信号处理中的计算问题2.1.1滤波和相关数字信号处理中的主要任务是对信号进行滤波，有两种形式的数字滤波器：有限长冲激响应滤波器（FIR）和无限长冲激响应滤波器（IIR）无限长冲激响应滤波器也称递归滤波器。它们的结构可用图2.1.1和图2.1.2表示。图2.1.1FIR滤波器对于FIR滤波器其输入输出关系为线性卷积。设d为N点的序列，滤波器有L个系数用g表示，即 ，那么其输出序列s就是， (2-1)数字信号处理中的另一个问题是计算两个序列的相关r， (2-2)显然它也可以用卷积
14、来计算，只要将一个序列颠倒就可以了。与线性卷积密切相关的是圆周卷积，设d和g都是n点的序列，圆周卷积定义为， (2-3)表示对n取模，在含义清楚的情况下下标n也可不写。因时，；时， 于是， (2-4)注意到当时，第一项的，是第二项的，所以， (2-5)此式表明线性卷积中下标大于等于n的部分折叠到下标0开始的地方，并将它们叠加起来。卷积还可以用多项式乘法来表示。设， (2-6)以及 (2-7)则 (2-8)不难验证的系数就是d和g的线性卷积。显然还可以写成，因此线性卷积是符合交换律的，还可以写成 (2-9)圆周卷积也可以用多项式表示，设， (2-10)以及 (2-11)则 (2-12)显然圆周卷
15、积也是符合交换律的，对取模只要简单地将多项式中的代以1，而代以。图2.1.1是用FIR滤波器来得到圆周卷积，输入序列重复2次，在输出的3n-1点中，中间的n点即为圆周卷积。图2.1.1用FIR滤波器得到圆周卷积圆周卷积是一种快速计算线性卷积的重要手段。为计算一个长序列的线性卷积，通常将输入序列分段计算，然后将输出序列拼接。对输入数据的分段一般有两种方法：一是数据分段不重叠，这样卷积的输出需要叠加；另一种数据分段重叠，这需要将卷积输出中的混叠部分舍去。假定滤波器系数的长度为n1点，数据分段不重叠的方法称重叠相加法（overlap-add），将数据分成长度为n2点的互不重叠的数据段，记， (2-1
16、3)然后，计算与，的点圆周卷积，显然计算结果就是两个序列的线性卷积，记为， (2-14)由于 ，所以 (2-15)因为是（）点的序列，因此上式中相邻两段之间有点的重叠，需要将它们叠加起来。如果，则可能出现两个以上的段重叠，所以一般要取。分段有重叠的方法称重叠保留法（overlap-save）。记， (2-16)，当 (2-17)该式表明，在每次的计算结果中后面的n2个点等于线性卷积，所以我们只要保留后面的n2个点，而丢弃前面不正确的n1-1个点。最后将每次计算保留下来的n2个点的正确值拼接起来就可以了。图2.1.2递归滤波器对于IIR滤波器其输入输出的关系为 ，这也可用多项式来表示。设， (2
17、-18)其中 ，则 (2-19)其中为商多项式，为剩余多项式，当n个数据全部进入移位寄存器后，其输出序列就是的系数，而系数的值保留在个寄存器中。2.1.2离散傅里叶变换离散傅里叶变换离（DFT）是数字信号处理中的另一个重要的计算问题，它与卷积是密切相关的，设是复数域或实数域中的n维向量，其一维离散傅里叶变换是复数域中的另一个n维向量V，它定义为 ，其中 也可用矩阵的形式表示： (2-20)由V也可求出原序列v，即离散傅里叶反变换（IDFT） (2-21)证明如下：因 (2-22)而 (2-23)于是 (2-24)其中 (2-25)事实上由离散傅里叶变换的矩阵形式可以看出 (2-26)显然 (2
18、-27)离散傅里叶变换与圆周卷积有密切的关系，即卷积定理。设序列e是序列f和g的圆周卷积，。 (2-28)则 ， 。 (2-29)其中分别是e，f，g的DFT。证明如下： (2-30)从而 还可以定义二维和多维离散傅里叶变换，由于多维离散变换的可分离性因此可以转化为一维离散傅里叶变换来计算。而一维离散傅里叶变换也可转化为多维离散傅里叶变换来计算。设v是复数域或实数域中的二维数组，则其二维离散傅里叶变换为复数域中的二维数组，定义为 (2-31)其中 ，也可以用矩阵表示 (2-32) (2-33) (2-34)其反变换为 (2-35)或用矩阵形式表示为 (2-35)2.2算法序列通常我们都是用一个
19、表达式或者它的等价形式来表示一个算法的，然而它并没有具体地规定计算过程，它只表达了输入量和输出量之间的关系。如果我们将这种关系用具体的计算步骤表达出来就是算法序列。例如按照Error! Reference source not found.式来计算两个复数的乘法，我们可以写出下面的计算步骤 (2-36)其中t是在计算过程中引入的中间变量，通过这个算法序列首先可以清楚地看出这个计算过程需要4次乘法和2次加法，其次我们可以方便地将这个算法序列变成计算机程序。如果按照Error! Reference source not found.式来计算两个复数的乘法，又可写出另外一个算法序列 (2-37)这个
20、算法序列中用到了3次乘法和5次加法。如果d和c是已知的，则和可预先计算好，这样加法次数就降为3次。第三章利用短卷积嵌套计算长卷积算法原理简介3.1二维卷积与多维卷积二维卷积是对一个二维数组进行的一种运算。可设想为一个二维的滤波过程，其中的一个二维数组是二维滤波器的系数，二维的数据通过它后形成一个二维的输出。图像信号是典型的二维信号，因此二维卷积对图像信号的处理是很有用的。现在给出它的定义，设是mn的数组，是pq的数组，它们的二维卷积定义为：，是一个(m+p-1)(n+q-1)的数组。根据这个定义容易推广到更高维的情况，但一般仅限于讨论二维的情况。二维卷积也可用多项式表示，将数组的每一行用多项式
21、表示，这样d和g就成为具有m和p个以多项式为元素的向量：，写成矩阵的形式：计算二维卷积的问题就变成了计算和两个多项式向量的一维卷积问题：则是m+p-1个多项式的向量：计算两个多项式向量的卷积在结构上与一维卷积完全相同，因此前面的算法在这里也适用。所不同的只是原来的乘法变成多项式乘法，而加法变成了多项式加法。其中的每一个多项式乘法又是一个卷积。这个计算过程可用图3.1.1表示。图3.1.1 mn与pq的二维卷积二维卷积还可以写成二元多项式的形式，这时：，类似地可用多项式的形式写出两个mn维数组的两维圆周卷积：，则是m个多项式的向量：或写成二元多项式的形式：其计算过程与计算线性卷积类似，如图3.1
22、.2，这个计算过程可解释为计算长度为m的多项式圆周卷积，而多项式圆周卷积中的乘法是以为模的多项式乘法，因而是一个长度为n的圆周卷积。图3.1.2 mn二维圆周卷积由图3.1.2可知计算一个mn的二维圆周卷积需要的乘法次数为：加法次数为：一个二维数组可以看成是mn维的或者是nm维的其乘法次数是相同的而加法次数是不同的。例如计算79的二维圆周卷积，因为；，它们的乘法次数为304，而加法次数按79计算时为1814，按97计算时为1848。而直接计算需要次乘法和次加法。这个计算过程还可以从另一个角度解释。计算长度为m的多项式圆周卷积，首先要计算和，。它们是用两个矩阵乘以多项式向量和得到的，这两个矩阵分
23、别用和表示，它们都是的矩阵，下标m表示它们是m点圆周算法中的B矩阵和A矩阵。而和也可用矩阵表示。记则：，然后计算，。这意味着要计算矩阵和的每一行元素的n点圆周卷积。因此我们将它们的行变成列再乘以和于是得到，和，将它们的对应元素相乘，；，这需要次乘法。于是矩阵的每一列就是多项式向量中每一个元素的系数。最后将矩阵的列变成行再左乘就得到了二维圆周卷积的结果。把这个计算过程画成流程图，如图3.1.3。 图3.1.3用Winograd算法计算 图3.1.4用二维DFT计算若用D和G表示d和g的二维DFT，；由于二维DFT也符合卷积定理，因此S就是s的二维DFT。也可用矩阵表示：，其中： ， ，其计算流程
24、图如图3.1.4。可以看到它们的计算过程是相似的，所不同的是用二维DFT计算时中间需要mn次乘法，并且在计算DFT和IDFT时还需要大量的乘法，而且是复数乘法；而快速卷积计算时中间需要次乘法，而且在第一步和最后一步的计算中是不需要乘法的。现在我们要回到用短卷积计算长卷积的问题上来，基本思路是将一个长的序列变换成二维或多维的数组，从而转化成一个二维或多维的卷积问题，而二维和多维的卷积是可以通过一些短的一维卷积来计算的。3.2 Agarwal-Cooley卷积算法设d和g是n点的序列，则它们的圆周卷积，。如果，且互素，则根据孙子定理可将一维的下标i和k用二维的下标和来表示。它们的关系为 和 其中满
25、足方程：，这样n点圆周卷积就可改写为令：，。于是：这是一个二维圆周卷积，如果按照上一节的方法计算它其乘法次数和加法次数为，或 根据这些公式将会看到短卷积算法中的乘法次数对整个算法的计算量起着更重要的作用。例如我们要计算504点的圆周卷积，因为，而8点的算法有两种情况和按第一种情况计算得到按第二种情况计算得到可以看到按照第二种8点的算法计算时其乘法和加法次数都要比用第一种算法少，虽然第二种算法的加法次数比第一种多了26次。因此在选择短卷积算法时一般取乘法次数少的为好。Agarwal-Cooley卷积算法的性能列于表3.2.1中。表3.2.1 Agarwal-Cooley卷积算法的性能下面我们用A
26、garwal-Cooley算法把两个短卷积算法表示成一个算法。上一节中在计算二维卷积时首先要计算，和，我们把这些矩阵写成分块的形式，并重新排列。记的列向量为，那么将矩阵用它的元素具体写出来就是所以记，这是一个的向量，它应该就是矩阵转置的列向量，现在用它构成一个的列向量，仍然记为，则：记这称为矩阵和矩阵的Kronecker积或称直积张量积等。它就是用的每一个元素去乘以从而构成一个的矩阵。这样就可以将写成简洁的形式，我们仍然用d表示数据但它已不是原来的二维数组，而是用原来的二维数组的列向量构成的具有mn个元素的一维数组。对滤波器系数做同样的处理，g也是用原来的二维数组的列向量构成的一个一维数组，则
27、然后计算，或写成矩阵的形式：其中M是由G的元素构成的的对角矩阵：，在形式上将它写成：。这里的是的个列向量构成的一维数组。记的列向量也就是的行向量为， 则：，并且：其中，。用它构成一个的一维数组，我们仍然记它为s，但它是由原来的二维数组的列向量构成的一维数组。于是：最后可以将它写成统一的形式：如果我们用原来二维数组的行向量构成一维数组，则可的到另外一种对称的形式：注意这里两个表达式中的和的排列次序是不同的。作为例子我们用2点和3点的短卷积算法来构造一个6点的算法。2点的Winograd短卷积算法为, 3点的Winograd短卷积算法为首先我们将点的一维数组用孙子定理变换成二维的数组，然后再用这个
28、二维数组的列向量构成一个一维向量。变换关系为，处理的过程示于图3.2.1。图3.2.1数组整序可以看到输入数据序列的次序是乱的。为了将它调整为自然的次序，我们定义初等矩阵：左乘某个矩阵将交换这个矩阵的第i和j行，右乘则交换第i和j列，并且。于是： 由于这个初等矩阵右乘于A，因此相当于交换A矩阵的列。对G做同样的处理得到：由于G是可以预先计算的，因此可以不交换B的列，当然也可进行交换。这样就变成：于是：输出数据的次序也是乱的，需要将它调整为自然的次序。只要在C矩阵的左边乘一个初等矩阵，即交换C矩阵的行。最后的算法写成：其中：3.3 分裂算法在Agarwal-Cooley算法中，我们将一个长的一维
29、数组转化成一个二维或多维的数组，从而就转化成计算二维或多维卷积的问题。而多维卷积可以通过一维卷积的嵌套来进行计算。例如前面讨论的二维卷积，我们首先将它看成是一维的多项式卷积，而多项式卷积中的每一个乘法又都是一维的卷积，这样就把一个二维的卷积转化成一维的卷积了。对于更多维的情况也是一样，例如要计算三维的卷积，我们可以把它转化成许多二维的卷积，而二维的卷积又可转化为许多一维的卷积。最后只要将多维的数组再还原为一维数组就可以了。所以这个问题归结为计算多维卷积的问题。我们还是以二维卷积来加以讨论。对于二维卷积可以用二元的多项式乘积表示：其中，如果，计算结果是线性卷积。如果，且，则计算结果为圆周卷积。假
30、设可分解为u个互素多项式，可分解为v个互素多项式：；。这样就可用计算，的剩余多项式来计算这个二元多项式的乘积，即计算：。然后用孙子定理重构。用和分别表示计算以和为模的多项式乘积所需要的乘法次数，则总的乘法次数为这样就将一个次数较高的二元多项式的乘积分裂为次数较小的二元多项式乘积。而每一个二元多项式的乘积都是一个二维卷积的问题，可以用前面介绍的嵌套的方法计算。分裂的方法是多样的。可以只对或分裂，当然也可以都分裂。下面以一个20点的圆周卷积为例说明它的计算过程。首先将一个20点的一维数组变换为45的二维数组：对g也做同样的处理，然后计算二元多项式乘积：将分解为，而对不做分解，这样就把它分裂成：下一
31、步是用孙子定理重构，因为所以 这里用了一次重构，如果将也分解，它将分裂为更多的多项式乘积，那么要做两次重构。因为：所以对做同样的处理：因此计算时是计算4点的一维圆周卷积，它需要5次乘法和15次加法。而计算则是计算4点的多项式卷积，因此需要5次多项式乘法和15次多项式加法。对于模为的乘法需要9次乘法和16次加法。因此59=45次乘法，516+415=140次加法。另外用孙子定理重构时需要15次多项式加法， 415=60次加法，计算剩余多项式需32次加法。所以这个算法共需要45+5=50次乘法和15+140+60+32=247次加法。如果用Agarwal-Cooley算法直接嵌套计算，因为，所以乘
32、法次数为510=50，加法次数为531+155=230。从这个例子来看计算量并没有改善，反而加法次数还多一些。但如果我们做更多的分裂，由于要计算的多项式乘积为次数较小的多项式乘积，因而有望减小计算量。为了减少计算量应尽可能分裂为次数较小的多项式乘积，但多项式的分解是受到数域的限制的，例如对于多项式在实数域中分解可分解为而在复数域中分解时可分解为，其中虽然在复数域中分解可分解为4个一次多项式，但在算法中将涉及复数的运算。那么有没有办法既要分解又避免复数运算呢，我们先举一个简单的例子，假定要计算：这是一个44的二维圆周卷积。首先将它分裂成：和还是用常规的方法进行计算，也就是用2点圆周卷积和4点圆周
33、卷积嵌套计算乘法次数为。如果也用嵌套的方法计算，则需要用5次以为模的多项式乘法，而以为模的多项式乘法需3次乘法，因此为53=15次。这个算法共需25次乘法。这与用两个4点的圆周卷积直接计算的乘法次数相同，也是25次乘法。但我们可以把计算的算法做得更好一些，可以将分解成：因为意味着。这样就可以将分为以为模的4个多项式乘积计算，乘法次数就变成12次。而计算这个44的二维圆周卷积总共是22次乘法。用这些多项式对取模后导致的结果是，原来应在变量y维中的计算转移到了在变量x维的计算。表3.3.1列出了分裂修正后Agarwal-Cooley卷积算法的性能。表3.3.1 分裂修正后Agarwal-Coole
34、y卷积算法的性能第四章 快速卷积嵌套算法实现4.1 16点循环卷积算法实现设和为已知序列，作多项式，(4-1)其中是和的循环卷积，于是有(4-2)由于是高度复合的多项式，式(4-2)可用winograd最佳算法计算。若记(4-3)于是有(4-4)若令(4-5)其中(4-6)(4-7)由孙子定理便有(4-8)从而计算出。由式（4-6）可计算出。同理由式(4-7)可计算出。将和代入式(4-5)得到。最后将值代入式(4-8)即可计算出。因此，该算法的程序框图如图(4.1)所示。图4.1 算法总体控制流程图4.2 算法性能分析从上述算法的描述上可以知道，其具有以下四个特点：（1）由这些最佳短卷积算法提
35、供了一种乘法量最少的长卷积算法；（2）精确度高，不像调用FFT那样需借用正弦、余弦函数而产生误差；（3）对于实序列的卷积计算只需用到实乘运算，对复序列的卷积计算也较方便，只要调用两次实序列的卷积，然后进行复乘即可；（4）并行性高，适合于向量运算。上述算法以，为模的多项式乘积以快速嵌套算法，各需3次乘法，3次加法；9次乘法，15次加法和21次乘法，77次加法。计算出后代入式(4-8)便可得到。计算过程中的简化与式(4-8)孙子定理恢复各需要30次加法，因此总运算量是35次乘法和159次加法。即，其中66次输入加法，93次输出加法。第五章 总结本文研究了数字信号处理方面的基础问题，如滤波器，离散傅
36、里叶变换，卷积的概念及应用等，查阅文献，针对卷积算法的计算进行深入研究，发现在离散卷积计算过程中的计算量会随着输入信号序列的长度而急速增加，传统的卷积计算算法已不能满足要求，而后研究了如何将一维卷积变换成二维卷积或多维卷积，而多维卷积中由包含简单的一维卷积，从而进行嵌套计算。研究了利用短卷积嵌套计算长卷积的算法，其中包括：二维卷积与多维卷积、Agarwal-Cooley卷积算法、分裂算法等。最终，实现16点循环卷积嵌套算法。通过本次论文设计，对数字信号处理专业知识有了深刻理解，提高了文献检索和科研能力。在对算法的学习和验证过程中，也学习了一些编程软件和编程语言。这对我以后的学习和工作都有很大的
37、帮助。参考文献1 J.W.Cooley, J.W.Tukey, An Algorithm for Maching Calculation of Complex Fourier Series, Math. Compution. Vol 19, 1995.2 C.M.Rader, Distance Convolution Via Mersenne Transform, IEEE Trans. C-21, 1992.3 H.J.Nussbaumer, P.Quandalle, Computation of Convolution and Discrete Fourier Transforms by
38、Polynomial Transforms, IBN J. Res. Dev Vol. 22, 1998.4 将增荣，多项式变换及其在卷积计算中的应用，计算数学，5：3（1998）.5 J.H. McClellan, C.M.Rader, Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Cliffs, N.J. 1978.6 S.Winograd, On Computing the Discrete Transform, Math. Comput. 32, 1978.7 S.Winograd, A New
39、 Method of Computing DFT,in 1977 IEEE Intern. Conf. Acoust, Speech and Signal Processing Proc, 1977.8 H.F. Silverman, An Introduction to Programming the WFTA, IEEE Trans,ASSP-25, 1997.9 H.J.Nussbaumer著，胡光锐译，快速傅立叶和卷积算法，上海科技文献出版社，198410 吕新华,武斌.基于圆周卷积的长序列小波变换快速实现J.信号处理. 2006(06)11陈启圣. 线性卷积、圆周卷积的计算机辅助教学
40、J.江汉大学学报. 1997(06)12张宪超,武继刚,蒋增荣,陈国良. 离散傅里叶变换的算术傅里叶变换算法J.电子学报. 2000(05)13 TuftsD W and SadasivG. The arithmetic Fourier transform. IEEE ASSP Magazine.199814 余品能,蒋增荣.图象及数字信号处理中的快速算法研究进展J.高校应用数学学报A辑(中文版).1991(02)15 刘伟,汪霞,马芙蓉.数字信号实时处理的一种快速算法J.科学之友(B版),2006（06).16 张明亮,李积逊.离散卷积和的一种计算方法J.济南职业学院学报.2007(04)17 龚妍,刘辉,曾喆昭.离散信号卷积运算研究J.长沙电力学院学报(自然科学版).2003(02)18 郑宝周,陈铁军,李辉.一种基于多项式变换的快速卷积算法J.微计算机信息.2005(24)
