可扩展的旋转因子表及FFT算法

An Extendible Look-Up Table of Twiddle Factors for FFT

该文提出了一个用于快速 Fourier变换计算的反写码序的旋转因子表 ,这种旋转因子表具有可扩展性 :本质上 ,这种旋转因子表的分量与变换的点数无关 .当点数改变时 ,这种旋转因子表无须重新计算或者容易扩展 ;根据这种旋转因子表 ,该文设计了一个结构规整的基于基 4计算 2 n 点 FFT的算法及软件程序 ,该程序与 FFTW软件包进行了对比实验 .文中还以蛋白质序列相似性分析计算为例 ,对作者的算法与 FFTW软件包中的相应算法进行了对比实验 ,结果表明 ,采用该文的算法可节省计算时间约 31.7% .

The Fourier transform arises in many fields of science, like signal processing, image processing, bioinformatics, computational physics and applied mathematics, etc. The most popular algorithm for computing a Fourier transform is the fast Fourier transform (FFT) algorithm. For implementation of FFT algorithms, one can create an array to store the kernel of the Fourier transform namely the so called twiddle factors, and this array is called look up table. In this paper, we recommend a bit reversed order (BRO) look up table of the twiddle factors for implementing of FFT algorithms with size of entry data N=2 n. This BRO look up table of twiddle factors is extendible, that is, it does not depend on the size of the data sequence as far as lower sizes are concerned and is easily extendible to larger sizes. The most four important twiddle factors 1, -i, (1-i)/2, and -(1+i)/2 are just located in the first four components of the BRO look up table of twiddle factors. In this paper, we also discuss some FFT algorithms with this BRO look up table of twiddle factors. Based on a classical FFT algorithm, we derive a new radix 4 based FFT algorithm and develop some programs. Experimental comparisons have been done between our new FFT algorithm and FFTW (Fastest Fourier Transform in the West) software package which is the most popular package about FFT computations. And the numerical results indicate that our new FFT algorithm and its related programs are effective. As an example for the application of our new FFT scheme, we consider the analyses of similarity of protein sequences that need a large number of FFT computations. The results show that the elapsed time of the program with our FFT scheme can be cut down by 31.7% from that of the program with the FFTW software package.