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

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

Определения

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

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

где $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).$

( Уравнение 1 )

показывать Вывод уравнения 1

${\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(u+kT)\cdot \underbrace {x_{_{T}}(t-u-kT)} _{x_{_{T}}(t-u),{\text{ by periodicity}}}\ du\right]\quad {\text{substituting }}u\triangleq \tau -kT\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(u+kT)\cdot x_{_{T}}(t-u)\right]\ du\\&=\int _{t_{o}}^{t_{o}+T}\underbrace {\left[\sum _{k=-\infty }^{\infty }h(u+kT)\right]} _{\triangleq \ h_{_{T}}(u)}\cdot x_{_{T}}(t-u)\ du\\&=\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \quad {\text{substituting }}\tau \triangleq u\end{aligned}}$

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

$x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,$ ( любое вещественное число )

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

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

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

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

Пример

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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