广义离散傅里叶变换的模多项式分解算法(MPDA)及其矩阵表现形式

§1.引言 离散傅里叶变换(DFT)和卷积计算在图象、数字信号处理中起着极为重要的作用,它们是实现数字滤波、进行频谱分析的基本工具.因此,其快速算法的研究异常活跃.在以上众多算法中,由于基-2、基-4快速傅氏变换(FFT)算法具有简洁的蝶式结构,并且可在原置实现等特点,应用极为广泛.70年代末提出的数论变换、多项式变换已发展成完整的理论,成为处理多维DFT和卷积的有力工具.然而它们对一般一     

数论在数字信号处理中的应用

今天,在几乎所有的工程领域中,都需要运用各种数学变换、通过计算机对数字信号进行处理,因此,这些变换成了数字信号处理中的一种重要的工具. 数字信号处理中两个最基本的运算是计算离散付里叶变换(DFT)和卷积.为了快速计算它们,最近,出现了好几种新的数学变换,例如计算卷积的数论变换(NTT),计算DFT的Winograd变换(WFTA)等等,这些变换的乘法次数比熟知的快速付里叶变换(FFT)要少.所有这些变换有一个共同的特点,就是以数论作为它们的数学工具.1979年,国外已写出专著,总结了这方面的工作;1980年,国内这方面的一些工作也写进了著作[2].本文将扼要介绍国内外这方面的工作.为了后面叙述方便,这里先介绍一下卷     

图象及数字信号处理中的快速算法研究进展

本文就各种特殊基的FFT算法、互素因子类算法、数论变换、多项式变换、DFT的计算复杂性及FFT的并行算法有关专题,简要地叙述了图象和数字信号处理中的快速算法(离散付里叶交换及卷积计算)的研究概况,并就笔者的观点指出了目前及将来若干进一步研究的主要问题.     

N=2^t点DFT的快速卷积算法

从所周知,循环卷积和离散富里叶变换(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))点     

FFT的一般计算式(B型)及其极小化问题

在快速富氏变换(FFT)领域中,以任意数M(M=2~n,n为任意正整数)为基的一般计算式问题,至今尚未解决.本文提出此问题并推证了它.文中的计算量比赵访熊李庆扬改进的FFT计算公式大约减少40％.文中得到了与“Bergland-Brigham结论”迥然不同的结果,并解决了实用中最优基的选取问题. 考虑离散富氏变换(DFT):     

三维DFT的FPT算法

本导出了一种三堆离散富氏变换(DFT)的快速多项式变换(FPT)算法，并对该算法的计算量与通常所用算法(行列法)进行了比较，最后对算法的优劣作了总结．     

FGFT的并行算法及其应用

常见的离散Fourier变换(DFT)的推广均定义在一个交换环上。我们在[1]、[2]中给出了DFT在一类非交换环上的推广(FGFT),并将它应用于一些快速线性计算问题。本文将不加证明地列出这些快速算法的并行计算效率。结果表明,这些计算问题亦具有很好的并行性。     

数论变换(三)

本文(一)和(二)部分,都是讨论一维数论变换,现在讨论多维的情况. 如果在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,它们的循环褶积是指     

基于二元多项式乘积的二维循环卷积算法

本文详细讨论一种基于多元多项式乘积的二维循环卷积算法,并与其快速多项式变换(FPT)算法进行了比较,比较结果显示该算法具有明显的优越性.     

广义Mbius变换和算术Fourier变换

离散Fourier变换(DFT)在数字信号处理等许多领域中占有重要地位.近年来,出现一种优于FFT的算术Fourier变换来计算DFT.在广义M     

任意长度离散余弦变换的快速算法

§1.引言 离散余弦变换(DCT)有趋于统计最佳交换Kavhunven-Lave变换(KLT)的渐近性质,在通信和信号处理中应用广泛,并在许多方面比离散富里叶变换(DFT)更好。     

广义M(o)bius变换和算术Fourier变换

离散Fourier变换(DFT)在数字信号处理等许多领域中占有重要地位.近年来,出现一种优于FFT的算术Fourier变换来计算DFT.在广义M(o)bius变换的基础上,本文采用了一种改进的AFT来计算DFT,这种方法可以直接提取DFT的系数,且用数论的方法阐明了这一过程,并展开了进一步的讨论.这也代表了数论方法应用在计算数学领域的一个新的发展方向.     

广义M(o|¨)bius变换和算术Fourier变换

