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

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

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

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

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

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

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

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

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

Преобразование иногда обозначается символом , например или . ^[А] ${\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 можно интерпретировать или вывести по-разному, например:

• Он полностью описывает преобразование Фурье с дискретным временем (DTFT) -периодической последовательности, которая содержит только дискретные частотные компоненты. ^[B] ( Использование DTFT с периодическими данными ) ${\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 также может быть вычислено вне области определения , и эта расширенная последовательность является периодической . Соответственно, иногда используются другие последовательности индексов, например (если четно) и (если нечетно), что равносильно замене левой и правой половин результата преобразования. ^[4] ${\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 и ), а также знаки экспонент являются наиболее распространенными соглашениями . Единственные фактические требования этих соглашений заключаются в том, чтобы ДПФ и IDFT имели показатели степени противоположного знака и чтобы произведение их коэффициентов нормализации было. Необычная нормализация как для ДПФ, так и для 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}}$

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

Изменение времени (т.е. замена на ) ^[C] соответствует изменению частоты (т.е. на ). ^{[5] : стр.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}}$

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

Если тогда . ^{[5] : стр. 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}}}$

что приводит к интерпретации как круговой свертки и ^{[6] [7]} Он часто используется для эффективного вычисления их линейной свертки. (см. Круговая свертка , Алгоритмы быстрой свертки и Сохранение перекрытия ) ${\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}.}$

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

Как видно выше, дискретное преобразование Фурье обладает фундаментальным свойством преобразования свертки в покомпонентное произведение. Естественный вопрос: единственный ли он обладает такой способностью? Было показано ^{[8] [9]} , что любое линейное преобразование, которое превращает свертку в поточечное произведение, является ДПФ с точностью до перестановки коэффициентов. Поскольку число перестановок 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}{\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 выше, удовлетворяет свойству интерполяции для . ${\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 до (вместо примерно такого же значения , как указано выше), аналогично формуле обратного ДПФ. Эта интерполяция не минимизирует наклон и обычно не имеет действительного значения ; его использование является распространенной ошибкой. ${\displaystyle N-1}$ ${\displaystyle -N/2}$ ${\displaystyle +N/2}$ ${\displaystyle x_{n}}$

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

Другой способ взглянуть на ДПФ — отметить, что в приведенном выше обсуждении ДПФ можно выразить как матрицу ДПФ , матрицу Вандермонда , введенную Сильвестром в 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}^{*}}$

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

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

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

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

Рассмотрим унитарную форму , определенную выше для ДПФ длины 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 and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiev and Wolf, 1997; Candan et al. др. , 2000; Ханна и др. , 2004; Гуревич и Хадани, 2008).

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

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

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

Для периода ДПФ 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]}$

Выбор собственных векторов матрицы ДПФ стал важным в последние годы для определения дискретного аналога дробного преобразования Фурье — матрицу ДПФ можно привести к дробным степеням путем возведения в степень собственных значений (например, Рубио и Сантанам, 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}}}}$

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

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

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

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

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

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

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

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

Существует также хорошо известный принцип детерминированной неопределенности, который использует разреженность сигнала (или количество ненулевых коэффициентов). ^[12] Пусть и число ненулевых элементов временной и частотной последовательностей и соответственно. Затем, ${\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}.}$

Как непосредственное следствие неравенства средних арифметических и геометрических , также имеется . Было показано, что оба принципа неопределенности справедливы для специально выбранных последовательностей «часток» (дискретных последовательностей импульсов) и находят практическое применение для приложений восстановления сигналов. ^[12] ${\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 соответственно. Это иногда называют обобщенным ДПФ (или GDFT ), также называемым смещенным ДПФ или смещенным ДПФ , и имеет свойства, аналогичные обычному ДПФ:

${\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 ² DFT). Такие смещенные преобразования чаще всего используются для симметричных данных для представления различных граничных симметрий, а для вещественно-симметричных данных они соответствуют различным формам дискретных косинусных и синусоидальных преобразований. ${\displaystyle 1/2}$ ${\displaystyle a=1/2}$ ${\displaystyle X_{k+N}=-X_{k}}$ ${\displaystyle b=1/2}$ ${\displaystyle a=b=1/2}$

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

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

Дискретное преобразование Фурье можно рассматривать как частный случай 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}}^{*},}$

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

Область цифровой обработки сигналов в значительной степени опирается на операции в частотной области (т.е. на преобразование Фурье). Например, в некоторых методах сжатия изображения и звука с потерями используется дискретное преобразование Фурье: сигнал разбивается на короткие сегменты, каждый преобразуется, а затем отбрасываются коэффициенты Фурье высоких частот, которые считаются незаметными. Декомпрессор вычисляет обратное преобразование на основе этого уменьшенного числа коэффициентов Фурье. (Приложения сжатия часто используют специализированную форму ДПФ, дискретное косинусное преобразование или иногда модифицированное дискретное косинусное преобразование .) Однако некоторые относительно недавние алгоритмы сжатия используют вейвлет-преобразования , которые дают более однородный компромисс между временной и частотной областью, чем полученный путем разделения данных на сегменты и преобразования каждого сегмента. В случае 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 ) ) + град( б ( Икс )) . Затем,

${\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 ) арифметических операций. Из-за своей простоты и скорости для операции преобразования часто выбирают алгоритм БПФ Кули-Тьюки , который ограничен составными размерами. В этом случае d следует выбирать как наименьшее целое число, большее суммы степеней входного полинома, которое можно разложить на небольшие простые множители (например, 2, 3 и 5, в зависимости от реализации БПФ).

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

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

