4.8. Ускоренный алгоритм свертки сигналов

В заключение этой главы приведем алгоритм ускоренной свертки сигналов, не нуждающийся в применении ДПФ. Он описан в работах [95, 103, 132], и идея его состоит в том, чтобы ценой некоторого увеличения количества операций сложения при вычислении свертки сократить количество операций умножения, требующих обычно больших затрат машинного времени.

Запишем формулу дискретной свертки (3.16) следующим образом:

и будем считать, что заданы все необходимые отсчетов Пусть также N — четное число; если N — нечетное, то будем рассматривать сумму максимального четного числа слагаемых.

Вычислим сначала попарные произведений внутри последовательностей

Тогда, как легко проверить,

Таким образом, вычисление свертки последовательностей сводится к вычислению свертки вдвое более коротких последовательностей, составленных из попарных сумм элементов исходных последовательностей. Что касается добавочных членов в (4.117) и 5, в (4.118), то не зависит от к и ее достаточно вычислить один раз для всех элементов свертки, может вычисляться рекуррентно для четных и нечетных к. Действительно, при к четном

Точно такая же формула справедлива для нечетных к.

Оценим количество операций, требуемых для вычисления К значений свертки . Для вычислений К сумм (4.119) требуется выполнить операций сложения и операций умножения. Вычисление

требует операций сложения и операций умножения. Вычисление четных значений требует операций (Уложения и операций умножения для плюс два сложения и два умножения на каждое из остальных т. е. операций сложения и операций умножения. Итого общее количество сложений

и общее количество умножений

Отсюда видно, что по сравнению с прямым вычислением (4.116), требующим операций сложения и операций умножения, описанный алгоритм требует примерно вдвое меньше умножений и в полтора раза больше сложений. По оценке [103] он оказывается в вычислительном отношении эффективнее, чем использование БПФ при

Эта оценка, конечно, является грубой, и граница применимости описанного алгоритма определяется соотношением времени сложения и времени умножения конкретного процессора.

Описанный прием в принципе можно использовать и при вычислении двумерной свертки:

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