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

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

Связь (непрерывным) преобразованием Фурье и дискретным преобразованием Фурье. Левый столбец: Непрерывная функция (вверху) и ее преобразование Фурье (внизу). Центральный левый столбец: Периодическое суммирование исходной функции (вверху). Преобразование Фурье (внизу) равно нулю, за исключением дискретных точек. Обратное преобразование представляет собой сумму синусоид, называемых Фурье. Центральный правый столбец: Исходная функция дискретизирована (умножена на динамическую диаграмму Дирака ) (вверху). Его преобразование периодическое суммирование (DTFT ) представляет собой исходное преобразование. Правый столбец: ДПФ (внизу) вычисляет дискретные выборки непрерывного ДВПФ. Обратное ДПФ (вверху) представляет собой периодическое суммирование исходных отсчетов. Алгоритм FFT вычисляет один цикл ДПФ, а его обратный результат - один цикл обратного ДПФ. Изображение преобразования Фурье (вверху слева) и его периодического суммирования (ДВПФ) в нижнем левом углу. Спектральные последовательности в (a) верхнем правом и (b) нижнем правом режиме вычисляются из (a) одного цикла периодического суммирования s (t) и (b) одного цикла периодического суммирования s (nT). Соответствующие формулы представляют собой (а) ряд Фурье интеграл и (b) DFTсуммирование. Его сходство с исходным преобразованием S (f) и его относительная простота вычислений используется часто мотивацией для вычислений ДПФ.

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

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

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

Содержание

• 1 Определение
• 2 Мотивация
• 3 Пример
• 4 Обратное преобразование
• 5 Свойства
  • 5.1 Линейность
  • 5.2 Инверсия времени и частоты
  • 5.3 Сопряжение во времени
  • 5.4 Действующая и мнимая части
  • 5.5 Ортогональность
  • 5.6 Теорема Планшереля и теорема Парсеваля
  • 5.7 Периодичность
  • 5.8 Теорема о сдвиге
  • 5.9 Теорема о круговой свертке и теорема о взаимной корреляции
  • 5.10 Двойственность теоремы свертки
  • 5.11 Тригетрический интерполяционный многочлен
  • 5.12 Унитарное ДПФ
  • 5.13 Выражение обратного ДПФ через ДПФ
  • 5.14 Собственные значения и собственные значения
  • 5.15 Принципы неопределенности
    • 5.15.1 Вероятностные принципы неопределенности
    • 5.15.2 Принцип детерминированной неопределенности
  • 5.16 ДПФ реальных и чисто мнимых сигналов
• 6 Обобщенное ДПФ (сдвинутая и нелинейная фаза)
• 7 Многомерное ДПФ
  • 7.1 Реальный вход многомерное ДПФ
• 8 Приложения
  • 8. 1 Спектральный анализ
  • 8.2 Банк фильтров
  • 8.3 Сжатие данных
  • 8.4 Уравнения с частными производными
  • 8.5 Умножение полиномов
    • 8.5.1 Умножение больших целых чисел
    • 8.5.2 Свертка
• 9 Некоторые пары дискретных преобразований Фурье
• 10 Обобщения
  • 10.1 Теория представлений
  • 10.2 Другие поля
  • 10.3 Другие конечные группы
• 11 Альтернативы
• 12 См. Также
• 13 Примечания
• 14 Ссылки
• 15 Дополнительная литература
• 16 Ссылки

Определение

Дискретное преобразование Фурье преобразует последовательность из N комплексных чисел $\{xn\}:\; =\; x\; 0,\; x\; 1,\dots ,\; x\; N\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{\backslash \; mathbf\; \{x\_\; \{n\}\}\; \backslash \; right\; \backslash \}:\; =\; x\_\; \{0\},\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{N-1\}\}$в другой установить комплексных чисел, $\{X\; k\}:\; =\; X\; 0,\; X\; 1,\dots ,\; XN\; -\; 1,\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{\backslash \; mathbf\; \{X\_\; \{k\}\}\; \backslash \; right\; \backslash \}:\; =\; X\_\; \{0\},\; X\_\; \{1\},\; \backslash \; ldots,\; X\_\; \{N-1\},\}$, который определяется как

$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; xn\; \cdot \; e\; -\; i\; 2\; \pi \; N\; kn\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; xn\; \cdot \; [cos\; \; (2\; \pi \; N\; kn)\; -\; i\; \cdot \; sin\; \; (2\; \pi \; N\; kn)],\; \{\backslash \; displ\; aystyle\; \{\backslash \; begin\; \{align\}\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; \backslash \; cdot\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\; \}\; \{N\}\}\; kn\}\; \backslash \backslash \; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; \backslash \; cdot\; \backslash \; left\; [\backslash \; cos\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\; \}\; kn\; \backslash \; right)\; -\; i\; \backslash \; cdot\; \backslash \; sin\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\}\; kn\; \backslash \; right)\; \backslash \; right],\; \backslash \; end\; \{align\}\}\}$

(уравнение 1)

где последнее выражение следует из первого формулой Эйлера.

Преобразование иногда обозначается символом $F\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\}$, как в $X\; =\; F\; \{x\}\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{X\}\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; \backslash \; \{\backslash \; mathbf\; \{x\}\; \backslash \; right\; \backslash \}\}$или $F\; (x)\; \{\; \backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; (\backslash \; mathbf\; \{x\}\; \backslash \; right)\}$или $F\; x\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; mathbf\; \{x\}\}$.

Мотивация

Ур.1также может быть оценена вне домена $k\; \in \; [0,\; N\; -\; 1]\; \{\backslash \; displaystyle\; k\; \backslash \; in\; [0,\; N-1]\}$, и эта расширенная последовательность $N\; \{\backslash \; displaystyle\; N\}$-периодическая. Соответственно, иногда используются другие данные индексов $N\; \{\backslash \; displaystyle\; N\}$, например $[-\; N\; 2,\; N\; 2-1]\; \{\backslash \; textstyle\; \backslash \; left\; [-\; \{\backslash \; frac\; \{N\}\; \{2\}\},\; \{\backslash \; frac\; \{N\}\; \{2\}\}\; -\; 1\; \backslash \; right]\}$(если $N\; \{\backslash \; displaystyle\; N\}$четное) и $[-\; N\; -\; 1\; 2,\; N\; -\; 1\; 2]\; \{\backslash \; textstyle\; \backslash \; left\; [-\; \{\backslash \; frac\; \{N-1\}\; \{2\}\},\; \{\backslash \; frac\; \{N-1\}\; \{2\}\}\; \backslash \; right]\}$(если $N\; \{\backslash \; displaystyle\; N\}$нечетно), что равносильно замене левой и правой половин результата преобразования.

Ур. 1 можно интерпретировать или вывести различными способами, например:

• Он полностью представлен преобразование Фурье в дискретном времени (DTFT) $N\; \{\backslash \; displaystyle\; N\}$-периодическая последовательность, которая содержит дискретные частотные составляющие. (Использование DTFT с периодическими данными )
• Он также может равномерно распределенные выборки непрерывного DTFT. (§ Выборка DTFT )
• Это взаимная корреляция входной след, $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$, и комплексная синусоида с баллом $k\; N\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{k\}\; \{N\}\}\}$. Таким образом, согласованный фильтр для этой частоты.
• Это дискретный аналог формулы для коэффициентов ряда ряда Фурье :

  $Иксn\; знак\; равно\; 1\; N\; \sum \; К\; знак\; равно\; 0\; N\; -\; 1\; Икс\; К\; \cdot \; ei\; 2\; \pi \; Kn\; /\; N,\; N\; \in \; Z,\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N-1\}\; X\_\; \{k\}\; \backslash \; cdot\; e\; ^\; \{i2\; \backslash \; pi\; kn\; /\; N\},\; \backslash \; quad\; n\; \backslash \; in\; \backslash \; mathbb\; \{Z\},\; \backslash ,\}$

  (уравнение 2)

  , которое также является $N\; \{\backslash \; displaystyle\; N\}$-периодическим. В области n ∈ [0, N - 1] это обратное преобразование Eq.1. В этой интерпретации каждый $X\; k\; \{\backslash \; dis\; playstyle\; X\_\; \{k\}\}$представляет собой комплексное число, к оторое кодируе т как амплитуды, так и фазу полного x синусоидальный компонент $(ei\; 2\; \pi \; kn\; /\; N)\; \{\backslash \; displaystyle\; (e\; ^\; \{i2\; \backslash \; pi\; kn\; /\; N\})\}$функции $x\; п.\; \{\backslash \; displaystyle\; x\_\; \{n\}.\}$частота синусоиды составляет k циклов на N выборок. Его амплитуда и фаза:

  $1\; N\; |\; X\; k\; |\; Знак\; равно\; 1\; N\; Re\; \; (Икс\; К)\; 2\; +\; Im\; \; (Икс\; К)\; 2\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; |\; X\_\; \{k\}\; |\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \{\backslash \; sqrt\; \{\backslash \; operatorname\; \{Re\}\; (X\_\; \{k\})\; ^\; \{2\}\; +\; \backslash \; operatorname\; \{Im\}\; (X\_\; \{k\})\; ^\; \{2\}\}\}\}$

  $arg\; \; (X\; k)\; =\; atan2\; \; (Im\; \; (Икс\; К),\; Re\; \; (Икс\; К))\; знак\; равно\; -\; я\; \cdot \; пер\; \; (Икс\; К\; |\; Икс\; К\; |),\; \{\backslash \; Displaystyle\; \backslash \; arg\; (X\_\; \{\; k\})\; =\; \backslash \; OperatorName\; \{atan2\}\; \{\backslash \; big\; (\}\; \backslash \; operatorname\; \{Im\}\; (X\_\; \{k\}),\; \backslash \; operatorname\; \{Re\}\; (X\_\; \{k\})\; \{\backslash \; big)\}\; =\; -\; i\; \backslash \; cdot\; \backslash \; operatorname\; \{\; ln\}\; \backslash \; left\; (\{\backslash \; frac\; \{X\_\; \{k\}\}\; \{|\; X\_\; \{k\}\; |\}\}\; \backslash \; right),\}$

  где atan2 - это форма с двумя аргументами функции arctan. В полярной форме $X\; k\; =\; |\; X\; k\; |\; e\; i\; arg\; \; (X\; k)\; =\; |\; X\; k\; |\; цис\; \; арг\; \; (Икс\; К)\; \{\backslash \; Displaystyle\; X\_\; \{k\}\; =\; |\; X\_\; \{k\}\; |\; e\; ^\; \{я\; \backslash \; arg\; (X\_\; \{k\})\}\; =\; |\; X\_\; \{k\}\; |\; \backslash \; OperatorName\; \{цис\}\; \backslash \; arg\; (X\_\; \{k\})\}$где cis - мнемоника для cos + i sin.

Нормализующий коэффициент, умножающий DFT и IDFT (здесь 1 и $1\; N\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{1\}\; \{N\}\}\}$), а знаки имеют степень просто условными обозначениями и различаются в некоторых вариантах обработки. Единственные требования этих соглашений состоят в том, что ДПФ и IDFT должны иметь экспоненты с противоположным знаком и чтобы произведение их коэффициентов нормализации было $1\; N\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{1\}\; \{N\}\}\}$. Нормализация $1\; N\; \{\backslash \; textstyle\; \{\backslash \; sqrt\; \{\backslash \; frac\; \{1\}\; \{N\}\}\}\}$как для DFT, так и для IDFT, например, делает преобразование унитарными. Дискретный импульс, $x\; n\; =\; 1\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; 1\}$при n = 0 и 0 в случае потери; может преобразоваться в $X\; k\; =\; 1\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; 1\}$для всех k (используйте коэффициенты нормализации 1 для DFT и $1\; N\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{1)))\}\; \{N\}\}\}$для IDFT). Сигнал постоянного тока, $X\; k\; =\; 1\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; 1\}$при k = 0 и 0 в случае потери; может обратно преобразоваться в $xn\; =\; 1\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; 1\}$для всех $n\; \{\backslash \; displaystyle\; n\}$(використов $1\; N\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{1\}\; \{N\}\}\}$для DFT и 1 для IDFT), что согласуется с рассмотрением DC как среднего среднего сигнал.

Пример

Пусть $N\; =\; 4\; \{\backslash \; displaystyle\; N\; =\; 4\}$и

$x\; =\; (x\; 0\; x\; 1\; x\; 2\; x\; 3)\; =\; (1\; 2\; -\; я\; -\; я\; -\; 1\; +\; 2\; я)\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{x\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; x\_\; \{0\}\; \backslash \backslash \; x\_\; \{1\}\; \backslash \; x\_\; \{2\}\; \backslash \backslash \; x\_\; \{3\}\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1\; \backslash \backslash \; 2-i\; \backslash \backslash \; -\; i\; \backslash \backslash \; -\; 1\; +\; 2i\; \backslash \; end\; \{pmatrix\}\}\}$

