2.3.3. Алгоритм быстрого преобразования Фурье по векторному основанию

Алгоритм одномерного быстрого преобразования Фурье достигает своей вычислительной эффективности благодаря стратегии divide et impera. Если длина ДПФ выражается, например, степенью двух, то ДПФ можно представить как комбинацию двух ДПФ половинной длины, каждое из которых в свою очередь можно заменить комбинацией двух ДПФ в одну четверть длины и т. д. Двумерный алгоритм ДПФ по векторному основанию по существу идентичен этому подходу. Двумерное ДПФ разбивается на последовательно меньшие двумерные ДПФ до тех пор, пока в конечном счете не остаются тривиальные двумерные ДПФ, которые и следует выполнить.

Можно вывести вариант алгоритма «прореживания» во времени, выражая -точечное ДПФ через четыре -точечных ДПФ (если  и  делятся на 2). Для простоты предположим, что . Процесс суммирования ДПФ выражения (2.71) можно разбить на 4 суммирования: первое по отсчетам  для  и  четных; второе - для  четных, а  нечетных; третье - для  нечетных, а  четных; четвертое -для  и  нечетных. Это дает

, где                   (2.77a)

.                                   (2.77б)

,                  (2.77в)

,                              (2.77г)

.              (2.77д)

Множества , ,  и  периодичны no  с горизонтальным и вертикальным периодами . Используя этот факт, а также то, что , можно из выражения (2.77а) вывести следующие тождества:

,              (2.78a)

,     (2.78б)

,      (2.78в)

.            (2.78г)

Эти соотношения показывают, каким образом вычислить четыре точки ДПФ , ,  и  для конкретных значений  из четырех точек , ,  и . Мы также видим, что необходимые отсчеты  (и аналогично остальные массивы ) можно получить путем -точечного ДПФ. Таким образом, выражение (2.77) описывает отсчеты -точечного ДПФ  через четыре -точечных ДПФ. По аналогии с одномерным случаем схема вычислений по формуле (2.78) называется «бабочкой», или, более правильно «бабочкой» по основанию . Отдельно «бабочка» по основанию  показана на рис. 2.4. Каждая «бабочка» требует выполнения трех комплексных умножений и восьми комплексных сложений (см. упр. (2.11), а для вычисления всех отсчетов  через , ,  и  необходимо вычислить  «бабочек». На рис. 2.5 представлена графическая схема последовательности, этих операций.

Рис. 2.4. «Бабочка» по основанию . Вычисление выходных данных по входным требует трех комплексных умножений и восьми комплексных сложений.

Рис. 2.5. Первая стадия «прореживания» БПФ по основанию . Для простоты показана только одна из четырех «бабочек».

Если  само делится на 2, то же самое разложение можно применить для вычисления -преобразований , ,  и . Этот процесс «прореживания» может продолжаться до тех пор, пока не останутся только массивы , подлежащие преобразованию; его можно выполнить, используя выражение (2.64), где вообще не требуется умножений. Полное преобразование массива  по векторному основанию показано на рис. 2.6.

Рис. 2.6. Полное -точечное ДПФ по основанию . На втором этапе показана лишь одна из четырех «бабочек».

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

,                                         (2.79)

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

Схема рис. 2.6 иллюстрирует операции, которые необходимо произвести при выполнении преобразования. Делая еще один шаг вперед, можно предположить, что она показывает также порядок, в котором следует располагать данные. В этом отношении мы связаны необходимостью изображать графическую схему таким образом, чтобы входные и выходные массивы выглядели одномерными, хотя на самом деле они двумерны. Выходной массив на схеме - это двумерный массив, имеющий обычный порядок.

Из-за последовательных делений на группы с четными и нечетными индексами данные в одномерном ДПФ воспринимаются в двоично-инвертированном порядке. Например, для  индекс  при последовательном «прореживании» будет классифицирован как четный, четный, нечетный, нечетный, поскольку остатками от деления 12 на 2 последовательно будут 0, 0, 1 и 1. Разумеется, 0011 - всего лишь двоично-инвертированное 4-битовое представление числа 12 (1100). В двумерном случае из-за последовательного разделения  на четно-четные, нечетно-четные и т. д. выходные данные будут получаться в порядке с инверсией расположения битов по обоим индексам  и . Этот порядок показан на рис. 2.7.

Рис. 2.7. Двумерная последовательность с двоично-инвертированным порядком расположения отсчетов для .

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

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