Теорема свертки - Convolution theorem - Wikipedia

В математика, то теорема свертки заявляет, что при подходящих условиях преобразование Фурье из свертка из двух сигналы это точечный продукт их преобразований Фурье. Другими словами, свертка в одном домене (например, область времени ) равно точечному умножению в другой области (например, частотная область ). Версии теоремы о свертке верны для различных Преобразования, связанные с Фурье. Позволять ${\displaystyle f}$ и ${\displaystyle g}$ быть двумя функции с свертка ${\displaystyle f*g}$. (Обратите внимание, что звездочка означает свертку в этом контексте, а не стандартное умножение. В тензорное произведение символ ${\displaystyle \otimes }$ иногда используется вместо этого.)

Если ${\displaystyle {\mathcal {F}}}$ обозначает преобразование Фурье оператор, тогда ${\displaystyle {\mathcal {F}}\{f\}}$ и ${\displaystyle {\mathcal {F}}\{g\}}$ являются преобразованиями Фурье ${\displaystyle f}$ и ${\displaystyle g}$, соответственно. потом

${\displaystyle {\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}}$^[1]

куда ${\displaystyle \cdot }$ обозначает точечное умножение. Это также работает наоборот:

${\displaystyle {\mathcal {F}}\{f\cdot g\}={\mathcal {F}}\{f\}*{\mathcal {F}}\{g\}}$

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

${\displaystyle f*g={\mathcal {F}}^{-1}{\big \{}{\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}{\big \}}}$

и:

${\displaystyle f\cdot g={\mathcal {F}}^{-1}{\big \{}{\mathcal {F}}\{f\}*{\mathcal {F}}\{g\}{\big \}}}$

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

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

Эта формулировка особенно полезна для реализации числовой свертки на компьютер: Стандартный алгоритм свертки имеет квадратичный вычислительная сложность. С помощью теоремы о свертке и быстрое преобразование Фурье, сложность свертки может быть уменьшена с ${\displaystyle O\left(n^{2}\right)}$ к ${\displaystyle O\left(n\log n\right)}$, с помощью нотация большой O. Это можно использовать для быстрого построения алгоритмы умножения, как в Алгоритм умножения § Методы преобразования Фурье.

Доказательство

Доказательство здесь показано для конкретного нормализация преобразования Фурье. Как упоминалось выше, если преобразование нормализовано иначе, то постоянная коэффициенты масштабирования появится в выводе.

Позволять ${\displaystyle f,g}$ принадлежат к L^п -Космос ${\displaystyle L^{1}(\mathbb {R} ^{n})}$. Позволять ${\displaystyle F}$ - преобразование Фурье ${\displaystyle f}$ и ${\displaystyle G}$ - преобразование Фурье ${\displaystyle g}$:

${\displaystyle {\begin{aligned}F(\nu )&={\mathcal {F}}\{f\}(\nu )=\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\,dx,\\G(\nu )&={\mathcal {F}}\{g\}(\nu )=\int _{\mathbb {R} ^{n}}g(x)e^{-2\pi ix\cdot \nu }\,dx,\end{aligned}}}$

где точка между ${\displaystyle x}$ и ${\displaystyle \nu }$ указывает на внутренний продукт из ${\displaystyle \mathbb {R} ^{n}}$. Позволять ${\displaystyle h}$ быть свертка из ${\displaystyle f}$ и ${\displaystyle g}$

${\displaystyle h(z)=\int _{\mathbb {R} ^{n}}f(x)g(z-x)\,dx.}$

Также

${\displaystyle \iint |f(x)g(z-x)|\,dz\,dx=\int \left(|f(x)|\int |g(z-x)|\,dz\right)\,dx=\int |f(x)|\,\|g\|_{1}\,dx=\|f\|_{1}\|g\|_{1}.}$

Следовательно Теорема Фубини у нас есть это ${\displaystyle h\in L^{1}(\mathbb {R} ^{n})}$ так что его преобразование Фурье ${\displaystyle H}$ определяется интегральной формулой

${\displaystyle {\begin{aligned}H(\nu )={\mathcal {F}}\{h\}&=\int _{\mathbb {R} ^{n}}h(z)e^{-2\pi iz\cdot \nu }\,dz\\&=\int _{\mathbb {R} ^{n}}\int _{\mathbb {R} ^{n}}f(x)g(z-x)\,dx\,e^{-2\pi iz\cdot \nu }\,dz.\end{aligned}}}$

Обратите внимание, что ${\displaystyle |f(x)g(z-x)e^{-2\pi iz\cdot \nu }|=|f(x)g(z-x)|}$ и, следовательно, с помощью приведенных выше аргументов мы можем снова применить теорему Фубини (т.е. поменять порядок интегрирования):

