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

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

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

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

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

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

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

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

Определение

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

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

$X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi {\tfrac {k}{N}}n}$    

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

Преобразование иногда обозначается символом ${\mathcal {F}}$, как в $\mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}$ или ${\mathcal {F}}\left(\mathbf {x} \right)$ или ${\mathcal {F}}\mathbf {x}$.

Уравнение 1 можно интерпретировать или вывести по-разному, например:

• Он полностью описывает преобразование Фурье дискретного времени (DTFT) $N$-периодическая последовательность, состоящая только из дискретных частотных составляющих. ( Использование DTFT с периодическими данными )
• Он также может предоставлять равномерно распределенные выборки непрерывного DTFT последовательности конечной длины. ( § Выборка DTFT )
• Это взаимная корреляция входной последовательности , $x_{n}$, и комплексная синусоида на частоте ${\textstyle {\frac {k}{N}}.}$ Таким образом, он действует как согласованный фильтр для этой частоты.
• Это дискретный аналог формулы для коэффициентов ряда Фурье :

  $C_{k}={\frac {1}{P}}\int _{P}x(t)e^{-i2\pi {\tfrac {k}{P}}t}\,dt.$

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

Обратное преобразование определяется следующим образом:

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

$x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}\cdot e^{i2\pi {\tfrac {k}{N}}n}$     ( Уравнение 2 )

Уравнение 2 . это также $N$-периодический (по индексу n). В уравнении 2 каждый $X_{k}$ - комплексное число, полярные координаты которого представляют собой амплитуду и фазу комплексной синусоидальной составляющей. $\left(e^{i2\pi {\tfrac {k}{N}}n}\right)$ функции $x_{n}.$ (см. Дискретный ряд Фурье синусоиды ). Частота равна $k$ циклов в $N$ образцы.

Коэффициент нормализации, умножающий DFT и IDFT (здесь 1 и ${\tfrac {1}{N}}$) и знаки показателей являются наиболее распространенными соглашениями . Единственные фактические требования этих соглашений заключаются в том, чтобы ДПФ и ИДПФ имели показатели степени противоположного знака и чтобы произведение их коэффициентов нормализации было ${\tfrac {1}{N}}.$ Необычная нормализация ${\sqrt {\tfrac {1}{N}}}$ как для ДПФ, так и для IDFT, пара преобразований становится унитарной.

Пример

В этом примере показано, как применить ДПФ к последовательности длины $N=4$ и входной вектор

$$\mathbf {x} ={\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}1\\2-i\\-i\\-1+2i\end{pmatrix}}.$$

Вычисление ДПФ $\mathbf {x}$ используя уравнение 1

$${\begin{aligned}X_{0}&=e^{-i2\pi 0\cdot 0/4}\cdot 1+e^{-i2\pi 0\cdot 1/4}\cdot (2-i)+e^{-i2\pi 0\cdot 2/4}\cdot (-i)+e^{-i2\pi 0\cdot 3/4}\cdot (-1+2i)=2\\X_{1}&=e^{-i2\pi 1\cdot 0/4}\cdot 1+e^{-i2\pi 1\cdot 1/4}\cdot (2-i)+e^{-i2\pi 1\cdot 2/4}\cdot (-i)+e^{-i2\pi 1\cdot 3/4}\cdot (-1+2i)=-2-2i\\X_{2}&=e^{-i2\pi 2\cdot 0/4}\cdot 1+e^{-i2\pi 2\cdot 1/4}\cdot (2-i)+e^{-i2\pi 2\cdot 2/4}\cdot (-i)+e^{-i2\pi 2\cdot 3/4}\cdot (-1+2i)=-2i\\X_{3}&=e^{-i2\pi 3\cdot 0/4}\cdot 1+e^{-i2\pi 3\cdot 1/4}\cdot (2-i)+e^{-i2\pi 3\cdot 2/4}\cdot (-i)+e^{-i2\pi 3\cdot 3/4}\cdot (-1+2i)=4+4i\end{aligned}}$$

приводит к

$$\mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}2\\-2-2i\\-2i\\4+4i\end{pmatrix}}.$$

Свойства

Линейность

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

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

частоты

Обращение времени (т.е. замена $n$ к $N-n$) в $x_{n}$ соответствует изменению частоты (т.е. $k$ к $N-k$). Математически, если $\{x_{n}\}$ представляет вектор x , тогда

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