Здесь мы демонстрируем, как вычислить ДПФ $x\; \{\; \backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\}$с использованием Eq.1 :

$X\; 0\; =\; e\; -\; i\; 2\; \pi \; 0\; \cdot \; 0/4\; \cdot \; 1\; +\; e\; -\; i\; 2\; \pi \; 0\; \cdot \; 1/4\; \cdot \; (2\; -\; я)\; +\; е\; -\; я\; 2\; \pi \; 0\; \cdot \; 2/4\; \cdot \; (-\; я)\; +\; е\; -\; я\; 2\; \pi \; 0\; \cdot \; 3/4\; \cdot \; (-\; 1\; +\; 2\; я)\; =\; 2\; \{\backslash \; Displaystyle\; X\_\; \{0\}\; =\; е\; ^\; \{-\; i2\; \backslash \; pi\; 0\; \backslash \; cdot\; 0/4\}\; \backslash \; cdot\; 1\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 0\; \backslash \; cdot\; 1/4\}\; \backslash \; cdot\; (2-i)\; +\; e\; ^\; \{-i2\; \backslash \; pi\; 0\; \backslash \; cdot\; 2/4\}\; \backslash \; cdot\; (-i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 0\; \backslash \; cdot\; 3/4\}\; \backslash \; cdot\; (-1\; +\; 2i)\; =\; 2\}$

$X\; 1\; =\; e\; -\; i\; 2\; \pi \; 1\; \cdot \; 0/4\; \cdot \; 1\; +\; e\; -\; i\; 2\; \pi \; 1\; \cdot \; 1/4\; \cdot \; (2\; -\; i)\; +\; e\; -\; i\; 2\; \pi \; 1\; \cdot \; 2/4\; \cdot \; (-\; i)\; +\; e\; -\; i\; 2\; \pi \; 1\; \cdot \; 3/4\; \cdot \; (-\; 1\; +\; 2\; я)\; знак\; равно\; -\; 2\; -\; 2\; я\; \{\backslash \; Displaystyle\; X\_\; \{1\}\; =\; е\; ^\; \{-\; i2\; \backslash \; pi\; 1\; \backslash \; cdot\; 0/4\}\; \backslash \; cdot\; 1\; +\; e\; ^\; \{-\; i2\; \backslash \; пи\; 1\; \backslash \; cdot\; 1\; /\; 4\}\; \backslash \; cdot\; (2-i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 1\; \backslash \; cdot\; 2/4\}\; \backslash \; cdot\; (-i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 1\; \backslash \; cdot\; 3/4\}\; \backslash \; cdot\; (-1\; +\; 2i)\; =\; -\; 2-2i\}$

$X\; 2\; =\; e\; -\; i\; 2\; \pi \; 2\; \cdot \; 0/4\; \cdot \; 1\; +\; e\; -\; i\; 2\; \pi \; 2\; \cdot \; 1/4\; \cdot \; (2\; -\; i)\; +\; e\; -\; i\; 2\; \pi \; 2\; \cdot \; 2/4\; \cdot \; (-\; i)\; +\; e\; -\; i\; 2\; \pi \; 2\; \cdot \; 3/4\; \cdot \; (-\; 1\; +\; 2\; я)\; знак\; равно\; -\; 2\; я\; \{\backslash \; Displaystyle\; X\_\; \{2\}\; =\; e\; ^\; \{-\; i2\; \backslash \; pi\; 2\; \backslash \; cdot\; 0/4\}\; \backslash \; cdot\; 1\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 2\; \backslash \; cdot\; 1/4\}\; \backslash \; cdot\; (2-i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 2\; \backslash \; cdot\; 2/4\}\; \backslash \; cdot\; (-\; i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 2\; \backslash \; cdot\; 3/4\}\; \backslash \; cdot\; (-1\; +\; 2i)\; =\; -\; 2i\}$

$X\; 3\; =\; e\; -\; i\; 2\; \pi \; 3\; \cdot \; 0/4\; \cdot \; 1\; +\; e\; -\; i\; 2\; \pi \; 3\; \cdot \; 1/4\; \cdot \; (2\; -\; i)\; +\; е\; -\; я\; 2\; \pi \; 3\; \cdot \; 2/4\; \cdot \; (-\; я)\; +\; е\; -\; я\; 2\; \pi \; 3\; \cdot \; 3/4\; \cdot \; (-\; 1\; +\; 2\; я)\; =\; 4\; +\; 4\; я\; \{\backslash \; Displaystyle\; X\_\; \{3\}\; =\; е\; ^\; \{-i2\; \backslash \; pi\; 3\; \backslash \; cdot\; 0/4\}\; \backslash \; cdot\; 1\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 3\; \backslash \; cdot\; 1/4\}\; \backslash \; cdot\; (2-i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 3\; \backslash \; cdot\; 2/4\}\; \backslash \; cdot\; (-i)\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; 3\; \backslash \; cdot\; 3/4\}\; \backslash \; cdot\; (-1\; +\; 2i)\; =\; 4\; +\; 4i\}$

$X\; =\; (X\; 0\; X\; 1\; X\; 2\; X\; 3)\; Знак\; равно\; (2\; -\; 2\; -\; 2\; я\; -\; 2\; я\; 4\; +\; 4\; я)\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{X\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; X\_\; \{0\; \}\; \backslash \backslash \; X\_\; \{1\}\; \backslash \; X\_\; \{2\}\; \backslash \backslash \; X\_\; \{3\}\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatri\; x\}\; 2\; \backslash \backslash \; -\; 2-2i\; \backslash \backslash \; -\; 2i\; \backslash \backslash \; 4\; +\; 4i\; \backslash \; end\; \{pmatrix\}\}\}$

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

Дискретное преобразование Фурье - это обратимое линейное преобразование

$F:\; CN\; \to \; CN\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; двоеточие\; \backslash \; mathbb\; \{C\}\; ^\; \{N\}\; \backslash \; to\; \backslash \; mathbb\; \{C\}\; ^\; \{N\}\}$

с $C\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{C\}\}$, обозначающим набор комплексных чисел. Его обратное преобразование известно как обратное дискретное преобразование Фурье (IDFT). Другими словами, для любого $N>0\; \{\backslash \; displaystyle\; N>0\}$, N-мерный комплексный вектор имеет DFT и IDFT, которые, в свою очередь, $N\; \{\backslash \; displaystyle\; N\}$- размер

Обратное преобразование задается следующим образом:

$xn\; =\; 1\; N\; \sum \; k\; =\; 0\; N\; -\; 1\; X\; k\; \cdot \; ei\; 2\; \pi \; N\; kn\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\; \}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N-1\}\; X\_\; \{k\}\; \backslash \; cdot\; e\; ^\; \{i\; \{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\}\; kn\}\}$

(Уравнение 3)

Свойства

Линейность

ДПФ является линейным преобразованием, т.е. если $F\; (\{xn\})\; k\; =\; X\; k\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{n\}\; \backslash \})\; \_\; \{k\}\; =\; X\_\; \{k\}\}$и $F\; (\{yn\})\; k\; =\; Y\; k\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{y\_\; \{n\}\; \backslash \})\; \_\; \{k\}\; =\; Y\_\; \{k\}\}$, тогда для любых комплексных чисел $a,\; b\; \{\backslash \; displaystyle\; a,\; b\}$:

$F\; (\{axn\; +\; byn\})\; к\; зна\; к\; равно\; a\; Икс\; К\; +\; б\; Y\; К\; \{\; \backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{ax\_\; \{n\}\; +\; by\_\; \{n\}\; \backslash \})\; \_\; \{k\}\; =\; aX\_\; \{k\}\; +\; bY\_\; \{k\}\}$

Время и частота реверсии

реверс времени (т.е. замена $n\; \{\backslash \; displaystyle\; n\}$на $N\; -\; n\; \{\backslash \; displaystyle\; Nn\}$) в $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$соответствует изменению частоты (например, $k\; \{\backslash \; displaystyle\; k\}$на $N\; -\; k\; \{\backslash \; displaystyle\; Nk\}$). Математически, если $\{xn\}\; \{\backslash \; displaystyle\; \backslash \; \{x\_\; \{n\}\; \backslash \}\}$представляет вектор x, то

if $F\; (\{xn\})\; k\; =\; Икс\; К\; \{\backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{n\}\; затем\; \backslash \})\; \_\; \{k\}\; =\; X\_\; \{k\}\}$

, $F\; (\{x\; N\; -\; n\; \})\; k\; =\; XN\; -\; k\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{Nn\}\; \backslash \})\; \_\; \{k\}\; =\; X\_\; \{Nk\}\}$

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

Если $F\; (\{xn\})\; k\; =\; X\; k\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{n\}\; \backslash \})\; \_\; \{k\}\; =\; X\_\; \{k\}\}$, затем $F\; (\{xn\; \ast \})\; k\; =\; XN\; -\; k\; \ast \; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{n\}\; ^\; \{*\}\; \backslash \})\; \_\; \{k\}\; =\; X\_\; \{Nk\}\; ^\; \{*\}\}$.

Действующая и мнимая части

В этой таблице показаны некоторые математические операции над $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$во временной области и соответствующие эффекты на его ДПФ $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$в частотной области.

Свойство	Временная область. $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$	Частотная область. $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$
Реальная часть времени	$\Re \; (xn)\; \{\backslash \; displaystyle\; \backslash \; Re\; \{\backslash \; left\; (x\_\; \{n\}\; \backslash \; right)\}\}$	$1\; 2\; (X\; k\; +\; XN\; -\; k\; -\; 1\; \ast )\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; left\; (X\_\; \{k\}\; +\; X\_\; \{Nk-1\}\; ^\; \{*\}\; \backslash \; right)\}$
Мнимая часть времени	$\Im \; (xn)\; \{\backslash \; displaystyle\; \backslash \; Im\; \{\backslash \; left\; (x\_\; \{n\}\; \backslash \; right)\}\}$	$1\; 2\; i\; (X\; k\; -\; XN\; -\; k\; -\; 1\; \ast )\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2i\}\}\; \backslash \; left\; (X\_\; \{k\}\; -X\_\; \{Nk-1\}\; ^\; \{*\}\; \backslash \; right)\}$
Действительная часть частоты	$1\; 2\; (xn\; +\; x\; N\; -\; n\; -\; 1\; \ast )\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; left\; (x\_\; \{n\}\; +\; x\_\; \{Nn-1\}\; ^\; \{*\}\; \backslash \; right)\}$	$\Re \; (X\; k)\; \{\backslash \; displaystyle\; \backslash \; Re\; \{\backslash \; left\; (X\_\; \{k\}\; \backslash \; right)\}\}$
Мнимая часть частоты	$1\; 2\; i\; (xn\; -\; x\; N\; -\; n\; -\; 1\; \ast )\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2i\}\}\; \backslash \; left\; (x\_\; \{n\}\; -x\_\; \{Nn-1\}\; ^\; \{*\}\; \backslash \; right)\}$	$\Im \; (X\; k)\; \{\backslash \; displaystyle\; \backslash \; Im\; \{\backslash \; left\; (X\_\; \{k\}\; \backslash \; right)\}\}$

Ортогональность

