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

Математические основы FFT

DFT преобразует последовательность комплексных чисел в частотные компоненты. Она определяется как:

X(k) = ∑n=0N-1 x(n) e-2πi kn/N

где x(n) — входная последовательность, X(k) — частотный компонент, и N — длина последовательности.

Алгоритм Кули-Туки (Cooley-Tukey Algorithm)

Алгоритм Кули-Туки разбивает DFT на более мелкие DFT, разделяя последовательность на четные и нечетные части:

X(k) = ∑n=0N-1 x(n) e-2πi kn/N

которые могут быть переписаны как:

X(k) = ∑n=0N/2-1 x(2n) e-2πi 2n k/N + e-2πi k/N ∑n=0N/2-1 x(2n+1) e-2πi 2n k/N

Это разделение позволяет рекурсивные вычисления меньших DFT, уменьшая вычислительную сложность от O(N2) до O(N log N).

Применение алгоритма

Алгоритм FFT неоднократно применяет рекурсивное разложение до тех пор, пока не будет достигнут базовый случай размера 1.Результаты затем объединяются с использованием коэффициентов витка, которые являются сложными экспоненциальными терминами:

WN(k) = e-2πi k/N

Эти факторы корректируют фазу меньших DFT во время рекомбинации, что позволяет эффективно вычислять полное преобразование.