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

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

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

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

В математике дискретное преобразование Фурье ( ДПФ ) преобразует конечную последовательность равноотстоящих выборок функции в последовательность равноотстоящих выборок дискретного временного преобразования Фурье (ДВПФ) той же длины, которая является комплексной функцией частоты. Интервал, с которым производится выборка ДВПФ, является обратной величиной длительности входной последовательности. [ ^{A] [1]}   Обратное ДПФ (ОДПФ) — это ряд Фурье , использующий выборки ДВПФ в качестве коэффициентов комплексных синусоид на соответствующих частотах ДВПФ. Оно имеет те же значения выборок, что и исходная входная последовательность. Поэтому говорят, что ДПФ является представлением в частотной области исходной входной последовательности. Если исходная последовательность охватывает все ненулевые значения функции, ее ДВПФ является непрерывным (и периодическим), и ДПФ обеспечивает дискретные выборки одного цикла. Если исходная последовательность представляет собой один цикл периодической функции, ДПФ обеспечивает все ненулевые значения одного цикла ДВПФ.

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

$${\displaystyle {\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}}}$$

результаты в $${\displaystyle \mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}2\\-2-2i\\-2i\\4+4i\end{pmatrix}}.}$$

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

Линейность

ДПФ является линейным преобразованием, т.е. если и , то для любых комплексных чисел : ${\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}}$

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

Изменение времени на обратное (т.е. замена на ) ^[D] в соответствует изменению частоты на обратное (т.е. на ). ^{[6] : стр.421} Математически, если представляет вектор x , то ${\displaystyle n}$ ${\displaystyle N-n}$ ${\displaystyle x_{n}}$ ${\displaystyle k}$ ${\displaystyle N-k}$ ${\displaystyle \{x_{n}\}}$

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

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

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

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

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

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

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

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

${\displaystyle 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'}}$

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

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

Если и являются ДПФ и соответственно, то теорема Парсеваля гласит: ${\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}\ \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 приводит к периодическому расширению.

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

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

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

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

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

${\displaystyle 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],}$

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

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

${\displaystyle (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}.}$

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

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

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

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

что приводит к интерпретации как круговой свертки и ^{[7] [8]} Он часто используется для эффективного вычисления их линейной свертки. (см. Круговая свертка , Быстрые алгоритмы свертки и Overlap-save ) ${\displaystyle x}$ ${\displaystyle y.}$

Аналогично, взаимная корреляция и определяется выражением : ${\displaystyle x}$ ${\displaystyle y_{_{N}}}$

${\displaystyle (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}.}$

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

Как было показано выше, дискретное преобразование Фурье обладает фундаментальным свойством переноса свертки в покомпонентное произведение. Возникает естественный вопрос, является ли оно единственным с такой способностью. Было показано ^{[9] [10]} , что любое линейное преобразование, которое превращает свертку в поточечное произведение, является ДПФ с точностью до перестановки коэффициентов. Поскольку число перестановок n элементов равно n!, существует ровно n! линейных и обратимых отображений с тем же фундаментальным свойством, что и ДПФ относительно свертки.

Теорема о свертке двойственность

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

${\displaystyle {\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}}$

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

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

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

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

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

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

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

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

Унитарное DFT

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

${\displaystyle \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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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}^{*}}$

Если мы рассматриваем DFT как просто преобразование координат, которое просто задает компоненты вектора в новой системе координат, то вышеизложенное — это просто утверждение, что скалярное произведение двух векторов сохраняется при унитарном преобразовании DFT. Для особого случая это означает, что длина вектора также сохраняется — это просто теорема Планшереля , ${\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} ^{*}\right)^{*}}$

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

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

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

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

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

Собственные значения матрицы DFT просты и хорошо известны, тогда как собственные векторы сложны, не уникальны и являются предметом продолжающихся исследований. Явные формулы даны со значительным количеством теории чисел. ^[11]

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

${\displaystyle \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)}.}$

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

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

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

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

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

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

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

Иначе говоря, характеристический многочлен имеет вид: ${\displaystyle \mathbf {U} }$