${\displaystyle H(\nu )=\int _{\mathbb {R} ^{n}}f(x)\left(\int _{\mathbb {R} ^{n}}g(z-x)e^{-2\pi iz\cdot \nu }\,dz\right)\,dx.}$

Подстановка ${\displaystyle y=z-x}$ дает ${\displaystyle dy=dz}$. Следовательно

${\displaystyle H(\nu )=\int _{\mathbb {R} ^{n}}f(x)\left(\int _{\mathbb {R} ^{n}}g(y)e^{-2\pi i(y+x)\cdot \nu }\,dy\right)\,dx}$

${\displaystyle =\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\left(\int _{\mathbb {R} ^{n}}g(y)e^{-2\pi iy\cdot \nu }\,dy\right)\,dx}$

${\displaystyle =\int _{\mathbb {R} ^{n}}f(x)e^{-2\pi ix\cdot \nu }\,dx\int _{\mathbb {R} ^{n}}g(y)e^{-2\pi iy\cdot \nu }\,dy.}$

Эти два интеграла являются определениями ${\displaystyle F(\nu )}$ и ${\displaystyle G(\nu )}$, так:

${\displaystyle H(\nu )=F(\nu )\cdot G(\nu ),}$

QED.

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

Подобный аргумент, как и приведенное выше доказательство, может быть применен к теореме о свертке для обратного преобразования Фурье;

${\displaystyle {\mathcal {F}}^{-1}\{f*g\}={\mathcal {F}}^{-1}\{f\}\cdot {\mathcal {F}}^{-1}\{g\}}$

${\displaystyle {\mathcal {F}}^{-1}\{f\cdot g\}={\mathcal {F}}^{-1}\{f\}*{\mathcal {F}}^{-1}\{g\}}$

так что

${\displaystyle f*g={\mathcal {F}}{\big \{}{\mathcal {F}}^{-1}\{f\}\cdot {\mathcal {F}}^{-1}\{g\}{\big \}}}$

${\displaystyle f\cdot g={\mathcal {F}}{\big \{}{\mathcal {F}}^{-1}\{f\}*{\mathcal {F}}^{-1}\{g\}{\big \}}}$

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

Теорема о свертке распространяется на умеренные распределения. Здесь, ${\displaystyle g}$ - произвольное умеренное распределение (например, Гребень Дирака )

${\displaystyle {\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}}$

${\displaystyle {\mathcal {F}}\{\alpha \cdot g\}={\mathcal {F}}\{\alpha \}*{\mathcal {F}}\{g\}}$

но ${\displaystyle f=F\{\alpha \}}$ должен быть "быстро убывающим" в сторону ${\displaystyle -\infty }$ и ${\displaystyle +\infty }$чтобы гарантировать существование как свертки, так и произведения умножения. ${\displaystyle \alpha =F^{-1}\{f\}}$ является гладкой "медленно растущей" обычной функцией, она гарантирует существование как произведения умножения, так и произведения свертки.^[2][3][4]

В частности, каждое умеренное распределение с компактным носителем, такое как Дельта Дирака, "быстро убывает". ограниченные функции, например, функция, которая постоянно ${\displaystyle 1}$гладкие "медленно растущие" обычные функции. Если, например, ${\displaystyle g\equiv \operatorname {III} }$ это Гребень Дирака оба уравнения дают Формула суммирования Пуассона и если, кроме того, ${\displaystyle f\equiv \delta }$ дельта Дирака, тогда ${\displaystyle \alpha \equiv 1}$ всегда равно единице, и эти уравнения дают Идентичность гребня Дирака.

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

Аналогичный свертка теорема для дискретных последовательностей ${\displaystyle x}$ и ${\displaystyle y}$ является:

${\displaystyle \scriptstyle {\rm {DTFT}}\displaystyle \{x*y\}=\ \scriptstyle {\rm {DTFT}}\displaystyle \{x\}\cdot \ \scriptstyle {\rm {DTFT}}\displaystyle \{y\},}$^[5][а]

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

Также есть теорема для круговые и периодические свертки:

${\displaystyle x_{_{N}}*y\ \triangleq \sum _{m=-\infty }^{\infty }x_{_{N}}[m]\cdot y[n-m]\equiv \sum _{m=0}^{N-1}x_{_{N}}[m]\cdot y_{_{N}}[n-m],}$

куда ${\displaystyle x_{_{N}}}$ и ${\displaystyle y_{_{N}}}$ находятся периодические суммирования последовательностей ${\displaystyle x}$ и ${\displaystyle y}$:

