快速卷积算法

我需要对两个一维信号进行卷积，其中一个平均有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;

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

来源

2011-05-18 Sambatyon

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

来源

2011-05-18 09:57:25

什么是零填充，需要？它确实使信号成为二的幂次？ – Sambatyon 2011-05-18 11:54:37

@Sambatyon：你需要零填充来使内核的大小与信号的大小相同（除非你使用overlap-add或overlap-save方法），你也需要它来将循环卷积转换为线性卷积。 – 2011-05-18 12:14:17

+1，FFT-multiply-IFFT绝对是您的选择。在你的情况下，把两个信号都加到（至少）125500点以避免循环包裹效应。根据您使用/查找哪种FFT实现，您可能需要以2的乘方来获得速度。 – mtrw 2011-05-18 20:51:50

那里有很多快速卷积算法。其中大多数使用FFT例程，例如FFTW。这是因为诸如卷积（在时域中）的操作减少到频域中的（频域表示的）倍增。目前大约需要5分钟的卷积运算（通过您自己的估算）可能需要几秒钟，一旦您使用FFT例程进行卷积运算。此外，如果过滤器长度和信号长度之间存在较大差异，则可能还需要考虑使用重叠保存或重叠添加。更多信息here。如果在Delphi中进行编码并不是首要问题，那么如果仅仅因为FFTW和其他一些库在C/C++中可用（不确定关于scipy或Delphi）的原因，您可能需要使用C/C++。

来源

2011-05-18 10:21:47 Sriram

快速卷积算法

回答

相关问题