1、快速卷积中嵌套算法的设计与实现摘 要离散富里叶变换(DFT)和卷积计算在图象、数字信号处理中起着重要的作用，因此对快速算法的研究早就引起人们足够的重视。针对卷积算法的计算进行深入研究，发现在离散卷积计算过程中的计算量会随着输入信号序列的长度而急速增加，传统的卷积计算算法已不能满足要求，本文研究了如何将一维卷积变换成二维卷积或多维卷积，而多维卷积中由包含简单的一维卷积，从而进行嵌套计算。研究了利用短卷积嵌套计算长卷积的算法，最终实现 16 点循环卷积嵌套算法，大幅度减少了卷积的计算量。关键词：卷积,快速,嵌套iDesign and implementation of the nested alg
2、orithm 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 fi
3、nd 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
4、 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 reducing the computation of convolution.Key Words: convolution;f
5、ast,;nested目 录摘 要 .iAbstract.ii第一章 绪论 .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第五章
6、 总结 .37参考文献 .38本文由闰土服务机械外文文献翻译成品淘宝店整理0第一章 绪论1.1课题研究背景随着大规模集成电路、计算机和数字信号处理器（DSP）的快速发展，数字信号处理技术已得到广泛应用。然而在许多具体的应用场合需要处理的数据量和计算量都是巨大的，特别是在某些实时性要求较高的应用领域，对信号的处理速度是苛刻的。当然可以设计研制速度更快的处理器来满足要求，但研制新的处理器需要较大的投入和较长的研制时间，况且还有赖于技术的进步。另一种方案就是设计高效的算法使计算量降到可以接受的水平，实际上也正是出现了著名的离散傅里叶变换（DFT）的快速算法（FFT）后，数字信号处理技术才迅速发展起来
7、并走向实用的。通常我们在表达一个算法的时候是以一种人们容易理解的方式表达出来的，然而这种表达方式计算起来并不高效，需要用较多的乘法和加法次数；另外一种表示方法就是从计算效率的角度来表示一个算法，但这种表达方法往往又会使得表达式变得让人难于理解。例如，我们要计算下面一个表达式的值 A(1-1)acdb如果按照这个表达式计算需要 4 次乘法和 3 次加法，不难看出上面的表达式也可写成(1-2)()Aabcd这样只需要 1 次乘法和 2 次加法就可以了。另一个典型的例子是计算两个复数的乘积(1-3)()()ejfajbcjd其中 直接计算需要 4 次乘法和 2 次加法，如eacbd果把它们写成1(1
8、-4)()()ebacd()()fbacd则需要 3 次乘法和 5 次加法就可以了，通常 DSP 计算乘法要比计算加法来得复杂。如果 c 和 d 都是常数，那么 和 可以预先计算好，这样只需要3 次乘法和 3 次加法。这个复数乘法也可用矩阵表示(1-5)ecdafb按照第二个算法还可以写成(1-6)0110()0()ce adf bc 或写成简洁的形式(1-7)eaCMAfb矩阵 A 与向量 相乘只是一些加法运算，因此称 A 为前加矩阵；矩Tab阵 M 为一对角阵，它代表了算法中的所有乘法运算；C 则称后加矩阵。如果将 作为一个系统的输入数据， 作为系统的输出数据。那么，, ,ef这个算法可描
9、述为：首先将输入数据进行一系列的加法运算，然后是一些乘法运算，最后又是一系列的加法运算。今后我们介绍的快速算法大多可以用这种矩阵结构表示，即它的中间是一个对角矩阵表示乘法运算，两边的矩阵元素是1，0，-1 等简单的数，表示加法运算。我们再来看两个矩阵相乘的问题设 ， ，其中 F 为某一数域，则 C 的元素CAB,mllnmnFC， (1-8)1lijikjcab1,;,ijn 若直接计算，每计算一个 C 中的元素就需要 次乘法和 次加法，因此l(1)l总共需要 次乘法和 次加法。现在我们来改进这个算法，使得乘法lmn()lmn次数几乎减少一半，而加法次数略有增加。利用下面的恒等式2(1-9)1
10、212121()ababab则 (1-10)2 2,12,2,12,21,2,1,221,;,l lijikjikjikjikjl likikjcabababimjn 这里假定 是偶数，否则可在 A 中加入一列 0，在 B 中加入一行 0。上面的l表达式中第一项需要的乘法次数为 ，每一个元素都需要计算，因此共 次2l 2lmn乘法；第二项与 j 无关，每一行只要计算一次，因此共 次乘法；而第三项2l与 i 无关，每一列只要计算一次，因此共 次乘法；这样计算 C 总共需要2ln次乘法。1()2lmnl对每一个元素需要计算的加法次数为 次，对每一行或每一列要计算312l的加法次数为 次，因此加法次
11、数总共为 次。12l 12lmnlmn对于一个大的矩阵乘法次数大约是直接计算的一半。但值得注意的是这种算法对计算误差会比较敏感，特别是采用定点数计算的时候，这是工程技术人员值得注意的问题。但本课程主要讨论快速算法的问题，对计算误差的问题不做进一步的讨论。1.2快速卷积算法的发展历史有限长序列卷积(1-11)1,01,.0yMlmlNxg广泛地应用于相关函数和功率谱的计算以及有限长脉冲响应数字滤波器的3设计和实现等众多的数字信号处理领域。然而,直接计算(l-11)式所需乘法及加法运算量，当卷积结果长度 N 较大时，将随着 量级增长很大。以致在快2(N)O速算法提出之前，(l-11)式的应用受到了
12、很大的限制。1960 年和 1963 年 Good 和 Thomas 分别发表了他们的快速算法，但并没有引起人们的重视。1965 年，Coley 和 Tukcy 提出了一种称之为快速傅里叶变换(FFT)的计算机实现算法。应用该算法计算(l-11)式，其乘法及加法运算量均可降低到。1966 年 Stockham 将它用于卷积的计算，从而也推动的数字信2(Nlog)O号处理技术的快速发展。Cooley-Tukey 算法也被人们广泛第学习和研究，这种算法也就是一般的数字信号教课书中都有介绍的 FFT 算法；1978 年，wiongrad 推出 WFT 算法，使得(l-11)式的运算量进一步得到降低。
13、然而 FFT 及 WFT 都存在两点不足，即：需要计算三角函数以及需要施行复数运算，即使输入值为实序列也是如此，而且当卷积结果长度 N 增大时，所需乘法及加法量仍然很大，难于实现实时相关或实时卷积计算。早在 1972 年，C.M.Rader 在前人关于 Galois 域上的离散傅里叶变换研究的基础上提出了应用默森变换方法，在取默森 M 为模的整数环上计算序列卷积的默森变换(MN)T 算法闭。接着 Agarwal 和 Burrsu 进行了更深入的研究，奠定了数论变换(NTT)的基础。NTT 的应用使得卷积的乘法运算量降低到 ，并且其算法结构便于(N)O硬件实现。然而遗憾的 NTT 受到字长及变换
14、长度的严格限制，因此在应用上就有很大的局限性。1978 年，Nussbaumer 提出了快速多项式变换(FPT)算法,虽然解除了字长及变换长度受限的约束，但其乘法及加法运算仍然保持在的量级上，因而更适合于软件实现。2(Nlog)O1.3课题研究内容(1)研究快速卷积算法的基本原理和实现方法;(2)设计和实现快速卷积算法;(3)设计和推导快速卷积的嵌套算法并对算法性能进行评估;4第 2章 快速卷积算法运算中的问题2.1数字信号处理中的计算问题2.1.1滤波和相关数字信号处理中的主要任务是对信号进行滤波，有两种形式的数字滤波器：有限长冲激响应滤波器（FIR）和无限长冲激响应滤波器（IIR）无限长冲
15、激响应滤波器也称递归滤波器。它们的结构可用 图 2.1.1 和 图 2.1.2 表示。D D D D. . . . .g0g1g2g3gL - 1 d2, d1, d0 s2, s1, s0gL - 2图 2.1.1FIR 滤波器对于 FIR 滤波器其输入输出关系为线性卷积。设 d 为 N 点的序列，滤波器有 L 个系数用 g 表示，即 ， ，那么其011,Nd 011,Lgg输出序列 s 就是， (2-1)10Liiksg,2iL数字信号处理中的另一个问题是计算两个序列的相关 r， (2-2)10Liikrdg0,12iN显然它也可以用卷积来计算，只要将一个序列颠倒就可以了。与线性卷积密切相
16、关的是圆周卷积，设 d 和 g 都是 n 点的序列，圆周卷积定义为， (2-3)1()0nniiks0,1i表示对 n 取模，在含义清楚的情况下下标 n 也可不写。因 时，()n ki5； 时， 于是()ikiki()iknik， (2-4)10iiknikisdgg0,1in注意到当 时，第一项的 ， 是第二项的 ，所以kiiki0nikd， (2-5)1100nniikikinsdgs 0,1i此式表明线性卷积中下标大于等于 n 的部分折叠到下标 0 开始的地方，并将它们叠加起来。卷积还可以用多项式乘法来表示。设， (2-6)10()Niidx10()Liigx以及(2-7)20()LNi
17、isxs则(2-8)()()sxdgx不难验证 的系数就是 d 和 g 的线性卷积。显然 还可以写成()sx ()sx，因此线性卷积是符合交换律的，还可以写成()sxgd(2-9)10Niiksgd圆周卷积也可以用多项式表示，设， (2-10)10()niidx10()niigx以及(2-11)10()niisxs则6(2-12)()mod1()mod1()n nsxxgxg显然圆周卷积也是符合交换律的，对 取模只要简单地将多项式中的n代以 1，而 代以 。 图 2.1.1 是用 FIR 滤波器来得到圆周卷积，nx,0nixix输入序列重复 2 次，在输出的 3n-1 点中，中间的 n 点即为
18、圆周卷积。D D D. . . . .g0g1g2gn - 1dn - 1 d1, d0, dn - 1 , d1, d0gn - 2 10,nxsx中间 n 点为圆周卷积图 2.1.1用 FIR滤波器得到圆周卷积圆周卷积是一种快速计算线性卷积的重要手段。为计算一个长序列的线性卷积，通常将输入序列分段计算，然后将输出序列拼接。对输入数据的分段一般有两种方法：一是数据分段不重叠，这样卷积的输出需要叠加；另一种数据分段重叠，这需要将卷积输出中的混叠部分舍去。假定滤波器系数的长度为 n1 点，数据分段不重叠的方法称重叠相加法（overlap-add） ，将数据分成长度为 n2 点的互不重叠的数据段，记， ， (2-13)2,miind20,1 ,012m 然后，计算 与 ， 的 点圆周卷积，显然计算,iig 2n结果就是两个序列的线性卷积，记为 ,mis， (2-14)11,(),00nnmiikikkksdgd0,1in由于 ，所以2,iinmd(2-15)2 221 1,() ,(),0 0n ni ikmnkmiknmink ksgdgs
