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

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

Определения [ править ]

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

\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,

^[1]^[2]

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

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

Тогда :

\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau =\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau \ \triangleq \ (h*x_{_{T}})(t)=(x*h_{_{T}})(t).

^[A]

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

x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,

( любое действительное число ) ^[c]

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

(h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .

^[d]^[e]

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

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

(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 уникальных значений. В частном случае, когда степень ненулевых обоих х и ч является ≤ N , оно сводится к матричному умножению , где ядро интегрального преобразования является циркулянтом .

Пример [ править ]

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

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

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

Перекрывающиеся блоки ввода [ править ]

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

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

Перекрывающиеся блоки вывода [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

^ Доказательство:
${\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \right]\quad t_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot \underbrace {x_{_{T}}(t-\tau -kT)} _{x_{_{T}}(t-\tau ),{\text{ by periodicity}}}\ d\tau \right]\quad {\text{substituting }}\tau \rightarrow \tau +kT\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\cdot x_{_{T}}(t-\tau )\right]\ d\tau \\&=\int _{t_{o}}^{t_{o}+T}\underbrace {\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\right]} _{\triangleq \ h_{_{T}}(\tau )}\cdot x_{_{T}}(t-\tau )\ d\tau \end{aligned}}$

Цитирование страниц [ править ]

^ McGillem и Купер , стр 172 (4-6)
^ McGillem и Купер , р 183 (4-51)
↑ Оппенгейм и Шафер , стр. 559 (8,59)
^ Оппенгейм и Шафера , р 571 (8,114),показано в цифровом виде
^ McGillem и Купер , стр 171 (4-22), представлены в цифровом виде

Ссылки [ править ]

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

Оппенгейм, Алан В .; Шафер, Рональд В .; Бак, Джон Р. (1999). Дискретно-временная обработка сигналов (2-е изд.). Река Аппер Сэдл, штат Нью-Джерси: Prentice Hall. С. 548 , 571. ISBN 0-13-754920-2. Также доступно на https://d1.amobbs.com/bbs_upload782111/files_24/ourdev_523225.pdf
McGillem, Clare D .; Купер, Джордж Р. (1984). Непрерывный и дискретный сигнал и системный анализ (2-е изд.). Холт, Райнхарт и Уинстон. ISBN 0-03-061703-0.

Дальнейшее чтение [ править ]

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

[3] Доказательство:
${\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \right]\quad t_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(\tau +kT)\cdot \underbrace {x_{_{T}}(t-\tau -kT)} _{x_{_{T}}(t-\tau ),{\text{ by periodicity}}}\ d\tau \right]\quad {\text{substituting }}\tau \rightarrow \tau +kT\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\cdot x_{_{T}}(t-\tau )\right]\ d\tau \\&=\int _{t_{o}}^{t_{o}+T}\underbrace {\left[\sum _{k=-\infty }^{\infty }h(\tau +kT)\right]} _{\triangleq \ h_{_{T}}(\tau )}\cdot x_{_{T}}(t-\tau )\ d\tau \end{aligned}}$

[4] McGillem и Купер , стр 172 (4-6)

[6] McGillem и Купер , р 183 (4-51)

[7] Оппенгейм и Шафер , стр. 559 (8,59)

[8] Оппенгейм и Шафера , р 571 (8,114),показано в цифровом виде

[9] McGillem и Купер , стр 171 (4-22), представлены в цифровом виде

[Jeruchim-1] Jeruchim, Michel C .; Балабан, Филипп; Шанмуган, К. Сэм (октябрь 2000 г.). Моделирование коммуникационных систем: моделирование, методология и методы (2-е изд.). Нью-Йорк: Kluwer Academic Publishers. С. 73–74. ISBN 0-30-646267-2.

[Udayashankara-2] Удайашанкара, В. (июнь 2010 г.). Цифровая обработка сигналов в реальном времени . Индия: Прентис-Холл. п. 189. ISBN. 978-8-12-034049-7.

[Priemer-5] Priemer, Roland (июль 1991). Вводная обработка сигналов . Продвинутая серия по электротехнике и вычислительной технике. 6 . Тинек, Нью-Джерси: World Scientific Pub Co Inc., стр. 286–289. ISBN 9971-50-919-9.

[Rabiner-10] Rabiner, Lawrence R .; Золото, Бернард (1975). Теория и применение цифровой обработки сигналов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. С. 63–67. ISBN 0-13-914101-4.

[1]