1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 57
Текст из файла (страница 57)
(7.4) т о 2--1 Так как Ьи — — 0 для й<-0, можно повысить нижний предел суммирования во внутренней сумме до А=О. Аналогично, поскольку а2 —— 0 для ))п, можно понизить верхний предел во внешней сумме до п — 1. Верхний предел внутреннего суммирования не меньше п 7.1. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ независимо от значения 1. Таким образом, можно заменить верхний предел на и — 1, так как Ь„=О при й)п, После этих изменений (7.4) превратится в (7.2); отсюда следует, что с1=а; Ь;. Итак, Р(а®Ь)= =Р(а) Р(Ь), откуда а®Ь=Р-'(Р(а) Р(Ь)).
П Свертка двух п-мерных векторов является 2п-мерным вектором. Это требует, чтобы в теореме о свертке вектора а и Ь были "разбавлены" и нулями. Чтобы избежать этого "разбавления", введем понятие обернутой свертки. Определение. Пусть а=[а„а„..., а„ь)г и Ь= [Ьо, Ь„... ...,Ь„1)г — два и-мерных вектора.
Положительно обернутой сверткой векторов а и Ь называется такой вектор с=[с„с„..., с„-1)г, что о-1 с1= „'Яа~Ь1 Г+ ч~~ ~ауЬ„+, у. О ~ 1+1 Отрицшпельно обернутой сверткой векторов а и Ь называется такой вектор й=[й„йь..., й„,)г, что к-1 11,= ~а~Ь, у — Х ауЬ„, г. УО Г1+1 В равд. 7.5 мы воспользуемся обернутой сверткой в алгоритме Шенхаге — Штрассена — алгоритме быстрого умножения целых чисел. А пока отметим следующее.
Вычислив значения двух полиномов степени и — 1 в корнях и-й степени из единицы и перемножив пары значений в соответствующих точках, мы получим и значений, по которым сможем однозначно интерполировать полипом степени и — 1. Вектор коэффициентов этого единственного полинома как раз и будет положительно обернутой сверткой векторов коэффициентов исходных полиномов. Теорема 7.2. Пусть а=[а„а„..., а„1[г и Ь=[Ь„Ь„... ...,Ь„1)г — два и-мерных вектора, а ы — примитивный корень и-й степени из единицы. Пусть фо=а.
Предположим, что элемент и имеет обратный. Тгмда 1) положительно обернутая свертка векторов а и Ь равна Р-'(Р(а) Р(Ь)), 2) если й=[й„й„..., й„-1)г — отрицательно обернутая сверт«а векторов а и Ь, а=[а„фа„..., фк-'а„ь)г, Ь=[Ьо, фЬ„... фо- Ь )г й=[йо фй1 ... фк-'й )г то й= = Р-' (Р (а) .Р (Ь)). Л о к а з а те л ь с т в о. Теорема доказывается аналогично теореме 7.! с учетом равенствафк= — 1. Леталиоставляем в качестве упражнения. П !О А.
Ако, Дкс. Хоокрофк, Дж. Укьккк гл. и выстгое пгаовглзовлнив огоье 7.2. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Очевидно, что преобразование Фурье вектора а из 1»л и обратное к нему можно вычислить за время Ол(и') а предположении, что каждая арифметическая операция над элементами кольца /» выполняется за один шаг. Однако если и — степень числа 2, то можно сделать это быстрее: известен алгоритм сложности Оо (и 1оя и), вычисляющий преобразование Фурье или обратное к нему, и мы думаем, что эта оценка неулучшаема, Приведем только алгоритм прямого преобразования Фурье.
Алгоритм обратного преобразования аналогичен и предоставляется читателю. Основная идея быстрого преобразования Фурье (ВПФ) является по своей природе алгебраической; мы находим подобие между частями тех и сумм, которые порождаются умножением Аа. Во всем этом разделе мы считаем, что и 2' для некоторого целого числа А. Вспомним, что вычисление вектора Аа эквивалентно вычислению л-1 полинома р(х)=Ха»х» в точках х=о»о, »о»,..., »ол-1. но вычислеГ~ ние р (х) в точке х=а равносильно нахождению остатка от деления р(х) на х — а. (Чтобы увидеть это, можно записать р(х) в виде (х — а) а(х)+с, где с — постоянная.
Тогда р(а)=с.) Таким образом, вычисление преобразования Фурье сводится к нахождению остатка л — 1 от деления полинома р(х)=л, а»х» степени и — 1 на каждый из »по полиномов х — »оо, х — »о»,..., х — »ол '. Обычное последовательное деление р(х) на каждый из полиномов х — »о» дает процесс сложности 0(и'). Чтобы построить более быстрый алгоритм, перемножим попарно х — »о», затем перемножим попарно получившиеся и/2 полиномов и т. д., пока не останется два полинома»/» и Рм каждый из котоРых Равен пРоизведению половины полиномов х — »о».
Далее делим р (х) на»/1 и»/,. соответствующие остатки г,(х) и г,(х) имеют степень не более и/2 — 1 каждый. Для каждого корня»о', для которого»/1 делится без остатка на х — о»', нахождение остатка от деления р (х) на х — о»' равносильно нахождению остатка от деления г,(х) на х — о»'. Аналогичное утверждение верно для каждого корня»о», для которого»/, делится без остатка на х — »о». Поэтому вычисление остатков от деления р(х) на каждый из полиномов х — »о» равносильно вычислению остатков ог деления г,(х) и г,(х) на каждый из и/2 подходящих полиномовх — »о».
Рекурсивное применение втой тактики "разделяй и властвуй" гораздо эффективнее прямолинейного метода деления р (х) на каждый полипом Х вЂ” О»'. При перемножении полиномов х — »о» можно ожидать, что произведения будут содержать результаты перекрестных умножений одночленов. Однако при подходящем упорядочении полиномов х — »о» К2. АЛГОРИТМ БПФ можно добиться, чтобы все произведения имели вид »Г вЂ” Гз', и это еще уменьшит время, затрачиваемое на умножения и деления полиномов. Изложим все зти идеи точнее. Пусть с„с„..., с„,— перестановка злементов Гз', в',...
...,м""', которую мы конкретизируем позже. Определим полиномы д,, где (л л2~(й и 1является целым кратным числа 2", Оч=1(22 — 1: 2+2~-1 Д (» — су). /=Г Таким образом, 422= (х — с,) (х — с,)... (х — с„,), ам=» — с, и в общем случае 4!ю =4ь ю-Г4Г~ 2 -ь,„-м Существует 2"- полиномов со вторым нижним индексом лГ, и каждый полипом х — с, делит в точности один из них. Полиномы д, изображены на рис. 7.1. (См.
также разд. 8.4 и 8.5.) наша цель — вычислить остаток от деления р(х) на дГ2(х) для каждого 1. Для этого вычислим остатки от деления р(х) на дГ„(х) для каждого д,„, начиная с лГ=Л вЂ” 1 и кончая лГ=О. Допустим, что уже вычислены полиномы Г,„степени 2" — 1, остающиеся от деления р (х) на д,„(х). (можно считать, что Г,„=р (х).) Поскольку д,„=д'д", где д'=д, , и д'=д, , - „ „ мы утверждаем, что остаток от деления р(х) на д'(х) равен остатку от деления г, на д'(х) и аналогичное утверждение верно и для д (х).
Для до- х- 2„,1 ,т-22 Х-С, Х-С2 Х-Гз Х-ГР 2 лл Рис. УЛ. Полиномы дГ . 10» Гл. г. БыстРОе пРБОБРАзОВАние ФуРье казательства положим р(х) =И,(х) д'(х)+г(, где степень полннома г, „, не превосходит 2 -3 — 1. Так как р (х) =И, (х) ()3„(х)+г,, то Из (х) Ц'(х)+ гг, — — Ив (х) дз (х) + г,„. (7.5) Разделим обе части равенства (7.5) на ([' (х); так как И,(х) ()'(х) и Из(х) ()3 (х) делятся без остатка, то остаток от деления г,„на (3'(х) равен г, „,. Таким Образом, можно получить остатки от деления р(х) на ' (х) и р (х) на ()" (х), разделив на (3' (х) и (7" (х) поли ком г,„степени "- — 1, а не полинам р(х) степени 2' — 1. Этот метод выполнения делений сам по себе дает экономию времени.
Но можно делать еще больше. Выбрав подходящий порядок элементов с„с„..., с„, для степеней а, можно добиться, чтобы каждый полипом дг имел вид х'" — а' при некотором в. Деление на такие полиномы вйполня- ется особенно просто. Лемма 7.2. Пусть п=2" и а — примитивный «орень степени и из единицы. Пусть [(((3(з...(1А 3! — двоичное представление целсео числа 1, где О() ..2" 3), а геу (3) — целое число с двоичным представлес+ а««-3 нием [((ь а ((в з...(Ц.
Обозначим с(=в "ю и ц( П (х — с3). 3 ! Тогда () =хз — а "(из"3. 3«г Док аз а тел ьетво. Доказательство проводится индук- цией по т. Базис, т. е. случай т=О, тривиален, нбо по определению ()3«=Х вЂ” О,=Х вЂ” а' (О. ДЛя ПрОВЕдЕНИя Шата ИНдуКцИИ ЗаМЕтИМ, что при т О а(ге ()3, «г-зч(+3««-г.
«г-3 = = (Х вЂ” а (цв '3) (Хз а Отз — + 3) где 1/2"-3 — четное число между О и 2" — 1. Тогда агее(33««г-«+33 — ава-гесве(3/за~-~3 таге«(неге-гзт .3 ° поскольку авв '=а«гз = — 1. Следовательно, хв«г аз геу(ив"г Ч вЂ” Хз"г а«ее(33«««3 Угю = поскольку геч(21)=31« веч(1). П Пример 7.1. Если и 8, то список с„с„...,с, есть аз, ве, а', вз, оз', а$«оз', аз.
Полиномы д(„иллюстрируются на рис. 7.2. а-( 3) То есп 3=~ЧР((а ( 323, 3 О 7.2. АЛГОРИТМ БПФ Л /~ ЛЛ е-ме е-мо л'-мо м-о(О е-е(' х-ее х-ыо е н(7 Рнс. 7.2. Полнномы Е(м нз леммы 7.2. Лемма 7.3. ()усть 2! ! р (х) = ~ агхг ! о и с — постоянная. Тогда остаток от деления р(х) на х' — с равен !-! Г(Х) = ~ (аГ+Сае о!) Х7. ! о Д о к а з а т е л ь с т в о. Достаточно заметить, что р (х) мож но представить в виде т (-! ~ аго(хг (х' — с)+г(х). (З ! о Итак, остаток от деления произвольного полинома степени 2! — 1 на х' — с можно найти за ОА(7) шагов. Любой из известных алгорит- Покажем, как использовать полиномы (7! для вычисления остат- КОВ.
ВНаЧаЛЕ ВЫЧИСЛЯЮТСЯ ОСтатКИ Г„н Г„От ДЕЛЕНИЯ Р (Х) На Х' — Еоо 7 и р(х) на х' — 224, где р(х)=Да(хг. затем вычисляются остатки Гм И Г21 От ДЕЛЕНИЯ Гоо На ХΠ— (ЕО И Гоо На ХΠ— Во И ОСтатКИ Го! И Г41 От деления го, на х* — оо' и го, на хо — еоо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
