互相关和卷积密切相关。简而言之，要使用 FFT进行卷积，您

1. 零填充输入信号a和b（在每个末尾添加零。零填充应该填充向量，直到它们达到至少N = size(a)+size(b)-1)
2. 对两个信号进行 FFT
3. 将结果相乘（逐元素乘法）
4. 做逆FFT

conv(a, b) = ifft(fft(a_and_zeros) * fft(b_and_zeros))

您需要进行零填充，因为 FFT 方法实际上是循环互相关，这意味着信号在末端环绕。因此，您添加足够的零以消除重叠，以模拟从零到无穷大的信号。

要获得互相关而不是卷积，您需要在进行 FFT 之前对其中一个信号进行时间反转，或者在 FFT 之后对其中一个信号进行复共轭：

• corr(a, b) = ifft(fft(a_and_zeros) * fft(b_and_zeros[reversed]))
• corr(a, b) = ifft(fft(a_and_zeros) * conj(fft(b_and_zeros)))

硬件/软件哪个更容易。对于自相关（信号与其自身的互相关），最好进行复共轭，因为这样您只需要计算一次 FFT。

如果信号是真实的，您可以使用真正的 FFT (RFFT/IRFFT) 并通过只计算一半的频谱来节省一半的计算时间。

您还可以通过填充到 FFT 优化的更大尺寸来节省计算时间（例如 FFTPACK 的5 平滑数， FFTW 的~13 平滑数，或简单硬件实现的 2 的幂）。

下面是 Python 中 FFT 相关与蛮力相关的示例： https ://stackoverflow.com/a/1768140/125507

这将为您提供互相关函数，它是相似度与偏移量的度量。为了获得波相互“排列”的偏移量，相关函数中会有一个峰值：

峰值的 x 值是偏移量，可以是负数也可以是正数。

我只看到这用于查找两个波之间的偏移量。通过在峰值上使用抛物线/二次插值，您可以获得更精确的偏移估计（比样本的分辨率更好） 。

要获得 -1 和 1 之间的相似值（负值表示一个信号随着另一个信号的增加而减小），您需要根据输入的长度、FFT 的长度、您的特定 FFT 实现来缩放幅度缩放等。波浪与自身的自相关将为您提供最大可能匹配的值。

请注意，这仅适用于具有相同形状的波浪。如果它们已经在不同的硬件上采样或添加了一些噪声，但仍然具有相同的形状，则此比较将起作用，但如果波形已通过滤波或相移改变，它们听起来可能相同，但胜出也不相关。

相关性是一种用一个数字表示两个时间序列（在您的情况下为音频样本）的相似性的方法。它是协方差的一种改编，实现如下：

period = 1/sampleFrequency;
covariance=0;

for (iSample = 0; iSample<nSamples; iSample++)
    covariance += (timeSeries_1(iSample)*timeSeries_2(iSample))/period;
    //Dividing by `period` might not even be necessary

相关性是协方差的归一化版本，它是协方差除以两个时间序列的标准差的乘积。当没有相关性（完全不相似）时，相关性将产生 0，而对于完全相关性（完全相似），相关性将产生 1。

您可以想象两个声音样本可能相似但不同步。这就是互相关的用武之地。您计算时间序列之间的相关性，其中一个偏移一个样本：

for (iShift=0; iShift<nSamples; iShift++)
    xcorr(iShift) = corr(timeSeries_1, timeSeries_2_shifted_one_sample);

然后找出系列中的最大值corr，你就完成了。（或者如果你发现足够的相关性就停下来）当然还有更多。您必须实施标准偏差，并且必须进行一些内存管理并实施时间转移的东西。如果所有音频样本的长度都相等，则可以不标准化协方差并继续计算交叉协方差。

与您之前的问题的一个很酷的关系：傅立叶分析只是对交叉协方差的一种改编。您无需移动一个时间序列并计算与另一个信号的协方差，而是计算一个信号与许多具有不同频率的（余）正弦波之间的协方差。这一切都基于相同的原则。

在信号处理中，互相关（MATLAB 中的 xcorr）是一个卷积运算，其中两个序列之一被反转。由于时间反转对应于频域中的复共轭，您可以使用 DFT 计算互相关，如下所示：

R_xy = ifft(fft(x,N) * conj(fft(y,N)))

其中 N = size(x) + size(y) - 1（最好向上取整到 2 的幂）是 DFT 的长度。

DFT 的乘法相当于时间上的循环卷积。将两个向量补零到长度 N 可防止 y 的循环移位分量与 x 重叠，这使得结果与 x 的线性卷积和时间反转的 y 相同。

滞后 1 是 y 的右循环移位，而滞后 -1 是左循环移位。互相关只是所有滞后的点积序列。基于标准 fft 排序，这些将位于可以按如下方式访问的数组中。索引 0 到 size(x)-1 是正滞后。指数 N-size(y)+1 到 N-1 是反向的负滞后。（在 Python 中，可以使用 R_xy[-1] 等负索引方便地访问负滞后。）

您可以将零填充的 x ​​和 y 视为 N 维向量。给定滞后的 x 和 y 的点积是|x|*|y|*cos(theta)。x 和 y 的范数对于圆形位移是恒定的，因此将它们分开只会留下角度 theta 的变化余弦。如果 x 和 y（对于给定的滞后）在 N 空间中是正交的，则相关性为 0（即 theta = 90 度）。如果它们是共线的，则值为 1（正相关）或 -1（负相关，即 theta = 180 度）。这导致归一化为统一的互相关：

R_xy = ifft(fft(x,N) * conj(fft(y,N))) / (norm(x) * norm(y))

这可以通过仅重新计算重叠部分的规范来实现，但是您也可以在时域中进行整个计算。此外，您会看到不同版本的规范化。有时互相关不是被归一化为单位，而是由 M（有偏）归一化，其中 M = max(size(x), size(y)) 或 M-|m| （第 m 滞后的无偏估计）。

为了获得最大的统计显着性，应在计算相关性之前去除平均值（DC 偏差）。这称为交叉协方差（MATLAB 中的 xcov）：

x2 = x - mean(x)
y2 = y - mean(y)
phi_xy = ifft(fft(x2,N) * conj(fft(y2,N))) / (norm(x2) * norm(y2))

如果您使用的是 Matlab，请尝试互相关函数：

c= xcorr(x,y)

这是 Matlab 文档：

xcorr估计随机过程的互相关序列。自相关作为一种特殊情况处理。

...

c = xcorr(x,y)返回长度为 2*N-1 向量的互相关序列，其中x和y是长度N向量 ( N > 1)。如果x和y的长度不同，则将较短的向量补零到较长向量的长度。

相关 http://www.mathworks.com/help/toolbox/signal/ref/eqn1263487323.gif