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