Круговая свертка

Математическая операция

Круговая свертка , также известная как циклическая свертка , представляет собой частный случай периодической свертки , которая представляет собой свертку двух периодических функций, имеющих одинаковый период. Периодическая свертка возникает, например, в контексте преобразования Фурье с дискретным временем (DTFT). В частности, DTFT произведения двух дискретных последовательностей представляет собой периодическую свертку DTFT отдельных последовательностей. И каждое DTFT представляет собой периодическое суммирование непрерывной функции преобразования Фурье (см. DTFT § Определение ). Хотя DTFT обычно являются непрерывными функциями частоты, концепции периодической и круговой свертки также напрямую применимы к дискретным последовательностям данных. В этом контексте круговая свертка играет важную роль в максимизации эффективности определенного вида общей операции фильтрации.

Определения

Периодическая свертка двух T-периодических функций может быть определена как : ${\displaystyle h_{_{T}}(t)}$ ${\displaystyle x_{_{T}}(t)}$

${\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,}$   ^{[1] [2]}

где t _o — произвольный параметр. Альтернативное определение, в терминах обозначения нормальной линейной или апериодической свертки, следует из выражения и как периодических сумм апериодических компонентов и , т.е .: ${\displaystyle h_{_{T}}(t)}$ ${\displaystyle x_{_{T}}(t)}$ ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).}$

Затем :

Обе формы можно назвать периодической сверткой . ^[a] Термин «круговая свертка» ^{[2] [3]} возникает из важного частного случая ограничения ненулевых частей обоих и интервалом . Тогда периодическое суммирование становится периодическим расширением ^[b] , которое также может быть выражено как круговая функция : ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle [0,T].}$

${\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,}$( любое действительное число ) ^[c]

А пределы интегрирования сводятся к длине функции : ${\displaystyle h}$

${\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .}$^{[д] [э]}

Дискретные последовательности

Аналогично, для дискретных последовательностей и параметра N мы можем записать круговую свертку апериодических функций и как : ${\displaystyle h}$ ${\displaystyle x}$

${\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}}$

Эта функция является N -периодической. Он имеет не более N уникальных значений. В особом случае, когда ненулевая степень как x , так и h ≤ N , его можно свести к умножению матриц , где ядром интегрального преобразования является циркулянтная матрица .

Пример

Круговую свертку можно ускорить с помощью алгоритма БПФ, поэтому его часто используют с КИХ-фильтром для эффективного вычисления линейных сверток. Эти графики иллюстрируют, как это возможно. Обратите внимание, что больший размер БПФ (N) предотвратит перекрытие, из-за которого график №6 не будет полностью соответствовать всему графику №3.

На рисунке показан случай, представляющий большой практический интерес. Длительность последовательности x равна N (или меньше), а длительность последовательности h значительно меньше. Тогда многие значения круговой свертки идентичны значениям x∗h , что на самом деле является желаемым результатом, когда последовательность h представляет собой фильтр с конечной импульсной характеристикой (FIR). Кроме того, круговая свертка очень эффективна для вычислений с использованием алгоритма быстрого преобразования Фурье (БПФ) и теоремы круговой свертки .

Существуют также методы работы с последовательностью x , длина которой превышает практическое значение N. Последовательность разбивается на сегменты ( блоки ) и обрабатывается кусочно. Затем отфильтрованные сегменты аккуратно соединяются вместе. Краевые эффекты устраняются путем перекрытия либо входных, либо выходных блоков. Чтобы объяснить и сравнить методы, мы обсудим их как в контексте последовательности h длиной 201, так и размера БПФ  N  = 1024.

Перекрывающиеся входные блоки

Этот метод использует размер блока, равный размеру БПФ (1024). Сначала мы опишем это в терминах нормальной или линейной свертки. Когда для каждого блока выполняется нормальная свертка, на краях блока возникают переходные процессы при запуске и затухании из-за задержки фильтра (200 выборок). Только 824 выходных сигнала свертки не подвержены краевым эффектам. Остальные отбрасываются или просто не вычисляются. Это приведет к появлению пробелов в выводе, если входные блоки смежны. Пробелов можно избежать за счет перекрытия входных блоков на 200 выборок. В каком-то смысле 200 элементов из каждого входного блока «сохраняются» и переносятся в следующий блок. Этот метод называется перекрытием-сохранением ^[4] , хотя метод, который мы описываем далее, требует аналогичного «сохранения» выходных выборок.

