Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 63
Текст из файла (страница 63)
Доказательство будет проводиться по индукции. Мм построим уповлетворяющий теореме регистр сдвига в предположении, что такие регистры последовательно построены для всех й г. — 1. Для йажлого й, й = 1, ..., г — 1, обозначим через ((.ы П»> (х)) регистр сдвига минимальной длины, геверирующкй а„ , а„ Примем за вредположение индукции, то Е„=шах(Е„о й — 1.»л), й.=!, каждый раз, когда )гю (х) Ш (гл — и (х) Это, очевидно, верна для йг †.
О, если ал ага~гэги ог нуля, поскольку !., =. О и !., = 1. В более общем случае, если а, — первый ненулевой элемент в аа. данной последовательности, то Е,, =- О и /.~ = г Тогда вредно. ложекие индукции относится к индексу й = ! Значение й в последней итерапии, приведшей к изменению ллины, будем обозначать через т.
Последнее означает, что при за. вершении (г — 1).й итерации т являетсн пелмм числом, таким, что зез зш г ПБ .Б р л р:ты ела т ым Теперь имеет место следующее равенство: г., Волн Л, .= О. та регистр (Е, м Р—" (х)) также генери 'ет пе еже г символов, и, таким образам, ), = Е,, и!а»(х) =-Р'-и (х).
Вели Л„-э-б, та н еабходичо построить аовый регист с в Напомним, что изменение ч г тр сдвига . Сл т. едовательно, н д. ины регистра сдвига произошла пр Е ))--» и ло предложению индукции ),=.Е. =-так[(. и т — !.,[=т — Е носнальку Е ) ,. Теперь выберем навий мнагочлеи ) ' (х) .=)о (х) — Л,Ь„'х' )с и (х) !» н положим ń— — беу )!'» (хЕ В ' ( Е этан случае поскольку х) чь „, и беу [х' "П вЂ” '»(х)1(г — т+ Е„, та -.г — т+ „ь та ,так[). а г — т+Е»)(шак!Е,м г — Е,,). Из теоремы 11.3.1 при условии, чта (Е„)а»(х)) гене н ег только доказать, что регистр сд (у„, )с'» вита „, )' (х)) гене и ег е.
'шслением разности межд а н сигнал . сть. 'анаше»» то велас»е с е д тв иным вы. ду аг сигналом на выходе обратной связи с, =» с„, — л,ь»[ас,.» -[- ч )с па г -» ! =Е„Е,ю1, ..., г — 1, х генерирует а„ ..., а„ и теорема доказана. О дани Теорема 11.3.3 (Алга игм ритм ""рлекэмна — - Месси) Пусть эа. аны аь ..., а„из некыларосс поля, и л с аны ) ..., „, и луаль лри наюльныс угла.
— х = 1 и Е, =-.О еылалняются слсдуюиум сье рим»саша, „т,с Оха аычисхс"из ) »»3 Длгэ»Бер . а — Мсв — » г .*е ( 1 си(1 — 6,) 1" Г';,',('„)1 = =( Т, :, 1~- 6 ) х ) [ 1».-п (х) ) ' 1 2л ас 6 — ! если сд анре.асю а Ь, Ю О и 21.„, ( -., г — 1, и 6, — О е ало»лианам с;у»ас Т»»ада )"'»( 6 ят сигея ми».- 'сч»гном наименьюеа тлелош, »т»»ффиг(ленты кт арсе» удсслс. тюртат рассяс»азам )[и» =- 1 и а,+ Е, )»ы»а =-О, »=» г-..!.в — '1, ...,2г.
Паказатс,шстеа. Следует из теоремы 1!.3.2. О В этой теореме Л, может обращаться в нуль, «а тол~ко а тоы случае, когда 6, —. О. Положим с тогда по определению ЬТБ, .= О. Блок-схема алгоритма Бер- р„е 1! е дл рю„в»ра» лекэчпа — Месси приведена на»ы--и «н. рис. 11.6. На г-и шаге указаншей алгоритм содержит число умваже. ний, рваное при.
римерно удвоенной степени чвогочлена )' (х . Степень чногочдена )о»(х) равна примерна г), и все 2л итераций, так что всего алгоритм содержит примерно 2»»' = д",г умножений и примерна такое же число сложений. Коро»е ио:кно скааать, что порядок числа у» мнажепкй в алгоритме Берлекэмпа — Месси равен и', или, формально, О (и"). Зяч Гл. >!. Нишэ иеюд реме яя тез яевнх нетям 11.4.рекурсивный алгоритм Берлеквмна — Месса Все рассмагреннме нами да сих пор методы решения теплице. вык систем уравнений содержат число умножений, пропорциональное ад В настоящем параграфе мы воспользуемся стратегией дублирования для того, чтобы снизить вычислительную сложность алгоритма Берленэмпа — Мессы при больших л.
число используемых на г.м шаге итераций умножений примерна равно удвоенной степени многочлена Рм (х). На перных шагах итерапий эта степень мала, н итерации выполняются легко, но с ростом г растет и сложность вычислений. В ускоренном алто.
ритме за сче> одновременаого выполнения нескольких нтерадий используется преимущество, которое дастся простотой вычислений на первых шагах. После выполнемия «аждой такой группы итераавй исходная задача модифицируется так, чтобы учесть это полученное решение. Затем сызнова начинается выполнение новой груп.
пы итераюй алгоритма Берлекэмпа — Месси, но уже для модифи. дироваяиой задаю н иодифндированного на'>альиаго значения мнагочлена 1(х) Рассматриваемое ниже построение начинается с более коыпакт. ной организанви алгорвтма Верлекэмпа — Месси. Заменим много- члены (м> (х) и и'> (х) полиномнальной матрипей размера 2хй> Рих> = ~ ямх> ай! Коэф$ипненп» многочлена Р)» (х) будем обозначать через Р))~>. Матрица Н" (х) определяется так, чп>бы иногочлены (о> (х) и Д'> (х) можно было вмчислить, используя уравнения ! н») Напомним, что сначала выполняечые в алгоритме Берлекзыпа— Масси вычисления аа>шсываются в виде двук уравнений' ь,-~'„«; , [ > -ь,, [> -ьх][>~ Следоэательна, Алгоритм модифнпирует как мзтрипу Ню (х), так и много.
члены (»'(х) и г»'(х). Прямой метод перевычнслсния р»'(х) требует примерно в дза раза больше умножений, поскольку матраца содержат не дэа элемента, а четыре Хотя в такой форме вычисления я дапускшот использование метода дублирования, мо чы получаем большее, чеч хатим, число умножений Надо соотнес.
ствующим образом реорганизовать вычисления. Рекурсивная форма алгоритча Берлекэчпа — Месси строится вокруг следующкх уравнений, эквивалентных эыписаины» ра. вее. Л =- 1 Р>'. Ра, -, 'Е Р»П»л,, — > —. ° Предполагая л четвьш, разобьем алгоритм пополам и положим р>ю(х) =. р'»" (х)р" »""(х). где ,П [Л б, )-б,)х1' Г ! — Лх1 Н (,) = П [ >(Лрб, (! — 6)х!' Яы будем вычислять каждую иэ половин отдельно, а затем нх пе.
ремножать Сложность при этом получас>ся иеньше, чем в исход. яам способе решения. Необходимо также реорганизовать уразне. няе, определяющее Л„Буден велвчнну Л, вычнсл>мь как г.й «озффинпент первой кочпонентм двумерного вектора мяогочленов 1( Таким образом, для г, больших чем я>2, ] = р'о п(х)Е'»>(х)! 1 = Е'и '>(х)а'">е(х) Л (х) ! Га (х) ! Л'(х)1 >а(х)~ где (я(х)1 а>"м>(х) =. р >"ы>(х) [ (а (х)З ЗЯ7 [ ;171 ,,и, шя —..М„ш Зсб Г .
Ы. Б В дн рею*ага ц с — — 1 Р с 11 7. Рамок е рят Берл к ы — М сш. Это завершает описание разбиения алгоритма Берлекзчпа — Месса. Основная форма алгоритма теперь записывается в виде ! г =4 ' (х).=! ., (, 1ро-п(,), где вместо Г'о (х) подставляется Г'о>(х) л. Гмо ( 7, ('а,,'х), а, (4) а первой яоловнне вычислений равен,(а, '), ' 7), рой половине вычисления модифиштруетс р я в вектор т ицаГм! х и (х), осле гога, как вычислены обе половины з р " (х) полу ~ается перемножением своих двух половив. ритма Берлекэмпа — Весси показано на рнс. ! 1.7. Разбиение алга , Б Заметим, гтп каж. ая нз и ° 3 , д оловня алгоритма гама является алгорнт.
чом Берлекэчпа — Ыессн Следовательно, если п(2 четно, то каждая 'ередь, если и равно сте- нз половин может быть разбита в свою оче е, ь, пени двух, та таное разбиение можно продолжить до тех п уду получены фрагменты, состпящие толька з ор, пока . ь а нз одаой итера-: пнн В этих фрагментах выполняются уже все вычисления, ио они достаточно тривиальны. На рис. 11 й алгоритма приведена рекурсивная форма берле.
кэмпа †(есси. Вся вычислительная работа сводится к вычислению полиномиальимх произведений, сочетакнцнх половинные резуль. таты. Этн вмчислеиия представляют собой свертки многочленав ° могут быть выполнены с помощью любого алгоритма линейной свертки. )1.5. Методы, осмоваииые на алгоритме Евклида В некоторых методах решения теплнцевых систем уравнений нспользуется алгоритм Евклида Наиболее подходящей для этого является описанная в равд. !0.7 рекурсивная форма алгоритма Евклида.
Начнем со следующей теплнцевой системы уравнений; Эзо та же самая теплипева система уравнений, которую в й 11.3 мы решали с помощью алгоритма Берлекзмпа — Весси. Пусть г — ~ а(х)= х.' а,х', Цх)=1+ ~)хй г=а грим произвеление этих мнагачленов й (х) = ) фб о (4 Нз выписанного матричного уравнения видно, что д,=б, (=п...,ул — 1, но при зкаченнях нгщекса г, больших чем 2п — 1, коэффициенты д, могу~ быть и ненулевыми. Рассмотрим задачу вычисления таких 1 (т] и й (х), которые удовлетворяют условиям бей ) (х) ( л, б*т д (х) < я — 1 и й (Н вЂ” ) (х) а (х) (пюб хт").
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
