Теорема о свертке

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

Функции непрерывной переменной

Рассмотрим две функции $u(x)$ и $v(x)$ с преобразованиями Фурье $U$ и $V$:

${\begin{aligned}U(f)&\triangleq {\mathcal {F}}\{u\}(f)=\int _{-\infty }^{\infty }u(x)e^{-i2\pi fx}\,dx,\quad f\in \mathbb {R} \\V(f)&\triangleq {\mathcal {F}}\{v\}(f)=\int _{-\infty }^{\infty }v(x)e^{-i2\pi fx}\,dx,\quad f\in \mathbb {R} \end{aligned}}$

где ${\mathcal {F}}$ обозначает преобразования Фурье оператор . Преобразование может быть нормализовано другими способами, и в этом случае постоянные коэффициенты масштабирования (обычно $2\pi$ или ${\sqrt {2\pi }}$) появится в теореме о свертке ниже. Свертка $u$ и $v$ определяется:

$r(x)=\{u*v\}(x)\triangleq \int _{-\infty }^{\infty }u(\tau )v(x-\tau )\,d\tau =\int _{-\infty }^{\infty }u(x-\tau )v(\tau )\,d\tau .$

В этом контексте звездочка обозначает свертку вместо стандартного умножения. Символ произведения тензорного $\otimes$ иногда вместо этого используется.

Теорема свертки утверждает, что :

$R(f)\triangleq {\mathcal {F}}\{r\}(f)=U(f)V(f).\quad f\in \mathbb {R}$    

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

Применение обратного преобразования Фурье ${\mathcal {F}}^{-1},$ дает следствие :

Теорема о свертке

$r(x)=\{u*v\}(x)={\mathcal {F}}^{-1}\{U\cdot V\},\quad \scriptstyle {\text{where }}\displaystyle \cdot \scriptstyle {\text{ denotes point-wise multiplication}}$    

( уравнение 1б )

Теорема также обычно применима к многомерным функциям.

show Многомерный вывод уравнения 1

Consider functions $u,v$ in Lp-space $L^{1}(\mathbb {R} ^{n}),$ with Fourier transforms $U,V$: ${\begin{aligned}U(f)&\triangleq {\mathcal {F}}\{u\}(f)=\int _{\mathbb {R} ^{n}}u(x)e^{-i2\pi f\cdot x}\,dx,\quad f\in \mathbb {R} ^{n}\\V(f)&\triangleq {\mathcal {F}}\{v\}(f)=\int _{\mathbb {R} ^{n}}v(x)e^{-i2\pi f\cdot x}\,dx,\end{aligned}}$ where $f\cdot x$ indicates the inner product of $\mathbb {R} ^{n}$:   $f\cdot x=\sum _{j=1}^{n}{f}_{j}x_{j},$   and   $dx=\prod _{j=1}^{n}dx_{j}.$ The convolution of $u$ and $v$ is defined by: $r(x)\triangleq \int _{\mathbb {R} ^{n}}u(\tau )v(x-\tau )\,d\tau .$ Also: $\iint |u(\tau )v(x-\tau )|\,dx\,d\tau =\int \left(|u(\tau )|\int |v(x-\tau )|\,dx\right)\,d\tau =\int |u(\tau )|\,\|v\|_{1}\,d\tau =\|u\|_{1}\|v\|_{1}.$ Hence by Fubini's theorem we have that $r\in L^{1}(\mathbb {R} ^{n})$ so its Fourier transform $R$ is defined by the integral formula: ${\begin{aligned}R(f)\triangleq {\mathcal {F}}\{r\}(f)&=\int _{\mathbb {R} ^{n}}r(x)e^{-i2\pi f\cdot x}\,dx\\&=\int _{\mathbb {R} ^{n}}\left(\int _{\mathbb {R} ^{n}}u(\tau )v(x-\tau )\,d\tau \right)\,e^{-i2\pi f\cdot x}\,dx.\end{aligned}}$ Note that $|u(\tau )v(x-\tau )e^{-i2\pi f\cdot x}|=|u(\tau )v(x-\tau )|,$  Hence by the argument above we may apply Fubini's theorem again (i.e. interchange the order of integration): ${\begin{aligned}R(f)&=\int _{\mathbb {R} ^{n}}u(\tau )\underbrace {\left(\int _{\mathbb {R} ^{n}}v(x-\tau )\ e^{-i2\pi f\cdot x}\,dx\right)} _{V(f)\ e^{-i2\pi f\cdot \tau }}\,d\tau \\&=\underbrace {\left(\int _{\mathbb {R} ^{n}}u(\tau )\ e^{-i2\pi f\cdot \tau }\,d\tau \right)} _{U(f)}\ V(f).\end{aligned}}$

