Опубликовано: в сборнике Международной конференции "Цифровая обработка сигналов и её применение", март, 2009Дискретная свертка является одной из часто используемых операций при цифровой обработке сигналов. Она применяется в цифровых фильтрах, при вычислении корреляции и других операциях.
Число операций для нахождения свертки прямым методом, т.е. по формуле из определения свертки, пропорционально произведению числа отсчетов в функциях. Для ее вычисления при большом числе отсчетов разработаны специальные быстрые алгоритмы, выполняющих эту функцию за меньшее количество вычислительных операций.
Во многих задачах цифровой обработки сигналов требуется найти свертку функций, в одной из которых количество отсчетов во много раз больше, чем в другой. Например, такую операцию требуется выполнять при цифровой фильтрации, когда одной из функций является фильтруемый сигнал, а другой – коэффициенты фильтра.
Вычисление такой свертки требует целый набор алгоритмов, состоящий из методов секционирования сигнала, вычисления линейной свертки через циклическую и быстрого метода вычисления циклической свертки. Наиболее часто для этого применяются методы перекрытия с накоплением (overlap-save) и перекрытия с суммированием (overlap-add) с использованием быстрого преобразования Фурье (БПФ, FFT) для вычисления циклической свертки. Эти методы хорошо работают при относительно большом числе отсчетов, однако при малом их числе проигрывают прямому методу.
В докладе рассматривается способ повышения эффективности метода перекрытия с накоплением, позволяющий уменьшить число необходимых вычислений при любом числе точек.
