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

Модуль SciPy scipy.fft является более полным надмножеством numpy.fft, который включает только базовый набор процедур.

Стандартные БПФ

fft(a[, n, axis, norm, out])	Вычисляет одномерное дискретное преобразование Фурье.
ifft(a[, n, axis, norm, out])	Вычисляет одномерное обратное дискретное преобразование Фурье.
fft2(a[, s, axes, norm, out])	Вычислить двумерное дискретное преобразование Фурье.
ifft2(a[, s, axes, norm, out])	Вычислить двумерное обратное дискретное преобразование Фурье.
fftn(a[, s, axes, norm, out])	Вычисляет N-мерное дискретное преобразование Фурье.
ifftn(a[, s, axes, norm, out])	Вычислить N-мерное обратное дискретное преобразование Фурье.

Вещественные БПФ

rfft(a[, n, axis, norm, out])	Вычисляет одномерное дискретное преобразование Фурье для действительного входа.
irfft(a[, n, axis, norm, out])	Вычисляет обратную матрицу rfft.
rfft2(a[, s, axes, norm, out])	Вычислить двумерное БПФ вещественного массива.
irfft2(a[, s, axes, norm, out])	Вычисляет обратную матрицу rfft2.
rfftn(a[, s, axes, norm, out])	Вычислить N-мерное дискретное преобразование Фурье для вещественного входа.
irfftn(a[, s, axes, norm, out])	Вычисляет обратную матрицу rfftn.

Эрмитовы БПФ

hfft(a[, n, axis, norm, out])	Вычислить БПФ сигнала, имеющего эрмитову симметрию, т.е. вещественный спектр.
ihfft(a[, n, axis, norm, out])	Вычислить обратное БПФ сигнала, имеющего эрмитову симметрию.

Вспомогательные процедуры

fftfreq(n[, d, device])	Возвращает частоты выборок дискретного преобразования Фурье.
rfftfreq(n[, d, device])	Возвращает частоты дискретного преобразования Фурье (для использования с rfft, irfft).
fftshift(x[, axes])	Сдвинуть компонент нулевой частоты в центр спектра.
ifftshift(x[, axes])	Обратная величина fftshift.

Основная информация

Анализ Фурье — это принципиально метод выражения функции как суммы периодических компонентов и восстановления функции из этих компонентов. Когда и функция, и её преобразование Фурье заменяются дискретизированными аналогами, это называется дискретным преобразованием Фурье (ДПФ). ДПФ стало основой численных вычислений частично из-за очень быстрого алгоритма его вычисления, называемого быстрым преобразованием Фурье (БПФ), который был известен Гауссу (1805) и был представлен в современной форме Кули и Тьюки [CT]. Press et al. [NR] предоставляют доступное введение в анализ Фурье и его приложения.

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

Детали реализации

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

\[A_k = \sum_{m=0}^{n-1} a_m \exp\left\{-2\pi i{mk \over n}\right\} \qquad k = 0,\ldots,n-1.\]

ДПФ в общем случае определён для комплексных входных и выходных данных, и одночастотная компонента на линейной частоте \(f\) представлен комплексной экспонентой \(a_m = \exp\{2\pi i\,f m\Delta t\}\), где \(\Delta t\) является интервалом выборки.

Значения в результате следуют так называемому «стандартному» порядку: Если A = fft(a, n), затем A[0] содержит нулевую частоту (сумму сигнала), которая всегда чисто вещественная для вещественных входных данных. Затем A[1:n/2] содержит положительно-частотные члены, и A[n/2+1:] содержит члены с отрицательными частотами в порядке убывания отрицательной частоты. Для чётного числа входных точек, A[n/2] представляет как положительную, так и отрицательную частоту Найквиста, а также является чисто вещественной для вещественного ввода. Для нечётного числа входных точек, A[(n-1)/2] содержит наибольшую положительную частоту, в то время как A[(n+1)/2] содержит наибольшую отрицательную частоту. Процедура np.fft.fftfreq(n) возвращает массив, содержащий частоты соответствующих элементов на выходе. Подпрограмма np.fft.fftshift(A) сдвигает преобразования и их частоты, чтобы поместить компоненты нулевой частоты в середину, и np.fft.ifftshift(A) отменяет этот сдвиг.

Когда входные данные a является сигналом во временной области и A = fft(a), np.abs(A) это его амплитудный спектр и np.abs(A)**2 является его спектром мощности. Фазовый спектр получается с помощью np.angle(A).

Обратное дискретное преобразование Фурье определяется как

\[a_m = \frac{1}{n}\sum_{k=0}^{n-1}A_k\exp\left\{2\pi i{mk\over n}\right\} \qquad m = 0,\ldots,n-1.\]

Он отличается от прямого преобразования знаком экспоненциального аргумента и стандартной нормализацией на \(1/n\).

Повышение типа

numpy.fft повышает float32 и complex64 массивы в float64 и complex128 массивы соответственно. Для реализации БПФ, которая не повышает типы входных массивов, см. scipy.fftpack.

Нормализация

Аргумент norm указывает, какое направление пары прямого/обратного преобразований масштабируется и с каким коэффициентом нормализации. По умолчанию нормализация ("backward") имеет прямые (прямые) преобразования без масштабирования, а обратные (обратные) преобразования масштабируются на \(1/n\). Можно получить унитарные преобразования, установив аргумент ключевого слова norm to "ortho" так что и прямое, и обратное преобразования масштабируются \(1/\sqrt{n}\). Наконец, установка ключевого аргумента norm to "forward" имеет прямые преобразования, масштабированные на \(1/n\) и обратные преобразования без масштабирования (т.е. прямо противоположно умолчанию "backward"). None является псевдонимом опции по умолчанию "backward" для обратной совместимости.

Вещественные и эрмитовы преобразования

Когда входные данные чисто вещественные, их преобразование является эрмитовым, т.е. компонент на частоте \(f_k\) является комплексно-сопряжённым компоненту на частоте \(-f_k\), что означает, что для действительных входных данных нет информации в компонентах отрицательной частоты, которая не была бы уже доступна из компонентов положительной частоты. Семейство rfft функции предназначены для работы с реальными входными данными и используют эту симметрию, вычисляя только положительные частотные компоненты, вплоть до частоты Найквиста. Таким образом, n входные точки производят n/2+1 комплексные выходные точки. Обратные этой семьи предполагают ту же симметрию своего ввода, и для вывода n точки используют n/2+1 входные точки.

Соответственно, когда спектр чисто вещественный, сигнал является эрмитовым. hfft семейство функций использует эту симметрию, применяя n/2+1 комплексные точки во входной (временной) области для n действительные точки в частотной области.

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

Более высокие размерности

В двух измерениях ДПФ определяется как

\[A_{kl} = \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} a_{mn}\exp\left\{-2\pi i \left({mk\over M}+{nl\over N}\right)\right\} \qquad k = 0, \ldots, M-1;\quad l = 0, \ldots, N-1,\]

который распространяется очевидным образом на более высокие размерности, и обратные в более высоких размерностях также распространяются аналогично.

Ссылки

[CT]

Кули, Джеймс У., и Джон У. Тьюки, 1965, "Алгоритм для машинного вычисления комплексных рядов Фурье," Math. Comput. 19: 297-301.

[NR]

Press, W., Teukolsky, S., Vetterline, W.T., и Flannery, B.P., 2007, Numerical Recipes: The Art of Scientific Computing, гл. 12-13. Cambridge Univ. Press, Cambridge, UK.

Примеры

Примеры см. в различных функциях.