Fast Fourier Transform Cropping Algorithm

When computing DFT,the length of input or output is obviously smaller than the whole length of DFT,we can use pruning algorithm to compute DFT,which reduce the complexity greatly.The DFT pruning algorithm have a great effct on DFT-based frequency domain LMS algorithm,the complexity-reduced computational implementation of the OFDM systems,and the frequency domain processing of SC-FDMA systems.This article mainly introduce the existing pruning algorithm,focus on researching the output pruning of DFT,and propose two algorithms to process the frequency domain signal of SC-FDMA after subcarrier mapping.The main works are summarized as follows:1.This paper begins with summarize all the existing pruning algorithms according to reading all the relevant foreign literature.And introduce the research status?the progress has been made and the application of the scene of all kind of pruning algorithms.We build a framework of the DFT pruning algorithms,which help us continue our research.2.This paper details radix-2 and split-radix FFT algorithms as well as the corresponding pruning algorithms,and general FFT pruning algorithm.We analyze their corresponding signal flow grahs and the computational complexity.3.This paper propose arbitrary continuous output interval pruning split-radix FFT algorithm based on split-radix pruning algorithm,which could obtain the value of a continuous output interval from any successive position quickly.This algorithm could process the SC-FDMA system which the subcarrier mapping use centralized subcarrier mapping perfectly.We analysis of the computational complexity of this algorithm and compared it with the relevant algorithm to show the advantages of our algorithm.4.This paper propose a partial DFT comb spectrum evaluate algorithm which based on transform decomposition algorithm and arbitrary continuous output interval pruning split-radix FFT algorithm.This algorithm could process the SC-FDMA system which the subcarrier mapping use distributed subcarrier mapping.We analysis of the computational complexity and range of applicable parameter of our algorithm.Showing the advantages of the algorithm.