Research On Fast Fourier Transform Of Sparse Signal

Fourier transform is a widely used signal analysis method in time-frequency domain,which is simple and intuitive.With the rapid development of information technology,the demand for real-time processing of wideband signal is increasing,which makes the sampling rate of signal higher and higher,data size biger and biger,and brings difficulties to real-time processing.However,with the research on structure of signal going more and more deeply,it is found that the signal is sparse in many practical fields.This provides a new idea for real-time processing.The sparse fast Fourier transform is a sublinear time algorithm to computing discrete Fourier transform of spectrum sparse signal,which provides a new way for sparse signal analysis.In this paper,sparse fast Fourier transform is proposed based on the sparse signal representation.Firstly,the purpose,technology and implementation method of time dimensiona lit y reduction process of signal is introduced.After that,it gives an introduction about spectrum reconstruction algorithms of sparse fast Fourier transform.Based on the research of sparse fast Fourier transform,this paper analyzes deeply to the performance of algorithms,and proposes some improved algorithm,and algorithms are realized in project.The key innovations of the paper are summarized as follows:1?For the signal with additive white Gaussian noise,the numerical characteristics of the signal vector containing additive white Gaussian noise are analyzed and deduced in the subsampling domain in this paper,and an improved algorithm for sparse fast Fourier transform is proposed.Considering signal contains noise or approximate sparse,the algorithm detects the existence of the effective frequency point in the bucket according to the numerical characterist ics.The necessary conditions of signal under additive white gaussian noise to reconstruct the full spectrum is verified by the simulation,then the algorithm of noisy signal is improved.Compared with the traditional algorithm of sparse fast Fourier transform,when signal-to-noise ratio < 0dB,the algorithm has smaller estimation error probability,and higher frequency estimation accuracy.2?For spectrum sparse signals with unknown sparsity,a sparisity adaptive sparse fast Fourier transform is proposed in this paper.This algorithm makes full use of the influence of time dimensionality reduction processing to frequency amplitude,and counts predicted frequency points of the signal in the sub-sampling domain by the method of energy detection,then gets approximate over-estimation of signal sparsity by several iteratives.Finally,the algorithm eliminates the redundant frequency points to obtains the ideal signal spectrum.Compared with the traditional sparse fast Fourier transform,this algorithm does not increase the time complexity.And sparse fast Fourier transform with unknown spectrum sparsity is implemented.3?Aiming at the parallelism in the algorithm,the algorithm of sparse fast Fourier transfor m based on CUDA paral el acceleration is implemented in the paper.The algorithm adopts the method of the GPU and CPU heterogeneous coordinate process,optimizes and improves the existing algorithms to parallel execute.Some structures is rewrited from the many times cycle originally to performing independently,and these structures are transferred to the CUDA for parallel computing.With the help of scientific computing hardware structure,the algorithm significantly reduces running time.And arithmetic speed is increased several times,even dozens of times in low signal sparsity.