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

Теорема о том, что при подходящих условиях преобразование Фурье свертки двух сигналов является точечным произведением их преобразований Фурье

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

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

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

где $\cdot \; \{\backslash \; displaystyle\; \backslash \; cdot\}$обозначает умножение по точкам. Он также работает наоборот:

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

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

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

и:

$е\; \cdot \; г\; =\; F\; -\; 1\; \{F\; \{f\}\; \ast \; F\; \{g\}\}\; \{\backslash \; displaystyle\; f\; \backslash \; cdot\; g\; =\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; \{\backslash \; big\; \backslash \; \{\}\; \{\backslash \; mathcal\; \{F\; \}\}\; \backslash \; \{f\; \backslash \}\; *\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{g\; \backslash \}\; \{\backslash \; big\; \backslash \}\}\}$

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

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

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

• 1 Доказательство
• 2 Теорема свертки для обратного преобразования Фурье
• 3 Теорема свертки для умеренных распределений
• 4 Функции последовательностей дискретных переменных
• 5 Теорема свертки для коэффициентов ряда Фурье
• 6 См. Также
• 7 Примечания
• 8 Ссылки на страницы
• 9 Ссылки
• 10 Дополнительная литература
• 11 Дополнительные ресурсы

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

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

$F\; (\nu )\; =\; F\; \{f\}\; (\nu )\; =\; \int \; R\; nf\; (x)\; e\; -\; 2\; \pi \; ix\; \cdot \; \nu \; dx,\; G\; (\nu )\; Знак\; равно\; F\; \{g\}\; (\nu )\; знак\; равно\; \int \; R\; ng\; (x)\; e\; -\; 2\; \pi \; ix\; \cdot \; \nu \; dx,\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; F\; (\backslash \; nu)\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{\; f\; \backslash \}\; (\backslash \; nu)\; =\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; f\; (x)\; e\; ^\; \{-\; 2\; \backslash \; pi\; ix\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dx,\; \backslash \backslash \; G\; (\backslash \; nu)\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{g\; \backslash \}\; (\backslash \; nu)\; =\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; g\; (x)\; e\; ^\; \{-\; 2\; \backslash \; pi\; ix\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dx,\; \backslash \; end\; \{align\}\}\}$

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

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

Также

$\iint \; |\; f\; (x)\; g\; (z\; -\; x)\; |\; d\; z\; d\; x\; =\; \int \; (|\; f\; (x)\; |\; \int \; |\; g\; (z\; -\; x)\; |\; d\; z)\; d\; x\; =\; \int \; |\; f\; (x)\; |\; Г\; \Vert \; 1\; д\; х\; знак\; равно\; \Vert \; е\; \Vert \; 1\; \Vert \; г\; \Vert \; 1.\; \{\backslash \; Displaystyle\; \backslash \; iint\; |\; е\; (х)\; г\; (zx)\; |\; \backslash ,\; dz\; \backslash ,\; dx\; =\; \backslash \; int\; \backslash \; left\; (|\; f\; (x)\; |\; \backslash \; int\; |\; g\; (zx)\; |\; \backslash ,\; dz\; \backslash \; right)\; \backslash ,\; dx\; =\; \backslash \; int\; |\; f\; (x)\; |\; \backslash ,\; \backslash \; |\; g\; \backslash \; |\; \_\; \{1\}\; \backslash ,\; dx\; =\; \backslash \; |\; f\; \backslash \; |\; \_\; \{1\}\; \backslash \; |\; g\; \backslash \; |\; \_\; \{1\}.\}$

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

$H\; (\nu )\; =\; F\; \{h\}\; =\; \int \; R\; nh\; (z)\; e\; -\; 2\; \pi \; iz\; \cdot \; \nu \; dz\; знак\; равно\; \int \; R\; n\; \int \; R\; nf\; (x)\; g\; (z\; -\; x)\; dxe\; -\; 2\; \pi \; iz\; \cdot \; \nu \; dz.\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; H\; (\backslash \; nu)\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{h\; \backslash \}\; =\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; h\; (z)\; e\; ^\; \{\; -2\; \backslash \; pi\; iz\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dz\; \backslash \backslash \; =\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; f\; (x)\; g\; (zx)\; \backslash ,\; dx\; \backslash ,\; e\; ^\; \{-\; 2\; \backslash \; pi\; iz\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dz.\; \backslash \; end\; \{align\}\}\}$

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