${\displaystyle \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 и Parks, 1972; Dickinson и Steiglitz, 1982; Grünbaum, 1982; Atakishiyev и Wolf, 1997; Candan и др. , 2000; Hanna и др. , 2004; Gurevich и Hadani, 2008).

Один из методов построения собственных векторов ДПФ для собственного значения основан на линейной комбинации операторов: ^{[12] [13] [14]} ${\displaystyle \lambda }$

${\displaystyle {\mathcal {P}}_{\lambda }={\frac {1}{4}}\left(\mathbf {I} +\lambda ^{-1}\mathbf {U} +\lambda ^{-2}\mathbf {U} ^{2}+\lambda ^{-3}\mathbf {U} ^{3}\right)}$

Для произвольного вектора вектор удовлетворяет: ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {u} (\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} }$

${\displaystyle {\textbf {U}}\mathbf {u} (\lambda )=\lambda \mathbf {u} (\lambda )}$

следовательно, вектор действительно является собственным вектором матрицы ДПФ . Операторы проецируют векторы на подпространства, которые ортогональны для каждого значения . ^[13] То есть для двух собственных векторов, и мы имеем: ${\displaystyle \mathbf {u} (\lambda )}$ ${\displaystyle \mathbf {U} }$ ${\displaystyle {\mathcal {P}}_{\lambda }}$ ${\displaystyle \lambda }$ ${\displaystyle \mathbf {u} (\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} }$ ${\displaystyle \mathbf {u} '(\lambda ')={\mathcal {P}}_{\lambda '}\mathbf {v} '}$

${\displaystyle \mathbf {u} ^{\dagger }(\lambda )\mathbf {u} '(\lambda ')=\delta _{\lambda \lambda '}\mathbf {u} ^{\dagger }(\lambda )\mathbf {v} '}$

Однако, в общем случае, метод проекционного оператора не создает ортогональных собственных векторов в пределах одного подпространства. ^[14] Оператор можно рассматривать как матрицу, столбцы которой являются собственными векторами , но они не ортогональны. Когда набор векторов , охватывающий -мерное пространство (где - кратность собственного значения ), выбирается для генерации набора собственных векторов к собственному значению , взаимная ортогональность не гарантируется. Однако ортогональный набор может быть получен путем дальнейшего применения алгоритма ортогонализации к набору , например, процесса Грама-Шмидта . ^[15] ${\displaystyle {\mathcal {P}}_{\lambda }}$ ${\displaystyle \mathbf {U} }$ ${\displaystyle \{\mathbf {v} _{n}\}_{n=1,\dots ,N_{\lambda }}}$ ${\displaystyle N_{\lambda }}$ ${\displaystyle N_{\lambda }}$ ${\displaystyle \lambda }$ ${\displaystyle \{\mathbf {u} _{n}(\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} _{n}\}_{n=1,\dots ,N_{\lambda }}}$ ${\displaystyle \lambda }$ ${\displaystyle \mathbf {u} _{n}(\lambda )}$ ${\displaystyle \{\mathbf {u} _{n}(\lambda )\}_{n=1,\dots ,N_{\lambda }}}$

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

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

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

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

Было найдено несколько других простых аналитических собственных векторов в замкнутой форме для специального периода DFT N (Kong, 2008 и Casper-Yakimov, 2024):

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

• ${\displaystyle 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 — целое число, следующие собственные векторы являются ДПФ:

• ${\displaystyle 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]}$
• ${\displaystyle F(m)=\cos \left({\frac {\pi }{N}}m\right)\prod _{s=K+1}^{3K-1}\sin \left({\frac {\pi (s-m)}{N}}\right)}$

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

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

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

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

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

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

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

затем

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

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

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

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

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

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

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

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

${\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},}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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\}}$, где обозначает комплексное сопряжение . ${\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}\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\}}$, где обозначает комплексное сопряжение . ${\displaystyle X^{*}\,}$

Обобщенное ДПФ (смещенная и нелинейная фаза)

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

${\displaystyle 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.}$

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

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

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

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

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

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

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

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

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

