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

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

自相关函数

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

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

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

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

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

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

算法步骤

1. 对$u_{n}\left ( n \right )$un​(n)补$N$N个0，得$u_{2n}\left ( n \right )$u2n​(n)，对$u_{2n}\left ( n \right)$u2n​(n)做快速傅立叶变换得$U_{2n}\left ( k \right )\quad\ k=0,1,2...2N-1$U2n​(k) k=0,1,2...2N−1。
2. 求$U_{2n}\left ( k \right )$U2n​(k)的幅度平方，然后除以$N$N,得到$\frac{1}{N}\left | U_{2n}\left ( k \right ) \right |^{2}$N1​∣U2n​(k)∣2。
3. 对$\frac{1}{N}\left | U_{2n}\left ( k \right ) \right |^{2}$N1​∣U2n​(k)∣2进行IFFT，得到$\hat{r_{0}}(m)\quad$r0​^​(m)$m=0,1,...,2N-1$m=0,1,...,2N−1，$\hat{r_{0}}(m)$r0​^​(m)与$\hat{r}(m)$r^(m)的关系为:$\hat{r}\left ( m \right )= \left\{\begin{matrix} \hat{r_{0}}\left ( m \right )& 0\leq m\leq N-1 \\ \hat{r_{0}}\left ( m + 2N \right )& -N+1\leq m\leq -1 \end{matrix}\right.$r^(m)={r0​^​(m)r0​^​(m+2N)​0≤m≤N−1−N+1≤m≤−1​

使用$Matlab$Matlab实现上述算法

仿真条件

随机信号$u\left ( n \right )$u(n)的观测样本由一段零均值、方差为$\sigma^{2}$σ2的复高斯白噪声序列$v\left ( n \right )$v(n)叠加3个归一化频率分别为$f_{1}=0.15,f_{2}=0.17,f_{3}=0.26$f1​=0.15,f2​=0.17,f3​=0.26，信噪比分别为$30dB,30dB,27dB$30dB,30dB,27dB的复正弦信号构成。

仿真结果

令信号观测样本长度$N=32$N=32，基于$FFT$FFT的自相关函数快速算法估计出的自相关函数$\hat{r_0}\left( m \right)$r0​^​(m),并与由信号观测样本直接计算得到的自相关函数进行比较，结果如下，$r_1$r1​代表基于$FFT$FFT的自相关函数快速算法估计出的自相关函数，$r_0$r0​代表由信号观测样本直接计算得到的自相关函数，可以看到，二者结果是一样的。

既然是快速算法，它到底比利用样本函数直接计算自相关函数快了多少？

利用$Matlab$Matlab中的$tic,toc$tic,toc函数，得到两种方法的运行时间，可以看到基于$FFT$FFT的自相关函数快速算法要比由信号观测样本直接计算自相关函数快一个数量级左右，这是很大的提升，特别是在样本点数$N$N很大时。

感兴趣的同学可以关注公众号 “工科南” 并回复 “$fftcorr$fftcorr” 获取相关的$Matlab$Matlab代码。