Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 15
Текст из файла (страница 15)
2 3 и которая доказынается по той же схеме, что и для целых чисел. Теорема 2.8.3. Для заданйого множесгпга попарно взаимно простых многочтятг т~е~ (х), таз (х), ..., гпм1(х) и множесаыа много. ысяое с~э~ (х), сп) (х), ..., см' (х), таких что бей спг (х) < < бей тса (х) система уроенениб сга(х)=с(х) (шобтсп(х)), с=О...., й, имеет не более одного решения с (х), удоегетеоряющею услал ю бей с (х) < д„' бей лрл (х). г=е Дохаэатегэстео. Па существу даказепечьство совпадает с доказательсгвоы теоремы 2.8.1. Предположим, что нмсются два решения, а имеюю с (т) = Снп (х) ти' (х) -1- с'а (х) с' (х) = 0' ") (х) т~г~ (х) -';- си~ (х), так что разность с (х) — с' (з) кратна многачлену тгп (х) длз каждого г.
Тогда чногочлен с (х) — с' (х) кратен н многочлену Цта>(х), причем бей (с (х) — с' (х))< бей ~ П тга (х)~ тг. о Следовательно, с (х) — сг (х) =- О, 0 доказателъство закончено. О Систеыа сравнений мажет быть решена так же, как и в случае кольце целых часел. В кольце многочленоа над некоторым полем для любых заданных з (М и 1(х) существуют мнагачлены а (х) н Ь (х)„удовлетворяющие условию НОД В (х), 1(х)  †. а (х) з (х) ф Ь (х) 1(х).
Пусть М (х) = Цти>(х) и Ми> (х) = М (х)(гп, (т); тогда =е НОД !М<г> (х), тиг (х)) = 1. Пусть Уа> (х) н лог (х) удовлетворяют раеенству Лиг(х) Мю (х) + паз (х) тсп (х) =- 1. Теорема 2.8.4. Пуст М (х) = Цто' (х) — произведение по° -г парно взаимно лрослмгк мнагочхеноес луста гИю (х) -- д! (х)(тп (к) и дгя эсех 1 многочгенм йнс (х) удмгетеоряют усгоеилм 77 о оаьа а 323 2 О 2 3 3 оггг Ь'ь=-': ь Задачи 76 Г». 2. В Л В В бетте Ун ВЛГ бру дггсг (х) М(и (х) -(- ниг (Х) тиг (х) =. !. Система сравнений с(о(х) — -с(х) (тодт(о(х)), ( — О, ..., Д, имеет единственное Решение, дав емое мншочленом с(х) —.
~ сс'3(х) Дг"3 (х) М(с' (х) (тад М (х)). с=в Дахсаателыагю. Нам нужна только доказать, что многочлен с (х) удовлетворяет каждому сравнению данной системы. Но с(х)=с('3(х)дпсг(х)Мги(х) (шодтиг(х)), так как тиг (х) является делителем мцогочлена Мг'3 (х), есл» г че !. Наконец, так как Вмсу (х) М(и (х) + л('3 (х) т(и (х) = ), то Л'('3(х) Ми((х) = ! (тадж('3(хЦ и с(х) = с(и (х) (тадж('3 (х)), что н завершает доказательство теоремы, д 2.(..П .
ус . л. Ру р . вы иП 2.2. ((у т руввоь я а р вея тру: х в ввл н 2.( юи мт сл мв. ет . б. Д,в ю гьа иь ир в их Рув Овр еы ь уива вк тт, б ( р Л Рл вн ел вь Ртг б не шл е нс А В увал яр» м рть у НОП П573,3ОВ! — Л (573 г- В 3ОВ. а —.с, ( в.(,! ( Ф Мь=( У.ь).г,-(а -( ь,)(-(( 3 ь)! ( 'Ььдь ь=(,ь„— в,ь,-а,ь, м,) ь -(. (,ь,л аМ вЂ”,ь 3- -(- ( „ь„ + ,ь, †: ~ь, — А) ( М (ть — ь,б вь ( ь)ь Д летн, «а лмрвв л 2 е лыс сбр еует еосыю, 2.37 пои э р «в ор (3) л р б . и твблиивиг г'гго .,'а~ ггог лагг 78 Г 2. В ыц е эб гр аиуи азг бру )2 ) 1) и г ! з, 2,18. 111НФ р й дииидь г ) Раи гр д сяр и р :брашна з Фу У,= ~ гзон а=б, ..., 1-О н преки, а зммна просю и Ну и пер сиювкэ к кв Р д Рыюс вом 1 —— он,г).
Да азась, есо р едз и„' р м юй омп орз у, ыдцвммой раве м Уз = У)Фига Я Р Ц Г Ь, ОЗРОС кого. 2.18. Г а адерж г им б ш ЗИ д й. Пр д ож, ио ни меы» за а. 31о з» д р д. ор д о маж рдивюдувоыда- В.Прмпм д, ссдр. 3)д,а дмв — 12дней Мож зз р д э ирд пордюмй юердца в гаду . И . у 3).д цмй ие яв н 12.дюв уи ыдмш, юпгиеть форИУЛУ з е вор зывои н и рз дн» в иду срез юз и шара в месяц . Сд «ы ью чгсз вма прим ров.
б. О» рюия а иирги ской раз сгц июж . А р а р юм А А В= )А — 8) 11) — А). Занечиння д .ез а В югкзу«ан м с вводи сакура,поуровцюяосгапж о даа дзц й я н, м реншинду . гу Впряг фа и Маыеии М) И941). м югр ф Вы дер В рыю )2) В949, ПВЗ) р д л и ссый «урс бо, н а ур е, адр ыннма в и и иа и н угзубденнц эаю , ишнй юпрг .и Мыераал п йюй ц» ебр и гырнн квгрцц йгн к у еб а, сп м ц цпиннм этим равилем м брм. Подирав )7) а ком ваде яэдожюа цо рссбрааава ця Фур е в произ.
эи мим Пыя Гму аыв в и В ар и Г ау НВН вЂ” 1832). Аб грунин Кур«ы з бр — 11*пи М Ну .Ю78,Мзды А И.гмн э й й югбрм. — 4-с цзя — М. Н у а, 1978. — Прим «рэ Г Э БЫСТРЫЕ АЛГОРИТМЫ КОРОТКИХ СВЕРТОК Наилучший известный способ эффективнога вычисления свер. ток состоит в использовании теоремы о свертке и быстрого алга. ритма преобразования Фурье Эшт способ обычно бывает достаточно удобен и часто работает с уловлетворнтельной скоростью, хотя существуют н лучшие методы. Однако в тех приложениях, в которых стоит заботэться о дальнейшем снижении вычисли.
тельных затрат, целесообразен переход к другим методам В слу. чае котла ллина свертки маля, лучшими с точки зрение числа умножений и сложений явлиютсн алгоритмы Винограда вычисле. ния свертки. Описание алгоритмов Винограда занимает основ. ную часть данной главы. В следующих главах будет показано, как можно, соединяя вместе эти малые алгоритчы.
строить алга. ритмы для длинных сверток. При таком подходе алгоритмы для длинных сверток окажутся хорошими, только если хороши алга. рятмы для коротких. Поэтому поиску алгоритмов коротких сверток улеляется большое внимание. Детали алгоритмов свертки могут зависеть ат нонкреюгого поля, над которым вычисляется свертка, но общая идея ностра. ения таких алгоритмов от поля не зависит. Хати, конечно, эав более важные приложении ямеют гюлп вещественных и комплексных чисел, мы описываем методы построения аагаритмов свертки примеиитевьно к любому представляющему интерес полю. 3.1.
Цнклнческне свертки н линейные свертки В компактном виде лннеииая свертка записмвается «ак произ. ведение многочленов 5 (х] = й (х) д (х). Коэффициенты зг этого многочлена даются равенствами и — г з, = У, й. бю = О, ..., Сф Н вЂ” 1, з-е где бей й (к) = С вЂ” 1 и бей Ц (х) =- йг — 1. 3! ц ти «е ы э е г ш о. з. ие ее Прямые способы вычисления произведения многачленов с держат число умножений и сложений, прямерна равное прои ведению степеней многачленов, ьгу; возможны, однако, друг спогобы вычисления такого произведения, содержащие меиьш числа вычислекий. Циклическая свертка, з (х) = й (х] Ц (х) (шаб х" — 1), где бей й (х) = бей б (х) — и — 1, ноэффипиенты даются равен. ствами так что свертку можно выгислять, выполняя последовательно преобразование Фурье, поточечиае умножение и обратное преобразоваяие Фурье.
Эта процедура иллюстрируется рис. 3.1 Средний блок содержит и «амплексных умважений, что мало ио сравнению с и'. Если и имеет много делителей, то описываемое в следующей главе быстрое преобразование Фурье может привести к «ущественному уменьшению числа вычислений в первом н третьем блоках, сведи их к величинам, также малым па сразив. ввю с пЕ Приведенная на рис. 3.1 процедура вычисления циклической свертки относится к комплексному случаю.
Поэтоьгу естественно ожидать, чта в случае вещественных аоследоэательвостей этот алгоритм сильнее, чем требуется, него эффективность может быть повышена. Некоторая модификация позволяет почти тем же самым алгоритмам вычислять одновременно две вещественные свертки. ! а = Е йп .пбю г =-О, э=а и двойные скобки обозначают вычисления по модулю я, есчи вычислять ее прямо по выписанным формулам, содержит и* умна жепий п я (и — 1) сложений Циклическую свертку можно также вы ~казать «ак линейную свертку с последующим нривелением по модулю х" — 1'). Следовательно, эффективные способы вы- числения линейной еертки при л т танжс к оффеитвв ы мета.
дам вычислення циклической свертки. Наоборот, эффективные методы вычисления циклической снертки можно легко превратить в э ктивные метолы вычисления линейной свергни. Й' опулярным способом вмчис.чения циклической свертки яа ляется использование теоремы о свертке и дискретного преобра. зованип Фурье. Согласно теореме о свертке в частотной области, Яь = Огры й = б...., я — 1, 3!.Вки»в»г»сртю В ад Ви вювть 2«=о«о«а=о,.„ 22 Г». 3. Бнстр р ою к р ткнх р Вн»»ет -! »! = — р.
«2» ! — о... » — ! -гь «=» Вм и Р . ЗЛ. Вы«и ж вню а сыр к а»иом р ар ы Отр к Вещественное преобразование Фурье обладает свойством симме. грин (см задачу 2.!2) — а = О, ..., н — 1. Предположим, что д' и б* — вещественные векторы длины л и пусть компоненты комплексного вектора б длины и задаются п авилон Р б! —.4 Р(д»н ! = О, ..., л — 1. Тогда его дискретное преобразование Фурье удовлегворпет равенствам О,=О(Ф!О;, Д О, ..., и — 1. О ь ''О» — !О». Следовательно, О; —. — (О«+ О„,(, 2 й —.О, ...,л — 1 О,' = —,. (О» — Ой «1. 2! Эти формулы позволяют вычислить преобразование Фурье лвух вещественных последовательностей, выполняя одно дискретное преобразование Фурье и некоторые дополнительные сложения.
Рс.3.2.В юн ау р ач ер ар»ю»» ия Ожь . Описанную идею можно применять и в обратном порядке, начнная с двух компленсных преобразований двух вещественных последовательностей. Для заданных комплексных преобразова. ний О' и О" пусть О, = Оь+!О«П 2 = О, ..., л — 1. где в общем случае и Оь и О» являются комнлекснымн числами. Тогда обратное преобразование Фурье приводит к равенствам Д»у б» 'гф! »=О .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
