Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 211
Текст из файла (страница 211)
ГГалияомы н быстрое преобразование Фурье Рне. ЗОА. Дерево входных векторов рекурсивных вызовов процедуры Кнсинычн-РРТ, Нвчвльный вызов выполняется для и = К в восходящем направлении, а не в нисходящем. Сначала берутся пары элементов, с помощью одного преобразования бабочки вычисляется ДПФ каждой пары, и пара заменяется вычисленным ДПФ.
В результате получается вектор, содержащий п/2 2-элементных ДПФ. Затем эти и/2 ДПФ объединяются в пары, и с помощью двух преобразований бабочки вычисляются ДПФ для каждых четырех элементов вектора, объединенных в четверки, после чего два 2-элементных ДПФ заменяются одним 4-элементным ДПФ. Теперь вектор содержит и/4 4-элементных ДПФ. Процесс продолжается до тех пор, пока не получится два и/2-элементных ДПФ, которые с помощью и/2 преобразований бабочки можно объединить в конечное и-элементное ДПФ. Чтобы превратить этот восходящий подход в код, используем массив А[0 .. и — Ц, который изначально хранит элементы входного вектора а в том порядке, в котором они появляются в листьях дерева на рис.
30.4. (Позже мы покажем, как определить этот порядок, который называется поразрядно обратной перестановкой (Ь!1-гечегза! регпппабоп).) Поскольку объединение в пары необходимо выполнять на каждом уровне дерева, введем в качестве счетчика уровней переменную л, которая изменяется от 1 (на нижнем уровне, где составляются пары для вычисления 2-элементных ДПФ) до !ли (на вершине, где объединяются два п/2-элементных ДПФ для получения окончательного результата).
Таким образом, алгоритм имеет следующую структуру. ! Рог л = 1 яо 1я п 2 Роги=О!оп — 1Ьу2' 3 объединить два 2' "-элементных ДПФ в А[(с .. к + 2' т — Ц и А[!с + 2' ~ )с + 2' — Ц в одно 2'-элементное ДПФ в А[к .. Й + 2' — Ц Тело цикла (строка 3) можно описать более подробным и точным псевдокодом. Скопируем цикл (Ьг из процедуры Кнсцкз!че-г РТ, отождествив у!~! с А[)с ., !с + 2' ' — Ц и у!т! с А[В+ 2' ' .. !с+ 2' — Ц. Поворачивающий множитель, используемый в каждом преобразовании бабочки, зависит от значения л; он представляет собой степень ы, где т = 2'. (Мы ввели переменную т исключительно для того„чтобы формула была удобочитаемой.) Введем еще одну временную переменную и, которая позволит выполнять преобразование бабочки на месте, без Рбо Часть И!.
Избраиные темы привлечения дополнительной памяти. Заменив строку 3 в общей схеме телом цикла, получим следующий псевдокод, образующий базис параллельной реализации, которая будет представлена позже. В данном коде сначала вызывается вспомогательная процедура В!Т-КЕЧЕКЯЕ-СОРУ(а, А), копирующая вектор а в массив А в том исходном порядке, в котором нам нужны эти значения. 1ТЕКАТ! ЧЕ-Р РТ (а) 1 В!Т-КЕЧЕКБЕ-СОРУ(а, А) 2 и = а.1епдй // и является степенью 2 3 Раг в = 1 го )к и 4 т = 2* зьс/ьь б Гогк = О!оп — 1Ьут 7 ы=1 8 аког д = 0 го т/2 — 1 9 ! = мА[Й+д+ т/2] 10 и = А[/с+д'] 1! А[Ь+д] = и+! 12 А[)с+д+ гп/2] = и — Г 13 ы — ы Мп 14 гебагп А Каким образом процедура В!т-Кечекзе-СОРУ размещает элементы входного вектора а в массиве А в требуемом порядке? Порядок следования листьев на рис. 30.4 представляет собой обратную перестановку, или реверс битов (Ь(ггечегза1 регпплабоп), т.е.
если геч(!с) — )лп-битовое целое число, образованное путем размещения битов исходного двоичного представления !с в обратном порядке ("задом наперед"), то элемент аь следует поместить в массиве на место А[геч()с)]. На рис.30.4, например, листья находятся в следующем порядке; О, 4, 2, 6, 1, 5, 3, 7; в двоичном представлении эта последовательность записывается как 000, 100, 010, 110, 001, 101, 011, 111. Если же записать биты каждого значения в обратном порядке, получится обычная числовая последовательность: 000, 001, 010, 011, 100, 101, 110, 111. Чтобы убедиться в том, что нам нужна именно обратная перестановка битов, заметим, что на верхнем уровне дерева индексы, младший бит которых равен О, помещаются в левое поддерево, а индексы, младший бит которых равен 1, помещаются в правое поддерево.
Исключал на каждом уровне младший бит, мы продолжаем процесс вниз по дереву, пока не получим в листовых узлах порядок, заданный обратной перестановкой битов. Поскольку функция геч(й) вычисляется очень легко, процедуру В!т-КечекзеСОРУ можно записать очень просто. В!Т-КЕЧЕКБЕ-СОРУ(а, А) 1 п = а.1епдй 2 1ог )с = 0 го и — 1 3 А[геч(!с)] = аь 961 1лаеа 30. Палннаыы н быстрое нреобразоеание Фурье Итеративная реализация БПФ выполняется за время 1В(п 18п). Вызов процедуры В1Т-КЕУЕКЕЕ-Сору(а, А) выполняется за время 0(п18 п), поскольку проводится п итераций, а целое число ст 0 до п — 1, содержазцее 18п бит, можно привести к обратному порядку за время О(18 п)4. (На практике мы обычно заранее знаем начальное значение и, поэтому можно составить таблицу, отображающую )с в геч(й), в результате процедура В1т-Кечекзе-Сору будет выполняться за время «9(п) с малой скрытой константой.
В качестве альтернативного подхода можно использовать схему амортизироваиного обратного бинарного битового счетчика, описанную в задаче 17.1.) Чтобы завершить доказательство того факта, что процедура 1текАт1че-РГТ выполняется за время (З(п 18 п), покажем, что число Ь(п) выполнений тела внутреннего цикла (строкн 8-13) равно ез(п 18п). Цикл Гог (строки 6-13) повторяется и/пз = и/2' раз для каждого значения л, а внутренний цикл (строки 8-13) повторяется т/2 = 2' 1 раз.
Отсюда 1ки Ь(п) = ~~1 — 2' ' л=1 1а н и =Е- 2 «=1 = Й(п18п) . Параллельная схема БПФ Чтобы получить эффективный параллельный алгоритм БПФ, можно воспользоваться многими нз свойств, которые позволили нам реализовать эффективный итеративный апгорнтм БПФ. Мы будем представлять параллельный алгоритм БПФ в виде схемы. На рис. 30.5 показана параллельная схема, которая вычисляет БПФ для и входных значений при и = 8. Она начинается с поразрядной обратной перестановки исходных значений, затем следуют 18п этапов, на каждом из которых параллельно выполняется п/2 операций бабочки.
Таким образом, глубина (41ер1Ь) схемы — максимальное количество вычислительных элементов между любыми входами и выходами — составляет 1В(18 п). Крайняя слева часть схемы РАкА~.ьн.-РРТ выполняет поразрядно обратную перестановку, а остальная часть имитирует итеративную процедуру 1ТЕКАТ1ЧЕРРТ.
Поскольку каждая итерация внешнего цикла Гог выполняет п/2 независимых преобразований бабочки, в данной схеме они выполняются параллельно. Значение л в каждой итерации 1текАт1че-РРТ соответствует каскаду преобразований бабочки, показанному на рис. 30.5. В пределах этапа н = 1,2,...,18п имеется п/2' групп преобразований бабочки (соответствующих различным значениям к процедуры 1текАт1че-ГРТ), в каждой группе выполняется 2' ' операций (соответствующих различным значениям 1 процедуры 1текАт1че-РГТ). кннзересные реялнзеннн реясрсь базен можно ньатн н разделе 7.1 «ннгн Г Уоррен Ллеорнлгмнческие трюки для лрагралсчигтое. — Мл И.Д. "Вильямс", 2003.
— Примеч. ред. 31 зе«. э«26 962 Часть ГГ1. Избранные мелы аь Уь а| У| аз Уз Уз аз Уь аь Уь Уз аз Рис. Збуй Схема параллельного вычисления БПФ (в данном случае — дла и = 8 входов). Кмкаое преобразование бабочки получает в качестве входных данных значения, поступаюшие по двум проводам, вместе с поворачиваюшим множителем и передаст полученные значения на два выходжцих провода. Различные этапы каскада преобразований бабочки нумеруются в соответствии с итерациями самого внешнего цикла процедуры 1тлклтгчп-ЕРТ. При проходе через бабочку в вычислениях участвуют только нижний и верхний провода; провода, проходяшие черсч середину бабочки, никак не взаимодействуют с ией, и их значения таске не меюпотся данной бабочкой.
Например, верхняя бабочка для а = 2 ничего не делает с проводом 1 (которому соответствует выходная переменная, обозначенная как ю); ее вход н выход находятся в проводах О и 2 (обозначенных соответственно как ро и рз) Для вычисления БПФ для и переменных ввода требуется схема глубиной сз(15 и), всего содержашая Н(п 1я и) операций бабочки.
Преобразования бабочки, показанные на рис. 30.5, соответствуют операциям во внутреннем цикле (строки 9-12 процедуры 1Тййлт1ЧБ-Гг Т). Заметим также, что используемые в бабочках поворачивающие множители соответствуют поворачивающим множителям, используемым в процедуре 1тййдт1чБ-ГРТ: на этапе л ис- О 1 12 — 1 пользуются значения ш, ш,..., огиз, где т = 2'. Упражнении 30.3.1 Покажите, как процедура 1тййлт(чй-ГгТ вычисляет ДПФ входного вектора (О, 2, 3, — 1, 4, б, 7, 9).
3().з.г Покажите, как реализовать алгоритм БПФ, в котором обратная перестановка битов выполняется в юнце, а не в начале процесса вычислений. (Указание: рассмотрите обратное ДПФ.) 963 Глава ЭО. Пааииаиы и биетрае ереабреаанание Фурье зо.з.з Сколько раз процедура 1теклт[уе-ГгТ вычисляет поворачивающие множители на каждом этапе? Перепишите процедуру 1тнклт!чв-ГРТ так, чтобы поворачивающие множители на этапе е вычислялись только 2' ' раз.
Зб.3.4 * Предположим, что сумматоры в преобразованиях бабочки в схеме БПФ иногда дают сбои, приводящие к нулевому результату независимо от подаваемых на вход значений. Предположим, что сбой произошел ровно в одном сумматоре, однако неизвестно, в каком именно. Опишите, как можно быстро выявить неисправный сумматор путем тестирования всей БПФ-схемы с помощью различных входных данных и изучения выходных.
Насколыю эффективен ваш метод? Задачи Зб.1. Умножение посредсиееаи декомпозиции а Покажите, как умножить два линейных полинома, ах + Ь и сх + а, используя только три операции умножения. (Указание: одно из умножений — (а+ б) . (с+ е().) б. Приведите два алгоритма декомпозиции для умножения полиномов с границей степени и, время выполнения которых — ее(п'Яз).
В первом алгоритме следует разделить коэффициенты исходного полинома на старшие и младшие, а во втором — на четные и нечетные. а Покажите, как перемножить два п-битовых целых числа за 0(п'Яз) шагов, где каждый шаг работает с не превышающим некоторую константу количеством однобитовых значений. Зйз. Матрицы Теплица Матрицей Теплица (Тоер!йя шапзх) называется матрица А = (а; ) размером и х и, в которой аб — — а;,, 1 для 1 = 2, 3,..., п и З = 2, 3,..., п. а Всегда лн сумма двух матриц Теплица является матрицей Теплица? Что можно сказать об их произведении? б. Каким должно быть представление матриц Теплица, чтобы сложение двух матриц Теплица размером и х и можно было выполнить за время 0(п)? е.
Предложите алгоритм умножения матрицы Теплица размером и х и на вектор длиной и со временем работы 0(п 1л и). Воспользуйтесь представлением, полученным при решении предыдущего пункта данной задачи. д Предложите эффективный алгоритм умножения двух матриц Теплица размером п х и и проанализируйте время его выполнения. Р64 Часть ПЬ Избранные немн ЗОЗ. Многанерное быстрое преобразование Фурье Можно обобщить одномерное дискретное преобразование Фурье, определенное уравнением (30.8), на Н-мерный случай.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
