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

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

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

Определение

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

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

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

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

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

Многомерный NUDFT

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

$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} }}$

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

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

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

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

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

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

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

где

$\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-I

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

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

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

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

Затем $x[n]$ являются коэффициентами вышеуказанного интерполяционного полинома.

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

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

где $\{L_{i}(z)\}_{i=0,1,...,N-1}$ являются фундаментальными полиномами:

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

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

$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}),$

где $c_{j}$ представляет собой разделенную разность $j$й порядок ${\hat {X}}[0],{\hat {X}}[1],...,{\hat {X}}[j]$ относительно $z_{0},z_{1},...,z_{j}$:

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

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

$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})}},$

$\vdots$

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

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

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

где

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

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

$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 ) приводит к $O(N^{2})$ алгоритм вычисления NUDFT, $O(N\log N)$ алгоритмы, основанные на быстром преобразовании Фурье (БПФ), существуют. Такие алгоритмы называются NUFFT или NFFT и были разработаны на основе передискретизации и интерполяции. мин-макс интерполяция, и низкоранговое приближение. В общем, NUFFT используют БПФ путем преобразования неоднородной проблемы в однородную задачу (или последовательность однородных задач), к которой можно применить БПФ. Библиотеки программного обеспечения для выполнения NUFFT доступны в 1D, 2D и 3D.

Приложения

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

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

См. также

• Дискретное преобразование Фурье
• Быстрое преобразование Фурье
• Спектральный анализ методом наименьших квадратов
• Периодограмма Ломба – Скаргла
• Спектральная оценка
• Неравномерно распределенные временные ряды

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

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