Research On Fast Fourier Transform Algorithm Based On Eisenstein

Fast Fourier transform(FFT)is one of the basic algorithms in the field of digital signal.It is widely used because of its fast speed of discrete Fourier transform(DFT).In the process of modulation and demodulation of OFMD,it plays an important role in the transformation of serial and parallel signals.It also plays an irreplaceable role in the conversion of time-domain signals to frequency-domain signals in speech system,image preservation,restoration,enhancement and so on.With the further improvement of real-time requirements in these application fields,FFT algorithm will face higher and higher computational performance requirements,so the research on faster Fourier transform algorithm has strong practical significance and industrial value.In this thesis,we mainly focus on the fast Fourier transform algorithm and Eisen-stein base,and introduce Eisenstein base into the Fourier transform correlation algo-rithm.The study uses the correlation properties of Eisenstein base to reduce the amount of calculation required by the algorithm so as to achieve faster calculation under the length of N=6m to reduce the calculation time of FFT.The main research work of this thesis includes the following three aspects:1.This thesis studies and analyzes the classification and principle of various Fourier transform algorithms,including discrete Fourier transform algorithm,fast Fourier transform algorithm and hybrid basis algorithm.It also summarizes and com-pares the calculation amount and implementation of the algorithms.2.This thesis introduces the properties of Eisenstein base in detail,and improves the complex multiplication in its number field property to reduce one addition.In this thesis,the classical base replaced by Eisenstein base is introduced into DFT and FFT,and the FFT algorithm of radix 2 and radix 3 based on Eisenstein base is proposed.Combined with the advantages of the new base,the split radix 2/6 and 3/6 fast Fourier transform algorithms based on Eisenstein are designed,and the principles and ideas of the algorithms are elaborated and compared in detail.3.Based on the analysis of Eisenstein base and combined with the advantages and disadvantages of Fourier correlation algorithm,four schemes of FFT with length of n=6m based on split radix 2/6 and 3/6 algorithm are designed.The detailed algo-rithm ideas of the four schemes are elaborated and compared.The results show that the split radix 3/6 algorithm has more advantages than the split radix 2/6 algorithm,and its algorithm complexity can reach 4.10N log N.In comparison with other algorithms,it shows that the proposed scheme needs about 40%less multiplication computation than other algorithms,and the computation time is shorter.