затем ${\mathcal {F}}(\{x_{N-n}\})_{k}=X_{N-k}$

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

Если ${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$ затем ${\mathcal {F}}(\{x_{n}^{*}\})_{k}=X_{N-k}^{*}$.

Действительная и мнимая часть

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

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

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

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

$u_{k}^{\mathsf {T}}u_{k'}^{*}=\sum _{n=0}^{N-1}\left(e^{{\frac {i2\pi }{N}}kn}\right)\left(e^{{\frac {i2\pi }{N}}(-k')n}\right)=\sum _{n=0}^{N-1}e^{{\frac {i2\pi }{N}}(k-k')n}=N~\delta _{kk'}$

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

Парсеваля

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

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

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

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

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

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

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

$X_{k+N}\ \triangleq \ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}\underbrace {e^{-i2\pi n}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}=X_{k}.$

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

Теорема

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

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

затем ${\mathcal {F}}\left(\left\{x_{n}\cdot e^{{\frac {i2\pi }{N}}nm}\right\}\right)_{k}=X_{k-m}$

и ${\mathcal {F}}\left(\left\{x_{n-m}\right\}\right)_{k}=X_{k}\cdot e^{-{\frac {i2\pi }{N}}km}$

взаимной корреляции

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

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

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

где $x_{_{N}}$ представляет собой суммирование периодическое $x$ последовательность : $(x_{_{N}})_{n}\ \triangleq \sum _{m=-\infty }^{\infty }x_{(n-mN)}.$

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

$(x*y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }\cdot (y_{_{N}})_{n-\ell }=\underbrace {{\mathcal {F}}^{-1}} _{\rm {DFT^{-1}}}\left\{X\cdot Y\right\}_{n}.$

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

$(y_{_{N}})_{n}=\sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{(n\operatorname {mod} N)},\quad n\in \mathbb {Z} .$

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

${\mathcal {F}}^{-1}\left\{X\cdot Y\right\}_{n}=\sum _{\ell =0}^{N-1}x_{\ell }\cdot y_{_{(n-\ell )\operatorname {mod} N}}$

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

Аналогично, взаимная корреляция $x$ и $y_{_{N}}$ дан кем-то :

$(x\star y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }^{*}\cdot (y_{_{N}})_{n+\ell }={\mathcal {F}}^{-1}\left\{X^{*}\cdot Y\right\}_{n}.$

дискретного

Как видно выше, дискретное преобразование Фурье обладает фундаментальным свойством преобразования свертки в покомпонентное произведение. Естественный вопрос: единственный ли он обладает такой способностью? Было показано что любое линейное преобразование, превращающее свертку в поточечное произведение, является ДПФ с точностью до перестановки коэффициентов. Поскольку число перестановок n элементов равно n!, существует ровно n! линейные и обратимые карты с тем же фундаментальным свойством, что и ДПФ, в отношении свертки.

свертки

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

${\mathcal {F}}\left\{\mathbf {x\cdot y} \right\}_{k}\ \triangleq \sum _{n=0}^{N-1}x_{n}\cdot y_{n}\cdot e^{-i{\frac {2\pi }{N}}kn}$

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

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

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

$p(t)={\begin{cases}{\frac {1}{N}}\left[X_{0}+X_{1}e^{i2\pi t}+\cdots +X_{N/2-1}e^{i2\pi (N/2-1)t}+X_{N/2}\cos(N\pi t)+X_{N/2+1}e^{-i2\pi (N/2-1)t}+\cdots +X_{N-1}e^{-i2\pi t}\right]&N{\text{ even}}\\{\frac {1}{N}}\left[X_{0}+X_{1}e^{i2\pi t}+\cdots +X_{(N-1)/2}e^{i2\pi (N-1)t}+X_{(N+1)/2}e^{-i2\pi (N-1)t}+\cdots +X_{N-1}e^{-i2\pi t}\right]&N{\text{ odd}}\end{cases}}$

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

для четного N Обратите внимание, что компонент Найквиста ${\textstyle {\frac {X_{N/2}}{N}}\cos(N\pi t)}$ обрабатывается специально.

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

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

Унитарное ДПФ

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

$\mathbf {F} ={\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\cdots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\cdots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\cdots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}$

