Fast Fourier Transform:Algorithm And Application

Discrete Fourier transform?DFT?is widely used in almost all the fields of science and engineering.DFT is the most important tool for signal processing.In communication area,DFT is used in orthogonal frequency division multiplexing?OFDM?system.However,the direct computation of DFT is an intensive computational task.Therefore,more efficient and lower intensive algorithms are required.The modified split-radix FFT?MSRFFT?proposed by Johnson and Frigo of Mas-sachusetts Institute of Technology implements a length-N=2^m DFT with the lowest com-putational complexity before two algorithms with lower complexity than MSRFFT were proposed in 2014.The latest two algorithms are all based on MSRFFT.However,MSRFFT requires more memory size to store its twiddle factors,and its decomposition is also more complexity than others.To improve its practicability,we reduce one decomposition group from four decomposition groups of MSRFFT,and reduce the accesses to lookup table from 5/8N-2to 15/32N-2.We propose an algorithm,radix-3/6^m FFT for computing length N = 6^m DFT.The new algorithm decomposes a DFT of length N = 6^m into a length-N/3 of sub-DFT and four length-N/6 of sub-DFTs.The four length-N/6 sub-DFTs are rotated specifically,avoiding the lower index of the twiddle factor contains the factor 3 and reducing the number of real operations.For a length-N= q×2^m of DFT,we decompose it into q length-2^m of sub-DFT by performing 2^m length-q DFT.By transforming,items with twiddle factors ?wⁿ?_N,W_N^N/4+n,...,W_N^?q-1?N/4+n?the total number of items is q?are ranged in a column or a row,and the common factor ?wⁿ?_N is extracted from these twiddle factors and then a scaled DFT is obtained.The SDFT can be implemented with an efficient algorithm reducing the number of operations.Due to prime FFT poorer accurate precision than powers-of-two FFT,we do an improvement of the above algorithm for length-N= q×2^m DFTs.By rotating transforming,we range the 2^m items with twiddle factor Wqn in a column or a row,and the common factor Wqn is extracted and then a length-2^m of SDFT is obtained.The scaled DFT?SDFT?can be implemented efficiently with scaled radix-2/8 FFT.As compared to the last algorithm,the computational complexity required by the latter algorithm is the same as that of the last one,but the accurate precision is improved by the latter one.For length-N=2^m DFTs,we propose four algorithms based on the technique of MSRFFT.These four algorithms overcome the shortcoming of MSRFFT by extending the technique of extracting common real number factor of MSRFFT to extracting complex number factor.As compared to SRFFT,two of the four algorithms improve the performance in the computational complexity,accurate precision,and accesses to lookup table.The other two algorithms are the algorithms of the lowest computational complexity as compared to the published algorithms.Due to high complexity of the algorithms with L-shape butterfly,we present an method for regularly implementing these algorithms.The method divides a L-shape butterfly into some butterfly units with two inputs and two outputs?BU-2?,and divide a butterfly block into some BU-2 block.ALL SRFFTs such as radix-2/8 FFT can be implemented like the radix-2 FFT with this method.By this method,we iteratively implement the MSRFFT algorithm and the radix-2/8 FFT.The experimental results show that,?1?MSRFFT requires less CPU time than other algorithms when DFTs are smaller,but requires more CPU time when DFTs are greater,since MSRFFT requires more memory size and the CPU time increases rapidly when DFT is great.?2?Our proposed algorithms for N = q×2^m requires less CPU time than other algorithms.As compared with FFTW,the algorithms requires less CPU time when DFT is small and requires more CPU time when DFT is great,since no memory optimization has be performed in our implementation.Pruned fast Fourier transform?FFT?is an efficient technique to compute discrete Fouri-er transform?DFT?when the input sequence is zero-padded and/or only a subset of DFT output points is needed.We utilize conjugate pairs to reduce real operations in the pruning FFT.We first devise the pruned conjugate pair FFT?PCPFFT?for output pruning.Three pruning FFTs,which are based on the conjugate pairs of twiddle factors and the transform decomposition,are then developed for output,input,and input/output pruning.The PCPFFT algorithm can take full use of conjugate pairs in output pruning but requires a non-bit-reversal permutation of the DFT sequence,and the other three algorithms have the advantages of reg-ularity and simplicity due to the transform decomposition.The results of evaluation and analysis show that the proposed pruning FFTs require fewer arithmetic operations compared with the state-of-the-art schemes.Multiple sequence alignment?MSA?is the most common task in bioinformatics.Mul-tiple alignment fast Fourier transform?MAFFT?is the fastest MSA program among those the accuracy of the resulting alignments can be comparable with the most accurate MSA programs.To improve MAFFT in efficiency,we modify the correlation computation scheme of MAFFT in three aspects.First,novel complex number based amino acid and nucleotide expressions are utilized in the modified correlation scheme.In doing so,half of the memory size and more than half of the related calculations,can be saved compared to the standard requirement.Second,linear convolution replaces cyclic convolution for computing the cor-relation of amino acid and nucleotide sequences,which can find more homologous regions in the process of computing the optimal path.Third,we devise a fast Fourier transform?FFT?algorithm for computing efficiently linear convolution.The FFT algorithm is based on conjugate pair split-radix FFT and does not require the permutation of order.The FFT is a novel output pruning method,in which only the real parts of the final outputs are re-quired.Simulation results show that the speed of the modified scheme is 3 times faster than that of MAFFT for computing the correlation between sequences,which is highly efficient.In the case when the lengths of sequence are powers-of-two,the former can identify about twice number of homologies compared to the latter one,and the CPU time on two-sequence alignment is about half that of MAFFT.Total,we propose several algorithms with the lowest computational complexity as com-pared with the published algorithms.The proposed implementation schemes can implement iteratively the algorithms with L-shape butterfly,like the implementation of radix-2 FFT.The modified MAFFT up 2?3 times the speed for the sequence correlation computation.