快速卷积中嵌套算法的设计内容与实现说明书.doc

《快速卷积中嵌套算法的设计内容与实现说明书.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、快速卷积中嵌套算法的设计与实现摘要离散富里叶变换(DFT)和卷积计算在图象、数字信号处理中起着重要的作用，因此对快速算法的研究早就引起人们足够的重视。针对卷积算法的计算进行深入研究，发现在离散卷积计算过程中的计算量会随着输入信号序列的长度而急速增加，传统的卷积计算算法已不能满足要求，本文研究了如何将一维卷积变换成二维卷积或多维卷积，而多维卷积中由包含简单的一维卷积，从而进行嵌套计算。研究了利用短卷积嵌套计算长卷积的算法，最终实现16点循环卷积嵌套算法，大幅度减少了卷积的计算量。关键词：卷积,快速,嵌套iDesignandimplement

2、ationofthenestedalgorithmoffastconvolutionAbstractDiscreteFourierTransform(DFT)andconvolutioncalculationplaysanimportantroleintheimage,adigitalsignalprocessing,andthereforethestudyoffastalgorithmshaveattractedenoughattention.ThroughtheIn-depthstudyoftheconvolutionalgorith

3、m,wefindthecalculationoftheconvolutioncalculationwillincreaseswiththelengthoftherapidoftheinputsignalsequence.Conventionalconvolutioncalculationalgorithmcan’tmeettherequirements.Thispaperstudieshowtheone-dimensionalconvolutiontransformintoamulti-dimensionalconvolutionortw

4、o-dimensional,andmulti-dimensionalconvolutionincludesimpleone-dimensionalconvolution.Usingshortconvolutioncalculatelongconvolution,andfinallyachieving16pointsnestedcircularconvolutionalgorithm,significantlyreducingthecomputationofconvolution.KeyWords:convolution;fast,;nes

5、tedi目录摘要iAbstractii第一章绪论11.1课题研究背景11.2快速卷积算法的发展历史31.3课题研究内容4第二章快速卷积算法运算中的问题52.1数字信号处理中的计算问题52.1.1滤波和相关52.1.2离散傅里叶变换82.2算法序列11第三章利用短卷积嵌套计算长卷积算法原理简介133.1二维卷积与多维卷积133.2Agarwal-Cooley卷积算法193.3分裂算法28第四章快速卷积嵌套算法实现344.116点循环卷积算法实现344.2算法性能分析35第五章总结37参考文献38本文由闰土服务机械外文文献翻译成品淘宝店整理第

6、一章绪论1.1课题研究背景随着大规模集成电路、计算机和数字信号处理器（DSP）的快速发展，数字信号处理技术已得到广泛应用。然而在许多具体的应用场合需要处理的数据量和计算量都是巨大的，特别是在某些实时性要求较高的应用领域，对信号的处理速度是苛刻的。当然可以设计研制速度更快的处理器来满足要求，但研制新的处理器需要较大的投入和较长的研制时间，况且还有赖于技术的进步。另一种方案就是设计高效的算法使计算量降到可以接受的水平，实际上也正是出现了著名的离散傅里叶变换（DFT）的快速算法（FFT）后，数字信号处理技术才迅速发展起来并走向实用的。通常我们在

7、表达一个算法的时候是以一种人们容易理解的方式表达出来的，然而这种表达方式计算起来并不高效，需要用较多的乘法和加法次数；另外一种表示方法就是从计算效率的角度来表示一个算法，但这种表达方法往往又会使得表达式变得让人难于理解。例如，我们要计算下面一个表达式的值A(1-1)如果按照这个表达式计算需要4次乘法和3次加法，不难看出上面的表达式也可写成(1-2)这样只需要1次乘法和2次加法就可以了。另一个典型的例子是计算两个复数的乘积(1-3)其中直接计算需要4次乘法和2次加法，如果把它们写成38(1-4)则需要3次乘法和5次加法就可以了，通常DSP计

8、算乘法要比计算加法来得复杂。如果c和d都是常数，那么和可以预先计算好，这样只需要3次乘法和3次加法。这个复数乘法也可用矩阵表示(1-5)按照第二个算法还可以写成(1-6)或写成简洁的形式(1-