где $\omega _{N}=e^{-i2\pi /N}$ является примитивным корнем N- й степени из единицы .

Например, в случае, когда $N=2$, $\omega _{N}=e^{-i\pi }=-1$, и

$\mathbf {F} ={\begin{bmatrix}1&1\\1&-1\\\end{bmatrix}},$

(которая является матрицей Адамара ) или когда $N=4$ как и в дискретном преобразовании Фурье § Пример выше, $\omega _{N}=e^{-i\pi /2}=-i$, и

$\mathbf {F} ={\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\\\end{bmatrix}}.$

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

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

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

${\begin{aligned}\mathbf {U} &={\frac {1}{\sqrt {N}}}\mathbf {F} \\\mathbf {U} ^{-1}&=\mathbf {U} ^{*}\\\left|\det(\mathbf {U} )\right|&=1\end{aligned}}$

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

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

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

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

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

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

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

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

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

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

ДПФ через

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

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

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

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

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

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

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

${\mathcal {F}}^{-1}(\mathbf {x} )={\frac {1}{N}}\operatorname {swap} ({\mathcal {F}}(\operatorname {swap} (\mathbf {x} )))$

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

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

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

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

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

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

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

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

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

$\lambda ^{4}=1.$

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

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

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

Кратности собственных значений λ унитарной матрицы ДПФ U как функция размера преобразования N (в терминах целого числа m ).

размер Н	λ = +1	λ = −1	λ = - я	λ = + я
4 m	м + 1	м	м	м - 1
4 m + 1	м + 1	м	м	м
4 m + 2	м + 1	м + 1	м	м
4 m + 3	м + 1	м + 1	м + 1	м

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

$\det(\lambda I-\mathbf {U} )=(\lambda -1)^{\left\lfloor {\tfrac {N+4}{4}}\right\rfloor }(\lambda +1)^{\left\lfloor {\tfrac {N+2}{4}}\right\rfloor }(\lambda +i)^{\left\lfloor {\tfrac {N+1}{4}}\right\rfloor }(\lambda -i)^{\left\lfloor {\tfrac {N-1}{4}}\right\rfloor }.$

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

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

• $F(m)=\sum _{k\in \mathbb {Z} }\exp \left(-{\frac {\pi \cdot (m+N\cdot k)^{2}}{N}}\right).$

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

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

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

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

• $F(m)=\prod _{s=K+1}^{L}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]$

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

• $F(m)=\sin \left({\frac {2\pi }{N}}m\right)\prod _{s=K+1}^{L-1}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]$

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

неопределенности

неопределенности

Если случайная величина X _k ограничена

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

затем

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

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

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

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

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

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

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

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

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

и

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

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

$H(X)+H(x)\geq \ln(N).$

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

неопределенности

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

$N\leq \left\|x\right\|_{0}\cdot \left\|X\right\|_{0}.$

Непосредственным следствием неравенства средних арифметических и геометрических является также $2{\sqrt {N}}\leq \left\|x\right\|_{0}+\left\|X\right\|_{0}$. Было показано, что оба принципа неопределенности справедливы для специально выбранных последовательностей «часток» (дискретных последовательностей импульсов) и находят практическое применение для приложений восстановления сигналов.

реальных и чисто

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

$x_{n}\in \mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}$, где $X^{*}\,$ обозначает комплексное сопряжение .

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

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

$x_{n}\in i\mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=-X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}$, где $X^{*}\,$ обозначает комплексное сопряжение .

(сдвинутая и нелинейная

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

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}(k+b)(n+a)}\quad \quad k=0,\dots ,N-1.$

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

Еще один интересный выбор $a=b=-(N-1)/2$, которое называется центрированным ДПФ (или CDFT ). Центрированное ДПФ обладает полезным свойством: когда N кратно четырем, все четыре его собственных значения (см. Выше) имеют одинаковую кратность (Рубио и Сантанам, 2005).

Термин GDFT также используется для обозначения нелинейного фазового расширения DFT. Следовательно, метод GDFT обеспечивает обобщение ортогональных блочных преобразований с постоянной амплитудой, включая линейные и нелинейные типы фаз. GDFT — это основа улучшить свойства традиционного ДПФ во временной и частотной области, например, авто/взаимную корреляцию, путем добавления правильно разработанной функции формирования фазы (в целом нелинейной) к исходным линейным фазовым функциям (Акансу и Агирман-Тосун, 2010).

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

