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

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

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

Определения

Периодическая свертка двух 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]}

где - произвольный параметр. Альтернативное определение, в терминах записи нормальной линейной или апериодической свертки, следует из выражения и как периодических сумм апериодических компонентов и , то есть : ${\displaystyle 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 , она сводится к умножению матриц , где ядром интегрального преобразования является циркулянтная матрица .

Пример

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

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

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

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

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

Когда для вычисления 824 незатронутых выборок DFT используется FFT, у нас нет возможности не вычислять затронутые выборки, но передние и задние краевые эффекты перекрываются и добавляются из-за круговой свертки. Следовательно, 1024-точечный обратный FFT (IFFT) вывод содержит только 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. Udayashankara, V. (июнь 2010 г.). Цифровая обработка сигналов в реальном времени . Индия: Prentice-Hall. стр. 189. ISBN 978-8-12-034049-7.
3. Праймер, Роланд (июль 1991 г.). Введение в обработку сигналов. Продвинутая серия по электротехнике и вычислительной технике. Том 6. Тинек, Нью-Джерси: World Scientific Pub Co Inc., стр. 286–289. ISBN 9971-50-919-9.
4. Rabiner, Lawrence R.; Gold, Bernard (1975). Теория и применение цифровой обработки сигналов . Englewood Cliffs, NJ: Prentice-Hall. стр. 63–67. ISBN 0-13-914101-4.

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

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

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