还在按部就班的算自相关？FFT让你体验飞一般的感觉！

本文同步发布在我的个人博客，希望大家可以到我的个人博客玩耍。http://www.weekreport.cn/archives/212

自相关函数

自相关（Autocorrelation），也叫序列相关，是一个信号于其自身在不同时间点的互相关。非正式地来说，它就是两次观察之间的相似度对它们之间的时间差的函数。它是找出重复模式（如被噪声掩盖的周期信号），或识别隐含在信号谐波频率中消失的基频的数学工具。它常用于信号处理中，用来分析函数或一系列值，如时域信号。–百度百科

自相关函数在随机信号处理领域非常重要，一般用下式计算一个随机信号的自相关。
$$R(s,t)=E[X(s)x(t)]$$
如果该随机信号是均方遍历的，则可以使用一个足够长样本函数的时间自相关去估计真实的自相关函数。

如果m和N都比较大，上式运算量很大，如何减小运算量，实现自相关函数的快速计算？

使用$FFT$算法实现自相关函数的快速计算

对时间自相关函数两边求傅立叶变换并整理得下式：

$U_n(w)$是样本信号的傅立叶变换，上式说明$\hat{r}(m)$和$u_n(n)$的功率谱是一对傅里叶变换，既然是傅立叶变换，自然可以用$FFT$算法实现快速计算。

算法步骤

1. 对$u_n\left(n\right)$补$N$个0，得$u_{2n}\left(n\right)$，对$u_{2n}<$