Дискретные преобразования, встроенные во время и пространство.

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

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

$X_{k_{1},k_{2},\dots ,k_{d}}=\sum _{n_{1}=0}^{N_{1}-1}\left(\omega _{N_{1}}^{~k_{1}n_{1}}\sum _{n_{2}=0}^{N_{2}-1}\left(\omega _{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},\dots ,n_{d}}\right)\right),$

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

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

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

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

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

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

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

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

реальным

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

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

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

Приложения

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

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

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

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

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

Оптика, дифракция и томография

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

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

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

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

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

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

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

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

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

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

Где c — вектор коэффициентов для c ( x ), а оператор свертки $*\,$ определяется так

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

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

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

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

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

С помощью быстрого преобразования Фурье полученный алгоритм выполняет O ( N log N ) арифметических операций. Из-за своей простоты и скорости алгоритм БПФ Кули-Тьюки , который ограничен составными для операции преобразования часто выбирается размерами. В этом случае d следует выбрать как наименьшее целое число, большее, чем сумма степеней входного полинома, которую можно разложить на небольшие простые множители (например, 2, 3 и 5, в зависимости от реализации БПФ).

Умножение больших целых чисел

Самые быстрые известные алгоритмы умножения очень больших целых чисел используют метод полиномиального умножения, описанный выше. Целые числа можно рассматривать как значение полинома, вычисляемого конкретно по базе чисел, при этом коэффициенты полинома соответствуют цифрам в этой базе (например, $123=1\cdot 10^{2}+2\cdot 10^{1}+3\cdot 10^{0}$). После полиномиального умножения умножение завершается относительно простым шагом переноса.

Свертка

Когда данные свернуты с помощью функции с широкой поддержкой, например, для понижающей дискретизации с большим коэффициентом выборки, из-за теоремы свертки и алгоритма БПФ может быть быстрее преобразовать их, умножить поточечно на преобразование фильтра, а затем обратить трансформируйте его. Альтернативно, хороший фильтр получается путем простого усечения преобразованных данных и повторного преобразования сокращенного набора данных.

дискретных преобразований

Некоторые пары ДПФ

$x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{i2\pi kn/N}$	$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}$	Примечание
$x_{n}e^{i2\pi n\ell /N}\,$	$X_{k-\ell }\,$	Теорема о сдвиге частоты
$x_{n-\ell }\,$	$X_{k}e^{-i2\pi k\ell /N}\,$	Теорема о сдвиге времени
$x_{n}\in \mathbb {R}$	$X_{k}=X_{N-k}^{*}\,$	Реальное ДПФ
$a^{n}\,$	$\left\{{\begin{matrix}N&{\mbox{if }}a=e^{i2\pi k/N}\\{\frac {1-a^{N}}{1-a\,e^{-i2\pi k/N}}}&{\mbox{otherwise}}\end{matrix}}\right.$	из геометрической прогрессии формулы
${N-1 \choose n}\,$	$\left(1+e^{-i2\pi k/N}\right)^{N-1}\,$	из биномиальной теоремы
$\left\{{\begin{matrix}{\frac {1}{W}}&{\mbox{if }}2n<W{\mbox{ or }}2(N-n)<W\\0&{\mbox{otherwise}}\end{matrix}}\right.$	$\left\{{\begin{matrix}1&{\mbox{if }}k=0\\{\frac {\sin \left({\frac {\pi Wk}{N}}\right)}{W\sin \left({\frac {\pi k}{N}}\right)}}&{\mbox{otherwise}}\end{matrix}}\right.$	$x_{n}$ — прямоугольная оконная функция W точек с центром в n = 0, где W — нечетное целое число , и $X_{k}$ — это sinc -подобная функция (в частности, $X_{k}$ является ядром Дирихле )
$\sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi }{cN}}\cdot (n+N\cdot j)^{2}\right)$	${\sqrt {cN}}\cdot \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi c}{N}}\cdot (k+N\cdot j)^{2}\right)$	Дискретизация и периодическое суммирование масштабированных функций Гаусса для $c>0$. Поскольку либо $c$ или ${\frac {1}{c}}$ больше единицы и, таким образом, гарантирует быструю сходимость одного из двух рядов при больших $c$ вы можете вычислить частотный спектр и преобразовать его во временную область, используя дискретное преобразование Фурье.

