Общие сведения о БПФ

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

Для вычисления одного коэффициента ДПФ необходимо выполнить операций комплексного умножения и суммирования. Расчет всего ДПФ, содержащего спектральных коэффициентов, потребует паропераций «умножение – сложение».

Если не является простым числом и может быть разложено на множители (является целочисленной степенью 2: N= , - целое число), то процесс вычислений можно ускорить, разделив исходную последовательность на части, вычислив для них ДПФ и объединив результаты.

При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления исходной последовательности на части : прореживание по времени или по частоте, и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).?

Первый алгоритм БПФ с основанием 2, известный как алгоритм БПФ Кули-Тьюки был опубликован в 1965 г. в США учеными Кули и Тьюки.