$H\; (\nu )\; =\; \int \; R\; nf\; (x)\; (\int \; R\; ng\; (z\; -\; x)\; e\; -\; 2\; \pi \; iz\; \cdot \; \nu \; dz)\; dx.\; \{\backslash \; Displaystyle\; Н\; (\backslash \; Nu)\; =\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; f\; (x)\; \backslash \; left\; (\backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; g\; (zx)\; e\; ^\; \{-2\; \backslash \; pi\; из\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dz\; \backslash \; right)\; \backslash ,\; dx.\}$

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

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

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

$=\; \int \; R\; nf\; (x)\; e\; -\; 2\; \pi \; ix\; \cdot \; \nu \; dx\; \int \; R\; ng\; (y)\; e\; -\; 2\; \pi \; iy\; \cdot \; \nu \; dy.\; \{\backslash \; Displaystyle\; =\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{n\}\}\; е\; (х)\; е\; ^\; \{-\; 2\; \backslash \; пи\; ix\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dx\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{п\; \}\}\; g\; (y)\; e\; ^\; \{-\; 2\; \backslash \; pi\; iy\; \backslash \; cdot\; \backslash \; nu\}\; \backslash ,\; dy.\}$

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

$H\; (\nu )\; =\; F\; (\nu )\; \cdot \; G\; (\nu ),\; \{\backslash \; Displaystyle\; H\; (\backslash \; nu)\; =\; F\; (\backslash \; nu)\; \backslash \; cdot\; G\; (\backslash \; nu),\}$

QED.

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

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

$F\; -\; 1\; \{f\; \cdot \; g\}\; =\; F\; -\; 1\; \{е\}\; \ast \; F\; -\; 1\; \{g\}\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; \backslash \; \{f\; \backslash \; cdot\; g\; \backslash \}\; =\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; \backslash \; \{f\; \backslash \; \}\; *\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; \backslash \; \{g\; \backslash \}\}$

так, чтобы

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

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

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

$F\; \{f\; \ast \; g\}\; =\; F\; \{f\}\; \cdot \; F\; \{g\}\; \{\; \backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{е\; *\; г\; \backslash \}\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{f\; \backslash \}\; \backslash \; cdot\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{g\; \backslash \}\}$

$F\; \{\alpha \; \cdot \; g\}\; знак\; равно\; F\; \{\alpha \}\; *\; F\; \{g\}\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{\backslash \; alpha\; \backslash \; cdot\; g\; \backslash \}\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{\backslash \; alpha\; \backslash \}\; *\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; \{g\; \backslash \}\}$

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

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

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

$DTFT\; \{x\; \ast \; y\}\; =\; DTFT\; \{x\}\; \cdot \; DTFT\; \{y\},\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DTFT\; \}\}\; \backslash \; displaystyle\; \backslash \; \{x\; *\; y\; \backslash \}\; =\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DTFT\}\}\; \backslash \; displaystyle\; \backslash \; \{x\; \backslash \}\; \backslash \; cdot\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DTFT\}\}\; \backslash \; displaystyle\; \backslash \; \{y\; \backslash \},\}$

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

Существует также теорема для циклических и периодических сверток :

