共查询到10条相似文献,搜索用时 781 毫秒
1.
§1.引言 离散傅里叶变换(DFT)和卷积计算在图象、数字信号处理中起着极为重要的作用,它们是实现数字滤波、进行频谱分析的基本工具.因此,其快速算法的研究异常活跃.在以上众多算法中,由于基-2、基-4快速傅氏变换(FFT)算法具有简洁的蝶式结构,并且可在原置实现等特点,应用极为广泛.70年代末提出的数论变换、多项式变换已发展成完整的理论,成为处理多维DFT和卷积的有力工具.然而它们对一般一 相似文献
2.
今天,在几乎所有的工程领域中,都需要运用各种数学变换、通过计算机对数字信号进行处理,因此,这些变换成了数字信号处理中的一种重要的工具. 数字信号处理中两个最基本的运算是计算离散付里叶变换(DFT)和卷积.为了快速计算它们,最近,出现了好几种新的数学变换,例如计算卷积的数论变换(NTT),计算DFT的Winograd变换(WFTA)等等,这些变换的乘法次数比熟知的快速付里叶变换(FFT)要少.所有这些变换有一个共同的特点,就是以数论作为它们的数学工具.1979年,国外已写出专著,总结了这方面的工作;1980年,国内这方面的一些工作也写进了著作[2].本文将扼要介绍国内外这方面的工作.为了后面叙述方便,这里先介绍一下卷 相似文献
3.
图象及数字信号处理中的快速算法研究进展 总被引:9,自引:0,他引:9
本文就各种特殊基的FFT算法、互素因子类算法、数论变换、多项式变换、DFT的计算复杂性及FFT的并行算法有关专题,简要地叙述了图象和数字信号处理中的快速算法(离散付里叶交换及卷积计算)的研究概况,并就笔者的观点指出了目前及将来若干进一步研究的主要问题. 相似文献
4.
从所周知,循环卷积和离散富里叶变换(DFT)可以互相计算,只要得到其中一个的快速算法就可导出另一个的快速算法。循环卷积目前已有乘法量为O(N)的最佳算法(特别是当N较小时),为此关键是如何将DFT转化为循环卷积,当DFT的长度N=p(p为素数),Rader利用有限域GF(p)的乘法群是循环群就成功地将p点DFT转化为Q(p)(F(p)为户的Euler函数)点循环卷积;当N=p~e时,由于商环Z/(p~e)存在F(p~c)阶元素,人们也成功地将p~c点DFT转化为P(p~(c-1))一系列循环卷积,即一个y(p~c)点循环卷积,二个P(p~(c-1))点 相似文献
5.
6.
本导出了一种三堆离散富氏变换(DFT)的快速多项式变换(FPT)算法,并对该算法的计算量与通常所用算法(行列法)进行了比较,最后对算法的优劣作了总结. 相似文献
7.
常见的离散Fourier变换(DFT)的推广均定义在一个交换环上。我们在[1]、[2]中给出了DFT在一类非交换环上的推广(FGFT),并将它应用于一些快速线性计算问题。本文将不加证明地列出这些快速算法的并行计算效率。结果表明,这些计算问题亦具有很好的并行性。 相似文献
8.
数丁 《数学的实践与认识》1978,(2)
本文(一)和(二)部分,都是讨论一维数论变换,现在讨论多维的情况. 如果在Z_M上引入m维(m≥2)的DFT,然后用类似FFT的快速演段来计算,就叫多维数论变换.关于Z_M上二维的DFT存在问题,国外给出了一个含混不清的充分条件,而我们给出了一组充分必要条件,参看文[4],为引用方便,把定义和结果简述如下:两个二维序列x_(n_1,n_2),h_(n_1,n_2),n_1=0,1,…,N_1-1,n_2=0,1,…,N_2-1,它们的循环褶积是指 相似文献
9.
本文详细讨论一种基于多元多项式乘积的二维循环卷积算法,并与其快速多项式变换(FPT)算法进行了比较,比较结果显示该算法具有明显的优越性. 相似文献