WikiDer > Дискретное преобразование Фурье

Связь между (непрерывным) преобразование Фурье и дискретное преобразование Фурье. Левая колонка: Непрерывная функция (вверху) и ее преобразование Фурье (внизу). Центральная левая колонка: Периодическое суммирование исходной функции (вверху). Преобразование Фурье (внизу) равно нулю, за исключением дискретных точек. Обратное преобразование представляет собой сумму синусоид, называемых Ряд Фурье. Центральный правый столбец: Исходная функция дискретизируется (умножается на Гребень Дирака) (верх). Его преобразование Фурье (внизу) представляет собой периодическое суммирование (DTFT) исходного преобразования. Правый столбец: DFT (внизу) вычисляет дискретные выборки непрерывного DTFT. Обратное ДПФ (вверху) представляет собой периодическое суммирование исходных отсчетов. В БПФ Алгоритм вычисляет один цикл ДПФ, и его обратный результат - один цикл обратного ДПФ.

Изображение преобразования Фурье (вверху слева) и его периодического суммирования (DTFT) в левом нижнем углу. Спектральные последовательности в (a) верхнем правом и (b) нижнем правом углу соответственно вычисляются из (a) одного цикла периодического суммирования s (t) и (b) одного цикла периодического суммирования последовательности s (nT) . Соответствующие формулы: (а) Ряд Фурье интеграл и (б) DFT суммирование. Его сходство с исходным преобразованием S (f) и относительная простота вычислений часто являются мотивацией для вычисления последовательности ДПФ.

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

ДПФ - самый важный дискретное преобразование, используется для выполнения Анализ Фурье во многих практических приложениях.^[1] В цифровая обработка сигналов, функция - это любое количество или сигнал который меняется со временем, например, давление звуковая волна, а радио сигнал, или ежедневно температура показания, снятые за конечный интервал времени (часто определяемый оконная функция^[2]). В обработка изображений, выборками могут быть значения пиксели вдоль строки или столбца растровое изображение. ДПФ также используется для эффективного решения уравнения в частных производных, а также для выполнения других операций, таких как извилины или умножение больших целых чисел.

Поскольку он имеет дело с ограниченным объемом данных, его можно реализовать в компьютеры к численные алгоритмы или даже посвященный аппаратное обеспечение. Эти реализации обычно используют эффективные быстрое преобразование Фурье (БПФ) алгоритмы;^[3] настолько, что термины «БПФ» и «ДПФ» часто используются как синонимы. До текущего использования "БПФ" инициализм могло также использоваться для двусмысленного термина "конечное преобразование Фурье".

Определение

В дискретное преобразование Фурье преобразует последовательность из N сложные числа ${displaystyle left {mathbf {x_ {n}} ight}: = x_ {0}, x_ {1}, ldots, x_ {N-1}}$ в другую последовательность комплексных чисел, ${displaystyle left {mathbf {X_ {k}} ight}: = X_ {0}, X_ {1}, ldots, X_ {N-1},}$ который определяется

где последнее выражение следует из первого следующим образом: Формула Эйлера.

Преобразование иногда обозначают символом ${displaystyle {mathcal {F}}}$, как в ${displaystyle mathbf {X} = {mathcal {F}} left {mathbf {x} ight}}$ или же ${displaystyle {mathcal {F}} left (mathbf {x} ight)}$ или же ${displaystyle {mathcal {F}} mathbf {x}}$.^[A]

Мотивация

Уравнение 1 также могут быть оценены вне домена ${displaystyle kin [0, N-1]}$, и эта расширенная последовательность ${displaystyle N}$-периодический. Соответственно, другие последовательности ${displaystyle N}$ иногда используются индексы, например ${extstyle left [- {frac {N} {2}}, {frac {N} {2}} - 1ight]}$ (если ${displaystyle N}$ четный) и ${extstyle left [- {frac {N-1} {2}}, {frac {N-1} {2}} ight]}$ (если ${displaystyle N}$ является нечетным), что означает замену левой и правой половин результата преобразования местами.^[4]

Уравнение 1 могут интерпретироваться или выводиться различными способами, например:

Коэффициент нормализации, умножающий DFT и IDFT (здесь 1 и ${extstyle {frac {1} {N}}}$), а знаки показателей просто условности, и различаются некоторыми методами лечения. Единственные требования этих соглашений состоят в том, чтобы ДПФ и IDFT имели экспоненты разного знака и чтобы произведение их коэффициентов нормализации было ${extstyle {frac {1} {N}}}$. Нормализация ${extstyle {sqrt {frac {1} {N}}}}$ как для ДПФ, так и для IDFT, например, делает преобразования унитарными. Дискретный импульс, ${displaystyle x_ {n} = 1}$ в п = 0 и 0 в противном случае; может превратиться в ${displaystyle X_ {k} = 1}$ для всех k (используйте коэффициент нормализации 1 для ДПФ и ${extstyle {frac {1} {N}}}$ для IDFT). Сигнал постоянного тока, ${displaystyle X_ {k} = 1}$ в k = 0 и 0 в противном случае; может обратно преобразоваться в ${displaystyle x_ {n} = 1}$ для всех ${displaystyle n}$ (использовать ${extstyle {frac {1} {N}}}$ для DFT и 1 для IDFT), что соответствует просмотру ОКРУГ КОЛУМБИЯ как среднее среднее сигнала.

Пример

Позволять ${displaystyle N = 4}$ и

${displaystyle mathbf {x} = {egin {pmatrix} x_ {0} x_ {1} x_ {2} x_ {3} end {pmatrix}} = {egin {pmatrix} 1 2-i -i -1 + 2iend {pmatrix}}}$

Здесь мы демонстрируем, как вычислить ДПФ ${displaystyle mathbf {x}}$ с помощью Уравнение 1:

${displaystyle X_ {0} = e ^ {- i2pi 0cdot 0/4} cdot 1 + e ^ {- i2pi 0cdot 1/4} cdot (2-i) + e ^ {- i2pi 0cdot 2/4} cdot (- i) + e ^ {- i2pi 0cdot 3/4} cdot (-1 + 2i) = 2}$

