1D Быстрая Свертка без БПФ - PullRequest
Новая
       17

1D Быстрая Свертка без БПФ

5 голосов
/ 30 августа 2011

Мне нужна 1D Свертка против 2 больших массивов.Я использую этот код в C #, но это займет много времени для запуска.

Я знаю, я знаю!FFT сверток очень быстро.Но в этом проекте я не могу его использовать.Проект не должен использовать FFT (не спрашивайте почему: /).

Это мой код на C # (кстати, портированный из matlab): 

var result = new double[input.Length + filter.Length - 1];
for (var i = 0; i < input.Length; i++)
{
    for (var j = 0; j < filter.Length; j++)
    {
        result[i + j] += input[i] * filter[j];
    }
}

Итак, кто-нибудь знает какой-нибудь алгоритм быстрой свертки с шириной FFT?

Ответы [ 4 ]

5 голосов
/ 01 сентября 2011

Свертка численно такая же, как полиномиальное умножение с дополнительным циклическим шагом.Таким образом, все алгоритмы умножения полиномов и больших целых могут быть использованы для выполнения свертки.

БПФ - единственный способ получить быстрое O (n log (n)) время выполнения.Но вы все равно можете получить субквадратичное время выполнения, используя подходы «разделяй и властвуй», такие как алгоритм Карацубы .

Алгоритм Карацубы довольно легко реализовать, когда вы поймете, как он работает.Он работает в O (n ^ 1.585) и, вероятно, будет быстрее, чем попытка супероптимизации классического подхода O (n ^ 2).

4 голосов
/ 30 августа 2011

Вы можете уменьшить количество индексированных обращений до result, а также свойства Length: 

int inputLength = filter.Length;
int filterLength = filter.Length;
var result = new double[inputLength + filterLength - 1];
for (int i = resultLength; i >= 0; i--)
{
    double sum = 0;
    // max(i - input.Length + 1,0)
    int n1 = i < inputLength ? 0 : i - inputLength + 1;
    // min(i, filter.Length - 1)
    int n2 = i < filterLength ? i : filterLength - 1;
    for (int j = n1; j <= n2; j++)
    {
        sum += input[i - j] * filter[j];
    }
    result[i] = sum;
}

Если вы еще больше разделите внешний цикл, вы можете избавиться отнекоторые повторяющиеся условия.(Предполагается, что 0 <<code>filterLength ≤ inputLength ≤ resultLength) 

int inputLength = filter.Length;
int filterLength = filter.Length;
int resultLength = inputLength + filterLength - 1;

var result = new double[resultLength];

for (int i = 0; i < filterLength; i++)
{
    double sum = 0;
    for (int j = i; j >= 0; j--)
    {
        sum += input[i - j] * filter[j];
    }
    result[i] = sum;
}
for (int i = filterLength; i < inputLength; i++)
{
    double sum = 0;
    for (int j = filterLength - 1; j >= 0; j--)
    {
        sum += input[i - j] * filter[j];
    }
    result[i] = sum;
}
for (int i = inputLength; i < resultLength; i++)
{
    double sum = 0;
    for (int j = i - inputLength + 1; j < filterLength; j++)
    {
        sum += input[i - j] * filter[j];
    }
    result[i] = sum;
}
0 голосов
/ 14 августа 2013

Вы можете использовать специальный БИХ-фильтр.Затем обработайте это как: 

y(n)= a1*y(n-1)+b1*y(n-2)...+a2*x(n-1)+b2*x(n-2)......

Я думаю, что это быстрее.

0 голосов
/ 30 августа 2011

Вот две возможности, которые могут привести к незначительному ускорению, но вам нужно проверить, чтобы быть уверенным.

  1. Разверните внутренний цикл, чтобы удалить некоторые тесты. Это будет легче, если вы знаете, что длина фильтра всегда будет кратна, если некоторое N
  2. Обратный порядок петель. Do filter.length проходит по всему массиву. Это делает меньшее разыменование во внутреннем цикле, но может иметь худшее поведение при кэшировании.
...