Матрица ДПФ

Дискретное преобразование Фурье, выраженное в виде матрицы

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

Определение

N - точечное ДПФ выражается как умножение , где — исходный входной сигнал, — квадратная матрица ДПФ размером N на N , а — ДПФ сигнала. ${\displaystyle X=Wx}$ ${\displaystyle x}$ ${\displaystyle W}$ ${\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}}}$,

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

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

Примеры

Двухочковый

Двухточечное ДПФ — это простой случай, в котором первая запись — это DC (сумма), а вторая запись — 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 \omega }$

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

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

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

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

Ниже кратко излагается, как работает 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. Таким образом, можно сказать, что верхние строки матрицы «измеряют» положительное частотное содержимое в сигнале, а нижние строки измеряют отрицательную частотную составляющую в сигнале.

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

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

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

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

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

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

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

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

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

Ссылки

• Yip, PC; Rao, K. Ramamohan, ред. (2001). "2. Дискретное преобразование Фурье". Справочник по преобразованию и сжатию данных . CRC Press. doi :10.1201/9781315220529. ISBN 978-1-315-22052-9.– Обработка DFT, основанная в основном на матрице DFT.

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

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