${displaystyle X_ {1} = e ^ {- i2pi 1cdot 0/4} cdot 1 + e ^ {- i2pi 1cdot 1/4} cdot (2-i) + e ^ {- i2pi 1cdot 2/4} cdot (- i) + e ^ {- i2pi 1cdot 3/4} cdot (-1 + 2i) = - 2-2i}$

${displaystyle X_ {2} = e ^ {- i2pi 2cdot 0/4} cdot 1 + e ^ {- i2pi 2cdot 1/4} cdot (2-i) + e ^ {- i2pi 2cdot 2/4} cdot (- i) + e ^ {- i2pi 2cdot 3/4} cdot (-1 + 2i) = - 2i}$

${displaystyle X_ {3} = e ^ {- i2pi 3cdot 0/4} cdot 1 + e ^ {- i2pi 3cdot 1/4} cdot (2-i) + e ^ {- i2pi 3cdot 2/4} cdot (- i) + e ^ {- i2pi 3cdot 3/4} cdot (-1 + 2i) = 4 + 4i}$

${displaystyle mathbf {X} = {egin {pmatrix} X_ {0} X_ {1} X_ {2} X_ {3} end {pmatrix}} = {egin {pmatrix} 2 -2-2i - 2i 4 + 4iend {pmatrix}}}$

Обратное преобразование

Дискретное преобразование Фурье обратимо, линейное преобразование

${displaystyle {mathcal {F}} двоеточие mathbb {C} ^ {N} o mathbb {C} ^ {N}}$

с ${displaystyle mathbb {C}}$ обозначающий набор сложные числа. Его обратное преобразование известно как обратное дискретное преобразование Фурье (IDFT). Другими словами, для любого ${displaystyle N> 0}$, N-мерный комплексный вектор имеет ДПФ и ОДПФ, которые в свою очередь ${displaystyle N}$-мерные комплексные векторы.

Обратное преобразование дается выражением:

Характеристики

Линейность

ДПФ является линейным преобразованием, т.е. если ${displaystyle {mathcal {F}} ({x_ {n}}) _ {k} = X_ {k}}$ и ${displaystyle {mathcal {F}} ({y_ {n}}) _ {k} = Y_ {k}}$, то для любых комплексных чисел ${displaystyle a, b}$:

${displaystyle {mathcal {F}} ({ax_ {n} + by_ {n}}) _ {k} = aX_ {k} + bY_ {k}}$

Реверс времени и частоты

Изменение времени вспять (т. Е. Замена ${displaystyle n}$ к ${displaystyle N-n}$)^[B] в ${displaystyle x_ {n}}$ соответствует изменению частоты (т. е. ${displaystyle k}$ к ${displaystyle N-k}$).^{[5]:стр.421} Математически, если ${displaystyle {x_ {n}}}$ представляет вектор Икс тогда

если ${displaystyle {mathcal {F}} ({x_ {n}}) _ {k} = X_ {k}}$

тогда ${displaystyle {mathcal {F}} ({x_ {N-n}}) _ {k} = X_ {N-k}}$

Спряжение во времени

Если ${displaystyle {mathcal {F}} ({x_ {n}}) _ {k} = X_ {k}}$ тогда ${displaystyle {mathcal {F}} ({x_ {n} ^ {*}}) _ {k} = X_ {N-k} ^ {*}}$.^{[5]:стр.423}

Реальная и мнимая часть

В этой таблице показаны некоторые математические операции над ${displaystyle x_ {n}}$ во временной области и соответствующие эффекты на его ДПФ ${displaystyle X_ {k}}$ в частотной области.

Свойство	Область времени ${displaystyle x_ {n}}$	Частотный диапазон ${displaystyle X_ {k}}$
Реальная часть времени	${displaystyle Re {left (x_ {n} ight)}}$	${displaystyle {frac {1} {2}} left (X_ {k} + X_ {N-k-1} ^ {*} ight)}$
Воображаемая часть времени	${displaystyle Im {left (x_ {n} ight)}}$	${displaystyle {frac {1} {2i}} left (X_ {k} -X_ {N-k-1} ^ {*} ight)}$
Действительная часть частоты	${displaystyle {frac {1} {2}} left (x_ {n} + x_ {N-n-1} ^ {*} ight)}$	${displaystyle Re {left (X_ {k} ight)}}$
Мнимая часть частоты	${displaystyle {frac {1} {2i}} left (x_ {n} -x_ {N-n-1} ^ {*} ight)}$	${displaystyle Im {left (X_ {k} ight)}}$

Ортогональность

Векторы ${displaystyle u_ {k} = left [left.e ^ {{frac {i2pi} {N}} kn}; ight |; n = 0,1, ldots, N-1ight] ^ {mathsf {T}}}$ для мужчин ортогональный базис по набору N-мерные комплексные векторы:

${displaystyle u_ {k} ^ {mathsf {T}} u_ {k '} ^ {*} = sum _ {n = 0} ^ {N-1} left (e ^ {{frac {i2pi} {N}}) kn} ight) left (e ^ {{frac {i2pi} {N}} (- k ') n} ight) = sum _ {n = 0} ^ {N-1} e ^ {{frac {i2pi} { N}} (k-k ') n} = N ~ дельта _ {kk'}}$

куда ${displaystyle ~ delta _ {kk '}}$ это Дельта Кронекера. (На последнем шаге суммирование тривиально, если ${displaystyle k = k '}$, где это 1 + 1 + ⋅⋅⋅ =N, а в противном случае - геометрическая серия которые можно явно просуммировать для получения нуля.) Это условие ортогональности можно использовать для вывода формулы для IDFT из определения DFT, и оно эквивалентно свойству унитарности, приведенному ниже.

Теорема Планшереля и теорема Парсеваля

Если ${displaystyle X_ {k}}$ и ${displaystyle Y_ {k}}$ являются ДПФ ${displaystyle x_ {n}}$ и ${displaystyle y_ {n}}$ соответственно тогда Теорема Парсеваля состояния:

${displaystyle sum _ {n = 0} ^ {N-1} x_ {n} y_ {n} ^ {*} = {frac {1} {N}} sum _ {k = 0} ^ {N-1} X_ {k} Y_ {k} ^ {*}}$

где звездочка обозначает комплексное сопряжение. Теорема Планшереля является частным случаем теоремы Парсеваля и утверждает:

${displaystyle sum _ {n = 0} ^ {N-1} | x_ {n} | ^ {2} = {frac {1} {N}} sum _ {k = 0} ^ {N-1} | X_ {k} | ^ {2}.}$

Эти теоремы также эквивалентны приведенному ниже условию унитарности.

Периодичность

Периодичность можно показать прямо из определения:

${displaystyle X_ {k + N} riangleq sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} (k + N) n} = sum _ { n = 0} ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} kn} нижняя часть {e ^ {- i2pi n}} _ {1} = sum _ {n = 0 } ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} kn} = X_ {k}.}$

Точно так же можно показать, что формула IDFT приводит к периодическому расширению.

Теорема сдвига

Умножение ${displaystyle x_ {n}}$ по линейная фаза ${displaystyle e ^ {{frac {i2pi (n-1)} {N}} m}}$ для некоторого целого числа м соответствует круговой сдвиг выхода ${displaystyle X_ {k}}$: ${displaystyle X_ {k}}$ заменяется на ${displaystyle X_ {k-m}}$, где нижний индекс интерпретируется по модулю N (т.е. периодически). Точно так же круговой сдвиг входа ${displaystyle x_ {n}}$ соответствует умножению выхода ${displaystyle X_ {k}}$ линейной фазой. Математически, если ${displaystyle {x_ {n}}}$ представляет вектор Икс тогда

если ${displaystyle {mathcal {F}} ({x_ {n}}) _ {k} = X_ {k}}$

тогда ${displaystyle {mathcal {F}} left (left {x_ {n} cdot e ^ {{frac {i2pi} {N}} nm} ight} ight) _ {k} = X_ {k-m}})$

и ${displaystyle {mathcal {F}} left (left {x_ {n-m} ight} ight} ight) _ {k} = X_ {k} cdot e ^ {- {frac {i2pi} {N}} km}}$

Теорема круговой свертки и теорема взаимной корреляции

В теорема свертки для преобразование Фурье с дискретным временем (DTFT) указывает, что свертка двух последовательностей может быть получена как обратное преобразование продукта отдельных преобразований. Важное упрощение происходит, когда одна из последовательностей является N-периодической, обозначенной здесь как ${displaystyle y _ {_ {N}},}$ потому что ${displaystyle scriptstyle {ext {DTFT}} displaystyle {y _ {_ {N}}}}$ отлична от нуля только на дискретных частотах (см. DTFT § Периодические данные), а значит, и его произведение на непрерывную функцию ${displaystyle scriptstyle {ext {DTFT}} displaystyle {x}.}$ Это приводит к значительному упрощению обратного преобразования.

${displaystyle x * y _ {_ {N}} = scriptstyle {m {DTFT}} ^ {- 1} displaystyle left [scriptstyle {m {DTFT}} displaystyle {x} cdot scriptstyle {m {DTFT}} displaystyle {y_ { _ {N}}} ight] = стиль сценария {m {DFT}} ^ {- 1} displaystyle left [scriptstyle {m {DFT}} displaystyle {x _ {_ {N}}} cdot scriptstyle {m {DFT}} displaystyle {y _ {_ {N}}} полет],}$

куда ${displaystyle x _ {_ {N}}}$ это периодическое суммирование из ${displaystyle x}$ последовательность:  ${displaystyle (x _ {_ {N}}) _ {n} riangleq sum _ {m = -infty} ^ {infty} x _ {(n-mN)}.}$

Обычно суммирование ДПФ и обратного ДПФ выполняется по области ${displaystyle [0, N-1].}$ Определение этих ДПФ как ${displaystyle X}$ и ${displaystyle Y,}$ результат:

${displaystyle (x * y _ {_ {N}}) _ {n} riangleq sum _ {ell = -infty} ^ {infty} x_ {ell} cdot (y _ {_ {N}}) _ {n-ell} = underbrace {{mathcal {F}} ^ {- 1}} _ {m {DFT ^ {- 1}}} left {Xcdot Yight} _ {n}.}$

На практике ${displaystyle x}$ последовательность обычно имеет длину N или меньше, и ${displaystyle y _ {_ {N}}}$ является периодическим продолжением N-длины ${displaystyle y}$-последовательность, которая также может быть выражена как круговая функция:

${displaystyle (y _ {_ {N}}) _ {n} = sum _ {p = -infty} ^ {infty} y _ {(n-pN)} = y _ {(noperatorname {mod} N)}, quad nin mathbb {Z}.}$

Тогда свертку можно записать как:

что приводит к интерпретации как круговой свертка ${displaystyle x}$ и ${displaystyle y.}$^[6][7] Его часто используют для эффективного вычисления их линейной свертки. (видеть Круговая свертка, Алгоритмы быстрой свертки, и Сохранение с перекрытием)

Точно так же взаимная корреляция из${displaystyle x}$ и${displaystyle y _ {_ {N}}}$ дан кем-то:

${displaystyle (xstar y _ {_ {N}}) _ {n} riangleq sum _ {ell = -infty} ^ {infty} x_ {ell} ^ {*} cdot (y _ {_ {N}}) _ {n + ell} = {mathcal {F}} ^ {- 1} left {X ^ {*} cdot Yight} _ {n}.}$

Двойственность теоремы свертки

Также можно показать, что:

${displaystyle {mathcal {F}} left {mathbf {xcdot y} ight} _ {k} riangleq sum _ {n = 0} ^ {N-1} x_ {n} cdot y_ {n} cdot e ^ {- i {frac {2pi} {N}} kn}}$

${displaystyle = {frac {1} {N}} (mathbf {X * Y_ {N}}) _ {k} ,,}$ что является круговой сверткой ${displaystyle mathbf {X}}$ и ${displaystyle mathbf {Y}}$.

Тригонометрический интерполяционный полином

В тригонометрический интерполяционный полином

${displaystyle p (t) = {egin {cases} {frac {1} {N}} left [X_ {0} + X_ {1} e ^ {i2pi t} + cdots + X_ {N / 2-1} e ^ {i (N / 2-1) 2pi t} + X_ {N / 2} cos (Npi t) + X_ {N / 2 + 1} e ^ {i (-N / 2 + 1) 2pi t} + cdots + X_ {N-1} e ^ {- i2pi t} ight] & N {ext {even}} {frac {1} {N}} left [X_ {0} + X_ {1} e ^ {i2pi t } + cdots + X_ {lfloor N / 2floor} e ^ {ilfloor N / 2floor 2pi t} + X_ {lfloor N / 2floor +1} e ^ {- ilfloor N / 2floor 2pi t} + cdots + X_ {N-1 } e ^ {- i2pi t} ight] & N {ext {odd}} end {case}}}$

