Все формулы РФ

Информатика / Алгоритмы и анализ данных

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

Дискретное преобразование Фурье переводит конечную последовательность в комплексные частотные коэффициенты. Обратная сумма восстанавливает все отсчёты; знак экспоненты и нормировку нужно выбирать согласованно.

Опубликовано: Обновлено:

Кодирование информацииАнализ данныхСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$X_k=\sum_{n=0}^{N-1}x_n e^{-2\pi i kn/N},\qquad x_n=\frac1N\sum_{k=0}^{N-1}X_k e^{2\pi i kn/N}$$
Схема ДПФ: два коэффициента одного косинуса
ДПФ: два коэффициента одного косинусаДПФ: два коэффициента одного косинуса00122032

Для x=(1;0;−1;0) показаны модули Xₖ. Горизонталь — индекс k, высота — |Xₖ|.

Обозначения

$xₙ$
отсчёт сигнала с номером n, единица сигнала
$Xₖ$
комплексный коэффициент прямого ДПФ, единица сигнала
$N$
число отсчётов, 1
$i$
мнимая единица, i²=−1, 1
$n,k$
целые индексы от 0 до N−1, 1

Условия применения

Дана конечная последовательность длины N≥1. Для физической частотной шкалы отсчёты должны быть равноотстоящими по времени. Прямая сумма здесь не нормирована, а обратная делится на N; другие соглашения требуют изменения обеих формул.

Ограничения

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

Подробное объяснение

Каждый коэффициент складывает отсчёты с вращающимися комплексными весами. Если изменение сигнала согласовано с выбранной гармоникой, вклады складываются; для других гармоник они могут сокращаться. Нулевая гармоника имеет все веса, равные единице, поэтому X₀ — сумма отсчётов.

Обратная формула следует из ортогональности корней единицы: сумма exp(2πi·km/N) по k равна N при m, кратном N, и нулю в остальных случаях. При подстановке прямой суммы в обратную остаётся только нужный отсчёт. Деление на N компенсирует именно эту сумму весов.

Для вещественных данных коэффициенты с индексами k и N−k комплексно сопряжены. Поэтому отрицательная частота не означает отдельную физическую волну: она входит в комплексную запись вещественной синусоиды. При чётном N особый индекс N/2 соответствует частоте Найквиста и не образует пары с другим индексом.

БПФ — способ быстро вычислить то же самое ДПФ. Изменение алгоритма не меняет определение Xₖ. Проверяйте нормировку в библиотеке: перенос коэффициентов из соглашения с множителем 1/√N в приведённую обратную формулу изменит масштаб восстановленного сигнала.

Как пользоваться формулой

  1. Зафиксируйте длину последовательности и нумерацию с нуля; выпишите соглашение о знаке прямой экспоненты.
  2. Для каждого частотного индекса умножьте все отсчёты на соответствующие комплексные веса и сложите произведения.
  3. Сопоставьте сопряжённые коэффициенты для вещественного сигнала и проверьте нулевой коэффициент суммой отсчётов.
  4. Выполните обратную сумму с положительным знаком и делением на длину; сравните восстановленные отсчёты с исходными.

Историческая справка

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

Во второй половине XX века быстрые алгоритмы сделали спектральную обработку обычным инструментом цифровых измерений. Современные руководства NumPy и SciPy поэтому рассматривают вместе определение суммы, обратное преобразование, расположение отрицательных частот и выбор нормировки. Имя Фурье указывает на гармонический анализ; саму конечную запись не следует представлять как единоличное изобретение автора любого конкретного алгоритма БПФ.

Историческая линия формулы

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

Пример

Дана безразмерная запись x=(1;0;−1;0), N=4. Для k=0 сумма равна 0. Для k=1 ненулевые слагаемые: 1·1 и (−1)·exp(−πi)=1, поэтому X₁=2. Для k=2 они равны 1 и −1, сумма 0. Для k=3 получаем снова 2. Итак, X=(0;2;0;2). Обратная формула даёт x₀=(2+2)/4=1, x₁=(2i−2i)/4=0, x₂=(−2−2)/4=−1, x₃=(−2i+2i)/4=0. Получены ровно исходные четыре числа. Коэффициенты двух сопряжённых гармоник складываются в вещественный косинус единичной амплитуды, а не в волну амплитуды 2. Нулевая сумма входа согласуется с отсутствием постоянной составляющей.

Частая ошибка

Не делите прямой и обратный результат на N одновременно: тогда восстановленный сигнал уменьшится в N раз. Модуль Xₖ ещё не равен амплитуде вещественного косинуса. Не меняйте местами временной и частотный индексы при подписи результата. БПФ и ДПФ не обозначают разные физические преобразования.

Практика

Задачи с решением

Постоянная запись

Условие. Найдите ДПФ x=(3;3;3;3).

Решение. X₀=3+3+3+3=12; для k=1,2,3 сумма корней единицы равна 0.

Ответ. (12;0;0;0).

Одиночный импульс

Условие. Найдите ДПФ x=(1;0;0;0).

Решение. В каждой сумме остаётся только n=0 с весом exp(0)=1.

Ответ. (1;1;1;1).

Дополнительные источники

  • https://numpy.org/doc/stable/reference/routines.fft.html
  • https://docs.scipy.org/doc/scipy/tutorial/fft.html
  • https://numpy.org/doc/stable/reference/generated/numpy.fft.fft.html

Связанные формулы

Информатика

Частоты и амплитуды по коэффициентам ДПФ

$\Delta f=\frac{f_s}{N},\quad f_k=\frac{kf_s}{N},\quad A_k=\frac{2|X_k|}{N}\quad(0<k<N/2)$

Шаг частот ДПФ равен частоте дискретизации, делённой на длину записи. Для вещественной гармоники точно на внутреннем частотном отсчёте амплитуда равна удвоенному модулю коэффициента, делённому на число отсчётов.

Информатика

Линейная свёртка конечных последовательностей

$y_n=\sum_{k=-\infty}^{\infty}x_k h_{n-k},\qquad L_y=L_x+L_h-1$

Линейная свёртка складывает сдвинутые копии одной последовательности с весами другой. Для конечных массивов, продолженных нулями, полный результат содержит сумму их длин минус один отсчёт.

Информатика

Размер аудиофайла по частоте дискретизации

$I=f\cdot t\cdot b\cdot c$

Размер аудиофайла по частоте дискретизации: формула I=f\cdot t\cdot b\cdot c помогает величины I, f, t, b заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.