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

 

Из формул  и видно, что для вычисления ДПФ и обратного ДПФ последовательности из N элементов требуется выполнить N2 с комплексными числами. Если число элементов массивов составляет порядка тысячи и более, то время необходимое на выполнение этих преобразований резко возрастает и теряется возможность обработки сигналов в реальное время.

В 60-е годы прошлого века Кули и Тьюки предложили метод вычисления коэффициентов Фурье, позволяющий снизить объем вычислений до N×ln2 N операций. Этот метод получил название алгоритма быстрого преобразования Фурье (БПФ).

Рассмотрим основную идею алгоритма БПФ для случая, когда число отсчетов N = 2p, где p – целое число.