Когда БПФ используется для вычисления 824 незатронутых выборок ДПФ, у нас нет возможности не вычислять затронутые выборки, но эффекты переднего и заднего края перекрываются и добавляются из-за круговой свертки. Следовательно, выход обратного БПФ (ОБПФ) по 1024 точкам содержит только 200 выборок краевых эффектов (которые отбрасываются) и 824 незатронутых выборки (которые сохраняются). Чтобы проиллюстрировать это, четвертый кадр рисунка справа изображает блок, который периодически (или «по кругу») расширяется, а пятый кадр изображает отдельные компоненты линейной свертки, выполняемой для всей последовательности. Краевые эффекты — это когда вклады расширенных блоков перекрывают вклады исходного блока. Последний кадр представляет собой составной вывод, а участок, окрашенный в зеленый цвет, представляет собой незатронутую часть.

Перекрывающиеся выходные блоки

Этот метод известен как перекрытие-добавление . ^[4] В нашем примере он использует смежные входные блоки размером 824 и дополняет каждый из них 200 выборками с нулевым значением. Затем он перекрывается и добавляет выходные блоки из 1024 элементов. Ничего не отбрасывается, но 200 значений каждого выходного блока необходимо «сохранить» для добавления к следующему блоку. Оба метода продвигают только 824 выборки за 1024-точечное ОБПФ, но сохранение с перекрытием позволяет избежать начального заполнения нулями и окончательного сложения.

Смотрите также

• Теорема о свертке
• Циркулянтная матрица
• Дискретное преобразование Гильберта

Цитаты страниц

1. МакГиллем и Купер, стр. 172 (4-6)
2. МакГиллем и Купер, стр. 183 (4-51)
3. Оппенгейм и Шафер, стр. 559 (8.59).
4. Оппенгейм и Шафер, стр. 571 (8.114), показано в цифровой форме.
5. МакГиллем и Купер, стр. 171 (4-22), показано в цифровой форме.

Рекомендации

1. Иерухим, Мишель С.; Балабан, Филипп; Шанмуган, К. Сэм (октябрь 2000 г.). Моделирование систем связи: моделирование, методология и методы (2-е изд.). Нью-Йорк: Издательство Kluwer Academic Publishers. стр. 73–74. ISBN 0-30-646267-2.
2. Удаяшанкара, В. (июнь 2010 г.). Цифровая обработка сигналов в реальном времени . Индия: Прентис-Холл. п. 189. ИСБН 978-8-12-034049-7.
3. Праймер, Роланд (июль 1991 г.). Вводная обработка сигналов. Продвинутая серия по электротехнике и вычислительной технике. Том. 6. Тинек, Нью-Джерси: World Scientific Pub Co Inc., стр. 286–289. ISBN 9971-50-919-9.
4. Рабинер, Лоуренс Р.; Голд, Бернард (1975). Теория и применение цифровой обработки сигналов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 63–67. ISBN 0-13-914101-4.

5. Оппенгейм, Алан В .; Шафер, Рональд В .; Бак, Джон Р. (1999). Дискретная обработка сигналов (2-е изд.). Река Аппер-Седл, Нью-Джерси: Прентис-Холл. стр. 548, 571. ISBN. 0-13-754920-2.
6. МакГиллем, Клэр Д.; Купер, Джордж Р. (1984). Непрерывный и дискретный сигнал и системный анализ (2-е изд.). Холт, Райнхарт и Уинстон. ISBN 0-03-061703-0.

дальнейшее чтение

• Оппенгейм, Алан В.; Вильски с С. Хамидом (1998). Сигналы и системы . Пирсон Образование. ISBN 0-13-814757-4.