Вычисление свертки с помощью ДПФ и ОДПФ

В формуле свертки для воздействия длины и ИХ длины :

,

где — длина линейной свертки:

С целью сокращения количества арифметических операций свертку вычисляют с использованием ДПФ и ОДПФ по следующему алгоритму:

1. ИХ и воздействие дополняют нулями до длины .

2. Переходят к круговой свертке для последовательностей одинаковых длин :

.

3. Вычисляют ДПФ реакции длины , равное произведению ДПФ:

, .

4. Вычисляют реакцию длины с помощью ОДПФ и ограничивают до длины воздействия .