Векторы $uk\; =\; [ei\; 2\; \pi \; N\; kn\; |\; п\; =\; 0,\; 1,\dots ,\; N\; -\; 1]\; T\; \{\backslash \; displaystyle\; u\_\; \{k\}\; =\; \backslash \; left\; [\backslash \; left.e\; ^\; \{\{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; kn\}\; \backslash ;\; \backslash \; право\; |\; \backslash ;\; n\; =\; 0,1,\; \backslash \; ldots,\; N-1\; \backslash \; right]\; ^\; \{\backslash \; mathsf\; \{T\}\}\}$образуют ортогональный базис над набором N-мерных комплексных векторов:

$uk\; T\; uk\; \prime \; \ast \; =\; \sum \; n\; =\; 0\; N\; -\; 1\; (ei\; 2\; \pi \; N\; kn)\; (ei\; 2\; \pi \; N\; (-\; k\; \prime )\; n)\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; ei\; 2\; \pi \; N\; (k\; -\; к\; \text{'})\; n\; знак\; равно\; N\; \delta \; kk\; \prime \; \{\backslash \; displaystyle\; u\_\; \{k\}\; ^\; \{\backslash \; mathsf\; \{T\}\}\; u\_\; \{k\; \text{'}\}\; ^\; \{*\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; \backslash \; left\; (е\; ^\; \{\{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; kn\}\; \backslash \; right)\; \backslash \; left\; (e\; ^\; \{\{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; (-\; k\; \text{'})\; n\}\; \backslash \; right)\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; e\; ^\; \{\{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; (kk\; \text{'})\; n\}\; =\; N\; ~\; \backslash \; delta\; \_\; \{kk\text{'}\}\}$

где $\delta \; kk\; \prime \; \{\backslash \; displaystyle\; ~\; \backslash \; delta\; \_\; \{kk\; \text{'}\}\}$- дельта Кронекера. (На последнем шаге суммирование является тривиальным, если $k\; =\; k\; \prime \; \{\backslash \; displaystyle\; k\; =\; k\; \text{'}\}$, где это 1 + 1 + ⋅⋅⋅ = N, а в случае потери - геометрический, который можно явно просуммировать для получения нуля.) Это условие ортогональности может предложить ряд формулы для IDFT из определения DFT, и оно эквивалентно своему унитарности ниже.

Теорема Планшереля и теорема Парсеваля

Если $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$и $Y\; k\; \{\backslash \; displaystyle\; Y\_\; \{k\}\; \}$- ДПФ для $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$и $yn\; \{\backslash \; displaystyle\; y\_\; \{n\}\}$соответственно. тогда теорема Парсеваля утверждает:

$\sum \; n\; =\; 0\; N\; -\; 1\; xnyn\; \ast \; =\; 1\; N\; \sum \; k\; =\; 0\; N\; -\; 1\; X\; k\; Y\; k\; \ast \; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; y\_\; \{n\}\; ^\; \{*\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N-1\}\; X\_\; \{k\}\; Y\_\; \{k\}\; ^\; \{*\}\}$

, где звездочка обозначает комплексное сопряжение. Теорема Планшереля является частным случаем теоремы Парсеваля и утверждает:

$\sum \; n\; =\; 0\; N\; -\; 1\; |\; х\; п\; |\; 2\; =\; 1\; N\; \sum \; k\; =\; 0\; N\; -\; 1\; |\; X\; k\; |\; 2.\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; |\; x\_\; \{n\}\; |\; ^\; \{2\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N-\; 1\}\; |\; X\_\; \{k\}\; |\; ^\; \{2\}.\}$

Эти теоремы также эквивалентны приведенному ниже условию унитарности.

Периодичность

Периодичность можно показать непосредственно из определения:

$X\; k\; +\; N\; \triangleq \; \sum \; n\; =\; 0\; N\; -\; 1\; xne\; -\; i\; 2\; \pi \; N\; (k\; +\; N)\; n\; Знак\; равно\; \sum \; n\; знак\; равно\; 0\; N\; -\; 1\; xne\; -\; я\; 2\; \pi \; N\; колено\; -\; я\; 2\; \pi \; n\; ⏟\; 1\; знак\; равно\; \sum \; n\; =\; 0\; N\; -\; 1\; xne\; -\; я\; 2\; \pi \; N\; kn\; =\; X\; k.\; \{\backslash \; Displaystyle\; X\_\; \{к\; +\; N\}\; \backslash \; \backslash \; треугольник\; \backslash \; \backslash \; сумма\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; (к\; +\; N)\; n\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; kn\}\; \backslash \; underbrace\; \{e\; ^\; \{-\; i2\; \backslash \; pi\; n\}\}\; \_\; \{1\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; kn\}\; =\; X\_\; \{k\}.\}$

Точно так же можно показать, что формула IDFT приводит к периодическому расширению.

Теорема о сдвиге

Умножение $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$на линейную фазу $ei\; 2\; \pi \; (n\; -\; 1)\; Н\; ·\; м\; \{\backslash \; displaystyle\; e\; ^\; \{\{\backslash \; frac\; \{i2\; \backslash \; pi\; (n-1)\}\; \{N\}\}\; m\}\}$для некоторого целого числа m соответствует циклическому сдвигу вывода $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$: $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$заменяется на $X\; k\; -\; m\; \{\backslash \; displaystyle\; X\_\; \{km\}\}$, где нижний индекс интерпретируется по модулю N (то есть периодически). Точно так же круговой сдвиг ввода $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$соответствует умножению вывода $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$линейной фазой. Математически, если $\{xn\}\; \{\backslash \; displaystyle\; \backslash \; \{x\_\; \{n\}\; \backslash \}\}$представляет вектор x, то

if $F\; (\{xn\})\; к\; знак\; равно\; Икс\; К\; \{\backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{n\}\; \backslash \})\; \_\; \{k\}\; =\; X\_\; \{k\}\}$

, $F\; (\{xn\; \cdot \; ei\; 2\; \pi \; Н\; нм\})\; К\; =\; Икс\; К\; -\; м\; \{\backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; (\backslash \; left\; \backslash \; \{x\_\; \{n\}\; \backslash \; cdot\; e\; ^\; \{\{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\})\; нм\}\; \backslash \; right\; \backslash \}\; \backslash \; right)\; \_\; \{k\}\; =\; X\_\; \{km\}\}$

и $F\; (\{xn\; -\; m\})\; k\; =\; X\; k\; \cdot \; e\; -\; i\; 2\; \pi \; N\; км\; \{\backslash \; displaystyle\; \{\; \backslash \; mathcal\; \{F\}\}\; \backslash \; left\; (\backslash \; left\; \backslash \; \{x\_\; \{nm\}\; \backslash \; right\; \backslash \}\; \backslash \; right)\; \_\; \{k\}\; =\; X\_\; \{k\}\; \backslash \; cdot\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\; \}\; км\}\}$

Теорема о круговой свертке и теорема о взаимной корреляции

Теорема о свертке для дискретного преобразования Фурье (DTFT) указывает, что свертка двух последовательностей может быть полученный как обратное преобразование продукта отдельных преобразований. Важное упрощение происходит, когда одна из последовательностей является N-периодической и обозначается здесь $y\; N,\; \{\backslash \; displaystyle\; y\; \_\; \{\_\; \{N\}\},\}$потому что $DTFT\; \{y\; N\}\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \{\backslash \; text\; \{DTFT\}\}\; \backslash \; displaystyle\; \backslash \; \{y\; \_\; \{\_\; \{N\}\}\; \backslash \}\}$отличен от нуля только на дискретных частотах (см. DTFT § Периодические данные ), а значит, и его работа с непрерывной функцией $DTFT\; \{x\}.\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \{\backslash \; text\; \{DTFT\}\}\; \backslash \; displaystyle\; \backslash \; \{x\; \backslash \}.\}$Это приводит к значительному упрощению обратного преобразования.

$x\; \ast \; y\; N\; =\; DTFT\; -\; 1\; [DTFT\; \{x\}\; \cdot \; DTFT\; \{y\; N\}]\; =\; DFT\; -\; 1\; [DFT\; \{x\; N\}\; \cdot \; DFT\; \{y\; N\}],\; \{\backslash \; displaystyle\; x\; *\; y\; \_\; \{\_\; \{N\}\}\; \backslash \; =\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DTFT\}\}\; ^\; \{-\; 1\}\; \backslash \; displaystyle\; \backslash \; left\; [\backslash \; scriptstyle\; \{\backslash \; rm\; \{DTFT\}\}\; \backslash \; displaystyle\; \backslash \; \{x\; \backslash \}\; \backslash \; cdot\; \backslash \; scriptstyle\; \{\backslash \; rm\; \{\; DTFT\}\}\; \backslash \; displaystyle\; \backslash \; \{y\; \_\; \{\_\; \{N\}\}\; \backslash \}\; \backslash \; right]\; \backslash \; =\; \backslash \; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; ^\; \{-\; 1\}\; \backslash \; displaystyle\; \backslash \; left\; [\backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\; \}\; \backslash \; displaystyle\; \backslash \; \{x\; \_\; \{\_\; \{N\}\}\; \backslash \}\; \backslash \; cdot\; \backslash \; scriptstyle\; \{\backslash \; rm\; \{DFT\}\}\; \backslash \; displaystyle\; \backslash \; \{y\; \_\; \{\_\; \{N\}\}\; \backslash \}\; \backslash \; right],\}$

