我在MATLAB中对其进行了原型设计。但是，我有点困惑。我以为它的工作原理如下（这是从内存中来的，如果我略有错误，请您道歉）。从使用
xcorr函数获得。现在，我完全期望不要获得自动相关的左侧（因为这是右侧的反映，因此无论如何都不需要）。但是，问题是我的右手侧似乎在中点附近反射。实际上，这意味着我得到的数据量约为预期的一半。 #1 楼
当然，pichenettes是正确的。 FFT实现循环卷积，而xcorr（）基于线性卷积。另外，您还需要在频域中平方绝对值。这是一个处理所有零填充，移位和截断的代码片段。%% Cross correlation through a FFT
n = 1024;
x = randn(n,1);
% cross correlation reference
xref = xcorr(x,x);
%FFT method based on zero padding
fx = fft([x; zeros(n,1)]); % zero pad and FFT
x2 = ifft(fx.*conj(fx)); % abs()^2 and IFFT
% circulate to get the peak in the middle and drop one
% excess zero to get to 2*n-1 samples
x2 = [x2(n+2:end); x2(1:n)];
% calculate the error
d = x2-xref; % difference, this is actually zero
fprintf('Max error = %6.2f\n',max(abs(d)));
评论
$ \ begingroup $
哇，好漂亮。使用上述方法，我的音高跟踪器的纯C版本（单线程，无SIMD）在0.8秒内运行，而基于Intel性能基元的版本在0.4秒内运行。太棒了！谢谢
$ \ endgroup $
–戈斯
2012年4月4日在8:04
#2 楼
Matlab xcorr计算$ 2N-1 $ FFT，其中$ N $是输入数据的长度（即，输入用$ N-1 $零填充）。这样可以避免圆度问题。#3 楼
为了进一步详细说明先前的答案，计算长度为$ N $的信号的自相关会导致（采样的）大小为$ 2N-1 $的自相关。好吧，实际上，它应该是无限的，但是$ [-（N-1），N-1] $之外的自相关无论如何都等于$ 0 $。现在，您希望使用离散傅里叶变换（DFT）进行计算，该公式的确是信号DFT平方大小的逆DFT。但是请考虑一下：如果不采取其他方式来计算自相关的DFT，如果您不想以这种方式丢失样本，那么您将得到一个大小为$ 2N-1 $的频谱！因此，该频谱的大小必须为$ 2N-1 $，这就是为什么您需要将时域信号零填充至$ 2N-1 $，计算DFT（在$ 2N-1 $点上） ，然后继续进行。
看到这种情况的另一种方法是分析在$ N $点上计算DFT时发生的情况：这等效于对（连续频率）离散时间傅立叶变换（DTFT）进行下采样。检索应该为$ 2N-1 $大小且具有$ N $大小的频谱采样不足的自相关，因此会导致时间混叠（圆现象是所谓的圆度），这解释了为什么您具有这种对称模式
实际上，Hilmar提供的代码也可以使用，因为只要您将零填充最大为$ N-1 $（在他的情况下，他计算的FT大小为$ N $），您对FT进行了“过度采样”，而您仍然获得了$ 2N-1 $个“有用”的采样（其他采样应为$ 0 $ s）。因此，为了提高效率，只需零填充到$ 2N-1 $，这就是您所需要的（好吧，如果您使用FFT，最好将零填充提高到$ 2N-1 $的下一个2的幂）。
简而言之：您应该这样做（以适应您的编程语言）：
autocorr = ifft( complex( abs(fft(inputData, n=2*N-1))**2, 0 ) )
或者在MATLAB中：
autocorr = ifft(abs(fft(inputData, 2*N-1)).^2)
#4 楼
xcorr函数的期望输出与FFT和IFFT函数的应用不同的主要原因是因为在将这些函数应用于信号时，最终结果是循环卷积的。线性卷积和圆形卷积可以在线性和圆形卷积中找到。可以通过最初对信号进行零填充并截断IFFT的最终输出来解决此问题。
评论
小心。除非数据是确定性的，否则我们通常只能估计自相关序列。自相关估计有两种常见的版本：有偏和无偏。自相关估计的无偏结果在统计上是无偏的。但是，对于高阶滞后，方差可能非常大，如果在矩阵求逆中使用自相关估计，则会导致问题。偏倚的样本表现出统计偏倚，但具有较小的方差（和均方误差）。两者在统计上都是一致的。您上面有一个未归一化的有偏估计。