An Extendible Look-Up Table of Twiddle Factors for FFT

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.