Свертка

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

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

Обобщения

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

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

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

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

Другие поля

Многие свойства ДПФ зависят только от того факта, что это примитивный корень из единицы , иногда обозначаемый или (так что ). К таким свойствам относятся полнота, ортогональность, свойства Планшереля/Парсеваля, периодичность, сдвиг, свертка и унитарность, а также многие алгоритмы БПФ. По этой причине дискретное преобразование Фурье может быть определено с использованием корней из единицы в полях , отличных от комплексных чисел, и такие обобщения обычно называются теоретико-числовыми преобразованиями (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 — конечная группа . В этой структуре стандартное ДПФ рассматривается как преобразование Фурье циклической группы , тогда как многомерное ДПФ представляет собой преобразование Фурье прямой суммы циклических групп.

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

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

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

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

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

Примечания

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

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

1. Стрэнг, Гилберт (май – июнь 1994 г.). «Вейвлеты». Американский учёный . 82 (3): 250–255. JSTOR  29775194. Это самый важный численный алгоритм нашего времени...
2. Сахидулла, Мэриленд; Саха, Гутам (февраль 2013 г.). «Новая оконная техника для эффективного расчета MFCC для распознавания говорящего». Письма об обработке сигналов IEEE . 20 (2): 149–152. arXiv : 1206.2437 . Бибкод : 2013ISPL...20..149S. дои :10.1109/ЛСП.2012.2235067. S2CID  10900793.
3. Дж. Кули , П. Льюис и П. Уэлч (1969). «Конечное преобразование Фурье». Транзакции IEEE по аудио и электроакустике . 17 (2): 77–85. дои : 10.1109/ТАУ.1969.1162036.{{cite journal}}: CS1 maint: multiple names: authors list (link)
4. «Сдвиг нулевой составляющей в центр спектра – MATLAB fftshift» . mathworks.com . Натик, Массачусетс 01760: The MathWorks, Inc. Проверено 10 марта 2014 г.{{cite web}}: CS1 maint: location (link)
5. Проакис, Джон Г.; Манолакис, Дмитрий Г. (1996), Цифровая обработка сигналов: принципы, алгоритмы и приложения (3-е изд.), Upper Saddle River, Нью-Джерси: Prentice-Hall International, Bibcode : 1996dspp.book.....P, ISBN 9780133942897, sAcfAQAAIAAJ
6. Оппенгейм, Алан В .; Шафер, Рональд В .; Бак, Джон Р. (1999). Дискретная обработка сигналов (2-е изд.). Река Аппер-Сэдл, Нью-Джерси: Прентис-Холл. п. 571. ИСБН 0-13-754920-2.
7. МакГиллем, Клэр Д.; Купер, Джордж Р. (1984). Непрерывный и дискретный сигнал и системный анализ (2-е изд.). Холт, Райнхарт и Уинстон. стр. 171–172. ISBN 0-03-061703-0.
8. Амиот, Эммануэль (2016). Музыка через пространство Фурье. Вычислительная музыкальная наука. Цюрих: Шпрингер. п. 8. дои : 10.1007/978-3-319-45581-5. ISBN 978-3-319-45581-5. S2CID  6224021.
9. Изабель Баракен; Николя Ратье (2023). «Единственность дискретного преобразования Фурье». Обработка сигнала . 209 : 109041. doi : 10.1016/j.sigpro.2023.109041. ISSN  0165-1684.
10. Массар, С.; Шпиндел, П. (2008). «Соотношение неопределенностей для дискретного преобразования Фурье». Письма о физических отзывах . 100 (19): 190401. arXiv : 0710.0723 . Бибкод : 2008PhRvL.100s0401M. doi : 10.1103/PhysRevLett.100.190401. PMID  18518426. S2CID  10076374.
11. ДеБруннер, Виктор; Гавличек, Джозеф П.; Пшебинда, Томаш; Озайдин, Мурад (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. Бибкод : 2005ITSP...53.2690D. дои : 10.1109/TSP.2005.850329. S2CID  206796625 . Проверено 23 июня 2011 г.
12. Донохо, DL; Старк, П.Б. (1989). «Принципы неопределенности и восстановление сигнала». SIAM Journal по прикладной математике . 49 (3): 906–931. дои : 10.1137/0149053. S2CID  115142886.
13. Сантанам, Балу; Сантанам, Таланаяр С. «Дискретные функции Гаусса-Эрмита и собственные векторы центрированного дискретного преобразования Фурье», Труды 32-й Международной конференции IEEE по акустике, речи и обработке сигналов (ICASSP 2007, SPTM-P12.4), vol. III, стр. 1385-1388.
14. Акансу, Али Н.; Агирман-Тосун, Хандан «Обобщенное дискретное преобразование Фурье с нелинейной фазой», IEEE Transactions on Signal Processing , vol. 58, нет. 9, стр. 4547–4556, сентябрь 2010 г.

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

• Бригам, Э. Оран (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. Бибкод : 1997JOSAA..14.1467A. дои : 10.1364/JOSAA.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: multiple names: authors list (link)
• Шамгар Гуревич; Ронни Хадани (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/LSP.2005.843762. S2CID  1499353.
• ФН Конг (2008). «Аналитические выражения двух дискретных сигналов Эрмита-Гаусса». Транзакции IEEE в схемах и системах II: Экспресс-кратки . 55 (1): 56–60. doi : 10.1109/TCSII.2007.909865. S2CID  5154718.

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

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