Обобщения

Теория представлений

Дополнительная информация: Теория представлений конечных групп § Дискретное преобразование Фурье.

ДПФ можно интерпретировать как комплексное представление конечной циклической группы . Другими словами, последовательность $n$ Комплексные числа можно рассматривать как элемент $n$-мерное комплексное пространство $\mathbb {C} ^{n}$ или, что эквивалентно, функция $f$ из конечной циклической группы порядка $n$ к комплексным числам, $\mathbb {Z} _{n}\mapsto \mathbb {C}$. Так $f$ является функцией класса на конечной циклической группе и, следовательно, может быть выражена как линейная комбинация неприводимых характеров этой группы, которые являются корнями из единицы.

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

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

Другие поля

Основные статьи: Дискретное преобразование Фурье (общее) и теоретико-числовое преобразование

Многие свойства ДПФ зависят только от того факта, что $e^{-{\frac {i2\pi }{N}}}$ — примитивный корень из единицы , иногда обозначаемый $\omega _{N}$ или $W_{N}$ (так что $\omega _{N}^{N}=1$). К таким свойствам относятся полнота, ортогональность, свойства Планшереля/Парсеваля, периодичность, сдвиг, свертка и унитарность, а также многие алгоритмы БПФ. По этой причине дискретное преобразование Фурье может быть определено с использованием корней из единицы в полях, отличных от комплексных чисел, и такие обобщения обычно называются теоретико-числовыми преобразованиями (NTT) в случае конечных полей . Дополнительные сведения см. в разделах теоретико-числовое преобразование и дискретное преобразование Фурье (общее) .

конечные

Основная статья: преобразование Фурье на конечных группах

Стандартное ДПФ действует на последовательность x ₀ , x ₁ , ..., x _{N −1} комплексных чисел, которую можно рассматривать как функцию {0, 1, ..., N − 1} → C . Многомерное ДПФ действует на многомерные последовательности, которые можно рассматривать как функции.

$\{0,1,\ldots ,N_{1}-1\}\times \cdots \times \{0,1,\ldots ,N_{d}-1\}\to \mathbb {C} .$

Это предполагает обобщение преобразований Фурье на произвольных конечных группах , которые действуют на функции G → C , где G — конечная группа . В этой структуре стандартное ДПФ рассматривается как преобразование Фурье циклической группы , тогда как многомерное ДПФ представляет собой преобразование Фурье прямой суммы циклических групп.

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

Альтернативы

Основная статья: Дискретное вейвлет-преобразование

Дополнительная информация: Дискретное вейвлет-преобразование § Сравнение с преобразованием Фурье

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

См. также

• Сопутствующая матрица
• Матрица ДПФ
• Быстрое преобразование Фурье
• ФФТПАК
• ФФТВ
• Обобщения матриц Паули
• Спектральный анализ методом наименьших квадратов
• Список преобразований, связанных с Фурье
• Многомерное преобразование
• Зак трансформирует
• Квантовое преобразование Фурье

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

