Приложение 8

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

Свойства и структура алгоритма

Общее описание алгоритма

Простой алгоритм Кули-Тьюки - один из вариантов быстрого преобразования Фурье для комплексных векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др. Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

Математическое описание алгоритма

Исходные данные: преобразуемый комплексный вектор [math]\displaystyle{ a }[/math] (элементы [math]\displaystyle{ a_{i} }[/math]).

Вычисляемые данные: комплексный вектор - результат преобразования [math]\displaystyle{ b }[/math] (элементы [math]\displaystyle{ b_{i} }[/math]).

При этом размерность векторов - [math]\displaystyle{ n }[/math], причём [math]\displaystyle{ n = 2^l }[/math]

Рекурсивное описание

Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2, получившиеся элементы умножаются на поворотные множители [math]\displaystyle{ exp (2 \pi i(m-1)(j-1)/n) }[/math] ([math]\displaystyle{ m }[/math] - номер строки, [math]\displaystyle{ j }[/math] - номер столбца), после чего выполняется БПФ порядка [math]\displaystyle{ n/2 }[/math] над каждым из столбцов. Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется [math]\displaystyle{ n/2 }[/math] "бабочек", а шагов - [math]\displaystyle{ l-1 }[/math]. Последний, [math]\displaystyle{ l }[/math]-й шаг вычисляет только суммы и разности.

Тригонометрические функции

Несмотря на то, что в вычислениях используются поворотные множители [math]\displaystyle{ exp (2 \pi i(m-1)(j-1)/n) }[/math], нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их [math]\displaystyle{ (1/2) n log_{2} n }[/math] штук, при этом в [math]\displaystyle{ n/2 }[/math] из них умножение не выполняется.

Макроструктура алгоритма

Макроструктура алгоритма лучше всего описывается рекурсивно, как [math]\displaystyle{ n/2 }[/math] преобразований Фурье порядка 2, умножение [math]\displaystyle{ n/2 }[/math] пар комплексных чисел и затем 2 БПФ порядка [math]\displaystyle{ n/2 }[/math].

Схема реализации последовательного алгоритма

Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их [math]\displaystyle{ log_{2} n }[/math]) для выполнения "бабочки" все элементы разбиваются на [math]\displaystyle{ n/2 }[/math] пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - [math]\displaystyle{ n/2 }[/math]. При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

Последовательная сложность алгоритма

Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за [math]\displaystyle{ n log_{2} n }[/math] операций комплексного сложения и [math]\displaystyle{ (1/2) n log_{2} n }[/math]операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к линейно-логарифмическому классу по последовательной сложности.

Информационный граф

Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива

Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

Ресурс параллелизма алгоритма

Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из [math]\displaystyle{ log_{2} n }[/math] операций комплексного сложения/вычитания и [math]\displaystyle{ log_{2} n }[/math] операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к логарифмическому классу по параллельной сложности. По ширине ЯПФ сложность алгоритма линейна.

Входные и выходные данные алгоритма

Входные данные: вектор [math]\displaystyle{ a }[/math] (элементы [math]\displaystyle{ a_{i} }[/math]).

Объём входных данных: [math]\displaystyle{ n }[/math] .

Выходные данные: вектор [math]\displaystyle{ b }[/math] (элементы [math]\displaystyle{ b_{i} }[/math]).

Объём выходных данных: [math]\displaystyle{ n }[/math].

Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейным.

При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – логарифмическая.

При этом алгоритм полностью детерминирован.

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