Эта теорема также справедлива для преобразования Лапласа , двустороннего преобразования Лапласа и, при соответствующей модификации, для преобразования Меллина и преобразования Хартли (см. Теорему об обращении Меллина ). Его можно расширить до преобразования Фурье абстрактного гармонического анализа, определенного над локально компактными абелевыми группами .

Периодическая свертка (коэффициенты ряда Фурье)

Учитывать $P$-периодические функции $u_{_{P}}$ и $v_{_{P}},$ которые можно выразить в виде периодических сумм :

$u_{_{P}}(x)\ \triangleq \sum _{m=-\infty }^{\infty }u(x-mP)$ и $v_{_{P}}(x)\ \triangleq \sum _{m=-\infty }^{\infty }v(x-mP).$

На практике ненулевая часть компонентов $u$ и $v$ часто ограничиваются продолжительностью $P,$ но ничто в теореме этого не требует.

Коэффициенты ряда Фурье :

${\begin{aligned}U[k]&\triangleq {\mathcal {F}}\{u_{_{P}}\}[k]={\frac {1}{P}}\int _{P}u_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} ;\quad \quad \scriptstyle {\text{integration over any interval of length }}P\\V[k]&\triangleq {\mathcal {F}}\{v_{_{P}}\}[k]={\frac {1}{P}}\int _{P}v_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}$

где ${\mathcal {F}}$ обозначает интеграл ряда Фурье .

• Точечное произведение: $u_{_{P}}(x)\cdot v_{_{P}}(x)$ также $P$-периодический, а коэффициенты его ряда Фурье задаются дискретной сверткой $U$ и $V$ последовательности:

${\mathcal {F}}\{u_{_{P}}\cdot v_{_{P}}\}[k]=\{U*V\}[k].$

• Свертка:

${\begin{aligned}\{u_{_{P}}*v\}(x)\ &\triangleq \int _{-\infty }^{\infty }u_{_{P}}(x-\tau )\cdot v(\tau )\ d\tau \\&\equiv \int _{P}u_{_{P}}(x-\tau )\cdot v_{_{P}}(\tau )\ d\tau ;\quad \quad \scriptstyle {\text{integration over any interval of length }}P\end{aligned}}$

также $P$-периодическая и называется периодической сверткой .

show Вывод периодической свертки

${\begin{aligned}\int _{-\infty }^{\infty }u_{_{P}}(x-\tau )\cdot v(\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}+kP}^{x_{o}+(k+1)P}u_{_{P}}(x-\tau )\cdot v(\tau )\ d\tau \right]\quad x_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}}^{x_{o}+P}\underbrace {u_{_{P}}(x-\tau -kP)} _{u_{_{P}}(x-\tau ),{\text{ by periodicity}}}\cdot v(\tau +kP)\ d\tau \right]\quad {\text{substituting }}\tau \rightarrow \tau +kP\\&=\int _{x_{o}}^{x_{o}+P}u_{_{P}}(x-\tau )\cdot \underbrace {\left[\sum _{k=-\infty }^{\infty }v(\tau +kP)\right]} _{\triangleq \ v_{_{P}}(\tau )}\ d\tau \end{aligned}}$

Соответствующая теорема о свертке :

${\mathcal {F}}\{u_{_{P}}*v\}[k]=\ P\cdot U[k]\ V[k].$    

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

show Вывод уравнения 2

${\begin{aligned}{\mathcal {F}}\{u_{_{P}}*v\}[k]&\triangleq {\frac {1}{P}}\int _{P}\left(\int _{P}u_{_{P}}(\tau )\cdot v_{_{P}}(x-\tau )\ d\tau \right)e^{-i2\pi kx/P}\,dx\\&=\int _{P}u_{_{P}}(\tau )\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi kx/P}dx\right)\,d\tau \\&=\int _{P}u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}\underbrace {\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi k(x-\tau )/P}dx\right)} _{V[k],\quad {\text{due to periodicity}}}\,d\tau \\&=\underbrace {\left(\int _{P}\ u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}d\tau \right)} _{P\cdot U[k]}\ V[k].\end{aligned}}$

Функции дискретной переменной (последовательности)

Путем вывода, аналогичного уравнению 1, существует аналогичная теорема для последовательностей, таких как выборки двух непрерывных функций, где теперь ${\mathcal {F}}$ обозначает оператор дискретного преобразования Фурье (DTFT). Рассмотрим две последовательности $u[n]$ и $v[n]$ с преобразованиями $U$ и $V$:

${\begin{aligned}U(f)&\triangleq {\mathcal {F}}\{u\}(f)=\sum _{n=-\infty }^{\infty }u[n]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} ,\\V(f)&\triangleq {\mathcal {F}}\{v\}(f)=\sum _{n=-\infty }^{\infty }v[n]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} .\end{aligned}}$

свертка Дискретная § $u$ и $v$ определяется :

$r[n]\triangleq (u*v)[n]=\sum _{m=-\infty }^{\infty }u[m]\cdot v[n-m]=\sum _{m=-\infty }^{\infty }u[n-m]\cdot v[m].$

Теорема свертки для дискретных последовательностей :

$R(f)={\mathcal {F}}\{u*v\}(f)=\ U(f)V(f).$    

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

Периодическая свертка

$U(f)$ и $V(f),$ как определено выше, являются периодическими с периодом 1. Рассмотрим $N$-периодические последовательности $u_{_{N}}$ и $v_{_{N}}$:

$u_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }u[n-mN]$ и $v_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }v[n-mN],\quad n\in \mathbb {Z} .$

Эти функции возникают в результате выборки $U$ и $V$ с интервалом в $1/N$ и выполнение обратного дискретного преобразования Фурье (ДПФ) на $N$ выборки (см. § Выборка DTFT ). Дискретная свертка :

$\{u_{_{N}}*v\}[n]\ \triangleq \sum _{m=-\infty }^{\infty }u_{_{N}}[m]\cdot v[n-m]\equiv \sum _{m=0}^{N-1}u_{_{N}}[m]\cdot v_{_{N}}[n-m]$

также $N$-периодическая и называется периодической сверткой . Переосмысление ${\mathcal {F}}$ оператор в качестве $N$ДПФ -длины, соответствующая теорема такова:

${\mathcal {F}}\{u_{_{N}}*v\}[k]=\ \underbrace {{\mathcal {F}}\{u_{_{N}}\}[k]} _{U(k/N)}\cdot \underbrace {{\mathcal {F}}\{v_{_{N}}\}[k]} _{V(k/N)},\quad k\in \mathbb {Z} .$    

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

И поэтому :

$\{u_{_{N}}*v\}[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u_{_{N}}\}\cdot {\mathcal {F}}\{v_{_{N}}\}\}.$    

( Уравнение 4б )

При правильных условиях это возможно. $N$последовательность длиной, содержащая сегмент без искажений $u*v$ свертка. Но когда ненулевая часть $u(n)$ или $v(n)$ последовательность равна или длиннее, чем $N,$ некоторые искажения неизбежны. Так обстоит дело, когда $V(k/N)$ последовательность получается путем прямой выборки DTFT бесконечно длинного импульсного отклика § дискретного преобразования Гильберта .

Для $u$ и $v$ последовательности, ненулевая длительность которых меньше или равна $N,$ окончательное упрощение:

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

$\{u_{_{N}}*v\}[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\}.$    

( уравнение 4c )

Эта форма часто используется для эффективной реализации числовой свертки на компьютере . (см. § Алгоритмы быстрой свертки и § Пример )

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

show Выводы уравнения 4