где коэффициенты Икс_k даются ДПФ Икс_п выше, удовлетворяет свойству интерполяции ${displaystyle p (n / N) = x_ {n}}$ за ${displaystyle n = 0, ldots, N-1}$.

Даже для Nобратите внимание, что Компонент Найквиста ${displaystyle {frac {X_ {N / 2}} {N}} cos (Npi t)}$ обрабатывается специально.

Эта интерполяция не уникальный: aliasing подразумевает, что можно добавить N к любой из частот комплексной синусоиды (например, изменение ${displaystyle e ^ {- it}}$ к ${displaystyle e ^ {я (N-1) t}}$ ) без изменения свойства интерполяции, но давая разные ценности между ${displaystyle x_ {n}}$ точки. Однако вышеприведенный выбор типичен, поскольку он обладает двумя полезными свойствами. Во-первых, он состоит из синусоид, частоты которых имеют наименьшие возможные величины: интерполяция ограниченный диапазон. Во-вторых, если ${displaystyle x_ {n}}$ настоящие числа, тогда ${displaystyle p (t)}$ тоже реально.

Напротив, наиболее очевидным полиномом тригонометрической интерполяции является тот, в котором частоты находятся в диапазоне от 0 до ${displaystyle N-1}$ (вместо примерно ${displaystyle -N / 2}$ к ${displaystyle + N / 2}$ как указано выше), аналогично обратной формуле ДПФ. Эта интерполяция делает нет минимизировать наклон, и нет как правило, с реальной стоимостью ${displaystyle x_ {n}}$; его использование - распространенная ошибка.

Унитарный ДПФ

Другой способ взглянуть на ДПФ - отметить, что в приведенном выше обсуждении ДПФ можно выразить как Матрица ДПФ, а Матрица Вандермонда, представил Сильвестр в 1867 г.,

${displaystyle mathbf {F} = {egin {bmatrix} omega _ {N} ^ {0cdot 0} & omega _ {N} ^ {0cdot 1} & ldots & omega _ {N} ^ {0cdot (N-1)} omega _ {N} ^ {1cdot 0} & omega _ {N} ^ {1cdot 1} & ldots & omega _ {N} ^ {1cdot (N-1)} vdots & vdots & ddots & vdots omega _ {N} ^ {(N-1 ) cdot 0} & omega _ {N} ^ {(N-1) cdot 1} & ldots & omega _ {N} ^ {(N-1) cdot (N-1)} end {bmatrix}}}$

куда ${displaystyle omega _ {N} = e ^ {- i2pi / N}}$ примитивный Nй корень единства.

Обратное преобразование затем дается обратной матрицей указанной выше:

${displaystyle mathbf {F} ^ {- 1} = {frac {1} {N}} mathbf {F} ^ {*}}$

С унитарный константы нормализации ${displaystyle 1 / {sqrt {N}}}$, ДПФ становится унитарное преобразование, определяемый унитарной матрицей:

${displaystyle {egin {выравнивается} mathbf {U} & = {frac {1} {sqrt {N}}} mathbf {F} mathbf {U} ^ {- 1} & = mathbf {U} ^ {*} | det (mathbf {U}) | & = 1end {выровнено}}}$

куда ${displaystyle det ()}$ это детерминант функция. Определитель - это произведение собственных значений, которые всегда равны ${displaystyle pm 1}$ или же ${displaystyle pm i}$ как описано ниже. В реальном векторном пространстве унитарное преобразование можно рассматривать как просто жесткое вращение системы координат, и все свойства жесткого вращения можно найти в унитарном ДПФ.

Ортогональность ДПФ теперь выражается как ортонормальность условие (которое возникает во многих областях математики, как описано в корень единства):

${displaystyle sum _ {m = 0} ^ {N-1} U_ {km} U_ {mn} ^ {*} = delta _ {kn}}$

Если Икс определяется как унитарное ДПФ вектора Икс, тогда

${displaystyle X_ {k} = sum _ {n = 0} ^ {N-1} U_ {kn} x_ {n}}$

и Теорема Парсеваля выражается как

${displaystyle sum _ {n = 0} ^ {N-1} x_ {n} y_ {n} ^ {*} = sum _ {k = 0} ^ {N-1} X_ {k} Y_ {k} ^ {*}}$

Если мы рассматриваем ДПФ как просто преобразование координат, которое просто определяет компоненты вектора в новой системе координат, то приведенное выше является просто утверждением, что скалярное произведение двух векторов сохраняется при унитарном преобразовании ДПФ. Для особого случая ${displaystyle mathbf {x} = mathbf {y}}$, это означает, что длина вектора также сохраняется - это просто Теорема Планшереля,

${displaystyle sum _ {n = 0} ^ {N-1} | x_ {n} | ^ {2} = sum _ {k = 0} ^ {N-1} | X_ {k} | ^ {2}}$

Следствие теорема круговой свертки состоит в том, что матрица ДПФ F диагонализирует любой циркулянтная матрица.

Выражение обратного ДПФ через ДПФ

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

Во-первых, мы можем вычислить обратное ДПФ, изменив все входные данные, кроме одного (Дюамель и другие., 1988):

${displaystyle {mathcal {F}} ^ {- 1} ({x_ {n}}) = {frac {1} {N}} {mathcal {F}} ({x_ {N-n}})}$

(Как обычно, индексы интерпретируются по модулю N; таким образом, для ${displaystyle n = 0}$, у нас есть ${displaystyle x_ {N-0} = x_ {0}}$.)

Во-вторых, можно также сопрягать входы и выходы:

${displaystyle {mathcal {F}} ^ {- 1} (mathbf {x}) = {frac {1} {N}} {mathcal {F}} left (mathbf {x} ^ {*} ight) ^ {* }}$