где $x\; N\; \{\backslash \; displaystyle\; x\; \_\; \{\_\; \{N\}\}\}$- это периодическое суммирование следовать $x\; \{\backslash \; displaystyle\; x\}$следовать :$(Икс\; N)\; N\; M\; =\; -\; \infty \; \infty \; Икс\; (N\; -\; M\; N).\; \{\backslash \; displaystyle\; (x\; \_\; \{\_\; \{N\}\})\; \_\; \{n\}\; \backslash \; \backslash \; Triangleq\; \backslash \; sum\; \_\; \{m\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; x\; \_\; \{(n-mN)\}.\}$

Обычно Суммирование DFT и обратного DFT выполняется в области $[0,\; N\; -\; 1].\; \{\backslash \; displaystyle\; [0,\; N-1].\}$Определение этих ДПФ как $X\; \{\backslash \; displaystyle\; X\}$и $Y,\; \{\backslash \; displaystyle\; Y,\}$результат: :

$(x\; \ast \; y\; N)\; n\; \triangleq \; \sum \; \ell \; =\; -\; \infty \; \infty \; x\; \ell \; \cdot \; (y\; N)\; n\; -\; \ell \; =\; F\; -\; 1\; ⏟\; DFT\; -\; 1\; \{X\; \cdot \; Y\}\; n.\; \{\backslash \; Displaystyle\; (х\; *\; Y\; \_\; \{\_\; \{N\}\})\; \_\; \{n\}\; \backslash \; треугольник\; \backslash \; сумма\; \_\; \{\backslash \; ell\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; x\; \_\; \{\backslash \; ell\}\; \backslash \; cdot\; (y\; \_\; \{\_\; \{N\}\})\; \_\; \{n-\; \backslash \; ell\}\; =\; \backslash \; underbrace\; \{\{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\}\; \_\; \{\backslash \; rm\; \{DFT\; ^\; \{-\; 1\}\}\}\; \backslash \; left\; \backslash \; \{X\; \backslash \; cdot\; Y\; \backslash \; right\; \backslash \}\; \_\; \{n\}.\}$

На практике придерживается $x\; \{\backslash \; displaystyle\; x\}$обычно имеет длину N или меньше, а $y\; N\; \{\backslash \; displaystyle\; y\; \_\; \{\; \_\; \{N\}\}\}$является периодическим продолжением N-длины $y\; \{\backslash \; displaystyle\; y\}$-последовательности, которая также может быть выражена как круговая функция :

$(y\; N)\; N\; знак\; равно\; \sum \; п\; знак\; равно\; -\; \infty \; \infty \; Y\; (N\; -\; п\; N)\; знак\; равно\; Y\; (N\; по\; модулю\; \; N),\; N\; \in \; Z.\; \{\backslash \; displaystyle\; (y\; \_\; \{\_\; \{N\}\})\; \_\; \{n\}\; =\; \backslash \; sum\; \_\; \{p\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; y\; \_\; \{(n-pN)\}\; =\; y\; \_\; \{(n\; \backslash \; operatorname\; \{mod\}\; N)\},\; \backslash \; quad\; n\; \backslash \; in\; \backslash \; mathbb\; \{Z\}.\}$

Тогда свертку можно записать как :

$F\; -\; 1\; \{X\; \cdot \; Y\}\; n\; =\; \sum \; \ell \; =\; 0\; N\; -\; 1\; x\; \ell \; \cdot \; y\; (N\; -\; \ell )\; мод\; \; N\; \{\backslash \; Displaystyle\; \{\backslash \; mathcal\; \{F\; \}\}\; ^\; \{-\; 1\}\; \backslash \; left\; \backslash \; \{X\; \backslash \; cdot\; Y\; \backslash \; right\; \backslash \}\; \_\; \{n\}\; =\; \backslash \; sum\; \_\; \{\backslash \; ell\; =\; 0\}\; ^\; \{N-1\}\; x\; \_\; \{\backslash \; ell\}\; \backslash \; cd\; ot\; y\; \_\; \{\_\; \{(n-\; \backslash \; ell)\; \backslash \; operatorname\; \{mod\}\; N\}\}\}$

, что приводит к интерпретации как круговая свертка $х\; \{\backslash \; displaystyle\; x\}$и $у.\; \{\backslash \; displaystyle\; y.\}$Он часто используется для использования их линейной свертки. (см. Круговая свертка, Алгоритмы быстрой свертки и Сохранение с перекрытием )

Аналогично, взаимная корреляция для $x\; \{\backslash \; displaystyle\; x\; \}$и $y\; N\; \{\backslash \; displaystyle\; y\; \_\; \{\_\; \{N\}\}\}$определяется как :

$(x\; \star \; y\; N)\; n\; \triangleq \; \sum \; \ell \; =\; -\; \infty \; \infty \; Икс\; \ell \; \ast \; \cdot \; (YN)\; N\; +\; \ell \; знак\; равно\; F\; -\; 1\; \{X\; \ast \; \cdot \; Y\}\; n.\; \{\backslash \; Displaystyle\; (x\; \backslash \; star\; y\; \_\; \{\_\; \{N\}\})\; \_\; \{n\}\; \backslash \; треугольникq\; \backslash \; sum\; \_\; \{\backslash \; ell\; =\; -\; \backslash \; infty\}\; ^\; \{\backslash \; infty\}\; x\; \_\; \{\backslash \; ell\}\; ^\; \{*\}\; \backslash \; cdot\; (y\; \_\; \{\_\; \{N\}\})\; \_\; \{n\; +\; \backslash \; ell\}\; =\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{\; -\; 1\}\; \backslash \; left\; \backslash \; \{X\; ^\; \{*\}\; \backslash \; cdot\; Y\; \backslash \; right\; \backslash \}\; \_\; \{n\}.\}$

Двойственность теоремы свертки

Также можно показать, что :

$F\; \{x\; \cdot \; y\; \}\; К\; \triangleq \; \sum \; N\; знак\; равно\; 0\; N\; -\; 1\; xn\; \cdot \; yn\; \cdot \; е\; -\; я\; 2\; \pi \; N\; kn\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; \backslash \; \{\backslash \; mathbf\; \{x\; \backslash \; cdot\; y\}\; \backslash \; right\; \backslash \}\; \_\; \{\; k\}\; \backslash \; \backslash \; треугольник\; q\; \backslash \; сумма\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; \backslash \; cdot\; y\_\; \{n\}\; \backslash \; cdot\; e\; ^\; \{-\; i\; \{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\}\; kn\; \}\}$

$=\; 1\; N\; (X\; *\; YN)\; k,\; \{\backslash \; displaystyle\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; (\backslash \; mathbf\; \{X\; *\; Y\_\; \{N\}\})\; \_\; \{k\},\; \backslash ,\}$, который представляет собой круговую свертку $X\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{X\}\}$и $Y\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{Y\}\}$.

Trig онометрический интерполяционный многочлен

Тригонометрический интерполяционный многочлен

$p\; (t)\; =\; \{1\; N\; [X\; 0\; +\; X\; 1\; ei\; 2\; \pi \; t\; +\; \cdots \; +\; XN\; /\; 2\; -\; 1\; ei\; (N\; /\; 2\; -\; 1)\; 2\; \pi \; t\; +\; XN\; /\; 2\; cos\; \; (N\; \pi \; t)\; +\; XN\; /\; 2\; +\; 1\; ei\; (-\; N\; /\; 2\; +\; 1)\; 2\; \pi \; t\; +\; \cdots \; +\; XN\; -\; 1\; e\; -\; i\; 2\; \pi \; t]\; N\; даже\; 1\; N\; [X\; 0\; +\; X\; 1\; ei\; 2\; \pi \; t\; +\; \cdots \; +\; X\; \lfloor \; N\; /\; 2\; \rfloor \; ei\; \lfloor \; N\; /\; 2\; \rfloor \; 2\; \pi \; t\; +\; X\; \lfloor \; N\; /\; 2\; \rfloor \; +\; 1\; e\; -\; i\; \lfloor \; N\; /\; 2\; \rfloor \; 2\; \pi \; t\; +\; \cdots \; +\; XN\; -\; 1\; е\; -\; я\; 2\; \pi \; t]\; N\; нечетное\; \{\backslash \; displaystyle\; p\; (t)\; =\; \{\backslash \; begin\; \{cases\}\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; left\; [X\_\; \{0\}\; +\; X\_\; \{1\}\; e\; ^\; \{i2\; \backslash \; pi\; t\}\; +\; \backslash \; cdots\; +\; X\_\; \{N\; /\; 2-1\}\; e\; ^\; \{i\; (N\; /\; 2-1)\; 2\; \backslash \; pi\; t\}\; +\; X\_\; \{N\; /\; 2\}\; \backslash \; cos\; (N\; \backslash \; pi\; t)\; +\; X\_\; \{N\; /\; 2\; +\; 1\}\; e\; ^\; \{i\; (-N\; /\; 2\; +\; 1)\; 2\; \backslash \; pi\; t\}\; +\; \backslash \; cdots\; +\; X\_\; \{N-1\}\; e\; ^\; \{-\; i2\; \backslash \; pi\; t\}\; \backslash \; right]\; N\; \{\backslash \; text\; \{even\}\}\; \backslash \; \backslash \; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; left\; [X\_\; \{0\}\; +\; X\_\; \{1\}\; e\; ^\; \{i2\; \backslash \; pi\; t\}\; +\; \backslash \; cdots\; +\; X\; \_\; \{\backslash \; lfloor\; N\; /\; 2\; \backslash \; rfloor\}\; e\; ^\; \{\; i\; \backslash \; lfloor\; N\; /\; 2\; \backslash \; rfloor\; 2\; \backslash \; pi\; t\}\; +\; X\; \_\; \{\backslash \; l\; flo\; или\; N\; /\; 2\; \backslash \; rfloor\; +1\}\; e\; ^\; \{-\; i\; \backslash \; lfloor\; N\; /\; 2\; \backslash \; rfloor\; 2\; \backslash \; pi\; t\}\; +\; \backslash \; cdots\; +\; X\_\; \{N-1\}\; e\; ^\; \{-\; i2\; \backslash \; pi\; t\}\; \backslash \; right]\; N\; \{\backslash \; text\; \{odd\}\}\; \backslash \; end\; \{cases\}\}\}$

где коэффициенты X k задаются ДПФ x n выше, удовлетворяет свой интерполяции $p\; (n\; /\; N)\; знак\; равно\; xn\; \{\backslash \; displaystyle\; p\; (n\; /\; N)\; =\; x\_\; \{n\}\}$для $n\; =\; 0,\dots ,\; N\; -\; 1\; \{\backslash \; displaystyle\; n\; =\; 0,\; \backslash \; ldots,\; N-\; 1\}$.

Для четного N обратите внимание, что компонент Найквиста $XN\; /\; 2\; N\; cos\; \; (N\; \pi \; t)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{X\_\; \{N\; /\; 2\}\}\; \{N\; \}\}\; \backslash \; cos\; (N\; \backslash \; pi\; t)\}$обрабатывается специально.

Эта интерполяция не уникальна: псевдонимы подразумевают, что можно добавить N к любой из частот комплексной синусоиды (например, изменив $e\; -\; it\; \{\backslash \; displaystyle\; e\; ^\; \{-\; it\}\}$до $ei\; (N\; -\; 1)\; t\; \{\backslash \; displaystyle\; e\; ^\; \{i\; (N-1)\; t\}\}$) без изменений свойств интерполяции, но с разными значениями между $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$очков. Однако вышеприведенный выбор типичен, поскольку он обладает двумя полезными свойствами. Во-первых, он состоит из синусоид, частоты которых имеют наименьшие возможные: интерполяция ограничена полосой. Во-вторых, если $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$являются действительными числами, то $p\; (t)\; \{\backslash \; displaystyle\; p\; (t)\}$действительно также.

Напротив, наиболее очевидным полиномом тригонометрической интерполяции, в котором частоты находятся в диапазоне от 0 до $N-1\; \{\backslash \; displaystyle\; N-1\}$(вместо примерно $-\; N\; /\; 2\; \{\backslash \; displaystyle\; -N\; /\; 2\}$to $+\; N\; /\; 2\; \{\backslash \; displaystyle\; +\; N\; /\; 2\}$как указано выше), аналогично обратному Формула ДПФ. Эта интерполяция не минимизирует наклон и обычно не имеет действительного значения для действительного $x\; n\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$; его использование - распространенная ошибка.

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

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

$F\; =\; [\omega \; N\; 0\; \cdot \; 0\; \omega \; N\; 0\; \cdot \; 1\dots \; \omega \; N\; 0\; \cdot \; (N\; -\; 1)\; \omega \; N\; 1\; \cdot \; 0\; \omega \; N\; 1\; \cdot \; 1\; \dots \; \Omega \; N\; 1\; \cdot \; (N\; -\; 1)\; ⋮\; ⋮\; \ddots \; ⋮\; \omega \; N\; (N\; -\; 1)\; \cdot \; 0\; \omega \; N\; (N\; -\; 1)\; \cdot \; 1\dots \; \omega \; N\; (N\; -\; 1)\; \cdot \; (N\; -\; 1)]\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{F\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; omega\; \_\; \{N\}\; ^\; \{0\; \backslash \; cdot\; 0\}\; \backslash \; omega\; \_\; \{N\}\; ^\; \{0\; \backslash \; cdot\; 1\}\; \backslash \; ldots\; \backslash \; omega\; \_\; \{N\}\; ^\; \{0\; \backslash \; cdot\; (N-1)\}\; \backslash \backslash \backslash \; omega\; \_\; \{N\}\; ^\; \{1\; \backslash \; cdot\; 0\}\; \backslash \; omega\; \_\; \{N\}\; ^\; \{1\; \backslash \; cdot\; 1\}\; \backslash \; ldots\; \backslash \; omega\; \_\; \{N\}\; ^\; \{1\; \backslash \; cdot\; (N-1)\}\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \backslash \; omega\; \_\; \{N\}\; ^\; \{(N-1)\; \backslash \; cdot\; 0\}\; \backslash \; omega\; \_\; \{N\}\; ^\; \{(N-1)\; \backslash \; cdot\; 1\}\; \backslash \; ldots\; \backslash \; omega\; \_\; \{N\}\; ^\; \{(N-1)\; \backslash \; cdot\; (N-1)\}\; \backslash \backslash \backslash \; end\; \{bmatrix\}\}\}$

где $\omega \; N\; =\; e\; -\; i\; 2\; \pi \; /\; N\; \{\backslash \; displaystyle\; \backslash \; omega\; \_\; \{N\}\; =\; e\; ^\; \{-\; i2\; \backslash \; pi\; /\; N\}\}$- примитив N-й корень из единицы.

Обратное преобразовани е затем дается обратного матрицей приведенной выше:

$F\; -\; 1\; =\; 1\; NF\; \ast \; \{\backslash \; displaystyle\; \backslash \; mat\; hbf\; \{F\}\; ^\; \{-\; 1\}\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; mathbf\; \{F\}\; ^\; \{\; *\}\}$

С унитарными константами нормализации $1\; /\; N\; \{\backslash \; displaystyle\; 1\; /\; \{\backslash \; sqrt\; \{N\}\}\}$, ДПФ становится унитарным преобразованием, определяемым унитарной матрицей:

$U\; =\; 1\; NFU\; -\; 1\; =\; U\; \ast \; |\; det\; (U)\; |\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; mathbf\; \{U\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{N\}\}\}\; \backslash \; mathbf\; \{F\}\; \backslash \backslash \backslash \; mathbf\; \{U\}\; ^\; \{-\; 1\}\; =\; \backslash \; mathbf\; \{U\}\; ^\; \{*\}\; \backslash \backslash \; |\; \backslash \; det\; (\backslash \; mathbf\; \{U\})\; |\; =\; 1\; \backslash \; end\; \{align\}\}\}$

где $det\; ()\; \{\backslash \; displaystyle\; \backslash \; det\; ()\}$- функция детерминанта . Определитель - это произведение собственных значений, которые всегда равны $\pm \; 1\; \{\backslash \; displaystyle\; \backslash \; pm\; 1\}$или $\pm \; i\; \{\backslash \; displaystyle\; \backslash \; pm\; i\}$как описано ниже. В векторном представлении унитарное преобразование можно рассматривать как просто жесткое вращение системы координат, и все свойства вращения можно найти в унитарном ДПФ.

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

$\sum \; m\; =\; 0\; N\; -\; 1\; U\; км\; U\; mn\; *\; =\; \delta \; kn\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{N-1\}\; U\_\; \{km\}\; U\_\; \{mn\}\; ^\; \{*\}\; =\; \backslash \; delta\; \_\; \{kn\}\}$

Если X обозначает унитарное ДПФ вектора x, то

$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; U\; knxn\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; U\_\; \{kn\}\; x\_\; \{n\}\}$

, а теорема Парсеваля выражается как

$\sum \; n\; =\; 0\; N\; -\; 1\; xnyn\; *\; знак\; равно\; \sum \; К\; знак\; равно\; 0\; N\; -\; 1\; Икс\; К\; Y\; К\; *\; \{\backslash \; Displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; y\_\; \{n\}\; ^\; \{*\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N\; -1\}\; X\_\; \{k\}\; Y\_\; \{k\}\; ^\; \{*\}\}$

Если мы рассматриваем ДПФ как просто преобразование координаты системы координат, то это приведенное выше просто утверждение, что скалярное произведение двух векторов сохраняется при унитарном преобразовании ДПФ. Для особого случая $x\; =\; y\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; =\; \backslash \; mathbf\; \{y\}\}$это означает, что длина времени также сохраняется - это просто Теорема Планшереля,

$\sum \; n\; =\; 0\; N\; -\; 1\; |\; х\; п\; |\; 2\; =\; \sum \; k\; =\; 0\; N\; -\; 1\; |\; X\; k\; |\; 2\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; |\; x\_\; \{n\}\; |\; ^\; \{2\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N-1\}\; |\; X\_\; \{k\}\; |\; ^\; \{2\}\}$

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

, выражая обратное ДПФ через ДПФ

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

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

$F\; -\; 1\; (\{xn\})\; =\; 1\; NF\; (\{x\; N\; -\; n\})\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-1\}\; (\backslash \; \{\; x\_\; \{n\}\; \backslash \})\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; \{x\_\; \{Nn\}\; \backslash \})\}$

