Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 193
Текст из файла (страница 193)
Чтобы превратить описанную последовательность действий в код, используем массив А [О..п — 1], который первоначально содержит элементы исходного вектора а в том порядке, в ютором они перечислены в листовых узлах дерева на рис. 30.4. (Позже мы покажем, как определить этот порядок, который называется норазрядно обратной перестановкой (Ь)ргечегза1 реппщайоп).) Поскольку объединение в пары необходимо выполнять на каждом уровне дерева, введем в качестве счетчика уровней переменную я, которая изменяется от 1 (на нижнем уровне, где составляются пары для вычисления 2-элементных ДПФ) до 1я п (в вершине, где объединяются два п/2-элементных ДПФ для получения окончательного результата). Таким образом, алгоритм имеет следующую структуру: ! !ог в — 1 го )яп 2 г!о$ог)а -О!оп — 1Ьу2' 3 до Обьединяем два 2' '-элементных ДПФ из А [!а ..
)а + 2' т — 1] и А[В + 2' т .. )а + 2' — 1] в одно 2'-элементное ДПФ в А[В .. )а + 2' — 1] Тело цикла (строка 3) можно более точно описать с помощью псевдокода. Копируем цикл !Ьг из процедуры Кассина)че РРТ, отождествив у[о) с А[)а..)а + 2' '— — 1] и у1)1 с А [)с+ 2' т..)а+ 2' — 1]. Поворачивающий множитель, используемый в каждом преобразовании бабочки, зависит от значения я; это степень ы где тп = 2'. (Мы ввели переменную т исключительно для того, чтобы формула была удобочитаемой.) Введем еще одну временную переменную и, которая позволит нам выполнять преобразование бабочки на месте, без привлечения до- 946 Часть ЧП. Избранные темы полннтельной памяти. Заменив строку 3 в общей схеме телом цикла, получим следующий псевдокод, образующий базис параллельной реализации, которая будет представлена далее.
В данном коде сначала вызывается вспомогательная процедура В1т КечекБе Согч(а, А), копирующая вектор а в массив А в том порядке, в котором нам нужны эти значения. 1теклт1че РРТ(а) 1 В1т Кечекзе СОРУ(а,А) 2 и — 1еиуГЛ[а] С> и является степенью 2. 3 аког в — 1 Го 1к и 4 доги -2' 5 2~Н/тл т б Гог 1с — 0 1о и — 1 Ьу т 7 бо ы — 1 8 тог2' -0 гога/2 — 1 9 бо 1 — ыА[Й+ 7'+ гп/2] 1О и — А[/с+ 2] 11 А[/с + 2] ~ — и + 1 12 А [к + 7 + гп/2] — и — ~ 13 со < — сом~д Каким образом процедура В1т Кечекзе Согч размещает элементы входного вектора а в массиве А в требуемом порядке? Порядок следования листов на рис.
30.4 является обратной перестановкой, или реверсом битов (Ь11-гечегза1 реппп1абоп), т.е. если геч (1с) — и-битовое целое число, образованное путем размещения битов исходного двоичного представления к в обратном порядке (" задом наперед"), то элемент аь следует поместить в массиве на место А [геч (/с)].
На рис. 30.4, например, листовые узлы следуют в таком порядке: О, 4, 2, 6, 1, 5, 3, 7; в двоичном представлении эта последовательность записывается как 000, 100, 010, 110, 001, 101, О! 1, 111; после записи битов каждого значения в обратном порядке получается обычная числовая последовательность: 000, 001, 010, 011, 100, 101, 110, 111. Чтобы убедиться, что нам нужна именно обратная перестановка битов, заметим, что на верхнем уровне дерева индексы, младший бнт которых равен О, помещаются в левое поддерево, а индексы, младший бит которых равен 1, помещаются в правое поддерево. Исключая на каждом уровне младший бит, мы продолжаем процесс вниз по дереву, пока не получим в листовых узлах порядок, заданный обратной перестановкой битов. Поскольку функция геч (/с) легко вычисляется, процедуру В ге Кечекзе Согч можно записать следующим образом: Глава 30.
Полнномы н быстрое преобразование Фурье 947 В1т Кечейзе СОРУ(а, А) 1 п — 1епдса[а[ 2 Гог)с — Осоп — 1 3 с)о А[геч()с)) — аь Итеративная реализация БПФ выполняется за время О (и!8 п). Обращение к процедуре Вп' Кечекзе Сору(а,А) выполняется за время 0(п18п), поскольку проводится п итераций, а целое число от 0 до п — 1, содержащее 18 и битов, можно преобразовать к обратному порядку за время 0 (18 п)з. (На практике мы обычно заранее знаем начальное значение п, поэтому можно составить таблицу, отображающую )с в геч (lс), в результате процедура Взт Кечекзе Сору будет выполняться за время О (и) с малой скрытой константой.
В качестве альтернативного подхода можно использовать схему амортизированного обратного бинарного битового счетчика, описанную в задаче 17-1.) Чтобы завершить доказательство того факта, что процедура 1тевлпче РРТ выполняется за время О (и !я п), покажем, что число Ь (п) выполнений тела самого внутреннего цикла (строки 8-13) составляет 6 (и!Еи). Цикл Гог (строки 6-13) повторяется п/гп = и/2' раз для каждого значения в, а внутренний цикл (строки 8-13) повторяется ги/2 = 2' 1 раз. Отсюда !кп !яи Г.( )=')' — ", 2'-'= )'-"=О( 18 ) в=1 в=1 Параллельная схема БПФ Чтобы получить эффективный параллельный алгоритм БПФ, можно использовать многие свойства, которые позволили нам реализовать эффективный итеративный алгоритм БПФ. Мы будем представлять параллельный алгоритм БПФ в виде схемы, которая похожа на схемы сравнения, описанные в главе 27.
Вместо компараторов в схеме БПФ используются преобразования бабочки, показанные на рис. 30.36. В данном случае также применимо понятие глубины, введенное нами в главе 27. Схема процедуры РдкАьЕЕь РРТ, вычисляющей БПФ для п введенных значений при и = 8, показана на рис. 30.5. Она начинается с поразрядной обратной перестановки исходных значений, затем следует 18 и этапов, на каждом из которых параллельно производится и/2 преобразований бабочки.
Таким образом, глубина схемы составляет 6 (18 п). На рисунке каждое преобразование бабочки получает в качестве исходных значения, поступающие по двум проводам, вместе с поворачивающим множителем, и передает полученные значения на два выходящих провода.
Различные этапы каскада преобразований бабочки нумеруются в соответствии с итерациями 'Интересные реаяизаиии реверса битов рассматриваются в разделе 7.1 книги Г. Уоррен. Алгоритмические трюки для программистов. — Мл Издательский дом "Вильямс", 2003. — Прим. ред. Часть Ч11. Избранные темы 948 Рис. 30.5. Схема процедуры Рлвльш. РГТ, вычисляющей БПФ при и = 8. самого внешнего цикла процедуры 1тивлт~ув РРТ. Только верхний и нижний провода, проходя через "бабочку", участвуют в вычислениях; провода, проходящие через середину "бабочки", никак не взаимодействуют с ней, и их значения также не меняются данной бабочкой". Например, верхняя бабочка на этапе 2 ничего не делает с проводом 1 (которому соответствует переменная вывода, обозначенная уз); ее переменные ввода и вывода находятся на проводах 0 и 2 (обозначенных уо и уз, соответственно).
Для вычисления БПФ для п переменных ввода требуется схема глубиной О (18 и), содержащая О (и 18 и) преобразований бабочки. Левая часть схемы Рлклы.а. РРТ выполняет поразрядно обратную перестановку, а остальная часть представляет собой итеративную процедуру 1тннлт~че РРТ. Поскольку при каждом повторении внешнего цикла 1ог выполняется п/2 независимых преобразований бабочки, в данной схеме они выполняются параллельно. Значение з в каждой итерации 1тивлт~чи РРТ соответствует каскаду преобразований бабочки, показанному на рис. 30.5. В пределах этапа з = 1, 2,..., 18 и имеется и/2' групп преобразований бабочки (соответствующих различным значениям /с процедуры 1тякАт~че РРТ), в каждой группе выполняется 2' ~ операций (соответствующих различным значениям з процедуры 1тикАтюн РРТ).
Преобразования бабочки, показанные на рис. 30.5, соответствуют преобразованиям во внутреннем цикле (строки 9-12 процедуры 1тияАт~чн РРТ). Заметим также, что используемые в "бабочках*' поворачивающие множители соответствуют Глава 30. Полиномы н быстрое преобразование Фурье 949 поворачивающим множителям, используемым в процедуре 1тнклт~че РРТ: на этапе з используются значения ~„„ь~,„,..., ю„,, где т = 2 .
о 1 ш/2 — 1 д Упражнения 30.3-1. Покажите, как процедура 1тнклт1чн РРТ вычисляет ДПФ исходного вектора (0,2,3,-1,4,5,7,9). 30.3-2. Покажите, как реализовать алгоритм БПФ, в котором обратная перестановка битов выполняется в конце, а не в начале процесса вычислений. (Указание: рассмотрите обратное ДПФ.) 30.3-3. Сколько раз процедура 1тнкАт|чп РРТ вычисляет поворачивающие множители на каждом этапе? Перепишите процедуру 1тнкАт]чя РРТ так, чтобы поворачивающие множители на этапе з вычислялись только 2' 1 раз * 30.3-4.
Предположим, что сумматоры в преобразованиях бабочки схемы БПФ иногда дают сбои, приводящие к нулевому результату независимо от подаваемых на вход значений. Предположим, что сбой произошел в точности в одном сумматоре, однаю не известно, в каюм именно.
Опишите, как можно быстро выявить неисправный сумматор путем тестирования всей БПФ-схемы с помощью различных вводов и изучения выводов. Насколько эффективен этот метод? Задачи 30-1. Умножение посредством декомпозиции а) Покажите, как умножить два линейных полинома ах + Ь и сх + + и', используя только три операции умножения. (Указание: одно из умножений (а+ Ь) (с+ с~).) б) Приведите два алгоритма деюмпозиции для умножения полиномов степени не выше и, время выполнения которых О (и'кз). В первом алгоритме следует разделить коэффициенты исходного полинома на старшие и младшие, а во втором — на четные и нечетные. в) Покажите, что два и-битовых целых числа можно умножить за О (в~к~) шагов, где каждый шаг оперирует с однобнтовыми значениями, количество которых не превышает некую константу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
