Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 17
Текст из файла (страница 17)
Пропелура ставит сваей цвлио минимизацию »псла умножений в поле Р, не пытаась минимизн. ровать число умножений в подполе. В большинстве практических случаев этими умножениями в подполе оказмваются умножения на малые целые числа, обычно на — 1, О илн 1, «оторие тризн. альпы. Начиная с данного момента, мы не будем учитивагь улгна. жения на рвцвональньге числа в полном числе умножений, хшн практически всегда надо проверять, являются ли эти рацио»аль. ние числа на самом деле малыми целыми числами. Быстрые алгоритмы свертки основаны на вычетах з~ь~(х)=К гм (з(»Я, й =О, ..., К вЂ” 1 Согласно китайской теореме для многочленов, многочлен а(х) можно вычислить по систеие остатков в соотнетствви с формулой 3 (х) = а~л' (х) зм' (х) -1- ..
+ а~» —" (х) Ф» — и (х) (шоб т (гД, где оо' (х), ..., а<» — и (х) — соответствующие многочлены с рациональными коэффициентами. Разобтм это вычисление на трн шага. Сначала вычисляются'остатки дгм (х) = й илм, Ы (х)1 и йм' (х) —. ))шлл,о (й(Р)! для всех й — О, ..., К * 1. Зги вычисления не содержит умножений. Затем вычисляются вели. чины .эглл(х) =й(х)4(х) (шобт~лл(х)) = = К л~гм ()7 гл~ г л[й(х)1 К гл! ю!3(4!) = = Я гм !О(лл(х)бгл>(х)). Наконец, вычисляется мвогочлен з(х).=а<э>(х)агл~(х) .1 ° ° -1-а<» — 'г(гг)М» п(»1 (пюбт(х)).
Так квк «оэффицненты всех многочденов а~л~ (х) ивляются рзцль опальными числами„то последний шаг также не содержит умно. жений. Структура алгоритма Винограда для вычисления свертки показана на рис. 3 7. Умножения возникают тольио на втором шащ при вычислении короткик сверток, задаваемых праизведе. пнями многа»левов, йгы (х) бгл)(х); так как число коэффициентов у мнагочленов йПлл (х) и ул~ (х) равна степени много. 93 Вн эб гм«н«а 1«юб рь- 31 Взиад сба «а (юаб т(т) 93 Га.
3. Бнсгрм элюрюнн яовоткнх с р Рнс 3.7. С руятурэ э ун н В н рэд д у к»«сыргок. члена тгы (х), та полное число умнпжений, необходимых для стандартнага способа вычисления этих произведении, К-~ рвано т (бей уны~ (х) !Д Эта дает существенное уменьшение ь — э числа необходимых умножений. Позже мм увидим, что исполь. завание той же самой кден разбиения иа еще более мелкие под. задачи позволяет добиться улучшения и при вычнсленви этих составляющих коротких сверток. На рис.
З.З дается поучительное сравнение алгоритма Вино. града вычисления свертки и алгоритма, основанного на дискрет. ном преобразовании Фурье. Для тога чтобы сделать эта сраваеаие более наглядным, алгоритм Винограда выписан в приведенных выше матричных обозначениях. После группировки членов и перехода к матричным обозначениям этот алгоритм записывается в виде Равенства 3 = б ПВВ! (Аб)), где точна обозначает паномпанентное произведение векторов Вй и Аб. Нз этого сравнения видно, чта ачгаритм Ввнограда яв.
ляется обобщением метода вычисления сверток с помощью пре. образованна Фурье. В качестве примерз рассмотрим вычисление свертки З.точечного вентора с 2-точечным векторам. Пусть В (х) = В,х + Вы б (х) = б,ээ -Р б,х + б,. Вша В.бб бт«т а б«а Э ас «блат «« В м««ба Рэс 3.3. Гаээээээе х у э бз з э э рюн. Пряное вычисление содержит шесть умножений н дза счоженея. Яы сначала построим алгоритм, содерукаший пят» умножений н восемь сложений. Эта не очень хороший алгоритм, на его па.
строение являетсн поугительным. Позже будет приведен алга. Ритм, кашрый лучше и содержит четыре умно кения н семь сложений. Степень линейной свертки з (х) =- В(х) б (с) равна трем. Вы. берем т (х) = х (х — 1) (х'-~; 1) = тгм (х) таГ (х) «ам (х). Мнажиттли взаимно просты; возможно и другое разложение ьгногочлена т (х), но для иллюстрации метода мы остановимся з~фб»Вю й.- О, ...,4 3 »чю»тп( ) (*) ж '( Ээ Га В Бы Зы затор ы «срок *сырта на выбранном разложении Вычеты равны й'») (2) = й» Ш») (х) = ды йи'фф —.а -'.-а, шифф=б +В+он й("(х) = й(ах-й», бм'(х) = б( -Р(Ỡ— 4). Пледовательно, 5(») (х) = й»б», з(() (х) = (й) ф й») (бз -~- б( .
б») з'2' (х) = (й,х -1-й,)(б(х-'г (4 — б»)) (шайх' ф 1). При вычислении Ф») (х) требуется одна умножение, при вычисли нии зи) (х) 'требуется одно умножение и, как мы увидим, при вычислении з'и (х) требуются три умножении. Вычисление В') (х) сволится к вычислению двух величин 5(2) и) (2) (2)бы) э» =й» ы 2( ) = й( )б( ) -)- й( )б( ) = й» ) . В) а (которые случайно имеют структуру пронзнедення комплексных чисел). Алгоритм зтОй части оычислений дается равенством и содержит три умножения. Последний п)аг состоит в вычислении з (х) па формуле 2(х)=а(»'(х)бм(х)ха(п(х)Ф)(х)фа(2)(х)*(2)(х) (шобх' — х~ьхэ — «), где а(»' (х), а'и (х) н а(и (х) вычисляются по китайской теореме об остатках следующим образом. Воспальзуемса соотношением л(ю(х))п(")(х) ф Ап»)(х) М(")(х) = 1 и построим следующую таблицу: о *-1 ° д( 22) (( -П 1'огда а'») (х) =- Ап»)(х) М(')(х).
Следовательно, ( з (х) = — (хз — «' + х — 1) з(») (х) + — (х» + х) Ф о (х) + э + — (2» — йх'+ х) ам) (х) (шаб х' — х'-)-х» — х). 1 э 2.3. д» рз . Вэиогр»х» . р «их юр зэ Последнее равенство мажет быть перезаписано в виде матричного равенства Теперь для построения нскомога алгоритма надо собрать вместе его отдельные часси. Всего имеются пять умножений, которые мы выпишем и выбраинон единообразной форме Определим новые обозна~ения, гаответствующие этой форме.
Используя пропеланные вычясления, для вектора О получаем определение 1 0 О О О 1 О О О о)1 () 0 О)1 О, О 0(е 1' ! 1 О О 0 О 1 0 0 0 О 1 1 О О ! 0 0 0 О Вектор В определяется аналогично, но в его определение мы включим знаменатели, которые должны появиться в матрице постсложеннй. Поэтому в данном ниже определении вектора В появлясгся самая левая матрица, содержащая извлеченные из М Гя 3 Бисюн* юр Р "*" Р матрипы пастслолгсннй множители 1(2. Таким образом ~Г) 3.3. Дл рнтн» Винограда 5 таст ороткнк с ръгя Н1 Так «ак вычисление вектора 6 является предваряющим алто.
ритм вычислением, та эту матрицу можно в дальнейшем просю отбросить Наконец, матрица постсложеиий имеет вид Описанный алгоритм в матричной форме приведен на рнс. 3 9. Порядок вмполнения сложений н такой форме алгоритма не укааан. Читатель мажет сам поэкспериментировать с выбором порядка сложений, ииннмиэируя ях число; никакой сцецнальной теории выполнения такой минимизации ае разработано, Легко выполни~ь все предсложения с помощью четмрех вещественных сложений. Пастсложения можно реалнэовать с помощью следующих восьми вещественных сложений: 5, =. Яо 51 -= с 1- Ст + бэ, С, —: б, — йм 5, = 91 + С, — СО с,— Э, ' лл 5,— -с,— Э,-РЭ1 Эта завершает рассматриваемый пример построения алгоритма Винограда длн свертки, но построенный алгоритм можно улуч.
швгь. Белее общая форма алгоритма Винограда соответствует Р . З.В. Прннср 5 арно а В р д 1 ня сырт выбору многочлена т (х) меньюей степени. Это приводит к не. правильному вмчислеиию свертки, но ошибка легко подправляется с помощью нескольких дополнительных вычислений Согласно алгоритму деления для многочленов можно эапнсать 5 (х) = кг (х) Ог (х) 1 й гю (5 (5)). Мы уже рассиотрелн случай дей т (х) ) дейв (х), в коюром частное () (х) тоягдественяо равно нулю. Если дей т (х) < дей 5 (х), та алгоритм Винограда позволяет вычислить 5(х) по модулю многочлена т (х).
Член гс (х) т (х) представляет собой погреш. ность, котОрую можно вычислить дополнительно н прибавить к результату. Простейшим явлнется случай, когда бейт (х) = = дей 5(х). Тогда многочлен й (х) явлнется константой, так «ак его степень должна быть равной нулю. Если т (х) — принеденный многочлеи степени л, то, ачевилно, Ц (х) — 5„ где 5„ — коэффи.
циент при х„ в многочлене 5(х). Следовательно, 5(х)=эги(х) 1 и 5~В(х)), и э„легко вычисляется «вк произведение старших иоэффициентов многочленов й (х) и д (х) Эту модификацию можно формально вилючить в основной алгоритм Винограда для вычисления свертки путем замены многочлена т (х) формальным выражением т (х) (х — «О). Утвер- ждение а (х) = 5 (х) (тод т (х) (х — )) представляет собой просто удобное сокращение для данного выше точного утверждения. Вернемся к предыдущему примеру и применим описанную модификацию алгоритма к вычислению свертки 5 (х) = (атх ф й,) (дахэ ф дгх ф де). В качестве ыодуля выберем теяерь многочлен х (х — !) (х+ -1- 1) (х — ). Алгоритм будет содержать четыре умножения; 4в аг и 100 Гл.
3. Высгрые з зр ы к р ппм сыр и з 1*) = х ( ) и ( ) зеки 00 = с — 1 шк х (В = л' — 1 Вм тзные зр да Числ ззы с снам Число земе гзи иы» уии и ния ысие д О, 0 а Кгиазексиыз сз ргзи Ч с о юмиыы ых Число кс аз хсим» а 2 2 Э Э 3 3 Э 13 4 4 7 Рис. 3.11. Харакг ристаки нз с орых алгоритма зы ишеиш юро их з им!- из з рюх. 51 И 1 Г 1 $ 1 Г з,м е и,+и 3 х 4 -б, о, -и.+, Рис.
3.12. Неи р ср й г 2 2 2 3 3 3 3 Э 3 4 4 4 4 3 7 20 !О 4 41 1Э 34 По Р р» в 1О1 гелей многачленом второй степени, то галучим шесть умноженнб, на меньшее число сложений.) Выкодной многочлеи дается равенством з(х) — -)(„. Ч мыл м о(2(к)0(х)).бди(тх(х — 1)(х-1 1)(с — 2). Остатки опревеляются матричными уравнениями где с целью сокраненни стройности и упорядоченности прннятык обозначений 04 и (74 формально определшотся нак вычеты по модулю многочлена (х — ).
Такам обрааом, 5» = бьОз для 2 = 0, ..., 4 Наконец, нспользун китайскую теорему аб остатках, длн мвагочлена з(х) получаем выражение з(х) = — 5,(хз — 2х' — х -1- 2) — — 5,(хз — х' — 2х) + -1- — 5, ( — х" -1- Зх' — 2х) -1- — 5,(хз — х) -1- 54 (х' — 2х* .1- х' -1- 2х). Запись последнего шага в матричном виде дастся равенствам Постоянные множители можно похоронить в константах лиаго.
нальной матрицы, переопределяя величины 54 и 0„. Длн выпол. пеняя свертки требуетси пять умножений. Матрица предсложений может быль реализована семью сложемиями, а матрица постсложеннй 13 сложениями. Окончательная форма алгоритма показана на рис. 3.12. Хоти алгорнты построен дли поля вежестиенных чисел. он приггжен и в пале комплексных чисел: пять умножений становятся пятью комплекснымн умножениями, а 20 сложений стзновятс» 20-ю комплексными сложениями. о о -! з (М вЂ”.— й (х) б (х) (шаб ш (х)), а 1 ! — ! -1 10З Гл. 3 Би Эи югоз1 ю Р * ыэюи Можно также специально строить алгоритм над полем комплексных чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
