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

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

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

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

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

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