delphi - 快速卷积算法

Question

我需要对两个一维信号进行卷积，一个平均有 500 个点(这个是汉宁窗函数)，另一个有 125000 个点。每次运行，我需要应用三倍的卷积运算。我已经有一个基于 scipy 文档运行的实现。如果您愿意，您可以在此处查看代码(前面是 Delphi 代码):

function Convolve(const signal_1, signal_2 : ExtArray) : ExtArray;
var
  capital_k : Integer;
  capital_m : Integer;
  smallest : Integer;
  y : ExtArray;
  n : Integer;
  k : Integer;
  lower, upper : Integer;
begin
  capital_k := Length(signal_1) + Length(signal_2) - 1;
  capital_m := Math.Max(Length(signal_1), Length(signal_2));
  smallest := Math.Min(Length(signal_1), Length(signal_2));
  SetLength(y, capital_k);
  for n := 0 to Length(y) - 1 do begin
    y[n] := 0;
    lower := Math.Max(n - capital_m, 0);
    upper := Math.Min(n, capital_k);
    for k := lower to upper do begin
      if (k >= Length(signal_1)) or (n - k >= Length(signal_2)) then
        Continue;
      y[n] := y[n] + signal_1[k] * signal_2[n - k];
    end;
  end;
  Result := Slice(y,
                  Floor(smallest / 2) - 1,
                  Floor(smallest / 2) - 1 + capital_m);
end;

问题是，这个实现太慢了。整个过程大约需要五分钟。我想知道是否可以找到一种更快的计算方法。

Answer 1

Fast convolution可以使用 FFT 进行。对两个输入信号进行 FFT(使用适当的零填充)，在频域中相乘，然后进行逆 FFT。对于较大的 N(通常 N > 100)，这比直接方法更快。