В-третьих, вариант этого трюка сопряжения, который иногда предпочтительнее, поскольку он не требует модификации значений данных, включает в себя замену реальной и мнимой частей (что может быть выполнено на компьютере, просто изменив указатели). Определять ${extstyle operatorname {swap} (x_ {n})}$ в качестве ${displaystyle x_ {n}}$ поменяв местами его реальную и мнимую части - то есть, если ${displaystyle x_ {n} = a + bi}$ тогда ${extstyle operatorname {swap} (x_ {n})}$ является ${displaystyle b + ai}$. Эквивалентно, $имя оператора {своп} (x_ {n})$ равно ${displaystyle ix_ {n} ^ {*}}$. потом

${displaystyle {mathcal {F}} ^ {- 1} (mathbf {x}) = {frac {1} {N}} имя оператора {swap} ({mathcal {F}} (имя оператора {swap} (mathbf {x} )))}$

То есть обратное преобразование такое же, как и прямое преобразование, при этом реальная и мнимая части меняются местами как для ввода, так и для вывода, с точностью до нормализации (Дюамель и другие., 1988).

Уловку сопряжения можно также использовать для определения нового преобразования, тесно связанного с ДПФ, т. Е. инволютивный- то есть противоположное самому себе. Особенно, ${displaystyle T (mathbf {x}) = {mathcal {F}} left (mathbf {x} ^ {*} ight) / {sqrt {N}}}$ явно обратный: ${displaystyle T (T (mathbf {x})) = mathbf {x}}$. Тесно связанная инволютивная трансформация (с коэффициентом (1 + я)/√2) является ${displaystyle H (mathbf {x}) = {mathcal {F}} left ((1 + i) mathbf {x} ^ {*} ight) / {sqrt {2N}}}$, поскольку ${displaystyle (1 + i)}$ факторы в ${displaystyle H (H (mathbf {x}))}$ отменить 2. Для реальных входов ${displaystyle mathbf {x}}$, реальная часть ${displaystyle H (mathbf {x})}$ не что иное, как дискретное преобразование Хартли, что тоже инволютивно.

Собственные значения и собственные векторы

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

Рассмотрим унитарную форму ${displaystyle mathbf {U}}$ определенное выше для ДПФ длины N, куда

${displaystyle mathbf {U} _ {m, n} = {frac {1} {sqrt {N}}} omega _ {N} ^ {(m-1) (n-1)} = {frac {1} { sqrt {N}}} e ^ {- {frac {i2pi} {N}} (m-1) (n-1)}.}$

Эта матрица удовлетворяет матричный полином уравнение:

${displaystyle mathbf {U} ^ {4} = mathbf {I}.}$

Это видно из обратных свойств выше: работа ${displaystyle mathbf {U}}$ дважды дает исходные данные в обратном порядке, поэтому ${displaystyle mathbf {U}}$ четыре раза возвращает исходные данные и, таким образом, единичная матрица. Это означает, что собственные значения ${displaystyle lambda}$ удовлетворяют уравнению:

${displaystyle lambda ^ {4} = 1.}$

Следовательно, собственные значения ${displaystyle mathbf {U}}$ четвертые корни единства: ${displaystyle lambda}$ равно +1, −1, +я, или -я.

Поскольку для этого есть только четыре различных собственных значения ${displaystyle N imes N}$ матрица, у них есть множественность. Кратность дает количество линейно независимый собственные векторы, соответствующие каждому собственному значению. (Есть N независимые собственные векторы; унитарная матрица никогда не дефектный.)

Проблема их множественности была решена McClellan и Parks (1972), хотя позже было показано, что она эквивалентна проблеме, решаемой с помощью Гаусс (Дикинсон и Стейглиц, 1982). Кратность зависит от значения N по модулю 4, и приводится в следующей таблице:

В противном случае характеристический многочлен из ${displaystyle mathbf {U}}$ является:

${displaystyle det (lambda I-mathbf {U}) = (lambda -1) ^ {leftlfloor {frac {N + 4} {4}} ightfloor} (lambda +1) ^ {leftlfloor {frac {N + 2} { 4}} ightfloor} (lambda + i) ^ {leftlfloor {frac {N + 1} {4}} ightfloor} (lambda -i) ^ {leftlfloor {frac {N-1} {4}} ightfloor}.}.$

Нет простой аналитической формулы для общих собственных векторов. Более того, собственные векторы не уникальны, потому что любая линейная комбинация собственных векторов для одного и того же собственного значения также является собственным вектором для этого собственного значения. Различные исследователи предлагали различные варианты собственных векторов, выбранных для удовлетворения таких полезных свойств, как ортогональность и иметь «простые» формы (например, McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candan и другие., 2000; Ханна и другие., 2004; Гуревич, Хадани, 2008).

Прямой подход заключается в дискретизации собственной функции непрерывного преобразование Фурье, из которых самым известным является Функция Гаусса.С периодическое суммирование функции означает дискретизацию ее частотного спектра, а дискретизация означает периодическое суммирование спектра, дискретизированная и периодически суммируемая функция Гаусса дает собственный вектор дискретного преобразования:

• ${displaystyle F (m) = sum _ {kin mathbb {Z}} exp left (- {frac {pi cdot (m + Ncdot k) ^ {2}} {N}} ight)}$.

Выражение в замкнутой форме для ряда может быть выражено как Тета-функции Якоби в качестве

• ${displaystyle F (m) = {frac {1} {sqrt {N}}} vartheta _ {3} left ({frac {pi m} {N}}, exp left (- {frac {pi} {N}}) ight) ight)}$.

Два других простых аналитических собственных вектора в замкнутой форме для специального периода ДПФ N были обнаружены (Kong, 2008):

На период ДПФ N = 2L + 1 = 4K + 1, где K является целым числом, следующий собственный вектор ДПФ:

• ${displaystyle F (m) = prod _ {s = K + 1} ^ {L} left [cos left ({frac {2pi} {N}} might) -cos left ({frac {2pi} {N}} вид ) ight]}$

На период ДПФ N = 2L = 4K, куда K является целым числом, следующий собственный вектор ДПФ:

• ${displaystyle F (m) = sin left ({frac {2pi} {N}} might) prod _ {s = K + 1} ^ {L-1} left [cos left ({frac {2pi} {N}}) might) -cos left ({frac {2pi} {N}} прицел) ight]}$

