基于FFT实现循环相关的代码正确性及参数顺序问题咨询

你使用的循环卷积实现代码：

def fft_convolution(a, b):
    return np.fft.irfft(np.fft.rfft(a) * np.fft.rfft(b))

你编写的循环相关实现代码：

def fft_correlation(a, b):
    return np.fft.irfft(np.fft.rfft(b) * np.conjugate(np.fft.rfft(a)))

实现正确性判定 #

这段循环相关代码是正确的。只要输入的两个序列a、b长度一致，计算出的N点循环互相关结果和按数学定义逐点计算的结果完全对齐，你多轮测试能正常运行不是巧合。唯一需要注意的边界情况是：如果两个输入长度不相等，要先将二者补零到相同长度再做FFT运算，否则要么触发维度报错，要么得到不符合预期的结果。

参数顺序交换的原因 #

很多人刚接触FFT实现相关的时候都会在顺序上踩坑，核心逻辑可以拆成两点说：

• 首先要明确卷积和互相关的定义差异。N点循环卷积的计算是把其中一个序列反序之后循环移位，和另一个序列逐点乘加；而循环互相关不需要反序，直接滑动其中一个序列做乘加，同时对固定的那个序列取共轭。二者滑动方向相反，这也是为什么卷积的FFT实现不需要共轭，而相关必须有一个FFT结果取共轭——根据FFT性质，频域取共轭正好对应时域序列反序加共轭，刚好补上了卷积和相关之间的差异。
• 其次，互相关运算不满足交换律，这和卷积完全不同。卷积里a和b交换顺序结果不变，但互相关里顺序换了结果就变了。你当前的写法rfft(b) * np.conjugate(rfft(a))，对应的语义是把b作为滑动模板，在固定序列a上做循环移位匹配，结果第n位就是b循环移n位后和a的逐点乘积和，完全符合绝大多数场景下调用corr(a, b)的参数语义。如果把共轭项的顺序写反，变成rfft(a) * np.conjugate(rfft(b))，得到的就是把a当模板在b上滑动的匹配结果，相当于你需要的结果做了一次循环反序，和传参的预期不匹配。

内容的提问来源于stack exchange，提问作者sten