快速卷积算法 [英] Fast convolution algorithm

问题描述

我需要卷积两个一维信号，一个平均有500个点（这是一个汉宁窗口函数），另一个是125000.每运行一次，我需要应用三次卷积运算。我已经根据scipy的文档执行了一个实现。你可以在这里看到代码（Delphi代码）：

  function Convolve（const signal_1，signal_2：ExtArray） ：ExtArray; 
 var 
 capital_k：整数; 
 capital_m：整数; 
最小：整数; 
 y：ExtArray; 
 n：整数; 
 k：整数; 
 lower，upper：Integer; 
 begin 
 capital_k：=长度（signal_1）+长度（signal_2） -  1; 
 capital_m：= Math.Max（Length（signal_1），Length（signal_2））; 
最小：= 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））或（n-k> = Length（signal_2））then 
继续; 
 y [n]：= y [n] + signal_1 [k] * signal_2 [n-k]; 
结束
结束
结果：= Slice（y，
楼层（最小/ 2） -  1，
楼层（最小/ 2） -  1 + capital_m） 
结束
  

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

解决方案

快速卷积可以使用FFT进行。取两个输入信号的FFT（适当的零填充），在频域中乘法，然后进行逆FFT。对于大N（通常N> 100），这比直接方法更快。

I need to convolve two one dimensional signals, one has on average 500 points (This one is a Hanning window function), the other 125000. Per run, I need to apply three times the convolution operation. I already have an implementation running based on the documentation of scipy. You can see the code here if you want to (Delphi code ahead):

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;

The problem is, this implementation is too slow. The whole procedure takes about five minutes. I was wondering if I can find a faster way of computing that.

解决方案

Fast convolution can be carried out using FFTs. Take the FFT of both input signals (with appropriate zero padding), multiply in the frequency domain, then do an inverse FFT. For large N (typically N > 100) this is faster than the direct method.

这篇关于快速卷积算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！