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

Алгоритмы быстрого преобразования Фурье (БПФ) предназначены для эффективного вычисления дискретного преобразования Фурье (ДПФ), которое представляет собой следующую сумму:

где , , ,  – выборка функции,  – выборка ее фурье-образа.

Одним из самых известных алгоритмов одномерного БПФ является алгоритм Кули-Тьюки по основанию 2. Он достигает своей вычислительной эффективности благодаря стратегии divide et impera. При использовании алгоритма Кули-Тьюки количество отсчетов в выборке функции должно быть кратно степени 2. Двумерное разбиение по основанию 2, делит выборку элементов на четыре выборки элементов и так далее до тех пор, пока не останутся выборки элементов, фурье-преобразование которых и следует выполнить (Рис. 1). Элементарное фурье-преобразование выборки элементов принято называть “бабочкой”.

Рис. 1. Схема прореживания двумерного ДПФ по основанию 2

Таким образом, при вычислении одномерного ДПФ длиной N необходимо выполнить двухточечных ДПФ, каждое из которых требует одно комплексное умножение и два комплексных сложения. Алгоритм двумерного ДПФ с разбиением на строки и столбцы требует проведения 2N одномерных ДПФ и вычислительная сложность его составляет: комплексных умножений и комплексных сложений.