14. Постановка задачи

Физический смысл дискретного преобразования Фурье состоит в том, чтобы представить некоторый дискретный сигнал в виде суммы гармоник. Параметры каждой гармоники вычисляются прямым преобразованием, а сумма гармоник - обратным.

Дискретное преобразование Фурье трансформирует последовательность комплексных (либо вещественных) чисел x_n  в последовательность комплексных чисел X_n . Прямое и обратное преобразования Фурье определяются, как:

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

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