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

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

В качестве обобщенного подхода к неравномерной выборке NUDFT позволяет получать информацию частотной области сигнала конечной длины на любой частоте. Одна из причин использования NUDFT заключается в том, что энергия многих сигналов неравномерно распределена в частотной области. Следовательно, неоднородная схема выборки может быть более удобной и полезной во многих приложениях для обработки цифровых сигналов . Например, NUDFT обеспечивает переменное спектральное разрешение, управляемое пользователем.

Определение [ править ]

Неоднородное дискретного преобразования Фурье трансформирует последовательность комплексных чисел в другой последовательности комплексных чисел , определяемых${\ displaystyle N}$${\ displaystyle x_ {0}, \ ldots, x_ {N-1}}$${\ Displaystyle X_ {0}, \ ldots, X_ {N-1}}$

${\ displaystyle X_ {k} = \ sum _ {n = 0} ^ {N-1} x_ {n} e ^ {- 2 \ pi ip_ {n} f_ {k}}, \ quad 0 \ leq k \ leq N-1,}$

( 1 )

где - точки выборки, а - частоты. Обратите внимание, что если и , то уравнение ( 1 ) сводится к дискретному преобразованию Фурье . Есть три типа NUDFT. ^[4]${\ displaystyle p_ {0}, \ ldots, p_ {N-1} \ in [0,1]}$${\ displaystyle f_ {0}, \ ldots, f_ {N-1} \ in [0, N]}$${\ displaystyle p_ {n} = n / N}$${\displaystyle f_{k}=k}$

• Неоднородное дискретное преобразование Фурье типа I (NUDFT-I) использует однородные точки выборки, но неоднородные (то есть нецелочисленные) частоты . Это соответствует вычислению обобщенного ряда Фурье в равноотстоящих точках.${\displaystyle p_{n}=n/N}$${\displaystyle f_{k}}$
• Неоднородное дискретное преобразование Фурье типа II (NUDFT-II) использует однородные (то есть целочисленные) частоты, но неоднородные точки выборки . Это соответствует вычислению ряда Фурье в точках без интервала.${\displaystyle f_{k}=k}$${\displaystyle p_{k}}$
• Неоднородное дискретное преобразование Фурье типа III (NUDFT-III) использует как неоднородные точки выборки, так и неоднородные частоты . Это соответствует вычислению обобщенного ряда Фурье в точках без интервала.${\displaystyle p_{n}}$${\displaystyle f_{k}}$

Подобный набор NUDFTs может быть определена путем подстановки для в уравнении ( 1 ). Однако, в отличие от однородного случая, эта подстановка не связана с обратным преобразованием Фурье. Инверсия NUDFT - отдельная проблема, обсуждаемая ниже.${\displaystyle -i}$${\displaystyle +i}$

Многомерный NUDFT [ править ]

Многомерный NUDFT преобразует -мерный массив комплексных чисел в другой -мерный массив комплексных чисел, определяемый${\displaystyle d}$${\displaystyle x_{\mathbf {n} }}$${\displaystyle d}$${\displaystyle X_{\mathbf {k} }}$

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}x_{\mathbf {n} }e^{-2\pi i\mathbf {p} _{\mathbf {n} }\cdot {\boldsymbol {f}}_{\mathbf {k} }}}$

где - точки выборки, - частоты, и - -мерные векторы индексов от 0 до . Многомерные NUDFT типов I, II и III определяются аналогично одномерному случаю. ^[4]${\displaystyle \mathbf {p} _{\mathbf {k} }\in [0,1]^{d}}$${\displaystyle {\boldsymbol {f}}_{\mathbf {n} }\in [0,N_{1}]\times [0,N_{2}]\times \cdots \times [0,N_{d}]}$${\displaystyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{d})}$${\displaystyle \mathbf {k} =(k_{1},k_{2},\ldots ,k_{d})}$${\displaystyle d}$${\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\ldots ,N_{d}-1)}$

Связь с Z-преобразованием [ править ]