(Как обычно, индексы интерпретируются по модулю N; таким образом, для $n\; =\; 0\; \{\backslash \; displaystyle\; n\; =\; 0\}$, мы имеем $x\; N\; -\; 0\; =\; x\; 0\; \{\backslash \; displaystyle\; x\_\; \{N-0\}\; =\; x\_\; \{0\}\}$.)

Во-вторых, можно также сопрягать входы и выходы:

$F\; -\; 1\; (x)\; =\; 1\; NF\; (x\; \ast )\; \ast \; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; (\backslash \; mathbf\; \{x\})\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; (\backslash \; mathbf\; \{x\}\; ^\; \{*\}\; \backslash \; right)\; ^\; \{*\}\}$

В-третьих, вариант этого трюка со спряжением, который иногда предпочтительнее, потому что не требует модификации Значения данных включают замену реальной и мнимой частей (что можно сделать на компьютере, просто изменив указатели ). Определите $swap\; \; (xn)\; \{\backslash \; textstyle\; \backslash \; operatorname\; \{swap\}\; (x\_\; \{n\})\}$как $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$с его действительная и мнимая части поменялись местами, то есть если $xn\; =\; a\; +\; bi\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; a\; +\; bi\}$, то $поменять\; местами\; \; (xn)\; \{\backslash \; textstyle\; \backslash \; operatorname\; \{swap\}\; (x\_\; \{n\})\}$равно $b\; +\; ai\; \{\backslash \; displaystyle\; b\; +\; ai\}$. Аналогично, $swap\; \; (xn)\; \backslash \; operatorname\; \{swap\}\; (x\_\; \{n\})$равно $ixn\; \ast \; \{\backslash \; displaystyle\; ix\_\; \{n\}\; ^\; \{*\}\}$. Тогда

$F\; -\; 1\; (x)\; =\; 1\; N\; поменять\; местами\; \; (F\; (поменять\; местами\; \; (x)))\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; (\backslash \; mathbf\; \{x\})\; =\; \{\backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; operatorname\; \{swap\}\; (\{\backslash \; mathcal\; \{F\}\}\; (\backslash \; operatorname\; \{swap\}\; (\backslash \; mathbf\; \{x\})))\}$

То есть обратное преобразование такое же, как прямое преобразование, при котором реальная и мнимая части меняются местами как для ввода, так и для вывода, с точностью до нормализации (Duhamel et al., 1988).

Уловка сопряжения также может использоваться для определения нового преобразования, тесно связанного с ДПФ, то есть инволютивного, то есть собственного обратного. В частности, $T\; (x)\; =\; F\; (x\; \ast )\; /\; N\; \{\backslash \; displaystyle\; T\; (\backslash \; mathbf\; \{x\})\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; (\backslash \; mathbf\; \{x\}\; ^\; \{*\}\; \backslash \; справа)\; /\; \{\backslash \; sqrt\; \{N\}\}\}$явно обратное: $T\; (T\; (x))\; =\; x\; \{\backslash \; displaystyle\; T\; (T\; (\backslash \; mathbf\; \{x\}))\; =\; \backslash \; mathbf\; \{x\}\}$. Близкое инволютивное преобразование (с коэффициентом (1 + i) / √2): $H\; (x)\; =\; F\; ((1\; +\; i)\; x\; *)\; /\; 2\; N\; \{\backslash \; Displaystyle\; H\; (\backslash \; mathbf\; \{x\; \})\; =\; \{\backslash \; mathcal\; \{F\}\}\; \backslash \; left\; ((1\; +\; i)\; \backslash \; mathbf\; \{x\}\; ^\; \{*\}\; \backslash \; right)\; /\; \{\backslash \; sqrt\; \{2N\}\}\}$, поскольку $(1\; +\; i)\; \{\backslash \; displaystyle\; (1\; +\; i)\}$факторы в $H\; (H\; (x))\; \{\backslash \; displaystyle\; H\; (H\; (\backslash \; mathbf\; \{x\}))\}$отменить 2. Для реальных входов $x\; \{\backslash \; displayst\; yle\; \backslash \; mathbf\; \{x\}\}$ действительная часть $H\; (x)\; \{\backslash \; displaystyle\; H\; (\backslash \; mathbf\; \{x\})\}$не что иное, как дискретное преобразование Хартли, которое также является инволютивным.

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

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

Рассмотрим унитарную форму $U\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\}$, определенную выше для ДПФ длины N, где

$U\; m,\; n\; =\; 1\; N\; \omega \; N\; (m\; -\; 1)\; (n\; -\; 1)\; =\; 1\; N\; e\; -\; i\; 2\; \pi \; N\; (m\; -\; 1)\; (n\; -\; 1).\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\; \_\; \{m,\; n\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{N\}\}\}\; \backslash \; omega\; \_\; \{N\}\; ^\; \{(m-1)\; (n-1)\}\; =\; \{\; \backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{N\}\}\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; (m-1)\; (n-1)\}.\}$

Эта матрица удовлетворяет условию матричный полином уравнение:

$U\; 4\; =\; I.\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\; ^\; \{4\}\; =\; \backslash \; mathbf\; \{I\}.\}$

Это видно из обратных свойств выше: работа $U\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\}$дважды возвращает исходные данные в обратном порядке, поэтому при использовании $U\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\}$четыре раза исходные данные возвращаются и, таким образом, матрица идентичности. Это означает, что собственные значения $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$удовлетворяют уравнению:

$\lambda \; 4\; =\; 1.\; \{\backslash \; displaystyle\; \backslash \; lambda\; ^\; \{4\}\; =\; 1.\}$

Следовательно, собственные значения $U\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\}$являются четвертыми корнями из единицы : $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$равно +1, -1, + i или -i.

Поскольку существует только четыре различных собственных значения для этой матрицы $N\; \times \; N\; \{\backslash \; displaystyle\; N\; \backslash \; times\; N\}$, они имеют некоторую кратность. Кратность дает количество линейно независимых собственных векторов, соответствующих каждому собственному значению. (Имеется N независимых собственных векторов; унитарная матрица никогда не дефектная.)

Проблема их множественности была решена Макклелланом и Парксом (1972), хотя позже было показано, что это так. эквивалентно проблеме, решаемой Гауссом (Дикинсон и Стейглиц, 1982). Кратность зависит от значения N по модулю 4 и дается следующей таблицей:

Кратности собственных значений λ унитарной матрицы ДПФ U как функция размер преобразования N (в виде целого числа m).

размер N	λ = +1	λ = −1	λ = −i	λ = + i
4m	m + 1	m	m	м - 1
4м + 1	м + 1	m	m	m
4м + 2	м + 1	м + 1	m	m
4м + 3	m + 1	m + 1	m + 1	m

Иначе говоря, особый многочлен для $U\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{U\}\}$равенство:

$det\; (\lambda \; I\; -\; U)\; =\; (\lambda \; -\; 1)\; \lfloor \; N\; +\; 4\; 4\; \rfloor \; (\lambda \; +\; 1)\; \lfloor \; N\; +\; 2\; 4\; \rfloor \; (\lambda \; +\; я)\; \lfloor \; N\; +\; 1\; 4\; \rfloor \; (\lambda \; -\; я)\; \lfloor \; N\; -\; 1\; 4\; \rfloor .\; \{\backslash \; displaystyle\; \backslash \; det\; (\backslash \; lambda\; I-\; \backslash \; mathbf\; \{U\})\; =\; (\backslash \; lambda\; -1)\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \{\backslash \; tfrac\; \{N\; +\; 4\}\; \{4\}\}\; \backslash \; right\; \backslash \; rfloor\}\; (\backslash \; lambda\; +\; 1)\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \{\backslash \; tfrac\; \{N\; +\; 2\}\; \{4\}\}\; \backslash \; right\; \backslash \; rfloor\}\; (\backslash \; lambda\; +\; i)\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \{\backslash \; tfrac\; \{N\; +\; 1\}\; \{4\}\}\; \backslash \; right\; \backslash \; rfloor\}\; (\backslash \; lambda\; -i)\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \{\backslash \; tfrac\; \{N-1\}\; \{4\}\}\; \backslash \; right\; \backslash \; rfloor\}.\}$

Нет простой аналитической формулы для общих векторов. Более того, собственного собственного значения не уникальны, поскольку любая линейная комбинация собственных векторов для одного и того же значения является собственный вектор для этого собственного значения. Различные варианты предлагали различные варианты различных векторов, выбранных для удовлетворения таких полезных свойств, как ортогональность, чтобы иметь «простые» (например, формы, McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Атакишиев и др.) Wolf, 1997; Candan et al., 2000; Hanna et al., 2004; Гуревич, Хадани, 2008).

Прямой подход заключается в дискретизации собственной функции непрерывного преобразования Фурье, наиболее известной из которых является функция Гаусса. <Время периодическое суммирование. - π ⋅ (м + N ⋅ К) 2 N) {\ Displaystyle F (m) = \ sum _ {k \ in \ mathbb {Z}} \ exp \ left (- {\ frac {\ pi \ cdot (m + N \ cdot k) ^ {2}} {N}} \ right)}.

Выражение замкнутой формы для ряда может быть выражено с помощью тета-функций Якоби как

• $F\; (м)\; знак\; равно\; 1\; N\; \vartheta \; 3\; (\pi \; м\; N,\; ехр\; \; (-\; \pi \; N))\; \{\backslash \; displaystyle\; F\; (m)\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{N\}\}\}\; \backslash \; vartheta\; \_\; \{3\}\; \backslash \; left\; (\; \{\backslash \; frac\; \{\backslash \; pi\; m\}\; \{N\}\},\; \backslash \; exp\; \backslash \; left\; (-\; \{\backslash \; frac\; \{\backslash \; pi\}\; \{N\}\}\; \backslash \; right)\; \backslash \; right)\}$.

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

Для периода ДПФ N = 2L + 1 = 4K + 1, где K - целое число, следующий собственный вектор Д ПФ:

• $F\; (m)\; =\; \prod \; s\; =\; K\; +\; 1\; L\; [соз\; \; (2\; \pi \; N\; m)\; -\; cos\; \; (2\; \pi \; N\; s)]\; \{\backslash \; displa\; ystyle\; F\; (m)\; =\; \backslash \; prod\; \_\; \{s\; =\; K\; +\; 1\}\; ^\; \{L\}\; \backslash \; left\; [\backslash \; cos\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\}\; m\; \backslash \; right)\; -\; \backslash \; cos\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\; \}\; s\; \backslash \; right)\; \backslash \; right]\}$

Для периода ДПФ N = 2L = 4K, где K - целое число, следующий собственный вектор ДПФ:

• $F\; (м)\; знак\; равно\; грех\; \; (2\; \pi \; N\; м)\; \prod \; s\; знак\; равно\; К\; +\; 1\; L\; -\; 1\; [соз\; \; (2\; \pi \; N\; м)\; -\; соз\; \; (2\; \pi \; N\; s)]\; \{\backslash \; Displaystyle\; F\; (m)\; =\; \backslash \; sin\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{\; N\}\}\; m\; \backslash \; right)\; \backslash \; prod\; \_\; \{s\; =\; K\; +\; 1\}\; ^\; \{L-1\}\; \backslash \; left\; [\backslash \; cos\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\}\; m\; \backslash \; right)\; -\; \backslash \; cos\; \backslash \; left\; (\{\backslash \; frac\; \{2\; \backslash \; pi\}\; \{N\}\}\; s\; \backslash \; right)\; \backslash \; right]\}$

Выбор собственных векторов матрицы DFT стал важным в последние годы для определения дискретного аналога дробного преобразования Фурье матрица ДПФ может быть преобразована в дробные степени путем возведения в степень собственных значений (например, Rubio and Santhanam, 2005). Для непрерывного преобразования Фурье естественными ортогональными собственными функциями являются функции Эрмита, поэтому в качестве собственных векторов ДПФ использовались различные дискретные аналоги этих функций, такие как Кравчука. многочлены (Атакишиев, Вольф, 1997). Однако «лучший» выбор векторов для определения дробного дискретного преобразования Фурье остается открытым вопросом.

Принципы неопределенности

Принцип вероятностной неопределенности

Если случайная величина X k ограничена

$\sum \; n\; =\; 0\; N\; -\; 1\; |\; X\; n\; |\; 2\; =\; 1,\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; |\; X\_\; \{n\}\; |\; ^\; \{2\}\; =\; 1\; ~,\}$

, затем

$P\; n\; =\; |\; X\; n\; |\; 2\; \{\backslash \; displaystyle\; P\_\; \{n\}\; =\; |\; X\_\; \{n\}\; |\; ^\; \{2\}\}$

может рассматриваться как представляющее дискретную функцию массы вероятности числа n с помощью функции массы вероятности, построенной из преобразованная переменная,

