有限长序列线性相关的快速算法研究

线性相关在信号处理中具有十分重要的作用，因此研究线性相关的快速运算具有重要意义。本文根据有限长序列的线性相关的定义，首先给出了基于快速傅立叶变换（Fast Fourier Transform，FFT）直接计算线性相关的快速算法，记为直接FFT算法；其次针对长度相差较大的有限长序列，提出了一种分段求和FFT算法，相比于直接FFT法，具有更小的运算量。仿真结果表明，相比于根据定义直接计算线性相关，直接FFT算法显著减少了运算量，且序列长度越长，改善效果越明显；若参与线性相关的两个序列长度相差较大，则相比于直接FFT算法，分段求和FFT算法具有更小的运算量，且序列长度差距越大，改善效果越好。

Fast Algorithm for Linear Correlation of Finite Length Sequences

Linear correlation plays an important role in signal processing, which indicates great significance to study the fast computation of linear correlation. In this paper, according to the definition of linear correlation for finite length sequence, an algorithm based on fast Fourier transform (FFT) for direct calculation of linear correlation is given, which is named direct FFT algorithm. To reduce the computational complexity, a piecewise summation FFT algorithm is proposed for linear correlation between two finite length sequences with large length differences. Simulation results show that compared with the linear correlation directly calculated according to the definition, the direct FFT algorithm significantly reduces the computational complexity, which becomes more apparent when the length of both sequences is longer. If the length of the two sequences involved in the linear correlation is quite different, the piecewise summation FFT algorithm has lower computation than the direct FFT algorithm, which becomes much clearer with the larger difference between the lengths of two sequences.