где деление определено как выполняемое поэлементно, а сумма обозначает набор вложенных суммирований выше. ${\displaystyle \mathbf {n} /\mathbf {N} }$ ${\displaystyle \mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,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^{i2\pi \mathbf {n} \cdot (\mathbf {k} /\mathbf {N} )}X_{\mathbf {k} }\,.}$

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

Многомерное ДПФ можно вычислить путем композиции последовательности одномерных ДПФ вдоль каждого измерения. В двумерном случае сначала вычисляются независимые ДПФ строк (т. е. вдоль ), чтобы сформировать новый массив . Затем вычисляются независимые ДПФ y вдоль столбцов (вдоль ), чтобы сформировать окончательный результат . В качестве альтернативы сначала можно вычислить столбцы, а затем строки. Порядок не имеет значения, поскольку вложенные суммирования выше коммутируют . ${\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}$

Приложения

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

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

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

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

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

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

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

Фильтр-банк

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

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

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

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

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

Умножение полиномов

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

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

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

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

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

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

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

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

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

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

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

Свертка

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

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

Обобщения

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

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

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

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

Другие поля

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

Другие конечные группы

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

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

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

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

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

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

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

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

Примечания

1. Эквивалентно, это отношение частоты дискретизации к количеству выборок.
2. Как линейное преобразование в конечномерном векторном пространстве , выражение ДПФ также может быть записано в терминах матрицы ДПФ ; при соответствующем масштабировании оно становится унитарной матрицей , и X _k, таким образом, можно рассматривать как коэффициенты x в ортонормированном базисе .
3. Ненулевые компоненты ДВПФ периодической последовательности представляют собой дискретный набор частот, идентичный ДПФ.
4. Обращение времени для ДПФ означает замену на , а не на , чтобы избежать отрицательных индексов. ${\displaystyle n}$ ${\displaystyle N-n}$ ${\displaystyle n}$ ${\displaystyle -n}$

Ссылки