$Q\; m\; =\; N\; |\; х\; м\; |\; 2.\; \{\backslash \; displaystyle\; Q\_\; \{m\}\; =\; N\; |\; x\_\; \{m\}\; |\; ^\; \{2\}\; ~.\}$

Для случая непрерывных функций $P\; (x)\; \{\backslash \; displaystyle\; P\; (x)\}$и $Q\; (k)\; \{\backslash \; displaystyle\; Q\; (k)\; \}$, неопределенности принципности Гейзенберга утверждает, что

$D\; 0\; (X)\; D\; 0\; (x)\; \ge \; 1\; 16\; \pi \; 2\; \{\backslash \; displaystyle\; D\_\; \{0\}\; (X)\; D\_\; \{\; 0\}\; (х)\; \backslash \; geq\; \{\backslash \; frac\; \{1\}\; \{16\; \backslash \; pi\; ^\; \{2\}\}\}\}$

где $D\; 0\; (X)\; \{\backslash \; displaystyle\; D\_\; \{0\}\; (X)\}$и $D\; 0\; (x)\; \{\backslash \; displaystyle\; D\_\; \{0\}\; (x)\}$- дисперсии $|\; X\; |\; 2\; \{\backslash \; displaystyle\; |\; X\; |\; ^\; \{2\}\}$и $|\; х\; |\; 2\; \{\backslash \; displaystyle\; |\; х\; |\; ^\; \{2\}\}$соответственно, причем достигается достижение в случае подходящим образом нормализованного гауссовского распределения. Хотя дисперсии могут быть применительно к ДПФ, аналогичный принцип неопределенности бесполезен, потому что неопределенность не будет инвариантной относительно сдвига. Тем не менее, значимый принцип неопределенности был введен Массаром и Спинделом.

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

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

$H\; (X)\; =\; -\; \sum \; n\; =\; 0\; N\; -\; 1\; P\; n\; ln\; \; P\; n\; \{\backslash \; displaystyle\; H\; (X)\; =\; -\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; P\_\; \{n\}\; \backslash \; ln\; P\_\; \{n\}\}$

и

$H\; (x)\; =\; -\; \sum \; m\; =\; 0\; N\; -\; 1\; Q\; m\; ln\; \; Q\; m,\; \{\backslash \; displaystyle\; H\; (x)\; =\; -\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{N-1\}\; Q\_\; \{m\}\; \backslash \; ln\; Q\_\; \{m\}\; ~,\}$

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

$H\; (X)\; +\; H\; (x)\; \ge \; ln\; \; (N).\; \{\backslash \; displaystyle\; H\; (X)\; +\; H\; (x)\; \backslash \; geq\; \backslash \; ln\; (N)\; ~.\}$

Равенство получается для $P\; n\; \{\backslash \; displaystyle\; P\_\; \{n\}\}$равно к переводам и модулей согласно нормализованной гребенки Кронекера периода $A\; \{\backslash \; displaystyle\; A\}$, где $A\; \{\backslash \; displaystyle\; A\}$- любой точный целочисленный делитель $N\; \{\backslash \; displaystyle\; N\}$. Тогда функция массы вероятности $Q\; m\; \{\backslash \; displaystyle\; Q\_\; \{m\}\}$будет иметь вида соответствующим образом переведенному гребенке Кронекера периода $B\; =\; N\; /\; A\; \{\backslash \; displaystyle\; B\; =\; N\; /\; A\}$.

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

Существует также хорошо известный принцип детерминированной неопределенности, который использует разреженность сигнала (или количество ненулевых коэффициентов). Пусть $\Vert \; Икс\; \Vert \; 0\; \{\backslash \; Displaystyle\; \backslash \; |\; х\; \backslash \; |\; \_\; \{0\}\}$и $\Vert \; Икс\; \Vert \; 0\; \{\backslash \; displaystyle\; \backslash \; |\; X\; \backslash \; |\; \_\; \{0\}\}$- ненулевых элементов временной и частотной последовательности $x\; 0,\; x\; 1,\dots ,\; x\; N\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{0\},\; x\_\; \{1\},\; \backslash \; ldots,\; x\_\; \{N-1\}\}$и $X\; 0,\; X\; 1,\dots ,\; XN\; -\; 1\; \{\backslash \; displaystyle\; X\_\; \{0\},\; X\_\; \{1\},\; \backslash \; ldots,\; X\_\; \{N-1\}\; \}$соответственно. Тогда

$N\; \le \; \Vert \; Икс\; \Vert \; 0\; \cdot \; \Vert \; Икс\; \Vert \; 0.\; \{\backslash \; Displaystyle\; N\; \backslash \; Leq\; \backslash \; |\; х\; \backslash \; |\; \_\; \{0\}\; \backslash \; cdot\; \backslash \; |\; X\; \backslash \; |\; \_\; \{0\}.\}$

Как непосредственное следствие имеет неравенства средних арифметических и геометрических, один также $2\; N\; \le \; \Vert \; x\; \Vert \; 0\; +\; \Vert \; X\; \Vert \; 0\; \{\backslash \; displaystyle\; 2\; \{\backslash \; sqrt\; \{\; N\}\}\; \backslash \; leq\; \backslash \; |\; х\; \backslash \; |\; \_\; \{0\}\; +\; \backslash \; |\; X\; \backslash \; |\; \_\; \{0\}\}$. Было показано, что оба принципа неопределенности являются жесткими для специально выбранных последовательностей «пикет-забор» (дискретные сигналы импульсов) и находят практическое применение для приложений восстановления сигналов.

ДПФ реального и чисто мнимых сигналов

• Если $x\; 0,\dots ,\; x\; N\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{0\},\; \backslash \; ldots,\; x\_\; \{N-1\}\}$- вещественные числа, как часто бывает в практических приложениях ДПФ $X\; 0,\dots ,\; XN\; -\; 1\; \{\backslash \; displaystyle\; X\_\; \{0\},\; \backslash \; ldots,\; X\_\; \{N-1\}\}$является даже симметричным :

$xn\; \in \; R\; \forall \; n\; \in \; \{0,\dots ,\; N\; -\; 1\}\; ⟹\; X\; k\; =\; X\; -\; k\; mod\; N\; \ast \; \forall \; k\; \in \; \{0,\dots ,\; N\; -\; 1\}\; \{\backslash \; displaystyle\; x\_\; \{n\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; \backslash \; quad\; \backslash \; forall\; n\; \backslash \; in\; \backslash \; \{0,\; \backslash \; ldots,\; N-1\; \backslash \}\; \backslash \; подразумевает\; X\_\; \{k\}\; =\; X\; \_\; \{-\; k\; \backslash \; mod\; N\}\; ^\; \{*\}\; \backslash \; quad\; \backslash \; forall\; k\; \backslash \; in\; \backslash \; \{0,\; \backslash \; ldots,\; N-1\; \backslash \}\}$, где $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\; \backslash ,\}$обозначает комплексное сопряжение.

Следует, что для четных $N\; \{\backslash \; displaystyle\; N\}$$X\; 0\; \{\backslash \; displaystyle\; X\_\; \{0\}\}$и $XN\; /\; 2\; \{\backslash \; displaystyle\; X\_\; \{N\; /\; 2\}\}$являются действительными, а оставшаяся часть ДПФ полностью определены комплексными числами $N\; /\; 2\; -\; 1\; \{\backslash \; displaystyle\; N\; /\; 2-1\}$.

• Если $x\; 0,\dots ,\; x\; N\; -\; 1\; \{\backslash \; displaystyle\; x\_\; \{0\},\; \backslash \; ldots,\; x\_\; \{N-1\}\}$- чисто мнимые числа, то ДПФ $X\; 0,\dots ,\; XN\; -\; 1\; \{\backslash \; Displaystyle\; X\_\; \{0\},\; \backslash \; ldots,\; X\_\; \{N-1\}\}$является нечетно-симметричным :

$xn\; \in \; i\; R\; \forall \; n\; \in \; \{\; 0,\dots ,\; N\; -\; 1\}\; ⟹\; Икс\; К\; =\; -\; Икс\; -\; К\; мод\; N\; *\; \forall \; k\; \in \; \{0,\dots ,\; N\; -\; 1\}\; \{\backslash \; displaystyle\; x\_\; \{n\}\; \backslash \; in\; i\; \backslash \; mathbb\; \{R\}\; \backslash \; quad\; \backslash \; forall\; n\; \backslash \; in\; \backslash \; \{0,\; \backslash \; ldots,\; N-1\; \backslash \}\; \backslash \; подразумевает\; X\_\; \{k\}\; =\; -\; X\; \_\; \{-\; k\; \backslash \; mod\; N\}\; ^\; \{*\}\; \backslash \; quad\; \backslash \; forall\; k\; \backslash \; in\; \backslash \; \{0,\; \backslash \; ldots,\; N\; -1\; \backslash \}\}$, где $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\; \backslash ,\}$обозначает комплексное сопряжение.

Обобщенное ДПФ (со сдвигом и без -линейная фаза)

Можно сдвинуть дискретизацию временной и / или частотной области на некоторые реальные сдвиги a и b, соответственно. Это иногда называют обобщенным ДПФ (или GDFT ), также называемым сдвинутым ДПФ или ДПФ с площадью, и имеет аналогичные свойства. к обычному ДПФ:

$Икс\; k\; =\; \sum \; N\; =\; 0\; N\; -\; 1\; xne\; -\; i\; 2\; \pi \; N\; (k\; +\; b)\; (n\; +\; a)\; k\; =\; 0,\dots ,\; N\; -\; 1.\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\}\; \{N\}\}\; (k\; +\; b)\; (n\; +\; a)\}\; \backslash \; quad\; \backslash \; quad\; k\; =\; 0,\; \backslash \; dots,\; N-1.\}$

Чаще всего использовалось сдвиги на $1/2\; \{\backslash \; displaystyle\; 1/2\}$(половина выборки). В то время как обычное ДПФ соответствует временному сигналу в частотной области, $a\; =\; 1/2\; \{\backslash \; displaystyle\; a\; =\; 1/2\}$производит сигнал, является антипериодическим в частотной области области. ($Икс\; к\; +\; N\; =\; -\; Икс\; к\; \{\backslash \; displaystyle\; X\_\; \{k\; +\; N\}\; =\; -\; X\_\; \{k\}\}$) и наоборот для $b\; =\; 1/2\; \{\backslash \; displaystyle\; b\; =\; 1/2\}$. Таким образом, конкретный случай $a\; =\; b\; =\; 1/2\; \{\backslash \; displaystyle\; a\; =\; b\; =\; 1/2\}$известен как дискретное преобразование Фурье с нечетной точностью (или O DFT). Такие сдвинутые преобразования чаще всего используются для различных симметричных симметрий, которые соответствуют различным граничным данным, которые соответствуют различным формам дискретных преобразователей косинус и синус.

Еще один интересный вариант: $a\; =\; b\; =\; -\; (N\; -\; 1)\; /\; 2\; \{\backslash \; displaystyle\; a\; =\; b\; =\; -\; (N-1)\; /\; 2\}$, то есть называется центрированным ДПФ (или CDFT ). Центрированное ДПФ имеет то полезное свойство, что, когда N кратно четырем, все четыре его собственных значения (см. Выше) имеют равные кратности (Rubio and Santhanam, 2005)

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

Дискретное преобразование Фурье может рассматривать как частный случай z-преобразование, вычисляемого на единичной окружности в комплексной плоскости; более общие z-преобразования соответствуют сложным сдвигам a и b выше.

Многомерное ДПФ

Обычное ДПФ преобразует одномерную последовательность или массив $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$, который является функцией ровно одной дискретной переменной n. Многомерное ДПФ многомерного массива $xn\; 1,\; n\; 2,\dots ,\; nd\; \{\backslash \; displaystyle\; x\_\; \{n\_\; \{1\},\; n\_\; \{2\},\; \backslash \; dots,\; n\_\; \{d\}\}\}$, который является функцией d дискретных чисел $n\; \ell \; =\; 0,\; 1,\dots ,\; N\; \ell \; -\; 1\; \{\backslash \; displaystyle\; n\; \_\; \{\backslash \; ell\}\; =\; 0,1,\; \backslash \; dots,\; N\; \_\; \{\backslash \; ell\}\; -1\}$для $\ell \; \{\backslash \; displaystyle\; \backslash \; ell\}$в $1,\; 2,\dots ,\; d\; \{\backslash \; displaystyle\; 1,2,\; \backslash \; dots,\; d\}$равно определено следующим образом образом:

