Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 19
Текст из файла (страница 19)
По!все н * О+мое юво кях еик з с Р ж Рзс. 3.!4. Ааюрш 4.то е»оа и л сюа сюртан. Рис 3.15 Хара р з ртке. = й (х) Ь (х) (шоб к" — 1) может быть записана пронэведеняя Оа Гл 3. В р »р и кор т з сверток »г! или з=Тд. Алгоритм Винограда, записываемый равенством э = С ЦВй). (Ад)), мажет быть записан также в виде з = СОА6, где А представлпет сапой матрицу размера М (п) х п, О является диагональной матрицей разиера М (и) х М (и), а С является матрндей размера п х М (и). Таким образом, алгоритм Винограда можно рассыатравать иек алгоритм разложения матрицы Т =- ССА, где Π— диагональная матрица, а С и А — матрицы, злеиентамн которых явлнются малые целые числа.
Так как а большинстве приложений многачлену й(х) соответ. ствует фиксированный КИО-фильтр, или по крийней мере КИО. фильтр, коэффнциенты которого меняются ве слишком часта, то вычисление О = Вй приходится выполнять не слишком часто и при подсчете общей вичислительной нагрузки им можно пре. небречь Следовательно, сложность матрицы В особой роли не играет. Роли матриц А н В симметричны, так «ак их можно поменять местами путем простого перенменаваннн векторов д и и.
Алгоритм Винограда вычисления свергни допускает построение ыатркц А и В, отличающихся талька перестановкой строк. и, следовательно, имеющих одну и ту же сложность; но в общем случае более целесообразно одну нз матрид строить более сложной и именно ей приписывать роль матрицы А. Удивительно то, что в алгоритме Пиклической свертки можно менять ролями даже матрицы С и А.
Способ сделать это описываетсн следующей теоремой Теорема З.б.! (теорема аб обмене матриц). Если тсплицееа мап лица 5 долутсагт факторизацию вида 5 =- СОЕ, пю оиа может быть пакже записана з види 5 ( и ) г и г ( С ) г где матрица Е атличжпил ат матрицы Е обращепяым порядкам столбцов, а матрица С атличаглмя ат матрицы С обраиу.иным порядкам строк. Доказапмльстш. Пусть ! представлнет собой обменную матрицу того же размера, что н матрица 5. Тогда бг = !5! — (!С)О(Е!) — СОЕ.
Операция транспанирования завершает доказательство. П Применим эту теорему к умножению миогочленов по модулю миогочлсна х — с, где й — некоторая константа Пусть надо вычислить » (х) .—. й (х) д (х) (пюд х" — э), где й (к) и д (х) миогочлены степени не более и — !. Если с = 1, то мы ииееи задачу о циклической свертке Случай 1 = †! (а в поле комплексных чисел и случаи Э = Ш!) также очень важен.
Запишем это произведение миогочленов в матричво-векторном виде )Гз,!ты.*ы!» или э=ту, где Т вЂ” теплицева ма~рипа. Алгоритм э =-С КВд) (АйЕ можно переэвписать в виде а .— СОАй, где Π— диагональная матрица, диагональные элементы которой равны компонентам вектора Вд Согласно теореме Э.б 1, з ==(А)г О(С)г и При»»сиятельно а залаяв вычвслення циклвческой свертки тео- рема З.б.! означает, что наиболее сложную иэ трех матриц А, В и С можно вмбрвть множителем арн векторе и я «включить» ее в ма»рину О.
3.7. Свертки в общих падях и кольцах Любой алгоритм свертки, такой как алгоритм Кука — Таама или алгоритм Винограда, нредстввляет собой некоторое тожде. ство, опирающееся на свойства аперапнй в данном поле, в чв. стнастн нв свойства ассоциативности, дисгрибутивносги н комму- !И Га З.имр *лот мзор саров ЗЗ цюмеаст алгар юв с р яв пз р н запйсвть ожений, сва(шод х' + 1) татнвности.
Алгоритм, построенный в одном поле, может быть использован а любом расширении этого поля. Он, однако, может оказаться не столь хорошим, как алгоритм, разработанный спе- циально для данного паля. В частности, алгоритм свертки двух вещественных последова- тельностей можно без изменений использовать для свертки после- довательностей комплексных чисел.
Если обозначить через М и А соответственно числа вещественных умножений и сложений, необходимых для вычисления вещественной свертки, и если для вычисления комплеисной свертки использовать тот же алгоритм с обычными комплексными умножениями и обычными номплекс- нымн сложениями, то а общей сложности получитсв 4М веще- ственных умножений и 2А -1-2М вещественных сложение. Если вместо этого воспользоваться построенным в равд. 1.1 комплекс- ным умножением н рассматривать одну часть свертки как отводы финсированного фильтра, та потребуется только ЗМ веществен- ных умножений и 2А -1- ЗМ выцественных сложений.
Если длина комплексной циклической свертки равна некото- рой стеяенн двойни, то мо к построить да» еще лучший алго- ритм. Для пояснения таге, «ак эта делается, рассмотрим свертку по модулю хм -1- 1. В кольце мнагочлеиов по модулю многочлена хм .1- 1, ! ) 1, имеется элемент, квадратный корень иэ которого равен минус единице. Действительно, †! = гм (юоб «'г ф 1) так что в рассматриваемом кольпе ьг — ! = х' . Воспользуемся Г ! этим элементом, чтобы выписать иомплексную свертку через две иещественные свертки.
Длн вычисления комплексной свертки з(х) =й(х)А(х) (шоб хы -1-1),, где й(х) = дв(х) + )йг(х) и А(х) = Аэ (х) ч- )б,(Х), можно вычислить по модулю х' .1. 1 четыре веще«тасиных све тки йи (х) ии (х), й, (х) оа (х), йя(х) д, (х) н й, (х) Ог (х) за (х) = йа (х) ба (х) — йг (х) А, (х), з,(х) =ба(х)б,(х)-1-д,(х)А„(х). Лучшая процедура, содержащая вдвое меньше уми дигся к введению многачленов а (х) -- — (йа (х) — х' й, (х)) (Дэ (х) — х' б, (х)) 1(х) = —, (Яа(х)-1-»Ы 'йг(х)) (Аа(х)+ х" 'б,(х)) (шоб «"-~- 1) вычисление которых сводите» к вычислению двух иещественных сверток.
Выходной многочлеи з (х) .= д (х) А (х) (пюб хм .Ь 1) дается при этом равенствами за(х) =- а(х) ЕЬ(х), зг(х) =хн '(а(х) — Ь(х)) (юоб хм+1). Мм хотим воспользоваться этой про~гедурой длн вычисления иомплексной циклической свертки з(х) =й(х)А(х) (шоб х" — 1), где л равно степени двойки.
Запишем х — ! .=(х — 1)(х-> !)(хз+ !Н'+ !) ... (х л.г-)). Тогда задача сводится к коротким циклическим свертиам вид 5! ~(х) = йг !(х)що (х) (вгоб хз + 1). Комплексные свертки по модулям х — 1 н х -г- 1 являются ска- лярамн, и нх произведена выч ляшс» как произведение «ам- плексвых чисел.
Их вклад в общую сложность очень ьгал Если остальные комплексные свергни вычислять через две веществен- ные свертки, то рассматриваеммй способ вычисления комплексной свертки потребует примерно вдвое больше вычислений, чеь~ «еще- ственная сасртка той же длины. Этот метод кониурнрует с методом разложения многочлена х" — 1 в поле комплексных чисел: х — 1 = (х — !)(я+1)(х — ))(х.г;)) ... (хгг — ))(хгг ф)). Каждая из инлииндуальиых подзадач теперь меньше, но арифме- тика является комплексной. 3.8. Сложность алгоритмов свертки Пусть задан алгоритм решения некоторой задачи; следует лн этим удовлетвориться или следуЕт попмтаться найти лучший алгоритм! На этот вопрос трудно ответить по нескольким аричннзм Во-первых, трудно выбрать критерий, согласно которому е ли можно утверждать, что а,тгарнтм.является наилучшим Д с даже такой критерий выбран, то трудно угвергкдать, что характеристики оптимального алгоритма соответствуют выбранному критерию.
Во м логик задачах критерием оптимальности служит минимизация числа умножений. Этот ирнтерий достаточно прост, так что удается показать некоторые теоремы, описывающие характеристики оптимального алгоритма. Конечно, после отыскания оптимального алгоритма может оказжьсн, что он нам не подойдет, 1!4 1'х 3 Высюм Г ««ер хе р З.З С. а«газ«ш ртк« ыб скажем, по числу сложений, но все-таки хочетсз знать. что предстазлзет собой такой алгоритм.
В данном разделе мы будем исследовать характеристики оптимального (в смысле минимального числа умножений) алгоритма свертки. Для этого надо уточнить понятие умножения, и мы сделаем зто таи, чтобы можно было ответить на интересуюшие иас вапросм. А именно,мы хотим определять умножение таким специальным образом, чтобы под произведением б б понималось произведение произволюгых веществеавых чисел, но туда бы ие входило произведение 22, так как его можно интерирегиравать как й Ь Е. Такое различие легио принять, но как быть с произведением 33 или (5)7) Е? Мы выберем опрсделевие, которое приводит к полезным результатам Вычисление б Е будем считать умножением только тогда, когда оба сомно'кителя.принимают произвольные вещественные значении, и не будем считать умножением, если произвольные вещественные зяачения допустимы талька для адяого из них, а другой должен быть рациоиальныы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
