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

Content

DSPL-2.0 is free digital signal processing algorithms library

Distributed under LGPL v3 license

GitHub project page.

Found a mistake? Select it with the mouse and press ctrl+enter
Введение

Одним из китов современной техники, несомненно, является операция свертки:

(1)
которая позволяет рассчитать сигнал на выходе линейного фильтра с импульсной характеристикой , при входном сигнале . При этом предполагается, что и  — абсолютно интегрируемые на все числовой оси функции [1, стр. 422], для того чтобы интеграл (1) сходился.

Графически прохождение сигнала через фильтр c импульсной характеристикой , в соответствии с (1), показано на рисунке 1

Прохождение сигнала  через фильтр c импульсной характеристикой
Figure 1. Прохождение сигнала через фильтр c импульсной характеристикой

В физически реализуемой системе реакция на входное воздействие не может наступить раньше самого воздействия, тогда импульсная характеристика должна быть равна нулю, при . Учитывая это свойство можно выражение (1) представить в виде:

(2)

Важным свойством операции свертки является коммутативность, т.е. . Действительно если в выражении (1) ввести замену переменной вида , то при этом , верхний предел интегрирования переходит в , а нижний предел переходит в . Тогда получаем:

(3)

В дискретном случае различают два вида сверток: линейную (или апериодическую) и циклическую. Циклическую свертку еще часто называют круговой или периодической.

Линейная свертка дискретных последовательностей

Пусть имеется два дискретных сигнала , , , определенных на всем диапазоне индексов . Тогда линейной сверткой дискретных сигналов является вида:

(4)

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

Для вычисления линейной свертки сигналы и и сдвигают относительно друг друга, все возможные перекрывающиеся отсчеты почленно перемножают и складывают как это представлено на рисунке 2.

Графическое представление линейной свертки
Figure 2. Графическое представление линейной свертки

Приведем пример вычисления линейной свертки. Пусть сигнал содержащий отсчета, а сигнал из отсчетов. Тогда процесс вычисления линейной свертки приведенных сигналов показан на рисунке 3.

Пример вычисления линейной свертки
Figure 3. Пример вычисления линейной свертки

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

Линейная свертка описывает прохождение сигнала , через КИХ-фильтр порядка с импульсной характеристикой , :

(5)

В выражении (5) пределы суммирования соответствуют длительности импульсной характеристики КИХ фильтра, так как при и .

Другим важнейшим прикладным значением линейной свертки является расчет произведения полиномов.

Пусть значения дискретной последовательности , , содержащей значение представляет собой коэффициенты полинома :

(6)
степени , а значения дискретной последовательности ,  — содержит коэффициентов полинома
(7)
степени . Тогда коэффициенты произведения полиномов будут равны линейной свертке . В результате мы получим коэффициент полинома степени .

Циклическая задержка цифровой последовательности

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

Операции по модулю в предположении выполняются по следующему правилам:

(8)

Например , , тогда . Если отрицательно, то . Таким образом операция по модулю для любого целого возвращает значение от до включительно.

Пример циклической задержки сигналов показан на рисунке 4 для и .

Циклическая задержка сигнала  при  и
Figure 4. Циклическая задержка сигнала при и

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

Пусть имеется две последовательности и , одинаковой длительности отсчетов. Циклической сверткой называется последовательность вида:

(9)

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

Графически пример вычисления циклической свертки (9) для показан на рисунке 5.

Пример вычисления циклической свертки
Figure 5. Пример вычисления циклической свертки

Заметим, что вычисление циклической свертки можно представить в матричной форме:

(10)

Можно видеть, что каждый столбец матрицы циклически задержан на один отсчет относительно предыдущего столбца. Особая структура матрицы допускает разработку высокоэффективных алгоритмов расчета циклической свертки [2].

Алгоритм быстрого вычисления циклической свертки на основе БПФ

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

Как мы знаем из свойств дискретного преобразования Фурье, ДПФ циклической свертки равно произведению спектров сворачиваемых сигналов:

(11)
где
(12)
Таким образом перемножив поэлементно спектры ДПФ исходных сигналов, и в взяв обратное дискретное преобразование Фурье, мы получим результат циклической свертки и . Расчет ДПФ целесообразно вести на основе алгоритмов быстрого преобразования Фурье. Тогда окончательно можно записать:
(13)
где и  — операторы прямого и обратного быстрого преобразования Фурье соответственно.

Схематично процесс расчета циклической свертки сигналов и использованием алгоритмов быстрого преобразования Фурье показан на рисунке 6.

Вычисление циклической свертки на основе БПФ
Figure 6. Вычисление циклической свертки на основе БПФ

Заметим, что эффективность алгоритмов БПФ зависит от длины выборки . Наиболее эффективные алгоритмы разработаны для длины равной целой степени двойки (так называемые алгоритмы по основанию два). При этом помимо высокой вычислительной эффективности, алгоритмы БПФ по основанию два отличаются регулярными структурами при аппаратной и программной реализации, а также прекрасно распараллеливаются при мультипроцессорной обработке.

Например для , выполнение матричного умножения (10) наивным методом, без использования ускорений, потребует операции вещественного умножения. Если же мы применим алгоритм вычисления циклической свертки на основе БПФ, то потребуется три БПФ длины (обратное БПФ также считается через прямое), плюс 1024 комплексных умножения для поэлементного перемножения результатов БПФ.

Каждое из трех БПФ требует количество умножений равное:

(14)
тогда получаем, что расчет свертки через БПФ требует комплексных умножений. Для получаем оценку 13312 операции комплексного умножения, что эквивалентно 53248 вещественных умножений, т.е. почти в 20 раз меньше, чем при наивном расчете циклической свертки. Важно заметить, что с ростом ускорение вычислений только растет, потому что заменяем квадратичный рост вычислительных операций произведением линейной и логарифмической функций.

Расчет линейной свертки через циклическую

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

Пусть и  — дискретные последовательности длительности и отсчетов соответственно. Линейная свертка последовательностей и вернет длительности отсчет. Если мы хотим получить как результат циклической свертки, то необходимо дополнить и до длины отсчет, как это показано на рисунке 7.

Добавление нулей для приведения линейной свертки к циклической
Figure 7. Добавление нулей для приведения линейной свертки к циклической

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

(15)

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

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

Например при и , необходимо дополнить и нулями до длины . Однако мы можем дополнить их до длины отсчетов и использовать БПФ по основанию два для расчета циклической свертки. При этом первые 6999 отсчетов результата циклической свертки будут представлять собой линейную свертку при и . Использование алгоритма БПФ для приведет к десятикратному снижению требуемых вещественных умножителей при вычислении линейной свертки при и .

Выводы

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

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

Reference

[1] Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. Москва, Наука, 1968, 496 с.

[2] Winograd S. On Computing the Discrete Fourier Transform. MATHEMATICS OF COMPUTATION, 1978, Vol. 32, Num. 141, pp. 175--189

[3] Оппенгейм А., Шаффер Р. Цифровая обработка сигналов. Москва, Техносфера, 2012. 1048 с. ISBN 978-5-94836-329-5

[4] Сергиенко А.Б. Цифровая обработка сигналов СПб, Питер, 2002.

Page update: 23.06.2020 (23:45:25)