$X\; k\; 1,\; k\; 2,\dots ,\; kd\; =\; \sum \; n\; 1\; =\; 0\; N\; 1\; -\; 1\; (\omega \; N\; 1\; k\; 1\; n\; 1\; \sum \; n\; 2\; =\; 0\; N\; 2\; -\; 1\; (\omega \; N\; 2\; k\; 2\; n\; 2\; \cdots \; \sum \; nd\; знак\; равно\; 0\; N\; d\; -\; 1\; \omega \; N\; dkdnd\; \cdot \; xn\; 1,\; n\; 2,\dots ,\; nd)),\; \{\backslash \; displaystyle\; X\_\; \{k\_\; \{1\},\; k\_\; \{2\},\; \backslash \; dots,\; k\_\; \{d\}\}\; =\; \backslash \; sum\; \_\; \{n\_\; \{1\}\; =\; 0\}\; ^\; \{N\_\; \{1\}\; -1\}\; \backslash \; left\; (\backslash \; omega\; \_\; \{N\_\; \{1\}\}\; ^\; \{~\; k\_\; \{1\}\; n\_\; \{1\}\}\; \backslash \; sum\; \_\; \{n\_\; \{\; 2\}\; =\; 0\}\; ^\; \{N\_\; \{2\}\; -1\}\; \backslash \; left\; (\backslash \; omega\; \_\; \{N\_\; \{2\}\}\; ^\; \{~\; k\_\; \{2\}\; n\_\; \{2\}\}\; \backslash \; cdots\; \backslash \; sum\; \_\; \{n\_\; \{d\}\; =\; 0\; \}\; ^\; \{N\_\; \{d\}\; -1\}\; \backslash \; omega\; \_\; \{N\_\; \{d\}\}\; ^\; \{~\; k\_\; \{d\}\; n\_\; \{d\}\}\; \backslash \; cdot\; x\_\; \{n\_\; \{1\},\; n\_\; \{2\},\; \backslash \; dots,\; n\_\; \{\; d\}\}\; \backslash \; right)\; \backslash \; right)\; \backslash ,,\}$

где $\omega \; N\; \ell \; =\; exp\; \; (-\; i\; 2\; \pi \; /\; N\; \ell )\; \{\backslash \; displaystyle\; \backslash \; omega\; \_\; \{N\; \_\; \{\backslash \; ell\}\}\; =\; \backslash \; exp\; (-i2\; \backslash \; pi\; /\; N\; \_\; \{\backslash \; ell\})\}$, как указано выше, а выходные индексы запускаются из $k\; \ell \; =\; 0,\; 1,\dots ,\; N\; \ell \; -\; 1\; \{\backslash \; displaystyle\; k\; \_\; \{\backslash \; ell\}\; =\; 0,1,\; \backslash \; dots,\; N\; \_\; \{\backslash \; ell\}\; -1\}$. Это более компактно выражено в нотации вектор, где мы определяем $n\; =\; (n\; 1,\; n\; 2,\dots ,\; nd)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{n\}\; =\; (n\_\; \{1\},\; n\_\; \{\; 2\},\; \backslash \; точки,\; n\_\; \{d\})\}$и $k\; =\; (k\; 1,\; k\; 2,\dots ,\; kd)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{k\}\; =\; (k\_\; \{1\},\; k\_\; \{2\},\; \backslash \; dots,\; k\_\; \{d\})\}$как d-мерные типы индексов от 0 до $N\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{N\}\; -1\}$, который мы определяем как $N\; -\; 1\; =\; (N\; 1\; -\; 1,\; N\; 2\; -\; 1,\dots ,\; N\; d\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{N\}\; -1\; =\; (N\_\; \{1\}\; -1,\; N\_\; \{2\}\; -1,\; \backslash \; точка,\; N\_\; \{d\}\; -1)\}$:

$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; e\; -\; i\; 2\; \pi \; k\; \cdot \; (n\; /\; N)\; xn,\; \{\backslash \; стиль\; отображения\; Икс\; \_\; \{\backslash \; mathbf\; \{k\}\}\; =\; \backslash \; сумма\; \_\; \{\backslash \; mathbf\; \{n\}\; =\; \backslash \; mathbf\; \{0\}\}\; ^\; \{\backslash \; mathbf\; \{N\}\; -1\}\; e\; ^\; \{-\; i2\; \backslash \; pi\; \backslash \; mathbf\; \{k\}\; \backslash \; cdot\; (\backslash \; mathbf\; \{n\}\; /\; \backslash \; mathbf\; \{N\})\}\; x\; \_\; \{\backslash \; mathbf\; \{n\}\}\; \backslash ,,\}$

где деление $n\; /\; N\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{n\}\; /\; \backslash \; mathbf\; \{\; N\}\}$определяется как $n\; /\; N\; =\; (n\; 1\; /\; N\; 1,\dots ,\; nd\; /\; N\; d)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{n\}\; /\; \backslash \; mathbf\; \{N\}\; =\; (n\_\; \{\; 1\}\; /\; N\_\; \{1\},\; \backslash \; точки,\; n\_\; \{d\}\; /\; N\_\; \{d\})\}$должно быть произведено поэлементно, сумма принимает во внимание набор вложенных суммирований выше.

Обратное к многомерному ДПФ аналогично одномерному случаю определяется следующим образом:

$xn\; =\; 1\; \prod \; \ell \; =\; 1\; d\; N\; \ell \; \sum \; k\; =\; 0\; N\; -\; 1\; ei\; 2\; \pi \; п\; \cdot \; (к\; /\; н)\; X\; к.\; \{\backslash \; displaystyle\; x\; \_\; \{\backslash \; mathbf\; \{n\}\}\; =\; \{\backslash \; frac\; \{1\}\; \{\backslash \; prod\; \_\; \{\backslash \; ell\; =\; 1\}\; ^\; \{d\}\; N\; \_\; \{\backslash \; ell\}\}\}\; \backslash \; sum\; \_\; \{\backslash \; mathbf\; \{k\}\; =\; \backslash \; mathbf\; \{0\}\}\; ^\; \{\backslash \; mathbf\; \{N\}\; -1\}\; e\; ^\; \{i2\; \backslash \; pi\; \backslash \; mathbf\; \{n\}\; \backslash \; cdot\; (\backslash \; mathbf\; \{k\}\; /\; \backslash \; mathbf\; \{N\})\}\; X\; \_\; \{\backslash \; mathbf\; \{\; k\}\}\; \backslash ,.\}$

3D-вводит ввод $xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$как суперпозицию синусоид, многомерное ДПФ выражает ввод как суперпозицию плоские волны или многомерные синусоиды. Направление колебания в пространстве: $k\; /\; N\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{k\}\; /\; \backslash \; mathbf\; \{N\}\}$. Амп амплитуды равны $X\; k\; \{\backslash \; displaystyle\; X\; \_\; \{\backslash \; mathbf\; \{k\}\}\}$. Это разложение имеет большое значение для всего, от обработки цифрового изображения (двумерного) до решения условий в частных производных. Решение разбивается на плоские волны.

Многомерное ДПФ может быть вычислено с помощью композиции следовать одномерных ДПФ по каждому измерению. В двумерном случае $xn\; 1,\; n\; 2\; \{\backslash \; displaystyle\; x\_\; \{n\_\; \{1\},\; n\_\; \{2\}\}\}$$N\; 1\; \{\backslash \; displaystyle\; N\_\; \{1\}\}$независимые ДПФ строк (т. Е. Вдоль $n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\}$) вычисляются сначала для формирования нового массива $yn\; 1,\; k\; 2\; \{\backslash \; displaystyle\; y\_\; \{\; n\_\; \{1\},\; k\_\; \{2\}\}\}$. Затем $N\; 2\; \{\backslash \; displaystyle\; N\_\; \{2\}\}$независимые ДПФ y вдоль столбцов (вдоль $n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\}$) вычисляются для формирования окончательного результата $Икс\; k\; 1,\; k\; 2\; \{\backslash \; displaystyle\; X\_\; \{k\_\; \{1\},\; k\_\; \{2\}\}\}$. В качестве альтернативы можно сначала вычислить столбцы, а затем строки. Порядок несущественен, потому что вложенные суммирования выше коммутируют.

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

Многомерное ДПФ с реальным вводом

Для входных данных $xn\; 1,\; n\; 2,\dots ,\; nd\; \{\backslash \; displaystyle\; x\_\; \{n\_\; \{1\},\; n\_\; \{2\},\; \backslash \; dots,\; n\_\; \{d\}\}\}$, состоящий из действующих чисел, выходные данные ДПФ имеют сопряженную симметрию, аналогичную одномерному случаю выше:

$Икс\; К\; 1,\; К\; 2,\dots ,\; kd\; =\; XN\; 1\; -\; K\; 1,\; N\; 2\; -\; k\; 2,\dots ,\; N\; d\; -\; kd\; \ast ,\; \{\backslash \; displaystyle\; X\_\; \{k\_\; \{1\},\; k\_\; \{2\},\; \backslash \; dots,\; k\_\; \{d\}\}\; =\; X\_\; \{N\_\; \{1\}\; -k\_\; \{1\},\; N\_\; \{2\}\; -k\_\; \{2\},\; \backslash \; dots,\; N\_\; \{d\}\; -k\_\; \{d\}\}\; ^\; \{*\},\}$

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

Приложения

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

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

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

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

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

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

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

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

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

Уравнения с частными производными

Часто используются дискретные преобразования Фурье для решения уравнений в частных производных, где снова ДПФ используется в качестве приближения для ряда Фурье (который восстанавливается в пределе бесконечного N). Преимущество этого подхода состоит в том, что он расширяет сигнал в комплексных экспонентах $einx\; \{\backslash \; displaystyle\; e\; ^\; \{inx\}\}$, которые являются собственными функциями дифференцирования: $d\; (einx)\; /\; dx\; =\; ineinx\; \{\backslash \; displaystyle\; \{\{\backslash \; text\; \{d\}\}\; \{\backslash \; big\; (\}\; e\; ^\; \{inx\}\; \{\backslash \; big)\}\}\; /\; \{\backslash \; text\; \{d\}\}\; x\; =\; ine\; ^\; \{inx\}\}$. Таким образом, в представлении Фурье дифференцирование выполняется просто - мы просто умножаем на $i\; n\; \{\backslash \; displaystyle\; in\}$. (Однако выбор $n\; \{\backslash \; displaystyle\; n\}$не является уникальным из-за наложения спектров; для того, чтобы метод был сходимым, выбор аналогичен выбору в тригонометрической интерполяции раздел выше.) Линейное дифференциальное уравнение с постоянными коэффициентами преобразуется в легко решаемое алгебраическое уравнение. Затем используется обратное ДПФ, чтобы преобразовать результат обратно в обычное пространственное представление. Такой подход называется спектральным методом.

Умножение полиномов

Предположим, мы хотим вычислить полиномиальное произведение c (x) = a (x) · b (x). Обычное выражение произведения для коэффициентов c включает линейную (ациклическую) свертку, где индексы не «зацикливаются». Это можно переписать как циклическую свертку, взяв сначала векторы коэффициентов для a (x) и b (x) с постоянным членом, а затем добавив нули так, чтобы результирующие векторы коэффициентов a и b имеют размерность d>deg (a (x)) + deg (b (x)). Тогда

$c\; =\; a\; \ast \; b\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{c\}\; =\; \backslash \; mathbf\; \{a\}\; *\; \backslash \; mathbf\; \{b\}\}$

где c - вектор коэффициентов для c ( x), а оператор свертки $\ast \; \{\backslash \; displaystyle\; *\; \backslash ,\}$определяется таким образом, что

$cn\; =\; \sum \; m\; =\; 0\; nambn\; -\; mmoddn\; =\; 0,\; 1\dots ,\; d\; -\; 1\; \{\backslash \; displaystyle\; c\_\; \{n\}\; =\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n\}\; a\_\; \{m\}\; b\_\; \{nm\; \backslash \; \backslash \; mathrm\; \{mod\}\; \backslash \; d\}\; \backslash \; qquad\; \backslash \; qquad\; \backslash \; qquad\; n\; =\; 0,1\; \backslash \; dots,\; d-\; 1\}$

Но свертка становится умножением в соответствии с ДПФ:

$F\; (c)\; =\; F\; (a)\; F\; (b)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; mathbf\; \{c\})\; =\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; mathbf\; \{a\})\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; mathbf\; \{b\})\}$

Здесь векторное произведение берется поэлементно. Таким образом, коэффициенты полинома произведения c (x) - это просто члены 0,..., deg (a (x)) + deg (b (x)) вектора коэффициентов

$c\; =\; F\; -\; 1\; (F\; (а)\; F\; (б)).\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{c\}\; =\; \{\backslash \; mathcal\; \{F\}\}\; ^\; \{-\; 1\}\; (\{\backslash \; mathcal\; \{F\}\}\; (\backslash \; mathbf\; \{a\})\; \{\backslash \; mathcal\; \{F\}\}\; (\backslash \; mathbf\; \{b\})).\}$

С помощью быстрого преобразования Фурье результирующий алгоритм требует O (N log N) арифметических операций. Из-за его простоты и скорости алгоритм БПФ Кули-Тьюки, который ограничен размерами составных, часто выбирается для операции преобразования. В этом случае d следует выбирать как наименьшее целое число, большее суммы степеней входного полинома, которое может быть разложено на малые простые множители (например, 2, 3 и 5, в зависимости от реализации БПФ).

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

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

