Вычисление сверток при помощи дискретных преобразований

Согласно теореме о свертке для преобразования Фурье, спектр свертки равен произведению спектров сворачиваемых последовательностей. Поскольку все рассмотренные преобразования обладают аналогичными свойствами, то их можно объединить понятием обобщенного преобразования Фурье. Тогда свертка двух векторов:

, , (12)

(13)

Таким образом, для получения свертки следует выполнить следующие действия:

1) найти преобразования Фурье (обобщенные спектры) сходных последовательностей;

2) вычислить поточечное произведение этих последовательностей;

3) вычислить обратное преобразование Фурье от произведения спектров.

Может показаться, что такой метод вычисления свертки довольно сложен, он тем не менее позволяет во многих случаях сократить объем вычислений. Это происходит вследствие того, что для выполнения БПФ существуют быстрые алгоритмы с числом операций, пропорциональным . Для многих приложений один из векторов (например, ) известен заранее, что позволяет предварительно вычислить произведение спектр . В этом случае вычисление свертки заключается в выполнении двух быстрых преобразований и перемножении чисел. Для БПФ это циклические свертки, для преобразования Адамара вычисляется диадная свертка.

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

Пример 5.3. Вычислить линейную свертку последовательностей и .

Так как и , то , и следует вычислить циклическую свертку последовательностей: ; и ;

Прямые преобразования Фурье последовательностей равны:

.

Поточечное произведение спектров:

.

Обратное преобразование Фурье дает значения свертки

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

Существует два метода секционирования - метод перекрытия с суммированием и метод перекрытия с накоплением. Предположим, что более длинной является последовательность . Она разбивается на блоки по отсчетов. Последовательность имеет длину .Линейная свертка каждого из блоков последовательности с последовательностью имеет размер и перекрывается со сверткой следующего блока в отсчетах. Поэтому на участке перекрытия их отсчеты следует сложить. Таким образом, на каждые входных отсчетов вычисляется -точечная циклическая свертка и выполняется - сложений.

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

Если длина блока увеличивается, то общее количество блоков уменьшается. При этом число преобразований становится меньше, но время выполнения каждого преобразования возрастает. С другой стороны, сокращение длины блока потребует большего числа коротких преобразований, поэтому существует оптимум между длиной блока и длиной короткой последовательности .

Поиск по сайту: