Свертка с использованием преобразования Фурье

Свертка функций s(t) и r(t) определяется, как

На практике приходится иметь дело с дискретной сверткой, в которой непрерывные функции заменяются наборами значений в узлах равномерной сетки (обычно берется целочисленная сетка):

Здесь –N и P определяют диапазон, за пределами которого r(t) = 0.

При вычислении свертки с помощью преобразования Фурье используется свойство преобразования Фурье, согласно которому произведение образов функций в частотной области эквивалентно свертке этих функций во временной области.

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

Единственная тонкость в работе алгоритма связана с тем, что в случае дискретного преобразования Фурье (в отличие от непрерывного) происходит свертка двух периодических функций, то есть наши наборы значений задают именно периоды этих функций, а не просто значения на каком-то отдельном участке оси. То есть алгоритм считает, что за точкой x_N идет не ноль, а точкаx₀, и так далее по кругу. Поэтому, чтобы свертка корректно считалась, необходимо приписать к сигналу достаточно длинную последовательность нулей.