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

一、引言由于大规模集成电路和各种快速算法的发展,以及近些年来数字硬件的价格迅速下降,使图象、数字信号处理技术发展迅速,其应用日益广泛,在通信、雷达、声纳、地震物探、遥感、生物医学及工业等各个部门已得到实际应用。快速富里叶变换(FFT)和积算法是实现数字滤波、计算离散富里叶交换(DFT)和进行频谱分析的基本方法。自从一九六五年,J.W.     

十六点和十一点高效短卷积算法

在本文中,我们利用卷积的模多项式表示式及孙子定理导出了16点和11点短卷积的有效算法,所需运算量是M_(16)=35,A_(16)=159;M_(11)=43,A_(11)=169;M'_(11)=41,A'_(11)=137。用同样的方法也可导出其它长度短卷积的算法。     

数论中的计算问题

有人说,数论更像一门实验科学。这大概是因为计算对它来说是十分重要的。     

两个最佳短卷积算法

借助卷积的模多项式表示式及中国剩余定理推导出计算16点和11点短卷积的最佳算法，其算术复杂性分别为M16=35，A16=159；M11=41，A=-137，是目前公布的运算量最小的算法。与已有的7种最佳短卷积算法一起，使可嵌套计算的卷积长度范围由48种扩展到120种，满足了实际应用的需要。