Выбор собственных векторов матрицы ДПФ стал важным в последние годы для определения дискретного аналога матрицы дробное преобразование Фурье- матрицу ДПФ можно преобразовать в дробные степени, возведя в степень собственные значения (например, Rubio and Santhanam, 2005). Для непрерывное преобразование Фурье, естественными ортогональными собственными функциями являются Функции Эрмита, поэтому различные их дискретные аналоги использовались в качестве собственных векторов ДПФ, такие как Полиномы Кравчука (Атакишиев, Вольф, 1997). Однако «лучший» выбор собственных векторов для определения дробного дискретного преобразования Фурье остается открытым вопросом.

Принципы неопределенности

Принцип вероятностной неопределенности

Если случайная величина Икс_k сдерживается

${displaystyle sum _ {n = 0} ^ {N-1} | X_ {n} | ^ {2} = 1 ~,}$

тогда

${Displaystyle P_ {n} = | X_ {n} | ^ {2}}$

можно рассматривать как дискретный функция массы вероятности из п, с ассоциированной функцией массы вероятности, построенной на основе преобразованной переменной,

${displaystyle Q_ {m} = N | x_ {m} | ^ {2} ~.}$

В случае непрерывных функций ${displaystyle P (x)}$ и ${displaystyle Q (k)}$, то Принцип неопределенности Гейзенберга утверждает, что

${displaystyle D_ {0} (X) D_ {0} (x) geq {frac {1} {16pi ^ {2}}}}$

куда ${displaystyle D_ {0} (X)}$ и ${displaystyle D_ {0} (x)}$ различия ${displaystyle | X | ^ {2}}$ и ${displaystyle | x | ^ {2}}$ соответственно, причем равенство достигается при подходящем нормированном Гауссово распределение. Хотя дисперсии могут быть определены аналогично для ДПФ, аналогичный принцип неопределенности бесполезен, потому что неопределенность не будет инвариантной относительно сдвига. Тем не менее, Массар и Спиндель ввели осмысленный принцип неопределенности.^[8]

Однако Хиршман энтропийная неопределенность будет полезный аналог для случая ДПФ.^[9] Принцип неопределенности Хиршмана выражается через Энтропия Шеннона двух функций вероятности.

В дискретном случае энтропии Шеннона определяются как

${displaystyle H (X) = - sum _ {n = 0} ^ {N-1} P_ {n} ln P_ {n}}$

и

${displaystyle H (x) = - sum _ {m = 0} ^ {N-1} Q_ {m} ln Q_ {m} ~,}$

и энтропийная неопределенность принцип становится^[9]

${displaystyle H (X) + H (x) geq ln (N) ~.}$

Равенство получается при ${displaystyle P_ {n}}$ равны переводам и модуляциям соответственно нормализованного Гребень Кронекера периода ${displaystyle A}$ куда ${displaystyle A}$ любой точный целочисленный делитель ${displaystyle N}$. Функция массы вероятности ${displaystyle Q_ {m}}$ тогда будет пропорционально переведенному соответствующим образом Гребень Кронекера периода ${displaystyle B = N / A}$.^[9]

Принцип детерминированной неопределенности

Существует также хорошо известный принцип детерминированной неопределенности, который использует разреженность сигнала (или количество ненулевых коэффициентов).^[10] Позволять ${displaystyle | x | _ {0}}$ и ${displaystyle | X | _ {0}}$ быть количеством ненулевых элементов временной и частотной последовательностей ${displaystyle x_ {0}, x_ {1}, ldots, x_ {N-1}}$ и ${displaystyle X_ {0}, X_ {1}, ldots, X_ {N-1}}$, соответственно. Потом,

${displaystyle Nleq | x | _ {0} cdot | X | _ {0}.}$

Как непосредственное следствие неравенство средних арифметических и геометрических, также есть ${displaystyle 2 {sqrt {N}} leq | x | _ {0} + | X | _ {0}}$. Было показано, что оба принципа неопределенности являются строгими для специально выбранных последовательностей «пикет-забор» (дискретные последовательности импульсов) и находят практическое применение для приложений восстановления сигнала.^[10]

ДПФ реальных и чисто мнимых сигналов

• Если ${displaystyle x_ {0}, ldots, x_ {N-1}}$ находятся действительные числа, как это часто бывает в практических приложениях, то ДПФ ${displaystyle X_ {0}, ldots, X_ {N-1}}$ является даже симметричный:

${displaystyle x_ {n} в mathbb {R} quad forall nin {0, ldots, N-1} подразумевает X_ {k} = X _ {- kmod N} ^ {*} quad forall kin {0, ldots, N-1 }}$, куда ${displaystyle X ^ {*},}$ обозначает комплексное сопряжение.

Отсюда следует, что для даже ${displaystyle N}$ ${displaystyle X_ {0}}$ и ${displaystyle X_ {N / 2}}$ являются действительными, а остальная часть ДПФ полностью определяется просто ${displaystyle N / 2-1}$ сложные числа.

• Если ${displaystyle x_ {0}, ldots, x_ {N-1}}$ являются чисто мнимыми числами, то ДПФ ${displaystyle X_ {0}, ldots, X_ {N-1}}$ является нечетно симметричный:

${displaystyle x_ {n} в imathbb {R} quad forall nin {0, ldots, N-1} подразумевает X_ {k} = - X _ {- kmod N} ^ {*} quad forall kin {0, ldots, N- 1}}$, куда ${displaystyle X ^ {*},}$ обозначает комплексное сопряжение.

Обобщенное ДПФ (сдвинутая и нелинейная фаза)

Можно сдвинуть дискретизацию преобразования во временной и / или частотной области на некоторые реальные сдвиги. а и б, соответственно. Иногда это называют обобщенное ДПФ (или же GDFT), также называемый сдвинутый ДПФ или же смещение ДПФ, и имеет свойства, аналогичные обычному ДПФ:

${displaystyle X_ {k} = sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} (k + b) (n + a)} quad quad k = 0, точки, N-1.}$

