Линейная и циклическая свертка

Содержание

Введение
Одним из китов радиотехники, несомненно, является операция свертки:
(1)
Свертка позволяет рассчитать сигнал на выходе линейного фильтра с импульсной характеристикой , при входном сигнале .
В дискретном случае различают два вида сверток: линейную (или апериодическую) и циклическую. Циклическую свертку еще часто называют круговой или периодической.

Линейная свертка
Рассмотрим линейную свертку. Пусть имеется два дискретных сигнала ,, и ,. В общем случае длины этих сигналов и могут отличаться. Линейной сверткой сигналов и называется дискретный сигнал вида:
(2)
Для вычисления линейной свертки сигналы и сдвигают относительно друг друга почленно перемножают и складывают. При этом предполагается, что при и , а также при и
Графическое представление линейной свертки представлено на рисунке 1.


Рисунок 1: Графическое представление линейной свертки

Отсчеты сигнала сдвигаются относительно отсчетов последовательности все возможные перекрывающиеся отсчеты почленно перемножаются и складываются.
На рисунке 2 приведен пример вычисления линейной свертки двух сигналов длиной 4 отсчета и длиной 3 отсчета.


Рисунок 2: Пример вычисления линейной свертки.

Необходимо отметить, что сигнал при вычислении свертки отражается слева-направо, поскольку самый первый отсчет (самый ранний по времени) и обрабатываться он также должен первым.

Циклическая свертка
Рассмотрим теперь циклическую свертку. В случае циклической свертки предполагается, что дискретные сигналы и - периодические с одинаковым периодом отсчетов. Тогда круговой сверткой сигналов и называется сигнал вида:
(3)
Результат циклической свертки также имеет длину отсчетов.
Рассмотрим циклическую свертку на примере двух сигналов и . Графически вычисление циклической свертки представлено на рисунке 3.


Рисунок 3: Вычисление циклической свертки

Красной линией отмечены границы периодов повторения сигнала . Заметим, что в силу периодичности сигналов .
Вычислим свертку пошагово:
(4)
Теперь рассчитаем :
(5)
Аналогично можно рассчитать и .
Используя циклическую свертку можно рассчитать линейную свертку двух сигналов. Для этого необходимо каждый из сигналов и длительностью и отсчетов соответственно дополнить нулями до длины .
Приведем пример вычисления линейной свертки через циклическую для длиной 4 отсчета и длиной 3 отсчета (этот пример был рассмотрен выше).
Дополним нулями и , так чтобы в каждой последовательности было по 6 отсчетов.
Вычислим циклическую свертку как это показано на рисунке 4.


Рисунок 4: Вычисление линейной свертки через циклическую <

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

Алгоритм быстрого вычисления свертки на основе БПФ
На первый взгляд может показаться, что вычисление линейной свертки через циклическую не имеет смысла, так как не сокращает вычисления. Действительно для вычисления линейной свертки требовалось умножений, и – длины сворачиваемых сигналов, а при вычислении линейной свертки через циклическую умножений и сложений. Однако рассмотрим дискретное преобразование Фурье от циклической свертки:
(6)
Подставив выражение для циклической свертки получим:
(7)
Поменяем местами операции суммирования:
(8)
Представим множитель в виде:
(9)
Подставив (9) в (8) получим:
(10)
Таким образом, спектр циклической свертки есть произведение спектров сворачиваемых сигналов, и для ее вычисления может быть применен алгоритм быстрого преобразования Фурье (БПФ). Таким образом схема вычисления циклической свертки может быть представлена на рисунке 5:


Рисунок 5: Вычисление циклической свертки с применением БПФ

Поскольку эффективные алгоритмы БПФ существуют не для всех длин , то можно предложить следующий метод вычисления циклической свертки. Исходные последовательности и , можно дополнить нулями до длины , поскольку для длин равных целой степени двойки разработаны эффективные алгоритмы БПФ, после этого применяем схему вычисления свертки, представленную на рисунке 5. На выходе получим , , из которого надо взять только первые отсчетов.
Аналогично можно поступить и при расчете линейной свертки через циклическую.
Рассмотрим пример. Пусть , а . Прямое вычисление линейной свертки потребует (12 миллионов) операций умножения и сложения.
Дополним каждую из последовательностей до 8192 отсчетов нулями и применим алгоритм БПФ с прореживание по времени, тогда на вычисление одного БПФ потребуется операций комплексного умножения или 428000 операций действительного умножения. Таких блоков БПФ будет всего 3 штуки, плюс надо учесть 8192 комплексных умножений спектров, итого , что почти в 7.5 раз ниже чем если бы мы считали линейную свертку в лоб.

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

Любые вопросы и пожелания вы можете оставить в гостевой книге, на форуме, или прислать по электронной почте admin@dsplib.ru


Система Orphus
Любое копирование материалов сайта без разрешения автора запрещено.
Разработка и дизайн Бахурин Сергей.