A time-domain derivation proceeds as follows: ${\begin{aligned}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}*v\}[k]&\triangleq \sum _{n=0}^{N-1}\left(\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot v_{_{N}}[n-m]\right)e^{-i2\pi kn/N}\\&=\sum _{m=0}^{N-1}u_{_{N}}[m]\left(\sum _{n=0}^{N-1}v_{_{N}}[n-m]\cdot e^{-i2\pi kn/N}\right)\\&=\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot e^{-i2\pi km/N}\underbrace {\left(\sum _{n=0}^{N-1}v_{_{N}}[n-m]\cdot e^{-i2\pi k(n-m)/N}\right)} _{\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\quad \scriptstyle {\text{due to periodicity}}}\\&=\underbrace {\left(\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot e^{-i2\pi km/N}\right)} _{\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]}\left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right).\end{aligned}}$ A frequency-domain derivation follows from § Periodic data, which indicates that the DTFTs can be written as: ${\mathcal {F}}\{u_{_{N}}*v\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}*v\}[k]\right)\cdot \delta \left(f-k/N\right).\quad \scriptstyle {\mathsf {(Eq.5a)}}$ ${\mathcal {F}}\{u_{_{N}}\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \delta \left(f-k/N\right).$ The product with $V(f)$ is thereby reduced to a discrete-frequency function: ${\begin{aligned}{\mathcal {F}}\{u_{_{N}}*v\}(f)&=G_{_{N}}(f)V(f)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot V(f)\cdot \delta \left(f-k/N\right)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot V(k/N)\cdot \delta \left(f-k/N\right)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)\cdot \delta \left(f-k/N\right),\quad \scriptstyle {\mathsf {(Eq.5b)}}\end{aligned}}$ where the equivalence of $V(k/N)$ and $\left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)$ follows from § Sampling the DTFT. Therefore, the equivalence of (5a) and (5b) requires: $\scriptstyle {\rm {DFT}}\displaystyle {\{u_{_{N}}*v\}[k]}=\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right).$ We can also verify the inverse DTFT of (5b): ${\begin{aligned}(u_{_{N}}*v)[n]&=\int _{0}^{1}\left({\frac {1}{N}}\sum _{k=-\infty }^{\infty }\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\cdot \delta \left(f-k/N\right)\right)\cdot e^{i2\pi fn}df\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\cdot \underbrace {\left(\int _{0}^{1}\delta \left(f-k/N\right)\cdot e^{i2\pi fn}df\right)} _{{\text{0, for}}\ k\ \notin \ [0,\ N)}\\&={\frac {1}{N}}\sum _{k=0}^{N-1}{\bigg (}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]{\bigg )}\cdot e^{i2\pi {\frac {n}{N}}k}\\&=\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle {\bigg (}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}{\bigg )}.\end{aligned}}$

Теорема о свертке для обратного преобразования Фурье

Существует также теорема о свертке для обратного преобразования Фурье:

Здесь, " $\cdot$" представляет произведение Адамара и " $*$" представляет собой свертку между двумя матрицами.

${\begin{aligned}&{\mathcal {F}}\{u*v\}={\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\\&{\mathcal {F}}\{u\cdot v\}={\mathcal {F}}\{u\}*{\mathcal {F}}\{v\}\end{aligned}}$

так что

${\begin{aligned}&u*v={\mathcal {F}}^{-1}\left\{{\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\right\}\\&u\cdot v={\mathcal {F}}^{-1}\left\{{\mathcal {F}}\{u\}*{\mathcal {F}}\{v\}\right\}\end{aligned}}$

Теорема о свертке для умеренных распределений

Теорема о свертке распространяется на умеренные распределения . Здесь, $v$ представляет собой произвольное умеренное распределение:

${\begin{aligned}&{\mathcal {F}}\{u*v\}={\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\\&{\mathcal {F}}\{\alpha \cdot v\}={\mathcal {F}}\{\alpha \}*{\mathcal {F}}\{v\}.\end{aligned}}$

Но $u=F\{\alpha \}$ должно «быстро уменьшаться» в сторону $-\infty$ и $+\infty$ чтобы гарантировать существование как продукта свертки, так и продукта умножения. Эквивалентно, если $\alpha =F^{-1}\{u\}$ является гладкой «медленно растущей» обычной функцией, она гарантирует существование как произведения умножения, так и произведения свертки.

В частности, каждое умеренное распределение с компактным носителем, такое как дельта Дирака , «быстро уменьшается». Аналогично, функции с ограниченной полосой пропускания , такие как функция, которая постоянно $1$ являются гладкими «медленно растущими» обычными функциями. Если, например, $v\equiv \operatorname {\text{Ш}}$ — гребенка Дирака, оба уравнения дают формулу суммирования Пуассона , и если, кроме того, $u\equiv \delta$ тогда это дельта Дирака $\alpha \equiv 1$ постоянно единица, и эти уравнения приводят к тождеству гребенки Дирака .

См. также

• Момент-производящая функция случайной величины

Ссылки

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

• Кацнельсон, Ицхак (1976), Введение в гармонический анализ , Дувр, ISBN  0-486-63331-4
• Ли, Бинг; Бабу, Г. Джогеш (2019), «Теорема о свертке и асимптотическая эффективность», Аспирантура по статистическому выводу , Нью-Йорк: Springer, стр. 295–327, ISBN  978-1-4939-9759-6
• Кратчфилд, Стив (9 октября 2010 г.), «Радость свертки» , Университет Джонса Хопкинса , получено 19 ноября 2010 г.

Дополнительные ресурсы

Наглядное представление использования теоремы свертки в обработке сигналов см.:

• Университете Джона Хопкинса в Моделирование с помощью Java : http://www.jhu.edu/signals/convolve/index.html