Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Свертка

Дискретной сверткой функций f(t) и g(t), определенных на множестве целых чисел Z, называется следующая операция:

Круговой дискретной сверткой не-периодической функции f с периодической функцией g называется следующая операция:

Дискретная свертка имеет много различных применений – умножение полиномов, арифметика произвольной точности, обработка сигналов. Круговая свертка не коммутативна – одна из функций является периодическим сигналом, а другая – не-периодическим ответом на сигнал. Операнды обычной свертки тоже часто имеют различный смысл, но сама операция коммутативна – результат свертки не меняется от перестановки функций f и g.

Представление данных

Областью определения функций f и g является всё множество целых чисел, но на практике мы имеем дело с данными ограниченной длины. Удобнее всего, когда функции f и g отличны от ноля только для неотрицательных t. Вычислительные подпрограммы пакета ALGLIB решают именно эту задачу – свертку двух функций, отличных от ноля только при неотрицательных значениях аргумента. Это позволяет воспользоваться простым соответствием между аргументом функции и индексом массива, в котором хранятся её значения: f(t=i) = f_array[i], 0 ≤ i < M и g(t=i) = g_array[i], 0 ≤ i < N (аналогичное соглашение применяется к результату работы подпрограммы).

В случае, если функции f и g отличны от ноля и при положительных, и при отрицательных значениях аргумента, можно воспользоваться тем, что при сдвиге одного из аргументов свертки результат также подвергается сдвигу в том же направлении на ту же величину (при сдвиге двух аргументов – на сумму отдельных смещений). Просто сдвиньте f и g вправо, пока все ненулевые значения не окажутся по одну сторону от ноля, вызовите подпрограмму для свертки, после чего сдвиньте обратно результат.

Реализация свертки в ALGLIB

Здесь мы для простоты будет считать, что N ≥ M, т.е. второй операнд длиннее первого, хотя быстродействие алгоритма не зависит от порядка, в котором передаются операнды. Широко известно, что свертка может быть вычислена с использованием быстрого преобразования Фурье за время O(N·log(N)). Вместе с тем, прямолинейное использование преобразования Фурье не всегда является оптимальным решением – в случае, если один из операндов короче другого, можно значительно ускорить вычисления, использовав другие алгоритмы. В зависимости от длин операндов, пакет ALGLIB может использовать следующие алгоритмы:

Для вычисления свертки используется входящий в состав ALGLIB алгоритм БПФ. Подпрограмма свертки автоматически подбирает длину операндов, по необходимости дополняя их нолями, чтобы достичь оптимального быстродействия (быстродействие БПФ сильно зависит от разложения длины операнда на простые множители). Таким образом, пользователям ALGLIB не надо беспокоиться об оптимальной длине операндов.

Manual entries

C++ conv subpackage   
C# conv subpackage   

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.