Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 192
Текст из файла (страница 192)
Для значений уо,уы...,у„/з ~ строка 11 дает: Уь = У[ ] + м~~Уь[, ] = А[о] (и~~) + ыьА[з] (ы~~) = А (аР), где последнее равенство следует из уравнения (30.9). Значения уь/з, у„/з+„..., У„з вычисляются в строке 12. Для значений /с = = О, 1,..., и/2 — 1 получаем: Уь+(ь/3) уь ™и уя уя + ма уя [о] ь [1) [0) я+(а/2) [ц = А[о) ~„Р'~ + ~оа~("/з)АТ ~ь,зй— а / А[о] / зь+ь ) + ь+(ть/2)А[1] ( 21~-и) и — А ~ь/+( /з)) а / Глава 30. Полиномы и быстрое преобразование Фурье 941 где второе равенство следует из 1о„ ( ~ ) = — 1оь, четвертое — поскольку ызь+" = ь+ (б/2) = ы2", а последнее — из уравнения (30.9).
Таким образом, возвращаемый процедурой Кнс1)кз1чн РЕТ вектор у действительно является ДПФ исходного вектора а. Внутри цикла )ог в строках 10 — 13 каждое значение у„умножается на м„ !1! ь для всех )б = 0,1,...,и/2 — 1. Полученное произведение прибавляется к у„ (о! и вычитается из него. Поскольку каждый множитель ы1 используется как с положительным, так и с отрицательным знаком, множители ш1 называются новорачивающиии множителями (ЬчкЫ!е (ас1огз). Чтобы определить время работы процедуры Кнс()кз)чн ррт, заметим, что, за исключением рекурсивных вызовов, каждый вызов занимает время 6 (и), где и— длина исходного вектора.
Таким образом, рекуррентное соотношение для времени выполнения выглядит следующим образом: Т(п) = 2Т(п/2)+ 9(п) = 9(п1бп) Итак, с помощью быстрого преобразования Фурье можно вычислить полипом степени не выше и в точках, являющихся комплексными корнями и-й степени из единицы, за время 9(п1бп). Интерполяция в точках, являющихся комплексными корнями из единицы Чтобы завершить рассмотрение схемы умножения полиномов, покажем, как выполняется интерполяция комплексных корней из единицы некоторым поли- номом, что позволяет перейти от формы значений в точках обратно к коэффнциентной форме.
Для осуществления интерполяции ДПФ записывается в виде матричного уравнения, после чего выполняется поиск обратной матрицы. Из уравнения (30.4) можно записать ДПФ как произведение матриц у = К,а, где К, — матрица Вандермонда, содержащая соответствующие степени ь~„: 1 1 1 1 Мв 2 з Уо р-1 2(ч-1) о~„ З(ч — 1) шн а1 У1 ~ и 1'~а а2 аз Уз н 1 2(н — 1) З(и-1) (н-1)(н-1) 1 1од ~ть ьб . ь~и Уп — 1 Для выполнения обратной операции, которая записывается как а = РГТ„1 (у), необходимо умножить у на матрицу У'„1, обратную К,. Часть Ч11.
Избранные темы 942 Теорема 30.7. Для 3,6 = 0,1,...,п — 1, (т',)с)-й элемент матрицы Ъ'„1 равен ~п "/п. Даказавыиьство. Покажем, что У„1У„= 1„, единичной матрице размера и х и. Рассмотрим (3',2')-й элемент матрицы Ъ;, ~у'„: и — 1 Ъ„], = '~у ~ы™3/и) (ы"1'/1 = ~у ю"0' 31/и . в=о ь=о Согласно лемме о суммировании (лемма 30.6), данная сумма равна 1, если у' = у, и 0 в противном случае. Заметим, что поскольку — (и — 1) < 3' — 3 < и — 1, у'-3 не кратно п, так что лемма применима. Если дана обратная матрица Ъ;, 1, обратное дискретное преобразование Фурье ПГТ,,1 (у) вычисляется по формуле 1 ь-1 а- = — ~ увы„ — ьу 1=О (30.11) для 1 = 0,1,...,и — 1.
Сравнивая уравнения (30.8) и (30.11), мы видим, что если модифицировать алгоритм БПФ вЂ” поменять ролями а и у, заменить ы„ на м,,1 и разделить каждый элемент результата на п — получится обратное ДПФ (см. упражнение 30.2-4). Таким образом, 13РТ,,1 также можно вычислить за время 6(п18п). Таким образом, с помощью прямого и обратного БПФ можно преобразовывать полинам степени не выше п из коэффициентной формы в форму значений в точках и обратно за время О (и 18 и). Применительно к умножению полиномов, мы показали следующее. Теорема 30.8 (Теорема о свертке).
Для любых двух векторов а и 6 длины п, где и является степенью 2, справедливо соотношение а З 6 = 11г'Т~,~ (13ГТз„(а) . ь1ГТз (6)), Упражнения 30.2-!. Докажите следствие 30.4. 30.2-2. Вычислите ДПФ вектора (О, 1, 2, 3). где векторы а и 6 дополняются нулями до длины 2п, а " '* обозначает покомпо- нентное произведение двух 2п-элементных векторов. Глава 30. Полиномы и быстрое преобразование Фурье 943 30.2-3. Выполните упражнение 30.1-1, используя схему с временем выполнения 6(п1бт1). 30.2-4. Напишите псевдокод для вычисления 13ГТ„1 за время 6 (и 1к и). 30.2-5.
Опишите обобщение процедуры БПФ для случая, когда п является степенью 3. Приведите рекуррентное соотношение для времени выполнения и решите его. *30.2-б. Предположим, что вместо выполнения и-элементного БПФ над полем комплексных чисел (где п четно), мы используем кольцо Е„, целых чисел по модулю т = 2'и1з+1, где $ — произвольное положительное целое число. Используйте ь1 = 21 вместо ь~и в качестве главного значения корня и-й степени из единицы по модулю тп.
Докажите, что прямое и обратное ДПФ в этой системе является вполне определенным. 30.2-7. Покажите, как для заданного списка значений го, з1,..., ги 1 (возможно, с повторениями) найти коэффициенты полинома Р (х) степени не выше и + 1, который имеет нули только в точках хо, г1,..., г„1 (возможно, с повторениями). Процедура должна выполняться за время О (п 18~ п). (Указанисс полипом Р (х) имеет нулевое значение в точке х тогда и только тогда, когда Р (х) кратен (х — зу).) * 30.2-8. Чирп-преобразованием (сЫ1р 1гапз1опп) некоторого вектора а = (ао, а1, ..., аи 1) является вектор у = (уо, у1,..., у„1), где уя = 2 " а х"1, а з — неюторое комплексное число.
Таким образом, ДПФ является частным случаем чирп-преобразования, полученного для х = ь1и. Докажите, что для любого комплексного числа з чирп-преобразование можно вычислить за время О (п1кп). (Указанигс воспользуйтесь уравнением п-1 у,ь'7з'У (,, '7 ) (,-1 -31'7 ) чтобы рассматривать чирп-преобразование как свертку.) 30.3 Эффективные реализации БПФ Поскольку практические приложения ДПФ, такие как обработка сигналов, требуют максимальной скорости, в данном разделе мы рассмотрим две наиболее эффективные реализации БПФ. Сначала будет описана итеративная версия алгоритма БПФ, время выполнения которой составляет 6 (и 1к п), однаю при этом в 6 скрыта меньшая константа, чем в случае рекурсивной реализации, предложенной в разделе 30.2. После этого мы вернемся к интуитивным соображениям, приведшим нас к итеративной реализации, для разработки эффективной параллельной схемы БПФ.
Часть Ч!1. Избранные темы 944 Итеративная реализация БПФ Прежде всего заметим, что в цикле Рог в строках !0-13 процедуры Кис~)кь)чн РРТ значение ь~„у„вычисляется дважды. В терминологии компиляторов ь 1)) такое значение называется общим подвыражением (соттоп зпЬехргезз)оп). Можно изменить цикл так, чтобы вычислять это значение только один раз, сохраняя его во временной переменной б: Рог/с -0 гоп/2 — 1 пот< — щу) !)) Уь ' — У), +г [о) )о) Уь+(и/з) ' Уь щ < — щщч Выполняемая в данном цикле операция (умножение щ„уь, сохранение произвеь О! дения в переменной 1, прибавление и вычитание 1 из уь ), известна как лреобра1о) зование бабочки (Ьпцег))у орегайоп), схематически представленное на рис.
30.3. Теперь покажем, как сделать структуру алгоритма БПФ итеративной, а не рекурсивной. На рис. 30.4 мы организовали входные векторы рекурсивных вызовов в обращении к процедуре Кис))кз)чн РРТ в древовидную структуру, в которой первый вызов производится для п = 8. Данное дерево содержит по одному узлу для каждого вызова процедуры, помеченному соответствующим входным вектором. Каждое обращение к процедуре Кис))нз)чн РРТ производит два рекурсивных вызова, пока не получит 1-элементный вектор.
Мы сделали первый вызов левым дочерним узлом, а второй вызов — правым. Посмотрев на дерево, можно заметить, что если удастся организовать элементы исходного вектора а в том порядке, в котором они появляются в листьях дерева, то выполнение процедуры Кнсикз)чн РРТ можно будет представить следующим образом. Берутся пары элементов, с помощью одного преобразования бабочки вычисляется ДПФ каждой пары, и пара заменяется своим ДПФ. В результате получается вектор, содержащий и/2 2-элементных ДПФ. Затем эти ДПФ у,' ь .-,..... в-,....-.—.у„) .;~ ~*,'ч ' о2", Г,' а) б) Рис. 30.3. Преобразование бабочки.
а) Слева поступают два вводимых значения, оз„" умножается на уь, соответствующие сумма и разность выводятся справа. б) Упрей) щенная схема преобразования бабочки, используемая в параллельной схеме БПФ Глава 30. Полиномы и быстрое преобразование Фурье 945 '. ~~ч.а~ а! аьа4 аа аа а7),2 Г (аа,а,,а„,аа) ~ ; (а„а~,а;,а.) ) (',ар,аа[~~ ~ (а.,а,) ) , )а,,а,) );)аьаг) ) .("'), .Ё (., ((аа)) ))а4)1 ~(аа)) !(а„)) Йа;)) Наг)~ Йаа)) (!а;) Рис. 30.4. Дерево входных векторов рекурсивных вызовов процедуры Квс))аз)чв РРТ. Начальный вызов производится для и = 8 обьединяются в пары, с помощью двух преобразований бабочки вычисляются ДПФ для каждых четырех элементов вектора, объединенных в четверки, после чего два 2-элементных ДПФ заменяются одним 4-элементным ДПФ. Теперь вектор содержит п/4 4-элементных ДПФ. Процесс продолжается до тех пор, пока не получится два п/2-элементных ДПФ, которые с помощью п/2 преобразований бабочки можно объединить в юнечное п-элементное ДПФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