$x\; N\; \ast \; y\; \triangleq \; \sum \; m\; =\; -\; \infty \; \infty \; x\; N\; [м]\; \cdot \; y\; [n\; -\; m]\; \equiv \; \sum \; м\; Знак\; равно\; 0\; N\; -\; 1\; Икс\; N\; [м]\; \cdot \; Y\; N\; [N\; -\; m],\; \{\backslash \; displaystyle\; x\; \_\; \{\_\; \{N\}\}\; *\; Y\; \backslash \; \backslash \; Triangleq\; \backslash \; sum\; \_\; \{m\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; x\_\; \{\_\; \{N\}\}\; [м]\; \backslash \; cdot\; y\; [нм]\; \backslash \; Equiv\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{N-1\}\; x\; \_\; \{\_\; \{N\}\}\; [m]\; \backslash \; cdot\; y\; \_\; \{\_\; \{N\}\}\; [нм],\}$

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

$x\; N\; [n]\; \triangleq \; \sum \; м\; знак\; равно\; -\; \infty \; \infty \; Икс\; [N\; -\; м\; N]\; \{\backslash \; Displaystyle\; х\; \_\; \{\_\; \{N\}\}\; [п]\; \backslash \; \backslash \; треугольник\; \backslash \; сумма\; \_\; \{м\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; х\; [n-mN]\}$и $y\; N\; [n]\; \triangleq \; \sum \; m\; =\; -\; \infty \; \infty \; y\; [n\; -\; m\; N].\; \{\backslash \; displaystyle\; y\; \_\; \{\_\; \{N\}\}\; [n]\; \backslash \; \backslash \; Triangleq\; \backslash \; sum\; \_\; \{m\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; y\; [n-mN].\}$

Теорема: :

$DFT\; \{\; x\; N\; \ast \; y\}\; =\; DFT\; \{x\; N\}\; \cdot \; DFT\; \{y\; N\},\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; \backslash \; displaystyle\; \backslash \; \{x\; \_\; \{\_\; \{N\}\}\; *\; y\; \backslash \}\; =\; \backslash \; \backslash \; scriptstyle\; \{\; \backslash \; rm\; \{DFT\}\}\; \backslash \; displaystyle\; \backslash \; \{x\; \_\; \{\_\; \{N\}\}\; \backslash \}\; \backslash \; cdot\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; \backslash \; displaystyle\; \backslash \; \{y\; \_\; \{\_\; \{N\}\}\; \backslash \},\}$

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

И, следовательно, :

$x\; N\; \ast \; y\; =\; DFT\; -\; 1\; [DFT\; \{x\; N\}\; \cdot \; DFT\; \{y\; N\}].\; \{\backslash \; displaystyle\; x\; \_\; \{\_\; \{N\}\}\; *\; y\; =\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; ^\; \{-\; 1\}\; \backslash \; displaystyle\; \{\backslash \; big\; [\}\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; \backslash \; displaystyle\; \backslash \; \{x\_\; \{\_\; \{N\}\}\; \backslash \}\; \backslash \; cdot\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; \backslash \; displaystyle\; \backslash \; \{y\; \_\; \{\_\; \{N\}\}\; \backslash \}\; \{\backslash \; big]\}.\}$

Для последовательностей x и y, не -нулевая длительность меньше или равна N, окончательное упрощение: :

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

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

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

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

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

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

где:

$[f\; \ast \; 2\; \pi \; g]\; (x)\; \triangleq \; \int \; -\; \pi \; \pi \; f\; (u)\; \cdot \; g\; [pv\; (x\; -\; u)]\; du,\; (и\; pv\; (x)\; \triangleq \; arg\; \; (eix)\; ⏟\; главное\; значение)\; =\; \int \; -\; \pi \; \pi \; f\; (u)\; \cdot \; g\; (x\; -\; u)\; du,\; когда\; g\; (x)\; 2\; \pi \; -периодичен.\; =\; \int \; 2\; \pi \; f\; (u)\; \cdot \; g\; (x\; -\; u)\; d\; u,\; когда\; обе\; функции\; 2\; \pi \; -периодичны,\; а\; интеграл\; ведется\; по\; любому\; интервалу\; 2\; \pi .\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; left\; [е\; *\; \_\; \{2\; \backslash \; pi\}\; g\; \backslash \; right]\; (x)\; \backslash \; \backslash \; треугольникq\; \backslash \; int\; \_\; \{-\; \backslash \; pi\}\; ^\; \{\backslash \; pi\}\; f\; (u)\; \backslash \; cdot\; g\; [\{\backslash \; text\; \{pv\}\}\; (xu)]\; \backslash ,\; du,\; \{\backslash \; big\; (\}\; \{\backslash \; text\; \{and\}\}\; \backslash \; underbrace\; \{\{\backslash \; text\; \{pv\}\}\; (x)\; \backslash \; \backslash \; треугольникq\; \backslash \; arg\; \backslash \; left\; (e\; ^\; \{ix\}\; \backslash \; right)\}\; \_\; \{\backslash \; text\; \{главное\; значение\}\}\; \{\backslash \; big)\}\; \backslash \backslash \; =\; \backslash \; int\; \_\; \{-\; \backslash \; pi\}\; ^\; \{\backslash \; pi\}\; f\; (u)\; \backslash \; cdot\; g\; (xu)\; \backslash ,\; du,\; \backslash \; scriptstyle\; \{\backslash \; text\; \{when\}\}\; g\; (x)\; \{\backslash \; text\; \{is\; 2\}\}\; \backslash \; pi\; \{\backslash \; text\; \{-periodic.\}\}\; \backslash \backslash \; =\; \backslash \; int\; \_\; \{2\; \backslash \; pi\}\; f\; (u)\; \backslash \; cdot\; g\; (xu)\; \backslash ,\; du,\; \backslash \; scriptstyle\; \{\backslash \; text\; \{когда\; обе\; функции\; 2\}\}\; \backslash \; pi\; \{\backslash \; text\; \{-периодические,\; а\; интеграл\; по\; любому\; 2\}\}\; \backslash \; pi\; \{\backslash \; text\; \{interval.\}\}\; \backslash \; end\; \{align\}\}\}$

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

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

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

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

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