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

Введение Линейная свертка дискретных последовательностей Циклическая задержка цифровой последовательности Циклическая свертка Алгоритм быстрого вычисления циклической свертки на основе БПФ Расчет линейной свертки через циклическую Выводы Список литературы

DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов Распространяется под лицензией LGPL v3 Страница проекта на SourceForge

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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