1. Табога, Марко (2021). «Дискретное преобразование Фурье — частоты», Лекции по матричной алгебре. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform-frequencies.
2. Стрэнг, Гилберт (май–июнь 1994 г.). «Вейвлеты». American Scientist . 82 (3): 250–255. JSTOR  29775194. Это самый важный численный алгоритм нашего времени...
3. Sahidullah, Md.; Saha, Goutam (февраль 2013 г.). «Новый метод оконной обработки для эффективного вычисления MFCC для распознавания говорящего». IEEE Signal Processing Letters . 20 (2): 149–152. arXiv : 1206.2437 . Bibcode : 2013ISPL...20..149S. doi : 10.1109/LSP.2012.2235067. S2CID  10900793.
4. Дж. Кули , П. Льюис и П. Уэлч (1969). «Конечное преобразование Фурье». Труды IEEE по аудио и электроакустике . 17 (2): 77–85. doi :10.1109/TAU.1969.1162036.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. "Сдвиг компонента нулевой частоты в центр спектра – MATLAB fftshift". mathworks.com . Natick, MA 01760: The MathWorks, Inc . Получено 10 марта 2014 г. .{{cite web}}: CS1 maint: location (link)
6. Proakis, John G.; Manolakis, Dimitri G. (1996), Цифровая обработка сигналов: принципы, алгоритмы и приложения (3-е изд.), Upper Saddle River, NJ: Prentice-Hall International, Bibcode : 1996dspp.book.....P, ISBN 9780133942897, sAcfAQAAIAAJ
7. Оппенгейм, Алан В .; Шефер, Рональд В .; Бак, Джон Р. (1999). Дискретная обработка сигналов (2-е изд.). Upper Saddle River, NJ: Prentice Hall. стр. 571. ISBN 0-13-754920-2.
8. МакГиллем, Клэр Д.; Купер, Джордж Р. (1984). Непрерывный и дискретный сигнальный и системный анализ (2-е изд.). Холт, Райнхарт и Уинстон. стр. 171–172. ISBN 0-03-061703-0.
9. Амиот, Эммануэль (2016). Музыка через пространство Фурье. Вычислительная музыкальная наука. Цюрих: Springer. стр. 8. doi : 10.1007/978-3-319-45581-5. ISBN 978-3-319-45581-5. S2CID  6224021.
10. Изабель Баракен; Николя Ратье (2023). «Уникальность дискретного преобразования Фурье». Обработка сигналов . 209 : 109041. Bibcode : 2023SigPr.20909041B. doi : 10.1016/j.sigpro.2023.109041 . ISSN  0165-1684.
11. Мортон, Патрик (1980). «О собственных векторах матрицы Шура». Журнал теории чисел . 12 (1): 122–127. doi :10.1016/0022-314X(80)90083-9. hdl : 2027.42/23371 .
12. Бозе, НК «Собственные векторы и собственные значения одномерных и nD матриц ДПФ». AEU-International Journal of Electronics and Communications 55.2 (2001): 131-133.
13. Candan, Ç. (2011). О собственной структуре матриц DFT [DSP education]. Журнал обработки сигналов IEEE, 28(2), 105-108.
14. Pei, SC, Ding, JJ, Hsue, WL, & Chang, KW (2008). Обобщенные коммутирующие матрицы и их собственные векторы для ДПФ, смещенных ДПФ и других периодических операций. IEEE Transactions on Signal Processing, 56(8), 3891-3904.
15. Эрсеге, Т. и Кариоларо, Г. (2003). Ортонормированный класс точных и простых собственных векторов ДПФ с высокой степенью симметрии. Труды IEEE по обработке сигналов, 51(10), 2527-2539.
16. Massar, S.; Spindel, P. (2008). "Соотношение неопределенности для дискретного преобразования Фурье". Physical Review Letters . 100 (19): 190401. arXiv : 0710.0723 . Bibcode : 2008PhRvL.100s0401M. doi : 10.1103/PhysRevLett.100.190401. PMID  18518426. S2CID  10076374.
17. ДеБруннер, Виктор; Хавличек, Джозеф П.; Пржебинда, Томаш; Озайдин, Мурад (2005). "Меры неопределенности на основе энтропии для L 2 ( R n ) , ℓ 2 ( Z ) {\displaystyle L^{2}(\mathbb {R} ^{n}),\ell ^{2}(\mathbb {Z} )} и ℓ 2 ( Z / N Z ) {\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )} с оптимальным преобразованием Хиршмана для ℓ 2 ( Z / N Z ) {\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )} " (PDF) . Труды IEEE по обработке сигналов . 53 (8): 2690. Bibcode : 2005ITSP...53.2690D. doi : 10.1109/TSP.2005.850329. S2CID  206796625. Получено 23.06.2011 .
18. Донохо, DL; Старк, PB (1989). «Принципы неопределенности и восстановление сигнала». Журнал SIAM по прикладной математике . 49 (3): 906–931. doi :10.1137/0149053. S2CID  115142886.
19. Сантханам, Балу; Сантханам, Таланаяр С. «Дискретные функции Гаусса-Эрмита и собственные векторы центрированного дискретного преобразования Фурье», Труды 32-й Международной конференции IEEE по акустике, речи и обработке сигналов (ICASSP 2007, SPTM-P12.4), т. III, стр. 1385-1388.
20. Акансу, Али Н.; Агирман-Тосун, Хандан «Обобщенное дискретное преобразование Фурье с нелинейной фазой», IEEE Transactions on Signal Processing , т. 58, № 9, стр. 4547–4556, сентябрь 2010 г.

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