${\displaystyle x_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }x[n-mN]}$ и ${\displaystyle y_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }y[n-mN].}$

Теорема:

${\displaystyle \scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}*y\}=\ \scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}\}\cdot \ \scriptstyle {\rm {DFT}}\displaystyle \{y_{_{N}}\},}$^[6][b]

куда DFT представляет собой N-длину Дискретное преобразование Фурье.

И поэтому:

${\displaystyle x_{_{N}}*y=\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle {\big [}\ \scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}\}\cdot \ \scriptstyle {\rm {DFT}}\displaystyle \{y_{_{N}}\}{\big ]}.}$

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

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

${\displaystyle x_{_{N}}*y\ =\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DFT}}\displaystyle \{x\}\cdot \ \scriptstyle {\rm {DFT}}\displaystyle \{y\}\right]}$

При определенных условиях подпоследовательность ${\displaystyle x_{_{N}}*y}$ эквивалентна линейной (апериодической) свертке ${\displaystyle x}$ и ${\displaystyle y}$, что обычно является желаемым результатом. (видеть Пример ) И когда преобразования эффективно реализованы с помощью Быстрое преобразование Фурье алгоритм, этот расчет намного эффективнее линейной свертки.

Теорема о свертке для коэффициентов ряда Фурье

Существуют две теоремы свертки для Ряд Фурье коэффициенты периодической функции:

• Первая теорема о свертке утверждает, что если ${\displaystyle f}$ и ${\displaystyle g}$ находятся в ${\displaystyle L^{1}([-\pi ,\pi ])}$, коэффициенты ряда Фурье 2π-периодический свертка из ${\displaystyle f}$ и ${\displaystyle g}$ даны:

${\displaystyle [{\widehat {f*_{2\pi }g}}](n)=2\pi \cdot {\widehat {f}}(n)\cdot {\widehat {g}}(n),}$^[A]

куда:

${\displaystyle {\begin{aligned}\left[f*_{2\pi }g\right](x)\ &\triangleq \int _{-\pi }^{\pi }f(u)\cdot g[{\text{pv}}(x-u)]\,du,&&{\big (}{\text{and }}\underbrace {{\text{pv}}(x)\ \triangleq \arg \left(e^{ix}\right)} _{\text{principal value}}{\big )}\\&=\int _{-\pi }^{\pi }f(u)\cdot g(x-u)\,du,&&\scriptstyle {\text{when }}g(x){\text{ is 2}}\pi {\text{-periodic.}}\\&=\int _{2\pi }f(u)\cdot g(x-u)\,du,&&\scriptstyle {\text{when both functions are 2}}\pi {\text{-periodic, and the integral is over any 2}}\pi {\text{ interval.}}\end{aligned}}}$

• Вторая теорема о свертке утверждает, что коэффициенты ряда Фурье произведения ${\displaystyle f}$ и ${\displaystyle g}$ даны дискретная свертка из ${\displaystyle {\hat {f}}}$ и ${\displaystyle {\hat {g}}}$ последовательности:

${\displaystyle \left[{\widehat {f\cdot g}}\right](n)=\left[{\widehat {f}}*{\widehat {g}}\right](n).}$

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

• Функция создания моментов из случайная переменная

Примечания

1. Масштабный коэффициент всегда равен периоду, 2π в этом случае.

Цитирование страниц

1. Оппенгейм и Шафер, стр 60 (2.169).
2. Оппенгейм и Шафер, с. 548.

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

1. McGillem, Clare D .; Купер, Джордж Р. (1984). Анализ непрерывных и дискретных сигналов и систем (2-е изд.). Холт, Райнхарт и Уинстон. п. 118 (3-102). ISBN  0-03-061703-0.
2. Хорват, Джон (1966). Топологические векторные пространства и распределения. Ридинг, Массачусетс: издательство Addison-Wesley Publishing Company.
3. Баррос-Нето, Хосе (1973). Введение в теорию распределений. Нью-Йорк, Нью-Йорк: Деккер.
4. Петерсен, Бент Э. (1983). Введение в преобразование Фурье и псевдодифференциальные операторы. Бостон, Массачусетс: издательство Pitman Publishing.
5. Proakis, John G .; Манолакис, Дмитрий Г. (1996), Цифровая обработка сигналов: принципы, алгоритмы и приложения (3-е изд.), Нью-Джерси: Prentice-Hall International, стр. 297, Bibcode:1996dspp.book ..... P, ISBN  9780133942897, sAcfAQAAIAAJ
6. Рабинер, Лоуренс Р.; Золото, Бернард (1975). Теория и применение цифровой обработки сигналов. Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc., стр. 59 (2,163). ISBN  978-0139141010.

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

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

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

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

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

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