NUDFT можно выразить как Z-преобразование . ^[5] NUDFT последовательности длины является${\displaystyle x[n]}$${\displaystyle N}$

${\displaystyle X(z_{k})=X(z)|_{z=z_{k}}=\sum _{n=0}^{N-1}x[n]z_{k}^{-n},\quad k=0,1,...,N-1,}$

где - Z-преобразование , и - произвольно различные точки на z-плоскости. Обратите внимание, что NUDFT сводится к DFT, когда точки выборки расположены на единичном круге под одинаковыми углами.${\displaystyle X(z)}$${\displaystyle x[n]}$${\displaystyle \{z_{i}\}_{i=0,1,...,N-1}}$

Выражая вышеизложенное в виде матрицы, мы получаем

${\displaystyle \mathbf {X} =\mathbf {D} \mathbf {x} }$

где

${\displaystyle \mathbf {X} ={\begin{bmatrix}X(z_{0})\\X(z_{1})\\\vdots \\X(z_{N-1})\end{bmatrix}},\quad \mathbf {x} ={\begin{bmatrix}x[0]\\x[1]\\\vdots \\x[N-1]\end{bmatrix}},{\text{ and}}\quad \mathbf {D} ={\begin{bmatrix}1&z_{0}^{-1}&z_{0}^{-2}&\cdots &z_{0}^{-(N-1)}\\1&z_{1}^{-1}&z_{1}^{-2}&\cdots &z_{1}^{-(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&z_{N-1}^{-1}&z_{N-1}^{-2}&\cdots &z_{N-1}^{-(N-1)}\end{bmatrix}}.}$

Прямая инверсия NUDFT [ править ]

Как мы видим, NUDFT характеризуется точками и, следовательно, точками. Если мы дополнительно разложим на множители , мы увидим, что это неособое, если точки различны. Если неособое, мы можем получить уникальное обратное NUDFT следующим образом:${\displaystyle \mathbf {D} }$${\displaystyle N}$ ${\displaystyle {z_{k}}}$${\displaystyle det(\mathbf {D} )}$${\displaystyle \mathbf {D} }$${\displaystyle N}$ ${\displaystyle {z_{k}}}$${\displaystyle \mathbf {D} }$

${\displaystyle \mathbf {x} =\mathbf {D^{-1}} \mathbf {X} }$.

Учитывая , что мы можем использовать метод исключения Гаусса для нахождения . Однако сложность этого метода есть . Чтобы решить эту проблему более эффективно, сначала определим напрямую полиномиальной интерполяцией:${\displaystyle \mathbf {X} {\text{ and }}\mathbf {D} }$${\displaystyle \mathbf {x} }$${\displaystyle O(N^{3})}$${\displaystyle X(z)}$

${\displaystyle {\hat {X}}[k]=X(z_{k}),\quad k=0,1,...,N-1}$.

Тогда - коэффициенты указанного выше интерполяционного полинома.${\displaystyle x[n]}$

Выражаясь полиномом Лагранжа порядка , получаем${\displaystyle X(z)}$${\displaystyle N-1}$

${\displaystyle X(z)=\sum _{k=0}^{N-1}{\frac {L_{k}(z)}{L_{k}(z_{k})}}{\hat {X}}[k],}$

где - фундаментальные многочлены:${\displaystyle \{L_{i}(z)\}_{i=0,1,...,N-1}}$

${\displaystyle L_{k}(z)=\prod _{i\neq k}(1-z_{i}z^{-1}),\quad k=0,1,...,N-1}$.

Выражая методом интерполяции Ньютона, получаем${\displaystyle X(z)}$

${\displaystyle X(z)=c_{0}+c_{1}(1-z_{0}z^{-1})+c_{2}(1-z_{0}z^{-1})(1-z_{1}z^{-1})+\cdots +c_{N-1}\prod _{k=0}^{N-2}(1-z_{k}z^{-1}),}$

где - разделенная разность- го порядка по :${\displaystyle c_{j}}$${\displaystyle j}$${\displaystyle {\hat {X}}[0],{\hat {X}}[1],...,{\hat {X}}[j]}$${\displaystyle z_{0},z_{1},...,z_{j}}$

${\displaystyle c_{0}={\hat {X}}[0],}$

${\displaystyle c_{1}={\frac {{\hat {X}}[1]-c_{0}}{1-z_{0}z_{1}^{-1}}},}$

${\displaystyle c_{2}={\frac {{\hat {X}}[2]-c_{0}-c_{1}(1-z_{0}z^{-1})}{(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})}},}$

${\displaystyle \vdots }$

Недостатком представления Лагранжа является то, что любая добавленная точка увеличивает порядок интерполяционного полинома, что приводит к необходимости пересчета всех основных полиномов. Однако любая дополнительная точка, включенная в представление Ньютона, требует только добавления еще одного члена.

Мы можем использовать нижнюю треугольную систему для решения :${\displaystyle \{c_{j}\}}$

${\displaystyle \mathbf {L} \mathbf {c} =\mathbf {X} }$

где

${\displaystyle \mathbf {X} ={\begin{bmatrix}{\hat {X}}[0]\\{\hat {X}}[1]\\\vdots \\{\hat {X}}[N-1]\end{bmatrix}},\quad \mathbf {c} ={\begin{bmatrix}c_{0}\\c_{1}\\\vdots \\c_{N-1}\end{bmatrix}},{\text{ and}}\quad \mathbf {L} ={\begin{bmatrix}1&0&0&0&\cdots &0\\1&(1-z_{0}z_{1}^{-1})&0&0&\cdots &0\\1&(1-z_{0}z_{2}^{-1})&(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&(1-z_{0}z_{N-1}^{-1})&(1-z_{0}z_{N-1}^{-1})(1-z_{1}z_{N-1}^{-1})&\cdots &\prod _{k=0}^{N-2}(1-z_{k}z_{N-1}^{-1})\end{bmatrix}}.}$

По приведенному выше уравнению можно вычислить в пределах операций. Таким образом, интерполяция Ньютона более эффективна, чем интерполяция Лагранжа, если последняя не модифицирована${\displaystyle \{c_{j}\}}$${\displaystyle O(N^{2})}$

${\displaystyle L_{k+1}(z)={\frac {(1-z_{k+1}z^{-1})}{(1-z_{k}z^{-1})}}L_{k}(z),\quad k=0,1,...,N-1}$.

Неоднородное быстрое преобразование Фурье [ править ]

Хотя наивное применение уравнения ( 1 ) приводит к алгоритму вычисления NUDFT, алгоритмы, основанные на быстром преобразовании Фурье (FFT), действительно существуют. Такие алгоритмы называются NUFFT или NFFT и были разработаны на основе передискретизации и интерполяции, ^{[6] [7] [8] [9]} min-max интерполяции ^[2] и аппроксимации низкого ранга. ^[10] В общем, NUFFT усиливают БПФ путем преобразования неоднородной проблемы в однородную задачу (или последовательность однородных проблем), к которой может применяться БПФ. ^[4] Программные библиотеки для выполнения NUFFT доступны в 1D, 2D и 3D. ^{[11] [12]}${\displaystyle O(N^{2})}$${\displaystyle O(N\log N)}$^{[13] [14]}

Приложения [ править ]

Приложения NUDFT включают в себя:

• Цифровая обработка сигналов
• Магнитно-резонансная томография
• Численные уравнения в частных производных
• Полулагранжевые схемы
• Спектральные методы
• Спектральный анализ
• Конструкция цифрового фильтра
• Конструкция антенной решетки
• Обнаружение и декодирование двухтональных многочастотных (DTMF) сигналов

См. Также [ править ]

• Дискретное преобразование Фурье
• Быстрое преобразование Фурье
• Неравномерно распределенные временные ряды
• Спектральная оценка

Ссылки [ править ]

Внешние ссылки [ править ]

• Неоднородное преобразование Фурье: Учебное пособие .
• NFFT 3.0 - Учебное пособие
• Библиотека программного обеспечения NUFFT