Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 18
Текст из файла (страница 18)
Он также будет содержать пять комплексных умножений, на числа иомплексаых сложевий уменьшится. Выберем многочлен з (х] '= х (х — 1) (х .(- 1) (х — !) (х -1- )). Вычисление астатиов дается равенствами Китайская теорема аб остатках (или интерполяциониая фор. мула Лагранжа) дает () «( + )! 4 з( + + ! )! ф — 3«(х« — зз + хт х) + 4 3« (хл -~-!х« — х' — )х) и 1 1 ф 1 5«(х" — )хз — "+!х). В матричной форме зю равенства записывается в виде Множители 1)4 можно спрятать в диагональвой матриде. Алгоритм содержат пять комплексных умножений, эквивалент шести комплексных сложений в матрице предсложений и эквивалент девяти иомплексных сложений в матрице постсложений, Процедуру Винограда можно использовать для построения сверток и большей длины, чеы те, что приведены на рис. 3.12; однако построенные таким образом большие алгоритмы, как пра. вила, громоздки и содержат слишном много сложений. Вместо этого можно строить большие алгоритмы нв мальм.
Есть не. сколько способов построения алгорвтмов даннмх сверток из зб В г а шт ю 1ОЗ алгоритыов коротких сверток. Некоторые вз них, а ниенна гнездовой метод и метод Агарвала — Куля, будут рассмотрены в гл. 7. Так!ге алгоритмы содержзт несколько больше умиажеаий, чем требуется для алгоритма Винограда, но число сложений у них существенно меньше. 3.5. Вычнсленне пронвведення многочленов по модулю неноторого многочлена Мы уже видели, как можно разбивать залачу вычисление циклической свертки или задачу вычисления линейной свертка на иескаюко подзадач меньшего размера Меньшие задачи опять ииеют вид где бейл«(х) = я и сте сии обоих мао ачленов б(х) и Л (*) меньше я, т. е форму произведения многочленов в кольце много.
членов но модулю ш (х). Для тато чтобы построить хороший алгоритм исходной линейной свертки, необходимо построить хорошие адгоритмы для каждого иэ меньших произведений мнагочлевов. Достаточно рассмотреть талька случай неприводимога мнагочлена ш (х), так как в пративноы случае разложение можно продолжать дальше. Кан будет доказана в разя. 3 3, для непрвводим«гго миагачлена ш (х) степени я число умножений, необходимых для вмчислеиия з (х), равна 2л — 1 Обычно в алгоритме с наименьшим возможным числом умножений требуется большое число сложений В практичесии прись«лемых адгоритмах должен достигаться разумный баланс между числом умножений и числом сложений В данном разделе рассматриваются практические аспекты построения таких алгарио«ав.
Наиболее прямой метал состоит в вычислении ливейной свертки Л (х) б (х) (нз что требуется по меньшей мере 2я — 1 умножений) и дальнейшем приведении результата по модулю ю (х)(что вообще ие требует умнах ений). Эта на первый взгляд может показатьсв парадоксальным, так как мы предлагали вычислять линейную свертку путем разбиения на подаадачи, соответствующие неприводимым миогачленам, а теперь сводим аадачу обратно к линей. ным сверткам. Однако этим маневрированием «вперед-иаззд» мы существенно снижаем степей«ь,лйниейной свертки, что и улучгоает ситуацию Мы уже расслштривали проиаве ние ь|ногочленов з (х) = й (х) б (х) (шрб х' -)- 1), ч ч '-1- -,'- ! '-1- ! 4-И4- '4-»4. ! '-1-* -1.
! '-1-л'-1-»"-1- '-1- '-1- Ч ! 3 !5 4! !5 45 33 53 557 3 3 7 Р 7 !5 !5 75 р ш юнна 104 Гк 3. В Рм»л Р» шзю» сшзю» которое формально совпадает с комплексным умножением. Сейчас пришло время построить этот алгоритм. Одновременна ыы будем рассматривать произведения многачленов з (х) = й (х) б (х) (шоб х') и з (х) -.- й (х) Д (х) (нюб х» -1- х -1- 1). Ва всех этих примерах й (х) = й»х -)-й» н б (х) = б,х 4-54. Уйы будем моднфипировзть опясанную в равд.
3.2 линейную (2хй)-«вертку Алгоритм этой линейной свертки в поли. номиальной форме запнсмвается в виде равенства з(х) = й (х), б (х) = й»б»л' 4- (й»Д ': йп(, — (й. — 2.) (Ỡ— Д»)). 4- ! йм(» и содержит трн умножения. Наша задача состоит в вычислении зтага произведения по грен модулям» ' 4-1, х' н х' -Рх .» 1. С»ютвшшвующие три произведения получаются простой заменой х* на — 1, 0 и — х — 1 соответственно. А именно, з (х) = й (х) \! (х) (»поб х -»- !) = (а»б» — аФ» — (а, — й,) (д» вЂ” д,)) х + й,б,— — а*а» з (х) = й(х) б (х) (шобх') = = 1а й» вЂ” йн(4 — (й» вЂ” й,) (Ỡ— б.)1 х -Р р йю 5 (х) = й (х) б (х) (шоб х .1- к -!. 1) (йм(4 (й» йл) (д» д ) ) Х !.
й д й»б» В матричной форме этв три алгоритма соответственна имеют вид 55П7-РР "Л Р ! Оз Второй из этих алгоритмов не очень хорош. Следуя по формаль- ному пути, мы построили алгарити, харантеристики' которого «уже следующего звриствчесного алгоритма, содержащего только одно сложение: Характеристики некоторых алгоритмов вычисления произведения многочленов по модулю неприводииого миогачлена зшабулироваиы на рис. 3.13. В некоторых случаях указаны характе. рнстикп двух алгоритмов решения олной и той же задачи. Например, для модуля х' -!.
1 указан алгоритм, содержащий 9 умножений и 15 сложений, и алгоритм, содержащий 7 умножений Р . 313. Хара рлсглл Р Р пю *г л эе м дулю эрл» пшел. н 41 сложение При ныборе того или иного алгоритма надо оценивать ситуацию и понимать. как данный алгоритм вкладывается в алгоритм большей задачи. Часто случается, что иесущественныс преимущества в числе умножений в малом алгоритме приводят к большим преимуществам, когда этот алгоритм используется в виде блока в большом алгор итнеув то время как большие потери в числе сложений малого алсоритма приводит лишь к незначительным потерям в числе сложений большого алгоритма. Так, например.
для модуля х',ф ! алгоритм с семью умножениями может на самом деле да»ь больше, чем это может показаться 3.6. Построение алгоритмов коротких цмнлическнх сверток Можно построить также н библиотеку хороших алгоритмов для вычисления коротких пиклнческих сверток. Эти алгоритмы можно строить как по мешду Винограда построении коротких ~от использовать в алгоритме даются равенствами ар~ ~ о -~ о~с,' з (х) = й (х) б !х) (шоб х" — 1), т,с! ос ! и з (х) = б (х) Л (х) (шоб «ч — 1), ЮЭ Гкв.ви рнеалср Г х р к сверток, так и другими снособачи Для построения алгоритма по методу Винограда надо быть унеренвыч а том, что каждое аз рассмзгрнваемых малых произведений мвагачлеиов может быть вычислено хорошим алгоритчоч.
Для этих подзадач мы будем пользоваться уже настроенными в средыдушеьт разделе алто. ритмани В настояшем разделе в иачестве примеров будут построены несколько хороших алгорвтмаа. Некоторые алгоритмы эычисле. ния коротких пнклическнх сверток првведены в приложении А. Излагаемый в гл. 7 метод, нзнестный пад названием алгоритма Агарвала — Кули, позволяет строить алгоритмы вычисления сверток больших длин, комбинируя известные алгоршмы для коротких пиклическнх сверток. Рассматрич задачу вычисления наклической свертки где оба мвогочлена б (х) и б (х) имеют степень, равную л — 1 Один нз ос бо ре е и состои в то .
чтобы найти сначала линейную свертку. а затем выполнить приведение по модулю — 1. Чтобы реализовать такой способ, нада модуль ш (х) для ансис.чения линейной свер~ки выбрать так, чтобы его степень была по меньшей мере равна 2н — 1, так как онв должна быть больше суммы степеней й (х) и б (х). Альтернативный способ состоит в использовании китзйской теоремы об остатках, на последнеч шаге которой для восстановления иногочлена а(х) в качестве модуля ш (х) используется непосредственно х" — 1, а в качестве взавмно простых модулей используются делители ага (х), тлпг(х), „ ш(и†" (х) мвогочлепа гл (х).
Так как сумма степеней этих простых делителей должна быть равна л, что мен*гг~е чем 2л - 1, то можно ожидать упрошення вычислений. С другой стороны, делители уже нельзя выбирать так, как нам удобно. Первый метод допускает выбор пранввольных делителей, но сумма их степеней должна быть равной 2» — 1, а не п. В качестве простейшего примера рассмотрим ни ~нелепое 4-нжечной пяклической свертки; Делателями многочлеаа х' 1 служат пиклотомические много. члены, хг — 1; (х — 1) (х + 1) (хт + 1) = ю(з) (х) ж! гг (х) югт~ (х). В этой задаче у иаснет реального выбора: циклотоьшческие много. члены предстаелвют собой такие подучи, ксторые необходимо 3 6. П с р » алгор ов аср ш* а знч х свар Винограда.
Коэффипиенты вычетов й)ы уже ностроили несколько алгоритмов вычисления умножения по модулю х* -'; 1. Одним из них является правило Следовательно, внутренние переменные даются определениями о,=во(~орга го ,о'. '(а о ' ! Далее, Яь = В„О„для й =- б, ..., 4. Китайская. теорема об остатках дает з(х) = ! (х'+хе+я+ 1)дчг(х) — — (х' — х'-1-х — 1)В'г(х)— — — (х' — 1) Ф'г (х) (мод х' — 1). в Таким образом 1 1 1 -1 О 1 ! — 1 О О О О ')1 Π— 1( 1 1 1 — 1 О ! 1 ! ! 0 ~Г1 ,'т 45 О 1 (,1=«1)ь(,1 ( а "— 1) 4466 ( ) = я — 1 ша ь ( ) =- я — 1 -1 0 Бнцмпмняи р Чслаэммте«з сч м эеа Ч о "м вник 7 сме яв Д е 15 62 31 76 72 46 74 1Ш Ш5 2 4 5 6 1О 16 ш 14 12 Зз 35 2 3 4 5 5 7 6 8 ч 16 16 в виде матричного Юа Гл.
3. Бмсгр е зг р нм к рмаяк сэ р Окончательный вид алгорнтма показан на рнс. 3.14. В упоряЛочиванни элементов матриц, «онечно, имеется некоторый произвол. В матрице предсложеняй допустнма пронэвольная перестановка строк, а в матрице постсложеняй — перестановка столбцов; зто не влияет на результаты вычнслепяй. На рнс. 3 15 приведены характсрнстнкк некоторых наялучшях нзвесгнмх алгорнтмов вычисления коротких сверток.
Этя алгоРитмы, часть нз которых приведена в прнложеннк А, построены по описанному методу. В некоторых случаях для уменьшения числа сложеннй использовались дополнительные методы, анало. гнчные тем, которые будут описаны ниже в оставшейся частя раздел». Рнс. 3.15 следовало бы дополнять характернстикамн коротннх сверток дл» пол» комолексных чисел.
Каждый алгоритм вычисления свертки в вещественном поле подходит в качестве алгоритма для комплексного поля. Но иногда многочлен х" — 1 над полем комплексных чисел разлагается на большее число простмх делителей, чем над полем вещественных чисел. Это в номплексном случае дает «онструктору алгоритма дополнительные возможности Алгоритм Винограда можно рассматривать «ак метод разложения некоторых матриц Пусть з, й и б — векторы ллины л, компонентами которык являются соответственно «озффкцненты многочлеков з(х), й(х) я б(х). Циклическая свертка з(х] = 36.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
