Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 37
Текст из файла (страница 37)
Таким образам, юа яолучаеы способ вычисления днумерной свертки, состоящий во включении одного быстрого алгоритма одномерной свертки в другой быстрый алгоритм одномерной свертки. Все сказанное здесь относительно линейной свертки, конечно, Относится и к циклической свертке и к вычислению произведения мвогачленов по модулю мвогочлена ю (х). Например, для вычисления лвумерной циклической (4х4). свертки воспользуемся алюритмом 4-точечной циклической сверг.
кн в виде, представленном на рис. 3.14: а == С ((Вй) (Аб)1. Этот алгоритм содержит пять умножений и 15 сложений. Счедова тельна, применение его для гшклической свертки многочленов потребует пяти умножений многочленов и \Б сложений много. членов. Каждое умножение мноючленов само является сверткой, б п , следовател по, для ег вычисл ния по этому алгоритму пот уется ять вещественных умножений н 15 вещественнык схоже. ннй. Таким образом, для вычисления двумерной циклической (4 к 4).свертки потребуется в данном алгоритме 25 вещественных тьшажений и 135 вещественных сложений. Эта процедура пред. ставленз на рис.
7.1 для вычисления циклической (я'хл ).свергни. Как показано на рисунке, подпрограмма должна знать индекс й' н иметь доступ к заранее вычисленной таблице ба з-. Используя последовательные операции иал двумерными таб. лгщамп, этот составной алгоритм можно представип, в виде еди. ного алгоритма. Сначала умиажим строну таблицы д на ма. трицу А", а каждую строку таблицы й ва ыатрицу В .
Затем умно. жич каждый столбец первой новей' таблицы на А' и каждый столбец второй новой таблицы на ВС Это даст нам две таблицы рак мера М (л') хМ (н"). Перемножим покомпонентно эти таблицы, Полученную таким образом (М (я) ЯМ (я))таблицу преобраз) ем к нужной выходной таблице з размера я* хо, умножив сначада каждый ее столбец ва СС а затем каждую строку полученной таблицм на СС На ркс. 7.2 для сравнения выписаны зта пропедура и пйа. педура, основанная на деуыернои преобразовааии Фурье н теореме ня о свертке.
Ясна, что рассматриваемая пропед)ра является обоб .еч процедуры, основанной иа двумернОм преобразовании азч Ф!рье Теперь «преобразование» состоит только из сложений, р: ~ер промежуточной таблицы равен не л'хлС а м (я')х ', но яд( (я'). Гнездоной алгоритм является более ощцим и в другом апю.
щыгия: ои позволяет вычислять двуиерное произведение много. Вгод г ро б азфф цге мг гол а ж*) = о,( ) мою еое щ*) Вход г гнезд гон алголою огермгг В ор до Влад г двумерную игдццу га юмюд одиаомг Вюод В)мод М (7) = 18, А (7) = 70. М (9) = 19, А (9) =. 74. 224 Гл. 7. Бнстрне аггорюнн н мгф) р»не р Вмюд Рг. 7Д. Дзюр и де)мери а ц г с а р « . членов по модулю любых ыногочленов ю' (з) и гп" (р), а метод, основанный на преобразовании Фурье, позволяет вычислять произведеяве только по модулю х"' — 1 и у' — 1. Характеристики гнездового алгоритма задаются числам М (Мм Х и") неабкодиммк умно кевнй и числам А (ц' х и") необходимых сложений. Легко видеть, что полное число умножений равно М (л' ил') =- М (л') М (о'). Диалогично, ив рнс.
7.1 легко увидеть, что А (л' хи") =- л'А (и") — М (л") А (и'). Полное числа умножений не зависит от тога, какой из делите. лей назван л', а какой л" Но число сложений аависит от такого выбора, и поэтому необходимо просматривать оба варианта. На- СЕ о( д '-0 сегрю лжи з( м'(*В (мф( у — )] (емб ( ги пример, дв)черную циклическую (7к9)свертку можно вычислять с помощью одномерных алгорятмаз с характеристиками Полное число умножений прн этом равно 304. а полное число сложений равно 1848 илн 1814 в зависимости от тога, чему выбрзно равным л'. Вв гз Р Ыа Г.
т Бытр«аэр н н ны р р« 7.2. Алгоритм Агарвала — Кули вычисления свертки Алгоритм Агарвала--Кули представляет собой метод преоб. разования л'пдтсчечной одномерной циклической свертки в дву- мерную циклическую (л' Хл")-свертку при условии, что числа л' и л" взаимно просты. Его можно использовать для того, чтобы скомбинировать алгоритм Винограда вычисления лпточечной цик- лической свергни, содержащий М (л') умножений, с алгорнтмом Виноградз вычисления ндточечнсй цинлической снерткя, содер- жащим М (л") умножений, и построить алгоритм вычисленяя л'лйтачечнсй циклической свертки, содержащий М (л')М (л") Умножений, В основе алгоритма Агарвала — Кули преобразования одно.
мерной циклической свертки в многомерную циклическую свертку лежит китайсная теорема об остатках лля целых чисел. Згим влго. ритм отличается ст алгоритма Вннограла, в котором исполь- зуется китайсиая теорема об осгатнах для мвогочленов. Он не обеспечивает столь сильного уменьшения числа умножений, как алгоритм Винограда вычислении свертки, на, с другой стороны, ан не имеет и тенденции к чрезмерному росту с ростом л чесли сложений, как в алгоритме Винограда. Кроме того, он лучше структурирован. Если л велико, та алгоритм Агарвала -Кули более управляем, так как мажет быть разбит на подпрограммы.
Для построения хороших алгоритмов свертки надо использовать алгоритм Агарвала †Ку разбиении длинной свертки на корот. кис циклические свертки, длн вычисления которых использовать затем эффективные алгоритмы Винограда вычисления корткнх циклических сверток Алгоритм Агарвалв — Кули строится на трех идеях. Сначала одномерная циклическая свертка с помощью китайский теоремм аб остатках (К. Т. О ) для целых чисел преобразуется в много.
мерную циклическую свертку; затем вдаль каждой координаты «спольэуется алгоритм Винограда вычнсленил короткой свертки; и, наконец, для сборки вместе полученных преобразований ис. пользуется теорема о кранекеровском произведении для матриц. Пусть заданы д, н й, для г = О, , л — 1, и иам надо по. строить коыпснеяты циклической свертка — г эг = Е М»г — »пМ »=» г = О, ..., н — 1, где двойные скобки в индексах обозначают вычисление по мо дулю л. Мы хотим преобразовать одномерную свертку в двумерную. Для этого воспользуемся «нтайской теоремой об остатках, поено.
Р ., т 3. И р мя юг Э т Агар — КГ а. л»нощей отобразить одномерный вектор вкодных данных в дву- мерную таблицу и выходную двумерную таблицу в одномерный вектор. Заменим ииденсы 1 и й парама инденсов (1', »') я (й', й") па правилу — (шод л'), »' = » (шод я'), й =й (шодл), й =й (птодл).
Занимаясь китайской теоремой сб остатках, мы уже вилелн, что старые инпексы восстанавливаются по новым согласна формуаам ! = Л'"н"»' — ' В'и'1 (шод и), »' = О, ..., и' — 1, г" = О, , л" — 1, А = Аг*л"А' -,'- Анп'й' (пюд л), й' = О, ..., л' — 1, й' †. О, ..., и" — 1, где целыс числа Аг' и Аг' определязжся равенством Аг'я' + Аг"л" = 1. Это то же самое соответствие между кампонентанн вентора н компонентами двумерной таблицы, которое было использовано в алто.
ритме Гуда †Томз. Описанное отображение иялюсгрнруется рис. 7.3. Све тк Р У зг = Е Мп — «пд» можно записать в виде ' †» ' †» »-зм з а 22З Га. 7. 93ютрме алгор н а и З ю рю10 Р с. 7.4. Хбрб юр 2 юг рати Аг р а — Кгэа э * сюртаа. Двойное суммирование ио й' я й эквивалентна одинарному суммированию по А, так как затрагивает одни и те же члены.
Оиреде. лим двумерные переменные, которые назовем также б, й и з, захава» их равенствами Або 3" би "1'-гл' ю й'=-О,..., л' — 1, й" =-О,, л' — 1, й' = О, ..., л' — 1, й" = О, ..., н" — 1, 2' = О, ..., л' — 1, й' = О, ..., л' — 1. 8», 3 = йэ"Ю1'5-л В новых переменных свертка записывается в анде ' — 1 ' — 1 а,, = ~ ~8555 бн,,п.,-нбмач 0'-02 -О где первые и вторые индексы вычисляются соответственно па ма. дулю л' и и". Теперь это двумеряая циклнческан свертна Тем не менее, мы пака не получили никакого уменьшения сложности вычислений. Для каждой пары индексов (1', 3 ) каждое число ббс 1. на что-то умножается, так что пока полное число умна. жеиий равно (л'л')К Для того, чтобы сделать алгоритм эффективным, нада восполь.
зоваться развнцяии в предыдущем разделе методами быстрого Ю 20 2 10 16 1 10 Ю гю гм гю .'0 гзи 12Ю ггм 56 532 гю 950 гю гбм 12Ю гзя 3мб ОЮ НО!2 ггш 2ибб Ю ПО 2 2 бн 20 50 2 О 5 0 гбоб 63 юао 21Ю ггм5 955 2 Ю96 2 2Ю гм 26 мбг 51 51 516 ЗЮ Ю 33 250 г ю 5В Ю 9 650 3 Ю ю абг Ь 13 609 562 61 Я 51 9 623 1Ю ОО 36 5Ю ню юю щв ы- ов 72 Х р З ар — Ктгч зн 0 Орган вычисления двумерной свертки. Алгоритм Агарвала — Кули в числения свертки состоит а переходе ат одномерных вектор н .двумерным таблицаы, в применении быстрых влгорнтмов дау.
мерной свертки и в обратном переходе от двумерной таблицы к одномерному выходному вектору. Характеристики л.точечнога алгоритма Агарвалз †Ку поды. тожены в таблице иа рис. 7.4. Полное числа сложений и умнаже. ний определяется гнездовым методом построения алгоритмов Лву. мерной циклической свертки из эффективных опномерпых алга. ритмов составляющих длин а' и л' по формулам А (л) .—.. л'А (л') -1- М (л') А (л'), М (и) = М (л') М (л"). Из этих формул видно, что число умножений в малых алие ритмах играет существенно более важную роль, чем число ело.
жений. Например, предположим, что алгоритм 504.точечной пик. лимеской свертки строится нз 7., 9. н В.точечных цинлических сверток с М (7) = 16, А (7) = 70, И (9) = !9, А (9) =- 74, или М (504) .— — 3648 А (504) = 26 ЗОЛ Таким образом, использование в 504-точечном алгоритме В.точеч. ного алгоритма с 12 умножениями приводит к уменьшению и числа умножений, и числа сложений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
