fft

Быстрое преобразование Фурье.

Библиотека

EngeeDSP

Синтаксис

Вызов функции

Y = fft(X) — вычисляет Дискретное преобразование Фурье (ДПФ) для аргумента X, используя алгоритм быстрого преобразования Фурье (БПФ). Аргумент Y имеет тот же размер, что и X.
- Если X — вектор, то fft(X) возвращает преобразование Фурье для этого вектора.
- Если X — матрица, то fft(X) рассматривает столбцы аргумента X как векторы и возвращает преобразование Фурье для каждого столбца.
- Если X — многомерный массив, то fft(X) рассматривает значения по первому измерению массива, размер которых не равен 1, как векторы и возвращает преобразование Фурье для каждого вектора.

Y = fft(X,n) — возвращает n-точечное ДПФ.
- Если X — вектор и длина X меньше n, то X дополняется нулями до длины n.
- Если X — вектор и длина X больше n, то X усекается до длины n.
- Если X — матрица, то каждый столбец обрабатывается как вектор.
- Если X — многомерный массив, то первое измерение массива, размер которого не равен 1, обрабатывается как вектор.

Y = fft(X,n,dim) — возвращает преобразование Фурье по размерности dim. Например, если X — матрица, то fft(X,n,2) возвращает n-точечное преобразование Фурье для каждой строки.

Аргументы

Входные аргументы

# X — входной массив
вектор | матрица | многомерный массив

Details

Входной массив, заданный как вектор, матрица или многомерный массив.

Если X — пустая матрица размером 0 на 0, то fft(X) возвращает пустую матрицу размером 0 на 0.

Типы данных	`Float64`, `Float32`, `Int8`, `Int16`, `Int32`, `UInt8`, `UInt16`, `UInt32`, `Bool`
Поддержка комплексных чисел	Да

# n — длина преобразования
[] (по умолчанию) | неотрицательный целочисленный скаляр

Details

Длина преобразования, заданная как [] или неотрицательный целочисленный скаляр. Указание положительного целого числа для длины преобразования может повысить производительность функции fft. Длина обычно указывается как степень двойки или значение, которое можно разложить на множители (с простыми множителями не более 7). Если n меньше длины сигнала, функция fft игнорирует оставшиеся значения сигнала после n-го элемента и возвращает усеченный результат. Если n равно 0, функция fft возвращает пустую матрицу.

Типы данных

Float64, Float32, Int8, Int16, Int32, UInt8, UInt16, UInt32, Bool

# dim — измерение, по которому выполняется операция
положительный целочисленный скаляр

Details

Измерение, по которому выполняется операция, задается как положительное целое число. Если измерение не указано, по умолчанию используется первое измерение массива, размер которого не равен 1.

fft(X,[],1) выполняет операцию по столбцам массива X и возвращает преобразование Фурье для каждого столбца.
fft(X,[],2) выполняет операцию по строкам массива X и возвращает преобразование Фурье для каждой строки.

Если dim больше ndims(X), то fft(X,[],dim) возвращает X. Если указано n, fft(X,n,dim) дополняет или усекает X до длины n по измерению dim.

Типы данных

Float64, Float32, Int8, Int16, Int32, UInt8, UInt16, UInt32, Bool

Выходные аргументы

# Y — представление в частотной области
вектор | матрица | многомерный массив

Details

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

Если аргумент X имеет тип Float32, то функция fft вычисляется с одинарной точностью, а Y также имеет тип Float32. В противном случае Y возвращается как тип Float64.

Размер аргумента Y определяется следующим образом:

Для Y = fft(X) или Y = fft(X,[],dim) размер Y равен размеру X.
Для Y = fft(X,n,dim) значение size(Y,dim) равно n, в то время как размер всех остальных измерений остается таким же, как у X.

Если X — вещественное число, то Y является сопряженно-симметричным, а количество уникальных точек в Y равно ceil((n+1)/2).

Типы данных

Float64, Float32

Дополнительно

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

Y = fft(X) и X = ifft(Y) реализуют преобразование Фурье и обратное преобразование Фурье соответственно. Для X и Y длины n эти преобразования определяются следующим образом:

где — один из корней из единицы.

Советы

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

Алгоритмы

Функции БПФ (fft, fft2, ifft, ifft2) основаны на библиотеке FFTW [1] [2].

Список литературы

FFTW (https://www.fftw.org)
Frigo, M., and S. G. Johnson. «FFTW: An Adaptive Software Architecture for the FFT.» Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. Vol. 3, 1998, pp. 1381–1384.