Матрица ДПФ - DFT matrix

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

Определение

An N-точечное ДПФ выражается как умножение ${\displaystyle X=Wx}$, куда ${\displaystyle x}$ это исходный входной сигнал, ${\displaystyle W}$ это N-к-N квадрат Матрица ДПФ и ${\displaystyle X}$ это ДПФ сигнала.

Матрица преобразования ${\displaystyle W}$ можно определить как ${\displaystyle W=\left({\frac {\omega ^{jk}}{\sqrt {N}}}\right)_{j,k=0,\ldots ,N-1}}$, или эквивалентно:

${\displaystyle W={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}}$,

куда ${\displaystyle \omega =e^{-2\pi i/N}}$ это примитивный Nй корень единства в котором ${\displaystyle i^{2}=-1}$. Мы можем избежать написания больших показателей для ${\displaystyle \omega }$ используя тот факт, что для любого показателя ${\displaystyle x}$ у нас есть личность ${\displaystyle \omega ^{x}=\omega ^{x\mod N}.}$ Это Матрица Вандермонда для корней из единицы с точностью до нормировочного множителя. Обратите внимание, что коэффициент нормализации перед суммой ( ${\displaystyle 1/{\sqrt {N}}}$ ) и знак экспоненты в ω являются просто условностями и различаются в некоторых трактовках. Все последующие обсуждения применимы независимо от соглашения, с минимальными изменениями. Единственное, что важно, это то, что прямое и обратное преобразования имеют показатели разного знака, и что произведение их коэффициентов нормализации равно 1 /N. Тем не менее ${\displaystyle 1/{\sqrt {N}}}$ выбор здесь делает результирующую матрицу ДПФ унитарный, что удобно во многих случаях.

Быстрое преобразование Фурье алгоритмы используют симметрию матрицы, чтобы сократить время умножения вектора на эту матрицу по сравнению с обычным ${\displaystyle O(N^{2})}$. Подобные методы могут применяться для умножения на такие матрицы, как Матрица Адамара и Матрица Уолша.

Примеры

Двухточечный

Двухточечное ДПФ - это простой случай, в котором первая запись - это ОКРУГ КОЛУМБИЯ (сумма), а вторая запись - это AC (разница).

${\displaystyle W={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}}$

Первая строка выполняет сумму, а вторая строка выполняет разницу.

Фактор ${\displaystyle 1/{\sqrt {2}}}$ состоит в том, чтобы сделать преобразование унитарным (см. ниже).

Четырехточечный

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

${\displaystyle W={\frac {1}{\sqrt {4}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}\\\end{bmatrix}}={\frac {1}{\sqrt {4}}}{\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\end{bmatrix}}}$

куда ${\displaystyle \omega =e^{-{\frac {2\pi i}{4}}}=-i}$.

Восемь баллов

Первая нетривиальная целочисленная степень двойки соответствует восьми точкам:

${\displaystyle W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\\omega ^{0}&\omega ^{4}&\omega ^{8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\\omega ^{0}&\omega ^{5}&\omega ^{10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\\omega ^{0}&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\\omega ^{0}&\omega ^{7}&\omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\\\end{bmatrix}}={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &-i&-i\omega &-1&-\omega &i&i\omega \\1&-i&-1&i&1&-i&-1&i\\1&-i\omega &i&\omega &-1&i\omega &-i&-\omega \\1&-1&1&-1&1&-1&1&-1\\1&-\omega &-i&i\omega &-1&\omega &i&-i\omega \\1&i&-1&-i&1&i&-1&-i\\1&i\omega &i&-\omega &-1&-i\omega &-i&\omega \\\end{bmatrix}}}$

куда

${\displaystyle \omega =e^{-{\frac {2\pi i}{8}}}={\frac {1}{\sqrt {2}}}-{\frac {i}{\sqrt {2}}}}$

(Обратите внимание, что ${\displaystyle \omega ^{8+n}=\omega ^{n}}$.)

На следующем изображении ДПФ изображено как матричное умножение с элементами матрицы, изображенными выборками комплексных экспонент:

Действительная часть (косинусоидальная волна) обозначена сплошной линией, а мнимая часть (синусоида) - пунктирной линией.

Верхний ряд - все единицы (масштабируется на ${\displaystyle 1/{\sqrt {8}}}$ для унитарности), поэтому он «измеряет» Компонент постоянного тока во входном сигнале. Следующая строка - это восемь отсчетов отрицательного одного цикла комплексной экспоненты, то есть сигнал с дробная частота -1/8, поэтому он «измеряет», насколько «сила» присутствует на дробной частоте +1/8 в сигнале. Напомним, что согласованный фильтр сравнивает сигнал с инвертированной во времени версией того, что мы ищем, поэтому, когда мы ищем fracfreq. 1/8 сравниваем с fracfreq. −1/8, поэтому эта строка отрицательная частота. Следующая строка представляет собой отрицательные два цикла комплексной экспоненты, дискретизированные в восьми разрядах, поэтому она имеет дробную частоту -1/4 и, таким образом, «измеряет» степень, в которой сигнал имеет дробную частоту +1/4.

Ниже показано, как работает 8-точечное ДПФ, строка за строкой, с точки зрения дробной частоты:

• 0 измеряет, сколько постоянного тока присутствует в сигнале.
• −1/8 измеряет, какая часть сигнала имеет дробную частоту +1/8
• −1/4 измеряет, какая часть сигнала имеет дробную частоту +1/4
• −3/8 измеряет, какая часть сигнала имеет дробную частоту +3/8
• −1/2 измеряет, какая часть сигнала имеет дробную частоту +1/2
• −5/8 измеряет, какая часть сигнала имеет дробную частоту +5/8
• −3/4 измеряет, какая часть сигнала имеет дробную частоту +3/4
• −7/8 измеряет, какая часть сигнала имеет дробную частоту +7/8

Эквивалентно можно сказать, что последняя строка имеет дробную частоту +1/8 и, таким образом, измеряет, какая часть сигнала имеет дробную частоту -1/8. Таким образом, можно сказать, что верхние строки матрицы «измеряют» положительную частотную составляющую в сигнале, а нижние строки измеряют отрицательную частотную составляющую в сигнале.

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

ДПФ является (или может быть посредством соответствующего выбора масштабирования) унитарным преобразованием, то есть таким, которое сохраняет энергию. Подходящий выбор масштабирования для достижения унитарности: ${\displaystyle 1/{\sqrt {N}}}$, так что энергия в физической области будет такой же, как энергия в области Фурье, т.е. Теорема Парсеваля. (Другие, неунитарные, масштабирования также обычно используются для удобства вычислений; например, теорема свертки принимает несколько более простой вид с масштабированием, показанным на дискретное преобразование Фурье статья.)

Другие свойства

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

Предельный случай: оператор Фурье

Основная статья: Оператор Фурье

Действительная часть (косинус)

Мнимая часть (синус)

В Оператор Фурье

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

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

• Многомерное преобразование
• Матрицы часов и сдвига

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

• Справочник по преобразованию и сжатию данных П. К. Ипа, К. Рамамохана Рао - См. Главу 2 для обработки ДПФ, основанного в основном на матрице ДПФ.

внешняя ссылка

• Оператор Фурье и прореживание во времени (DIT)