用快速多项式变换（FPT）计算二维离散富里叶变换（DFT）

本文利用快速多项式变换(FPT)计算N×M 型二维DFT(M=2~m,N=2~(m-r+1),1≤r≤m),所需的乘法及加法次数(复乘及复加)分别为M_u=1/2NMlog_2M-3/2NM+N~2+N(1+log_2M-log_2N)A_d=NMlog_2NM,与通常的以2为基的二维FFT 比较,加法次数相同,乘法次数减少约30—40%,从而提高了计算精度。本算法还适用于并行算法。     

二维 DFT 和 DCT 的 Systolic 阵列

超级计算中一个活跃的研究领域是将某些有限和,如离散富里叶变换(DFT)、离散余弦变换(DCT),映射到多处理机阵列上。本文首先通过二维DFT的行列分解算法流程图,给出了计算二维DFT的二种Systolic阵列:一种是由N_1个处理器组成的线性阵列,所花时间步为O(N_1N_2)(设二维DFT为N_1×N_2长的),与行列分解算法在单处理机上顺序执行所花时间相比,加速比为O(N)(设N_1=N_2=N)。这一结果无论是在时间消耗,还是在PE数量上都是目前最优的。另一种是由N_1×N_2个处理器组成的矩形阵列,所需时间为O(N_1+N_2),与行列算法在单处理机上顺序运行所花时间相比,加速比为O(N~2)(这里仍假定N_1=N_2=N)。本文还给出了二维DCT的与二维DFT相似的Systoilc阵列结构。不难将上述阵列推广到多维的情况。     

二维离散富里叶变换(DFT)的FPT算法及其在计算机上的实现

本文首先用与[1]不同的方法推导了二维 DFT的FPT算法,所需运算量为 M=1/2NMlog_2M-2/3NM+N~2+N(1+log_2M-log_2N) A_d=NMlog_2NM与常用的二维FFT比较,两者加法量相同,乘法量本算法减少20--40％.然后比较详细的讨论了如何在通用计算机上实现这种算法,同时给出了我们在CYBER-73O机和银河机(YH)上试算的情况,结果表明,算法正确,所需计算时间比常用二维FFT减少20％左右(在YH机上减少35％左右)。     

DFT 的新算法

本文通过对离散富里叶变换(Discrete Fourier Transform,简记作DFT)矩阵的分解与FFT 算法相结合,提出了一个计算DFT 的新算法。由对矩阵的分解把求N=2~t 点的DFT 问题化为求16个N/16阶方阵与相应列向量相乘的问题(N≥16)。从而减少了乘法运算次数,且还具有良好的并行运算性质。     

多元多项式乘积的 FPT算法

本文详细讨论了多元多项式乘积的多项式变换(FPT)算法。首先给出了二元的情况,然后推广到了一般多元多项式,最后给出了这种算法在计算二维循环卷积中的应用,由此可见,这种算法在计算多维卷积和多维DFT 时是很有效的。     

二维离散余弦变换与二维离散Fourier变换的快速算法

文中提出N×M2D—DCT(Ⅱ)的一种快速算法,其需实运算量为:M_u=1/2NMlog_2N+1/4MNlog_2M,A_d=3/2NMlog_2NM—3MN—1/2M~2+M+N(其中N、M为2的幂)。当N=M时,与文[5]的结果一样、这是目前最好的结果。但文[5]算法不稳定,容易产生较大的误差。本文克服了这一缺点。并利用此2D—FCT(Ⅱ)导出了2D—DCT.2D—DST和2D—DCST的快速算法及2D—DFT的一种快速算法。2D—DFT快速算法的运算量与文[1]中用FPT计算2D—DFT相近。     

DFT的Z变换算法

文中讨论了用Z变换计算DFT的方法。对于N=2~t的DFT,本算法所需的加法及乘法量分别为:(?),与Cooley-Tukey基-2算法比较,乘法量与加法量均减少25%,文中还讨论了本算法在微机上的实现,给出流程图。在运算时间上,本算法与通用FFT算法程序进行比较:节省时间30%。     

一维变换与二维变换的等价以及二维DFT的向量算法

本文证明了当且仅当[R]=[P]~T(?)[Q]时,一维变换r=[R]X与二维变换[Y]=[Q][X][P]相互等价。此外,讨论了Hadamard变换以及具有循环卷积特性的一维变换与二维变换的等价问题。最后,利用上述等价定理,导出了二维DFT的一种比行列算法更为有效的快速算法——向量算法。     

快速多项式变换(FPT)及其在计算机上的实现

本文首先推导了两种快速多项式(FPT)算法,所需加法次数均为A_(?)=MN~2log_2N然后讨论了FPT在计算机上的实现,给出了详细框图。在附录中给出了FPT的FORTRAN源程序。     

基于单DSP实现并行扩维离散Hartley变换算法的研究

提出了一种将N点的一维离散Hartley变换(简称DHT)分解成N0×N1点的二维DHT(其中N=N0×N1)和一些运算量很小的附加运算的并行扩维DHT算法,此算法通过减少数据相关性的方法突破了DSP高效求解快速离散Hartley变换(简称FHT)时问题规模受片内内存容量限制问题,降低了编程复杂性,并在TMS320C80的单处理单元上进行了该算法实现方法的研究.结果表明,理论分析和试验结果吻合,该算法适合在单DSP上实现.