Свертка

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

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

Некоторые пары ДПФ

$xn\; =\; 1\; N\; \sum \; k\; =\; 0\; N\; -\; 1\; X\; kei\; 2\; \pi \; kn\; /\; N\; \{\backslash \; displaystyle\; x\_\; \{n\}\; =\; \{\backslash \; frac\; \{\; 1\}\; \{N\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{N-1\}\; X\_\; \{k\}\; e\; ^\; \{i2\; \backslash \; pi\; kn\; /\; N\}\}$	$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; xne\; -\; я\; 2\; \pi \; kn\; /\; N\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; i2\; \backslash \; pi\; kn\; /\; N\}\}$	Примечание
$xnei\; 2\; \pi \; N\; \ell \; /\; N\; \{\backslash \; displaystyle\; x\_\; \{n\}\; e\; ^\; \{i2\; \backslash \; pi\; n\; \backslash \; ell\; /\; N\}\; \backslash ,\}$	$X\; k\; -\; \ell \; \{\backslash \; displaystyle\; X\_\; \{k-\; \backslash \; ell\}\; \backslash ,\}$	Теорема о сдвиге частоты
$xn\; -\; \ell \; \{\backslash \; displaystyle\; x\_\; \{n-\; \backslash \; ell\}\; \backslash ,\}$	$X\; ke\; -\; i\; 2\; \pi \; k\; \ell \; /\; N\; \{\backslash \; displaystyle\; X\_\; \{k\}\; e\; ^\; \{-\; i2\; \backslash \; pi\; k\; \backslash \; ell\; /\; N\}\; \backslash ,\}$	теорема о сдвиге времени
$xn\; \in \; R\; \{\backslash \; displaystyle\; x\_\; \{n\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\}$	$X\; k\; =\; XN\; -\; k\; \ast \; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; X\_\; \{Nk\}\; ^\; \{*\}\; \backslash ,\}$	Действительное ДПФ
$an\; \{\backslash \; displaystyle\; a\; ^\; \{n\}\; \backslash ,\}$	$\{N\; if\; a\; =\; ei\; 2\; \pi \; k\; /\; N\; 1\; -\; a\; N\; 1\; -\; ae\; -\; i\; 2\; \pi \; k\; /\; N\; иначе\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{\{\backslash \; begin\; \{matrix\}\}\; N\; \{\backslash \; t\_dv\; \{if\}\}\; a\; =\; e\; ^\; \{i2\; \backslash \; pi\; k\; /\; N\}\; \backslash \; \backslash \; \{\backslash \; frac\; \{1-a\; ^\; \{N\}\}\; \{1-a\; \backslash ,\; e\; ^\; \{-\; i2\; \backslash \; pi\; k\; /\; N\}\}\}\; \{\backslash \; t\_dv\; \{else\}\}\; \backslash \; end\; \{matrix\}\}\; \backslash \; right.\}$	из геометрических прогрессий sion формула
$(N\; -\; 1\; n)\; \{\backslash \; displaystyle\; \{N-1\; \backslash \; choose\; n\}\; \backslash ,\}$	$(1\; +\; e\; -\; i\; 2\; \pi \; k\; /\; N)\; N\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; left\; (1\; +\; e\; ^\; \{-\; i2\; \backslash \; pi\; k\; /\; N\}\; \backslash \; right)\; ^\; \{N-1\}\; \backslash ,\}$	из биномиальной теоремы
	$\{\; 1,\; если\; К\; знак\; равно\; 0\; грех\; \; (\pi \; W\; К\; N)\; W\; грех\; \; (\pi \; К\; N)\; иначе\; \{\backslash \; Displaystyle\; \backslash \; left\; \backslash \; \{\{\backslash \; begin\; \{matrix\}\; 1\; \{\backslash \; t\_dv\; \{if\}\}\; k\; =\; 0\; \backslash \backslash \; \{\backslash \; frac\; \{\backslash \; sin\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; pi\; Wk\}\; \{N\}\}\; \backslash \; right)\}\; \{W\; \backslash \; sin\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; pi\; k\}\; \{N\}\}\; \backslash \; right)\}\}\; \{\backslash \; t\_dv\; \{иначе\}\}\; \backslash \; end\; \{matrix\}\}\; \backslash \; right.\}$	$xn\; \{\backslash \; displaystyle\; x\_\; \{n\}\}$- прямоугольная оконная функция из точек W с центром в n = 0, где W - нечетное целое число, а $X\; k\; \{\backslash \; displaystyle\; X\_\; \{k\}\}$- функция, подобная sinc (в частности, $Икс\; К\; \{\backslash \; Displaystyle\; X\_\; \{k\}\}$является ядром Дирихле )
$\sum \; j\; \in \; Z\; exp\; \; (-\; \pi \; c\; N\; \cdot \; (n\; +\; N\; \cdot \; j)\; 2)\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{j\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\}\; \backslash \; exp\; \backslash \; left\; (-\; \{\backslash \; frac\; \{\backslash \; pi\}\; \{cN\}\}\; \backslash \; cdot\; (n\; +\; N\; \backslash \; cdot\; j)\; ^\; \{2\}\; \backslash \; right)\}$	$с\; N\; \cdot \; \sum \; j\; \in \; Z\; ехр\; \; (-\; \pi \; с\; N\; \cdot \; (к\; +\; N\; \cdot \; j)\; 2)\; \{\backslash \; displaystyle\; \{\backslash \; sqrt\; \{cN\}\; \}\; \backslash \; cdot\; \backslash \; sum\; \_\; \{j\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\}\; \backslash \; exp\; \backslash \; left\; (-\; \{\backslash \; frac\; \{\backslash \; pi\; c\}\; \{N\}\}\; \backslash \; cdot\; (k\; +\; N\; \backslash \; cdot\; j)\; ^\; \{2\}\; \backslash \; right)\}$	Дискретизация и периодическое суммирование масштабированных функций Гаусса для $c>0\; \{\backslash \; displaystyle\; c>0\}$. Поскольку либо $c\; \{\backslash \; displaystyle\; c\}$, либо $1\; c\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{c\}\}\}$больше единицы и поэтому гарантирует быстрая сходимость одного из двух рядов, для больших $c\; \{\backslash \; displaystyle\; c\}$вы можете выбрать вычисление частотного спектра и преобразование во временную область с использованием дискретного преобразования Фурье.

Обобщения

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

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

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

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

Другие поля

Многие свойства ДПФ зависят только от того факта, что $e\; -\; i\; 2\; \pi \; N\; \{\backslash \; displaystyle\; e\; ^\; \{-\; \{\backslash \; frac\; \{i2\; \backslash \; pi\; \}\; \{N\}\}\}\}$- примитивный корень из единицы, иногда обозначаемый $\omega \; N\; \{\backslash \; displaystyle\; \backslash \; omega\; \_\; \{N\}\}$или $WN\; \{\backslash \; displaystyle\; W\_\; \{N\}\}$(так что $\omega \; NN\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; omega\; \_\; \{N\}\; ^\; \{N\}\; =\; 1\}$). Такие свойства включают полноту, ортогональность, свойства Планшереля / Парсеваля, периодичности, сдвига, свертки и унитарности, указанные выше, а также многие алгоритмы БПФ. По этой причине дискретное преобразование Фурье может быть определено с использованием корней из единицы в полях, отличных от комплексных чисел, и такие обобщения обычно называются теоретико-числовыми преобразованиями (NTT) в случае конечные поля. Для получения дополнительной информации см. теоретико-числовое преобразование и дискретное преобразование Фурье (общее).

Другие конечные группы

Стандартное ДПФ действует на последовательность x 0, x 1,..., x N − 1 комплексных чисел, которые можно рассматривать как функцию {0, 1,..., N - 1} → С . Многомерное ДПФ действует на многомерные последовательности, которые можно рассматривать как функции

$\{0,\; 1,\dots ,\; N\; 1\; -\; 1\}\; \times \; \cdots \; \times \; \{0,\; 1,\dots ,\; N\; d\; -\; 1\}\; \to \; C.\; \{\backslash \; Displaystyle\; \backslash \; \{0,1,\; \backslash \; ldots,\; N\_\; \{1\}\; -1\; \backslash \}\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; \backslash \; \{0,1,\; \backslash \; ldots,\; N\_\; \{d\}\; -1\; \backslash \}\; \backslash \; to\; \backslash \; mathbb\; \{C\}.\}$

Это предлагает обобщение на преобразования Фурье на произвольных конечных группах, которые действуют на функции G → C, где G - конечная группа. В этой структуре стандартное ДПФ рассматривается как преобразование Фурье на циклической группе , в то время как многомерное ДПФ представляет собой преобразование Фурье на прямой сумме циклических групп.

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

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

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

См. Также

• Сопутствующая матрица
• Матрица DFT
• Быстрое преобразование Фурье
• FFTPACK
• FFTW
• Обобщения матриц Паули
• Список преобразований Фурье
• Многомерное преобразование
• Преобразование Зака ​​
• Квантовое преобразование Фурье

Примечания

Ссылки

Дополнительная литература

• Бригам, Э. Оран (1988). Быстрое преобразование Фурье и его приложения. Энглвуд Клиффс, Нью-Джерси: Prentice Hall. ISBN 978-0-13-307505-2.
• Смит, Стивен У. (1999). «Глава 8: Дискретное преобразование Фурье». Руководство для ученых и инженеров по цифровой обработке сигналов (второе изд.). Сан-Диего, Калифорния: California Technical Publishing. 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. doi : 10.1109 / 29.1519.
• J. Х. Макклеллан; Т. В. Паркс (1972). «Собственные значения и собственные векторы дискретного преобразования Фурье». Протоколы IEEE по аудио и электроакустике. 20 (1): 66–74. doi : 10.1109 / TAU.1972.1162342.
• Брэдли В. Дикинсон; Кеннет Стейглиц (1982). «Собственные векторы и функции дискретного преобразования Фурье» (PDF). Транзакции IEEE по акустике, речи и обработке сигналов. 30 (1): 25–31. CiteSeerX 10.1.1.434.5279. doi : 10.1109 / TASSP.1982.1163843.(Обратите внимание, что в этой статье есть очевидная опечатка в таблице кратностей собственных значений: столбцы + i / −i меняются местами. Правильная таблица может можно найти в McClellan and Parks, 1972, и легко подтверждается численно.)
• F. А. Грюнбаум (1982). «Собственные векторы дискретного преобразования Фурье». Журнал математического анализа и приложений. 88 (2): 355–363. doi : 10.1016 / 0022-247X (82) 90199-8.
• Атакишиев Натиг М. Курт Бернардо Вольф (1997). «Дробное преобразование Фурье-Кравчука». Журнал Оптического общества Америки A. 14 (7): 1467–1477. Bibcode : 1997JOSAA..14.1467A. doi : 10.1364 / JOSAA.14.001467.
• C. Кандан; М. А. Кутай; Х. М. Озактас (2000). «Дискретное дробное преобразование Фурье» (PDF). Транзакции IEEE по обработке сигналов. 48 (5): 1329–1337. Bibcode : 2000ITSP... 48.1329C. doi : 10.1109 / 78.839980. hdl : 11693/11130.
• Магди Тауфик Ханна, Набила Филип Атталла Сейф и Валид Абд эль-Магуид Ахмед (2004). «Подобные собственные векторы Эрмита-Гаусса матрицы дискретного преобразования Фурье на основе сингулярного разложения ее ортогональных проекционных матриц». IEEE Transactions on Circuits and Systems I: Regular Papers. 51 (11): 2245–2254. doi : 10.1109 / TCSI.2004.836850. CS1 maint: несколько имен: список авторов (ссылка )
• Шамгар Гуревич; Ронни Хадани (2009). диагонализация дискретного преобразования Фурье ». Прикладной и вычислительный гармонический анализ. 27 (1): 87–99. arXiv : 0808.3281. doi : 10.1016 / j.acha.2008.11.003. Препринт в.
• Шамгар Гуревич; Ронни Хадани; Нир Сочен (2008). «Конечный гармонический осциллятор и его приложения к последовательностям, коммуникации и радар ". IEEE Transactions по теории информации. 54 (9): 4239–4253. arXiv : 0808.1495. Bibcode : 2008arXiv0808.1495G. doi : 10.1109 / TIT.2008.926440. Препринт в.
• Хуан Г. Варгас-Рубио; Балу Сантханам (2005). многоугольное центрированное дискретное дробное преобразование Фурье ". Письма об обработке сигналов IEEE. 12 (4): 273–276. Bibcode : 2005ISPL... 12..273V. doi : 10.1109 / LSP.2005.843762.
• F.N. Конг (2008). "Аналитические выражения двух дискретных сигналов Эрмита-Гаусса". IEEE Transactions on Circuits and Systems II: Express Briefs. 55 (1): 56–60. doi : 10.1109 / TCSII.2007.909865.

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

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