Циклическая свертка

Циклическая свертка определяется для периодических последовательностей длины N выражением

(9)

В силу периодичности последовательностей номера отсчетов берутся по модулю N, поэтому s(-n) = s(N-n), h(-n) = h(N-n). Матричная запись циклической свертки имеет вид:

При вычислениях по модулю N из свойств сравнений следует, что N ≡ 0, поэтому в полиномиальном представлении z^N = 1 циклическая свертка может рассматриваться как произведение двух полиномов по модулю полинома z^N = 1:

(10)

Обозначим

Произведение по модулю z^N - 1 просто означает, что

(11)

Таким образом, если положить равными нулю значения w(N), w(N-1), w(2N-2), то линейную свертку можно вычислить через циклическую.

Пример 5.2. Для трехточечной циклической свертки с учетом равенства z³ = 1 получим

Используя результаты примера 5.1 и соотношения (11) , запишем коэффициенты циклической свертки:

Эти равенства можно получить и с помощью матричного соотношения.

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

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

,, (12)

(13)

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

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

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

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

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

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

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

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

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

.

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

.

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

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

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

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

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