Чаще всего смены ${displaystyle 1/2}$ (половина выборки). В то время как обычное ДПФ соответствует периодическому сигналу как во временной, так и в частотной областях, ${displaystyle a = 1/2}$ производит сигнал, который является антипериодическим в частотной области (${displaystyle X_ {k + N} = - X_ {k}}$) и наоборот для ${displaystyle b = 1/2}$Таким образом, частный случай ${displaystyle a = b = 1/2}$ известен как нечетное время нечетная частота дискретное преобразование Фурье (или O² Такие сдвинутые преобразования чаще всего используются для симметричных данных, чтобы представить различные граничные симметрии, а для вещественно-симметричных данных они соответствуют разным формам дискретных данных. косинус и синус трансформирует.

Еще один интересный выбор ${displaystyle a = b = - (N-1) / 2}$, который называется центрированный ДПФ (или же CDFT). Центрированное ДПФ обладает тем полезным свойством, что при N кратно четырем, все четыре его собственных значения (см. выше) имеют равную кратность (Rubio and Santhanam, 2005)^[11]

Термин GDFT также используется для нелинейных фазовых расширений DFT. Следовательно, метод GDFT обеспечивает обобщение для ортогональных блочных преобразований с постоянной амплитудой, включая линейные и нелинейные типы фазы. GDFT - это структура для улучшения свойств традиционной DFT во временной и частотной области, например авто / кросс-корреляции, путем добавления правильно разработанной функции формирования фазы (нелинейной, в общем) к исходным линейным функциям фазы (Akansu and Agirman-Tosun, 2010).^[12]

Дискретное преобразование Фурье можно рассматривать как частный случай z-преобразование, вычисляемая на единичной окружности в комплексной плоскости; более общие z-преобразования соответствуют сложный сдвиги а и б над.

Многомерное ДПФ

Обычное ДПФ преобразует одномерную последовательность или множество ${displaystyle x_ {n}}$ это функция ровно одной дискретной переменной п. Многомерное ДПФ многомерного массива ${displaystyle x_ {n_ {1}, n_ {2}, dots, n_ {d}}}$ это функция d дискретные переменные ${displaystyle n_ {ell} = 0,1, точки, N_ {ell} -1}$ за ${displaystyle ell}$ в ${displaystyle 1,2, dots, d}$ определяется:

${displaystyle X_ {k_ {1}, k_ {2}, dots, k_ {d}} = sum _ {n_ {1} = 0} ^ {N_ {1} -1} left (omega _ {N_ {1}) } ^ {~ k_ {1} n_ {1}} сумма _ {n_ {2} = 0} ^ {N_ {2} -1} осталось (омега _ {N_ {2}} ^ {~ k_ {2} n_ {2}} cdots sum _ {n_ {d} = 0} ^ {N_ {d} -1} omega _ {N_ {d}} ^ {~ k_ {d} n_ {d}} cdot x_ {n_ {1 }, n_ {2}, точки, n_ {d}} ight) ight) ,,}$

куда ${displaystyle omega _ {N_ {ell}} = exp (-i2pi / N_ {ell})}$ как указано выше и d выходные индексы запускаются из ${displaystyle k_ {ell} = 0,1, точки, N_ {ell} -1}$. Более компактно это выражается в вектор обозначение, где мы определяем ${displaystyle mathbf {n} = (n_ {1}, n_ {2}, dots, n_ {d})}$ и ${displaystyle mathbf {k} = (k_ {1}, k_ {2}, dots, k_ {d})}$ в качестве d-мерные векторы индексов от 0 до ${displaystyle mathbf {N} -1}$, который мы определяем как ${displaystyle mathbf {N} -1 = (N_ {1} -1, N_ {2} -1, точки, N_ {d} -1)}$:

${displaystyle X_ {mathbf {k}} = sum _ {mathbf {n} = mathbf {0}} ^ {mathbf {N} -1} e ^ {- i2pi mathbf {k} cdot (mathbf {n} / mathbf { N})} x_ {mathbf {n}} ,,}$

где разделение ${displaystyle mathbf {n} / mathbf {N}}$ определяется как ${displaystyle mathbf {n} / mathbf {N} = (n_ {1} / N_ {1}, точки, n_ {d} / N_ {d})}$ выполняется поэлементно, а сумма обозначает набор вложенных суммирований выше.

Обратное к многомерному ДПФ аналогично одномерному случаю определяется следующим образом:

${displaystyle x_ {mathbf {n}} = {frac {1} {prod _ {ell = 1} ^ {d} N_ {ell}}} sum _ {mathbf {k} = mathbf {0}} ^ {mathbf { N} -1} e ^ {i2pi mathbf {n} cdot (mathbf {k} / mathbf {N})} X_ {mathbf {k}} ,.}$

Поскольку одномерный ДПФ выражает ввод ${displaystyle x_ {n}}$ как суперпозиция синусоид, многомерное ДПФ выражает входные данные как суперпозицию плоские волны, или многомерные синусоиды. Направление колебаний в пространстве ${displaystyle mathbf {k} / mathbf {N}}$. Амплитуды ${displaystyle X_ {mathbf {k}}}$. Это разложение имеет большое значение для всего от цифровая обработка изображений (двумерный) к решению уравнения в частных производных. Решение разбивается на плоские волны.

Многомерное ДПФ можно вычислить с помощью сочинение последовательности одномерных ДПФ по каждому измерению. В двумерном случае ${displaystyle x_ {n_ {1}, n_ {2}}}$ то ${displaystyle N_ {1}}$ независимых ДПФ строк (т. е. вдоль ${displaystyle n_ {2}}$) сначала вычисляются для формирования нового массива ${displaystyle y_ {n_ {1}, k_ {2}}}$. Тогда ${displaystyle N_ {2}}$ независимых ДПФ у по колоннам (по ${displaystyle n_ {1}}$) вычисляются для формирования окончательного результата ${displaystyle X_ {k_ {1}, k_ {2}}}$. В качестве альтернативы можно сначала вычислить столбцы, а затем строки. Порядок несущественен, потому что вложенные суммирования выше ездить.

Таким образом, алгоритм вычисления одномерного ДПФ достаточен для эффективного вычисления многомерного ДПФ. Этот подход известен как строка столбец алгоритм. Есть также по сути многомерные алгоритмы БПФ.

Многомерное ДПФ с реальным вводом

Для исходных данных ${displaystyle x_ {n_ {1}, n_ {2}, dots, n_ {d}}}$ состоящий из действительные числа, выходы ДПФ имеют сопряженную симметрию, аналогичную одномерному случаю выше:

