快速多项式变换(FPT)算法计算二维离散傅里叶变换(DFT)的一种新的改进方法

本文研究了利用快速多项式变换(FPT)来计算大小为N×N(N=2~t)的二维离散傅里叶变换。本文首先对多项式变换计算二维DFT的实现方案进行了讨论,提出了更利于具有专门乘法硬件处理器计算的FPf实现方案——用FFT法汁算FPT中奇DFT的算法。并在此基础上,通过对乘法和加法的综合考虑,对这种实现方案提出了一种改进方法。这种改进方法通过抽点,将一次N点奇DFT,分解为2次2点DFT,在乘法量基本保持不变下,加法量比原FPT减少5%左右。这种算法比常规的行——列法在乘法上减少约50%,在加法上减少约15%。     

快速W变换

本文给出一种效率高且结构简单的算法,用以计算所有四种类型的N=2~M点离散W变换(DWT)。其中对第Ⅰ种离散W变换(DWT-Ⅰ,亦称离散Hartley变换,DHT)所需的计算量为:乘法(N/2)(log_2N-3)+2次;加法(N/2)(3log_2-5)+6次。这比已发表的其他计算DWT-Ⅰ(DHT)算法的效率均高。     

一种新的按位块分段快速排序算法

针对分段快速排序法因分段映射策略不理想而造成算法复杂度显著增加之问题，文章提出了一种由按位块分段、分段映射和局部快速排序所组成的新排序算法——按位块分段快速排序法（以下简称为“按位块分段快速排序”）。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下，按位块分段快速排序法的时间复杂度可以达到O（N），而附加存储空间开销却仅仅为N＋M（M为分段数目，1≤M≤N），同时排序速度明显优于Quick Sort、分段快速排序、分“档”统计插入排序和Proponion Split Sort等算法。     

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

本文把长为plq(p为奇数,q为任意自然数)的DHT转化为Pl个长为q的DHT的计算及其附加运算,附加运算只涉及P点cos-DFT和sin-DFT的计算;对长度(P1l,1,Psls 2l (p1, , ps为奇素数)的DHT,用同样的递归技术得到其快速算法,因而可计算任意长度的DHT;文中还论证了计算长为N的DHT所需的乘法和加法运算量不超过O(Nlog2N)。当长度为N=pl时,本文算法的乘法量比其他已知算法更少。     

FIR数字滤波器的一种快速算法

FIR数字滤波器本质上是一种线性卷积的运算,当数字滤波器的阶次N很大时,计算量很大,计算速度很慢,达不到系统对实时性的要求。文章介绍了一种数字信号处理算法,该算法将线性卷积运算转换成加法运算,利用加法运算进行求解,避免了数据堆积,加快了运算速度,从而使数字滤波器处理过程实时、快速。     

改进的算术傅立叶变换（AFT）算法

算术傅立叶变换（AFT）是一种非常重要的傅立叶分析技术。AFT的乘法量少（仅为O（N））,算法结构简单,非常适合VLSI设计,具有广泛的应用。但AFT的加法量很大,为O（N∧2）,因此减少AFT的加法运算是很重要的工作。本文通过分析AFT的采样特点,给出了奇函数和偶函数的AFT的改进算法。然后在此基础上给出了一般函数的AFT的改进算法。改进算法比原算法的加法运算量降低了一半,因此计算速度快了一倍。本文改进的偶函数和奇函数的AFT算法还分别可以用来计算离散余弦变换（DCT）和离散正弦变换（DST）。     

WPS头部文件的探讨

金山汉字系统中的文字处理软件WPS有两种文字编辑方式:一种为“D”方式,另一种为“N”方式。其不同之处就在于用“D”方式编辑出来的文件(以下简称D型文件)其首部存在一个1K(1024)字节长的‘头’;而用“N”方式则没有这样的‘头’。这个‘头’的大小体现在文件长度上,例如用“N”编辑一个M字节的文件,那么用“D”编辑同样内容的文件,其长度则为1024+M个字节。     

A*B模N的快速计算

在保密的密码体制中,A*B模N计算是一种重要的计算。由于涉及的n其字长很长,所以它的高速计算方法比较重要。本文论述了在采用的分量不大于n+3比特宽度时,对于n比特的自变量只需要2n保留进位加法,继尔再用最终的同化(assimilation)补添两次进位。     

基于窄带Mumford—Shah模型的图像分割方法

在结合Mumford-Shah模型和水平集方法中的窄带解法优点的基础上，提出了一种新的图像分割模型。Mumford-Shah模型虽然具有良好的图像分割结果，但是其每次迭代过程都需要对所有图像数据进行计算，因而很费时，导致这种方法不适用于大的图像数据，特别是三维图像的分割。本文通过一种新的初始化方法把Mumford-Shah模型和水平集中的窄带解法结合在一起。这种新 的初始化方法是通过在特定条件下简化快速行进法得到的。通过去除快速步进法中费时的 排序过程，使得初始化的计算时间只有O（N）。窄带Mumford-Shah模型把分割计算限制在窄带范围内，避免了大量的计算，但取得了与原始的Mumford-Shah模型相同的分割效果。实验结果表明基于快速步进法的初始化方法是可行的，而窄一喧M－S分割模型一次迭代计算的时间比原M－S模型减少许多。     

基于子集划分的素长度二维DCT快速算法

该文针对素长度类型的2维离散余弦变换(DCT)变换,提出一种子集划分准则,并根据该准则将2维DCT变换输出的频域数据集合划分为若干个互不相交子集;将对频域的计算转换为对2(N－1)个N点1维素数尺寸DCT的奇系数或偶系数的计算;最后给出了该算法的乘法复杂度和加法运算复杂度。相对于行列分解法,该算法节省了约一半的乘法次数,省略了数据的转置存储过程,而加法的运算复杂度基本维持不变。