Алгоритмы - построение и анализ (1021735), страница 192
Текст из файла (страница 192)
Рассмотрим два множества А и В, каждое из которых содержит п целых чисел, заключенных в пределах от 0 до 10и. Мы хотим вычислить декарнгову сумму (Сапегйап яип) А и В, определенную следующим образом: С = (х + у: х е А и у е В) Заметим, что целые числа из множества С заключены в пределах от 0 до 20п.
Требуется найти элементы С и указать, сколько раз каждый элемент С выступает в роли суммы элементов А и В. Покажите, что эту задачу можно решить за время О (и !я и). (Указание: представьте А и В в виде полиномов степени не выше 10п.) 30.2 ДПФ и БПФ В разделе 30.1 утверждалось, что используя в качестве точек комплексные корни из единицы, можно выполнять вычисление и интерполяцию полиномов за время О (п1яп). В данном разделе мы дадим определение комплексных корней из единицы и изучим их свойства, определим дискретное преобразование Фурье (ДПФ), а затем покажем, как с помощью БПФ можно вычислять ДПФ и обратное ему преобразование за время О (п!я п). Комплексные корни из единицы Комплексным корнем и-й степени нз единицы (сошр1ех ийг гоог оГ ишгу) является комплексное число ш, такое что ш" = 1.
Существует ровно п комплексных корней п-й степени из единицы: ез™гь/", где Й = О, 1,..., п — 1. Для интерпретации данной формулы воспользуемся следующим определением экспоненты комплексного числа: егк = соа (и) + г з1п (и) Часть Ч!1. Избранные темы 936 Рис. 30.2. Расположение значений ьф,юв,...,ив~ на комплексной плоскости, где юа = ез"'ув— главное значение корня восьмой степени нз единицы На рис.
30.2 показано, что п комплексных корней из единицы равномерно распределены по окружности единичного радиуса с центром в начале координат комплексной плоскости. Значение зяГ/н Ып ке Е (30.6) называется главным значением кормя гь-й етелеии иэ единицы (1йе рппс)ра! и!и пют оГцлйу); все остальные комплексные корни и-й степени из единицы являются его степенями2. Указанные и комплексных корней и-й степени из единицы о о'п~~п1' ' '1о'и образуют группу относительно операции умножения (см. раздел 31.1). Эта группа имеет ту же структуру, что и алдитивная группа (ли, +) по модулю гт, посколь- (г+а) юоб и кУ из огпп = огпо = 1 следУет, что м~ьопь = ь4 . Аналогично, юп т = мп '. Основные свойства комплексных корней и-й степени из единицы приведены в следующих леммах. Лемма 30.3 (Лемма о сокращении).
Для любых целых чисел п > О, 7с > 0 и г! > 0 аь ь (30.7) Многие авторы определяют ьь, иначе: ьь, = е а и". Это альтернативное определение обычно используется в обработке сигналов. Лежащие в основе математические концепции в основном одинаковы для обоих определений.
Часть 1(П. Избранные темы 938 Требование, что 1с не делится на и, гарантирует, что знаменатель не равен О, поскольку ша = 1 только тогда, когда гс делится на и. и Дискретное преобразование Фурье Напомним, что мы хотим вычислить полинам и-1 А(х) = ,'з а хз, у=о степень котоРого не выше и, в точках шо,го~1,..., пгп 1 (котоРые пРедставлЯют собой и комплексных корней и-й степени из единицы)з.
Без потери общности можно предположить, что и является степенью 2, поскольку заданную границу степени всегда можно увеличить, добавив, если необходимо, старшие нулевые коэффициентыл. Предположим, что полинам А задан в коэффициентной форме: а = (аО,а1,...,а„1). ОлрЕдЕЛИМ КОНЕЧНЫЕ рЕЗуЛЬтатЫ уьо й = 0,1,...,И вЂ” 1, с помощью формулы и-1 Уь = А (оган) = ~~1 айогпз у=о (30.8) Вектор у = (уо, у1,...,уп 1) представляет собой дискретггое лреобразоваиие Фурье (ДПФ) (Бйзсге1е Ровпег ТгапзГопп, ПРТ) вектора коэффициентов а = = (ао, а1,..., а„1). Это можно также записать как у = ПРТ„(а).
Быстрое преобразование Фурье С помощью метода быстрого преобразования Фурье (БПФ) (Разг Роипсг Тгапз1опп, РРТ), основанного на использовании специальных свойств комплексных корней из единицы, 1)РТп (а) можно вычислять за время 6 (и1к и), в отличие от метода непосредственного преобразования.
В методе БПФ применяется стратегия декомпозиции, в которой отдельно используются коэффициенты полинома А (х) с четными и нечетными индексами, Здесь и на самом деле представляет собой величину, юторая в разделе 30.1 обозначалась как 2п, поскольку прежде чем выполнять вычисление, пределы степени заданных полиномов была улвоены. Таким образом, при умножении полиномов речь в действительности идет о комплексных юриях из единицы 2п-й степени. 'При использовании БПФ в обработке сигналов добавлять нулевые юзффициенты в целях получения степеней 2 не рекомендуется, так как зто приводит к возникновению высокочастотных артефактов. Одним из методов получения размерности, равной степени 2, в обработке сигнааоа является отражение (шнтоппя). Пусть п' — наименьшая целая степень 2, превышающая п; тогда одним из способов отражения является задание а ь; = и, з для) = 0,1,..., и' — п — 1.
Глава 30. Полнномы н быстрое преобразование Фурье 939 чтобы определить два новых полинома А!о! (х) и А!з! (х) степени не выше и/2: А! ! (х) = ао+ азх+ а4х + + а„зх ~ А1~! (х) = а! + азх+ азх + + а„зх"7~ 1 . Заметим, что А]о! содержит все коэффициенты А (х) с четными индексами (двоичное представление этих индексов заканчивается цифрой О), а А!!! содержит все коэффициенты с нечетными индексами (двоичное представление которых заканчивается цифрой !).
Для определенных таким способом полиномов справедливо равенство А(,) А]о](,з)+„]т!( г) (30.9) так что задача вычисления А (х) в точках юо, ыт,..., м,", ! сводится к следующим задачам: 1. вычислить два полинома А!о! (х) и А1~! (х) степени не выше и/2 в точках ( 4)',( И' ( ." ')' (30.10) а затем 2. объединить результаты с использованием формулы (30.9). КЕС!Жя!чЕ РРТ(а) 1 и — 1еидй[а] 2 Ыи= 1 3 твен гетпгн а 4 ы < езлчв 5 м+ — 1 б а — (ао,аз,...,а„з) ]о! 7 а — (аы аз,..., а„з) ]1! З р!о! — Кесария!че ррт(а!о!) 9 у]!! — Кес[жз!че РРТ(а(~!) !> и является степенью 2 Согласно лемме о делении пополам„список значений (30.10) сдержит уже не и различных значений, а только и/2 комплексных корней степени (и/2) из единицы, причем каждый корень встречается в списке ровно два раза.
Следовательно, поли- номы А!о! и А!'! с границей степени и/2 рекурсивно вычисляются в и/2 комплексных корнях и/2-й степени из единицы. Эти подзадачи имеют точно такой же вид, как и исходная задача, но их размерность вдвое меньше. Таким образом, мы свели вычисление и-элементного Рг Т„к вычислению двух и/2-элементных РРТ„7з. Такая декомпозиция является основой следующего рекурсивного алгоритма БПФ, который вычисляет ДПФ и-элементного вектора а = (ао, аы..., а„1), где и является степенью 2.
Часть Ч![. Избранные темы 940 10 1ог й — 0 го и/2 — 1 11 по уь Ф уя + ануя [о) 12 Уь~-(а/з) + Уь ь'Уь [о] [з] 13 ~Мз 14 ге(пгп у (> Предполагается, что у — вектор-столбец Процедура Кнсикячн ГРТ работает следующим образом. Строки 2-3 описывают базис данной рекурсии: ДПФ одного элемента является самим этим элементом, следовательно, в данном случае уо=аоыз =ао 1=ао о Строки 6-7 определяют векторы коэффициентов полиномов А[о] и А[з]. Строки 4, 5 и 13 гарантируют, что ь~ обновляется надлежащим образом, т.е.
всякий раз, когда выполняются строки 11-12, ы = мь,. (Сохранение текущего значения ы от итерации к итерации позволяет экономить время по сравнению с многократным вычислением ыь с нуля с помощью цикла 1ог.) В строках 8-9 выполняются рекурсивные вычисления РГТ„/з, при этом получаются следующие значения (й = 0,1,...,п/2 — 1): у[ ] = А['] (о~а/ ), или, поскольку согласно лемме о сокращении, ыь = м~~, „[о] 4[о) ( зь) УЯ А[з] ( зь) В строках 11-12 комбинируются результаты рекурсивных вычислений РРТ„/з. Для значений уо,уы...,у„/з ~ строка 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бп). Интерполяция в точках, являющихся комплексными корнями из единицы Чтобы завершить рассмотрение схемы умножения полиномов, покажем, как выполняется интерполяция комплексных корней из единицы некоторым поли- номом, что позволяет перейти от формы значений в точках обратно к коэффнциентной форме. Для осуществления интерполяции ДПФ записывается в виде матричного уравнения, после чего выполняется поиск обратной матрицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