${displaystyle X_ {k_ {1}, k_ {2}, dots, k_ {d}} = X_ {N_ {1} -k_ {1}, N_ {2} -k_ {2}, dots, N_ {d}) -k_ {d}} ^ {*},}$

где звездочка снова означает комплексное сопряжение, а ${displaystyle ell}$-й нижний индекс снова интерпретируется по модулю ${displaystyle N_ {ell}}$ (за ${displaystyle ell = 1,2, ldots, d}$).

Приложения

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

Спектральный анализ

Когда ДПФ используется для спектральный анализ сигналов, то ${displaystyle {x_ {n}},}$ последовательность обычно представляет собой конечный набор равномерно распределенных временных отсчетов некоторого сигнала. ${displaystyle x (t),}$, куда ${displaystyle t}$ представляет время. Преобразование непрерывного времени в отсчеты (дискретное время) изменяет базовый преобразование Фурье из ${displaystyle x (t)}$ в преобразование Фурье с дискретным временем (DTFT), что обычно влечет за собой искажение, называемое сглаживание. Выбор подходящей частоты дискретизации (см. Курс Найквиста) является ключом к минимизации этого искажения. Точно так же преобразование очень длинной (или бесконечной) последовательности в управляемый размер влечет за собой тип искажения, называемый утечка, что проявляется в потере детализации (или разрешения) в DTFT. Выбор подходящей длины подпоследовательности является первичным ключом к минимизации этого эффекта. Когда доступных данных (и времени на их обработку) больше, чем количество, необходимое для достижения желаемого разрешения по частоте, стандартным методом является выполнение нескольких ДПФ, например, для создания спектрограмма. Если желаемый результат представляет собой спектр мощности, а в данных присутствует шум или случайность, усреднение составляющих величины нескольких ДПФ является полезной процедурой для уменьшения отклонение спектра (также называемый периодограмма в контексте); два примера таких методов: Метод Велча и Бартлетт метод; общий предмет оценки спектра мощности зашумленного сигнала называется спектральная оценка.

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

• Процедуру иногда называют заполнение нулями, которая является конкретной реализацией, используемой вместе с быстрое преобразование Фурье (БПФ) алгоритм. Неэффективность выполнения умножения и сложения с нулевыми «выборками» более чем компенсируется внутренней эффективностью БПФ.
• Как уже говорилось, утечка накладывает ограничение на собственное разрешение ДПФ, поэтому существует практический предел преимуществ, которые можно получить от мелкозернистого ДПФ.

Банк фильтров

Видеть § Банки фильтров БПФ и § Выборка DTFT.

Сжатие данных

Область цифровой обработки сигналов в значительной степени зависит от операций в частотной области (то есть от преобразования Фурье). Например, несколько с потерями Методы сжатия изображения и звука используют дискретное преобразование Фурье: сигнал разрезается на короткие сегменты, каждый преобразуется, а затем коэффициенты Фурье высоких частот, которые считаются незаметными, отбрасываются. Декомпрессор вычисляет обратное преобразование на основе этого уменьшенного числа коэффициентов Фурье. (Приложения сжатия часто используют специализированную форму ДПФ, дискретное косинусное преобразование или иногда модифицированное дискретное косинусное преобразование.) Однако некоторые относительно недавние алгоритмы сжатия используют вейвлет-преобразования, которые дают более равномерный компромисс между временной и частотной областями, чем полученный путем разделения данных на сегменты и преобразования каждого сегмента. В случае JPEG2000, это позволяет избежать ложных функций изображения, которые появляются, когда изображения сильно сжаты с исходным JPEG.

Уравнения с частными производными

Дискретные преобразования Фурье часто используются для решения уравнения в частных производных, где снова ДПФ используется как приближение для Ряд Фурье (которое восстанавливается в пределе бесконечного N). Преимущество этого подхода в том, что он расширяет сигнал в комплексные экспоненты. ${displaystyle e ^ {inx}}$, которые являются собственными функциями дифференцирования: ${displaystyle {{ext {d}} {ig (} e ^ {inx} {ig)}} / {ext {d}} x = ine ^ {inx}}$. Таким образом, в представлении Фурье дифференцирование выполняется просто - мы просто умножаем на ${displaystyle in}$. (Однако выбор ${displaystyle n}$ не уникален из-за алиасинга; чтобы метод был сходимым, выбор аналогичен выбору в тригонометрическая интерполяция следует использовать раздел выше.) A линейное дифференциальное уравнение с постоянными коэффициентами превращается в легко решаемое алгебраическое уравнение. Затем используется обратное ДПФ для преобразования результата обратно в обычное пространственное представление. Такой подход называется спектральный метод.

Полиномиальное умножение

Предположим, мы хотим вычислить полиномиальное произведение c(Икс) = а(Икс) · б(Икс). Обычное произведение для коэффициентов c включает линейную (ациклическую) свертку, при которой индексы не «зацикливаются». Это можно переписать как циклическую свертку, взяв векторы коэффициентов для а(Икс) и б(Икс) с постоянным членом сначала, затем добавляя нули так, чтобы результирующие векторы коэффициентов а и б иметь размер d > град (а(Икс)) + град (б(Икс)). Потом,

${displaystyle mathbf {c} = mathbf {a} * mathbf {b}}$

Где c - вектор коэффициентов при c(Икс), а оператор свертки ${displaystyle *,}$ определяется так

${displaystyle c_ {n} = sum _ {m = 0} ^ {n} a_ {m} b_ {n-m mathrm {mod} d} qquad qquad qquad n = 0,1dots, d-1}$

Но свертка становится умножением под ДПФ:

${displaystyle {mathcal {F}} (mathbf {c}) = {mathcal {F}} (mathbf {a}) {mathcal {F}} (mathbf {b})}$

Здесь векторное произведение берется поэлементно. Таким образом, коэффициенты полинома произведения c(Икс) - это просто члены 0, ..., deg (а(Икс)) + град (б(Икс)) вектора коэффициентов

${displaystyle mathbf {c} = {mathcal {F}} ^ {- 1} ({mathcal {F}} (mathbf {a}) {mathcal {F}} (mathbf {b})).}$