Fast Demodulation Algorithm Of Underwater Acoustic Based On The Sparse Fourier Transform

The Sparse Fourier Transform is a recent algorithm for Discrete Fourier Transforms onsparse signals developed by four researchers at MIT in2012. By leveraging the sparsity ofthe frequency domain, the SFT algorithm computes the full spectrum with high probabilityin sub-linear time, outperforms the traditional FFT algorithm for almost10to100times.Consequently, it has the potential to deal with real-time processing of big data in signalprocessing domain, such as radar, sonar et al. In this Master Thesis, the theory of SFT willbe comprehensively introduced, analyzed and evaluated, then it will be implemented to aexisted underwater acoustic communication system, several optimizations are proposed bothon fast synchronization and fast demodulation. The main work are as follows:Firstly, through a sufficient survey of the recent algorithms, this paper summarizes anddescribes the theoretical framework of SFT algorithm, introduces the error guarantees ofrecovery, reviews the key technical problems such as random spectrum permutation,subsampled FFT and the design of flat window function filter. Combining with the latesttheoretical achievements of MIT, sums up four different kinds of reconstruction means, andverifies each of them in MATLAB simulation platform.Secondly, faster algorithm based on SFT for synchronization in underwater acousticcommunication was studied. Signal synchronization is ultimately the cross-correlationoperation between the local sequence and the received signal, and fast correlation is alwaysdone utilizing the FFT. Since the output of the correlation process has a single major spike,it’s sparse indeed, this paper aimed to reduce the cost of the process by SFT algorithm,proposed an aliasing-subsampling-aliasing optimization algorithm, reduced the computation-al complexity from O(N log2N) to O(N).Third, faster algorithm based on SFT for demodulation of MFSK signals in underwateracoustic communication was studied. While using FFT for demodulation of MFSK signalsor multi-carrier MFSK signals, the frequency domain has only a few number of non-zerocoefficients, and they come from a finite number of determined coordinate position. On thisbasis, utilizing two kinds of reconstruction method in SFT algorithm, aliasing-basedcongruential method and hash mapping, two faster demodulation algorithm for MFSK signals were designed, through MATLAB simulation experiments, analyzed the algorithmperformance impact on the parameters and signal to noise ratio.The research achievements of this paper, in terms of theory, we elaborate the sparseFourier transform theory systematically. In terms of engineering, we optimize the synchroni-zation and demodulation process in underwater acoustic communication utilizing SFTalgorithm, effectively reduce the computational complexity, thus, provide a strong technicalsupport for the real-time processing of underwater acoustic communication.