GFT及离散卷积的并行算法及其实现

PARALLEL ALGORITHMS FOR GFT,SKEW-CYCLIC CONVOLUTION AND CYCLIC CONVOLUTION

一、GFT的计算 GFT是离散富里叶变换DFT的一种推广.它在许多方面有实际应用,其定义为: 设a,b为二个实数,x_n(n=0,1,…,N—1)为一实序列,称 X_k=sum from n=0 to N-1 x_nW_N^((n+a)(k+b)),k=0,1…,N-1,为具有时间参数a及频率参数b的广义DFT.简记为GFT(a,b),其中W_N=e^(-i2π/N)。

Based on the parallel algorithms for DCT and DST, parallel algorithms for generalizeddiscrete Fourier transform(GFT), skew-cyclic convolution and cyclic convolution are proposed.These algorithms are simple in construction and easy for programming. Compared with para-llel algorithms using FFT, the proposed algorthms have remarkably reduced time complexity.As part of the applied software library of YH-I super computer, the programs in FORTRANhave been made. They can run, on YH-I, more than eight times faster by vector computa-tion than by scalar computation. So, the programs are highly vectorized.