• Brigham, E. Oran (1988). Быстрое преобразование Фурье и его приложения . Englewood Cliffs, NJ: Prentice Hall. ISBN 978-0-13-307505-2.
• Смит, Стивен В. (1999). "Глава 8: Дискретное преобразование Фурье". Руководство для ученых и инженеров по цифровой обработке сигналов (второе издание). Сан-Диего, Калифорния: California Technical Publishing. ISBN 978-0-9660176-3-2.
• Cormen, Thomas H. ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein (2001). "Глава 30: Полиномы и БПФ". Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 822–848. ISBN 978-0-262-03293-3.особенно раздел 30.2: DFT и FFT, стр. 830–838.
• P. Duhamel; B. Piron; JM Etcheto (1988). «О вычислении обратного DFT». Труды IEEE по акустике, речи и обработке сигналов . 36 (2): 285–286. doi :10.1109/29.1519.
• JH McClellan; TW Parks (1972). «Собственные значения и собственные векторы дискретного преобразования Фурье». Труды IEEE по аудио и электроакустике . 20 (1): 66–74. doi :10.1109/TAU.1972.1162342.
• Брэдли В. Дикинсон; Кеннет Стейглиц (1982). «Собственные векторы и функции дискретного преобразования Фурье» (PDF) . Труды IEEE по акустике, речи и обработке сигналов . 30 (1): 25–31. CiteSeerX  10.1.1.434.5279 . doi :10.1109/TASSP.1982.1163843.(Обратите внимание, что в этой статье имеется очевидная опечатка в таблице кратностей собственных значений: столбцы + i /− i поменяны местами. Правильную таблицу можно найти в работе Макклеллана и Паркса, 1972, и ее легко подтвердить численно.)
• FA Grünbaum (1982). «Собственные векторы дискретного преобразования Фурье». Журнал математического анализа и приложений . 88 (2): 355–363. doi : 10.1016/0022-247X(82)90199-8 .
• Натиг М. Атакишиев; Курт Бернардо Вольф (1997). «Дробное преобразование Фурье-Кравчука». Журнал Оптического общества Америки А. 14 (7): 1467–1477. Бибкод : 1997JOSAA..14.1467A. дои : 10.1364/JOSAA.14.001467.
• C. Candan; MA Kutay; HMOzaktas (2000). "Дискретное дробное преобразование Фурье" (PDF) . IEEE Transactions on Signal Processing . 48 (5): 1329–1337. Bibcode :2000ITSP...48.1329C. doi :10.1109/78.839980. hdl : 11693/11130 . Архивировано (PDF) из оригинала 21.09.2017.
• Magdy Tawfik Hanna, Nabila Philip Attalla Seif и Waleed Abd El Maguid Ahmed (2004). "Собственные векторы типа Hermite-Gaussian матрицы дискретного преобразования Фурье на основе сингулярного разложения ее ортогональных проекционных матриц". IEEE Transactions on Circuits and Systems I: Regular Papers . 51 (11): 2245–2254. doi :10.1109/TCSI.2004.836850. S2CID  14468134.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Шамгар Гуревич; Ронни Хадани (2009). «О диагонализации дискретного преобразования Фурье». Прикладной и вычислительный гармонический анализ . 27 (1): 87–99. arXiv : 0808.3281 . doi :10.1016/j.acha.2008.11.003. S2CID  14833478. препринт в.
• Шамгар Гуревич; Ронни Хадани; Нир Сочен (2008). «Конечный гармонический осциллятор и его применение в последовательностях, связи и радаре». Труды IEEE по теории информации . 54 (9): 4239–4253. arXiv : 0808.1495 . Bibcode : 2008arXiv0808.1495G. doi : 10.1109/TIT.2008.926440. S2CID  6037080. препринт в.
• Хуан Г. Варгас-Рубио; Балу Сантханам (2005). «О многоугольном центрированном дискретном дробном преобразовании Фурье». IEEE Signal Processing Letters . 12 (4): 273–276. Bibcode : 2005ISPL...12..273V. doi : 10.1109/LSP.2005.843762. S2CID  1499353.
• FN Kong (2008). «Аналитические выражения двух дискретных сигналов Эрмита-Гаусса». Труды IEEE по схемам и системам II: Экспресс-краткие обзоры . 55 (1): 56–60. doi :10.1109/TCSII.2007.909865. S2CID  5154718.
• Каспер, Уильям; Якимов, Милен (2024). «Ограниченное дискретное преобразование Фурье». arXiv : 2407.20379 [math.CA].

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

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