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

Простейший способ вычисления дискретного преобразования Фурье (ДПФ) – прямое суммирование, оно приводит к N операциям на каждый коэффициент. Всего коэффициентов N, так что общая сложность . Такой подход не представляет практического интереса, так как существуют гораздо более эффективные способы вычисления ДПФ называемые быстрым преобразованием Фурье (БПФ), имеющее сложность. БПФ применяется только к последовательностям, имеющим длину (число элементов) кратную степени 2. Наиболее общий принцип, заложенный в алгоритм БПФ, заключается в разбиении входной последовательности на две последовательности половинной длины. Первая последовательность заполняется данными с четными номерами, а вторая – с нечетными. Это дает возможность вычисления коэффициентов ДПФ через два преобразования размерностьюN/2.

Обозначим , тогда.

Для m<N/2 тогда можно записать. Учитывая, что элементы ДПФ с индексом большим, чемN/2 являются комплексно сопряженными к элементам с индексами меньшимиN/2 можно записать. Таким образом, можно вычислить БПФ длиннойN, используя два ДПФ длиннойN/2. Полный алгоритм БПФ заключается в рекурсивном выполнении выше описанной процедуры, начиная с объединения одиночных элементов в пары, затем в четверки и так до конца.