• Бригам, Э. Оран (1988). Быстрое преобразование Фурье и его приложения . Энглвуд Клиффс, Нью-Джерси: Прентис Холл. ISBN  978-0-13-307505-2 .
• Смит, Стивен В. (1999). «Глава 8: Дискретное преобразование Фурье» . Руководство для ученых и инженеров по цифровой обработке сигналов (второе изд.). Сан-Диего, Калифорния: Калифорнийское техническое издательство. ISBN  978-0-9660176-3-2 .
• Кормен, Томас Х .; Чарльз Э. Лейзерсон ; Рональд Л. Ривест ; Клиффорд Стейн (2001). «Глава 30: Полиномы и БПФ». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 822–848 . ISBN  978-0-262-03293-3 . особенно раздел 30.2: ДПФ и БПФ, стр. 830–838.
• П. Дюамель; Б. Пирон; Дж. М. Эчето (1988). «О вычислении обратного ДПФ». Транзакции IEEE по акустике, речи и обработке сигналов . 36 (2): 285–286. дои : 10.1109/29.1519 .
• Дж. Х. Макклеллан; Т. В. Паркс (1972). «Собственные значения и собственные векторы дискретного преобразования Фурье». Транзакции IEEE по аудио и электроакустике . 20 (1): 66–74. дои : 10.1109/ТАУ.1972.1162342 .
• Брэдли В. Дикинсон; Кеннет Стейглиц (1982). «Собственные векторы и функции дискретного преобразования Фурье» (PDF) . Транзакции IEEE по акустике, речи и обработке сигналов . 30 (1): 25–31. CiteSeerX   10.1.1.434.5279 . дои : 10.1109/ТАССП.1982.1163843 . (Обратите внимание, что в этой статье есть очевидная опечатка в таблице кратностей собственных значений: столбцы + i /- i поменяны местами. Правильную таблицу можно найти в McClellan and Parks, 1972, и ее легко подтвердить численно.)
• Ф. А. Грюнбаум (1982). «Собственные векторы дискретного преобразования Фурье» . Журнал математического анализа и приложений . 88 (2): 355–363. дои : 10.1016/0022-247X(82)90199-8 .
• Натиг М. Атакишиев; Курт Бернард Вольф (1997). «Дробное преобразование Фурье-Кравчука». Журнал Оптического общества Америки А. 14 (7): 1467–1477. Бибкод : 1997JOSSA..14.1467A . дои : 10.1364/JOSSAA.14.001467 .
• К. Кандан; М.А. Кутай; ХМОзактас (2000). «Дискретное дробное преобразование Фурье» (PDF) . Транзакции IEEE по обработке сигналов . 48 (5): 1329–1337. Бибкод : 2000ITSP...48.1329C . дои : 10.1109/78.839980 . hdl : 11693/11130 . Архивировано (PDF) из оригинала 21 сентября 2017 г.
• Магди Тауфик Ханна, Набила Филип Атталла Сейф и Валид Абд Эль Магид Ахмед (2004). «Собственные векторы, подобные Эрмиту-Гауссу, дискретной матрицы преобразования Фурье, основанные на разложении по сингулярным значениям ее матриц ортогональных проекций». Транзакции IEEE в схемах и системах I: Регулярные статьи . 51 (11): 2245–2254. дои : 10.1109/TCSI.2004.836850 . S2CID   14468134 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Шамгар Гуревич; Ронни Хадани (2009). «О диагонализации дискретного преобразования Фурье». Прикладной и вычислительный гармонический анализ . 27 (1): 87–99. arXiv : 0808.3281 . дои : 10.1016/j.acha.2008.11.003 . S2CID   14833478 . препринт на.
• Шамгар Гуревич; Ронни Хадани; Нир Сочен (2008). «Конечный гармонический генератор и его применение в последовательностях, связи и радаре». Транзакции IEEE по теории информации . 54 (9): 4239–4253. arXiv : 0808.1495 . Бибкод : 2008arXiv0808.1495G . дои : 10.1109/TIT.2008.926440 . S2CID   6037080 . препринт на.
• Хуан Г. Варгас-Рубио; Балу Сантанам (2005). «О многоугловом центрированном дискретном дробном преобразовании Фурье». Письма об обработке сигналов IEEE . 12 (4): 273–276. Бибкод : 2005ISPL...12..273В . дои : 10.1109/ЛСП.2005.843762 . S2CID   1499353 .
• ФН Конг (2008). «Аналитические выражения двух дискретных сигналов Эрмита-Гаусса». Транзакции IEEE в схемах и системах II: Экспресс-кратки . 55 (1): 56–60. дои : 10.1109/TCSII.2007.909865 . S2CID   5154718 .

Внешние ссылки

• Интерактивное объяснение ДПФ
• Учебное пособие по Matlab по дискретному преобразованию Фурье, заархивировано 4 марта 2016 г. в Wayback Machine.
• Интерактивное флеш-руководство по ДПФ
• Математика дискретного преобразования Фурье Джулиуса О. Смита III
• FFTW: Быстрая реализация DFT - закодирована на C и под лицензией General Public License (GPL).
• Пакет БПФ общего назначения: еще одна быстрая реализация ДПФ на C и FORTRAN, разрешительная лицензия.
• Объяснение: дискретное преобразование Фурье
• Дискретное преобразование Фурье
• Индексирование и сдвиг дискретного преобразования Фурье
• Свойства дискретного преобразования Фурье
• Обобщенное дискретное преобразование Фурье (GDFT) с нелинейной фазой