离散Fourier变换(DFT)在数字信号处理等许多领域中占有重要地位.近年来,出现一种优于FFT的算术Fourier变换来计算DFT.在广义Mobius变换的基础上,本文采用了一种改进的AFT来计算DFT,这种方法可以直接提取DFT的系数,且用数论的方法阐明了这一过程,并展开了进一步的讨论.这也代表了数论方法应用在计算数学领域的一个新的发展方向.     

关于一些代数问题的复杂性下界

一、引言自从六十年代中期Cooley和Tukey提出工作量为O(nlog_2n)的FFT算法以来离散Fourier变换(DFT)已真正成为很多应用领域的有力工具。能否在量级上继续降低FFT的工作量呢?这一问题曾一度吸引了很多著名的学者。1973年,Morgenstern证明了DFT的线性复杂性下界为n/2log_2n,从而使得这些无休止的尝试暂告段落。     

循环差分-微分模上双变元维数多项式的Gr?bner基算法北大核心CSCD

Gr?bner基算法是在计算机辅助设计和机器人学、信息安全等领域广泛应用的重要工具.文章在周梦和Winkler(2008)给出的差分-微分模上Gr?bner基算法和差分-微分维数多项式算法基础上,进一步研究了分别差分部分和微分部分的双变元维数多项式算法.在循环差分-微分模情形,构造和证明了利用差分-微分模上Gr?bner基计算双变元维数多项式的算法.     

循环差分-微分模上双变元维数多项式的Gr?bner基算法

Gr?bner基算法是在计算机辅助设计和机器人学、信息安全等领域广泛应用的重要工具.文章在周梦和Winkler(2008)给出的差分-微分模上Gr?bner基算法和差分-微分维数多项式算法基础上,进一步研究了分别差分部分和微分部分的双变元维数多项式算法.在循环差分-微分模情形,构造和证明了利用差分-微分模上Gr?bner基计算双变元维数多项式的算法.     

用多项式变换计算多维离散W变换

1．引言多维离散W变换作为多维离散Hartley变换的推广［1－3］，是处理多维问题的一种工具．在计算机视觉、高清晰度电视（HDTV）以及可视电话等领域，经常要对运动图象进行分析和处理，通常称为多帧检测（Multi－WameDetection，简称MFD）［4－5］，这时三维离散w变换是一种可行的方法．由于不需要进行复数运算，比三维离散傅立叶交换（DFT）有优越性．而对运动的三维图象进行处理时，可采用四维离散w变换．对维数更高的多维信号进行处理时，可采用多维离散w变换．对三维以上的w变换，需要的运算量非常大，设计好的快速算法极为重要…     

QTT分解及其在高维数字信号处理上的应用

近几年张量列(TT)和量子化张量列(QTT)分解方法被证明是一种非常有效的特征降维工具,并已广泛应用于PDE、算法加速和信号处理等领域.给出了关于QTT分解的一些新结果.首先用分块张量的方法扩展了QTT的定义,使之适用于更加复杂的降维问题.同时指出新定义的QTT分解也是一种基于流形学习的降维工具.其次讨论了QTT与小波变换和卷积在结构上的联系与区别,并指出QTT也是一种特征提取工具.最后将QTT分解应用于三维数据(MRI图像)的去噪和边缘检测,取得了不错的效果.     

双特征参数基因识别算法实现

基因识别问题首要的工作是对数字化后的基因序列利用离散傅里叶变换(DFT)进行频谱分析.对于很长的DNA序列,功率谱或信噪比计算量很大,推导出了DNA序列在Voss映射、Z-curve映射和实数映射下的信噪比快速算法,以及在Voss映射与Z-curve映射下的信噪比的关系.针对阈值确定的问题提出了基于滑动窗口的局部阈值的算法,在分类时达到了很好的效果.另外,实现了基于移动序列信噪比曲线的基因识别方法.最后,由于DNA序列的3-周期性实际上反映了核苷酸在基因序列的三个子序列上分布的"非均衡性",因此引入"方差均值"特征来衡量该非均衡性,提出了基于方差均值的单因素基因识别方法及以信噪比和方差均值作为特征向量,并设计多项式分类器的基因识别算法.     

广义Moebius变换和算术Fourier变换

离散Fourier变换(DFT)在数字信号处理等许多领域中占有重要地位．近年来，出现一种优于FFT的算术Fourier变换来计算DFT．在广义Moebius变换的基础上，本文采用了一种改进的AFT来计算DFT，这种方法可以直接提取DFT的系数，且用数论的方法阐明了这一过程，并展开了进一步的讨论．这也代表了数论方法应用在计算数学领域的一个新的发展方向．