Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 38
Текст из файла (страница 38)
Выполнять вычисления надо следующим образом. Сначала наждый столбец двумерной таблицы уыножэется на матрицу А'. Затеч начинается вычисление нраизведенкй мнагочленов. Этот процесс начинается умножением каждой строки двумерной таб. лици на матрицу АЦ Затем каждая строка пакамоояентно умно. жается на вектор констант, твк чта и вся двумерназ таблица умножается пакомпонентно и» таблицу «онстант. Умножение мнагочленов завершается умножением каждого столбца на ма.
трипу С', а затем каждой строки на матрицу С'. М (8) =- 14, А (В) = 46 или М (8) = !2, А (В) =- 72. Может показаться, что алгоритн В.точечной циклической свертки с 14 умножениями лучше, так как ан содержит всего нз два умно. жения больше, во зато на 26 сложений меньше Оливка вхлюче ние ша в алгоритм 50фточечнай свертки прявадит к удивитель.
ным результатам: М (504) = 4256, А (504) .=- 28 240 ззг где я = ССАб. ч г' охг о -г и. 0 и С Где ЗЗО Г» 7 Ни а е ы р мс в ие сырт Эта последовательность вычислений может быть аредставлена в более иомвактном виде, если собрать воедино два алгоритма циклических сверток. Запишем входную двумерную таблицу в виде стека по столбцам, представив ее однаиерным входным массивом Аналогично запишем и выходную двумерную таблицу, вытянув ее в выходной одномерный массив. Тогда алгоритм примет вид з = ЯС х С') (6' х 6") (А' х А")) б.
Аналогично, можно выходную двумерную таблицу записывать в виде одномерного массива, считывая ее по строкам Тогда алто. ритм запишется даже в более симметричной форме з .—. ЯС' х С ) (6' и 6") (А' х А")) б, где компоненты вектора з выписаны в другом порядке, хотя и остаются неизменными В любом из случаев, вводя очевидные обозначения для матриц, можно записать Есть егце одна последнии деталь, о которой надо позаботиться: компоненты векторов з и б выписаны не в своем есмттвениом парпдке. Сначала они выписывались в двумерную матрицу вдоль главной диагонали, а вате» в виде стека столбцов (или строк). Для тогщ чтобы периуть «омповеиты на их естественное место, надо переставить столбцы матрицы А и строки матрицы С.
В качестве примера построим алгоритм 12-точечной цнкличе. ской свертки Воспользуемся следующим З.точечным алгоритмом циклической свертки: о -Рог — — о. '~ з о ~ — п)~ ог,е оц~ ~ т Гп. А р Аарызз — Кт а аыиа р и следующим алгоритмом 4.точечной циклической свертки Сначала вывишем 12 коэффициентов фильтра в виде двумерной (Зх 4).таблицы, располагая их вдоль главной диагонали, и вытя. гиааз затем ик в стек по столбаам; Тогда диагональная (20х20)-матрипа 6 в терминах кронекеров- ского произведение записывается равен«твои 232 Г т.
Бнстр лют юп рзю р т 3. Аэ Гн н Э Ту же самую конструнцию надо применить к (2 компонентам входного вентара данных; выпишем «ронекеравскую матрицу А' х А" полностью. т Наконец, перестаиовна столбцов дает Эта полностью определяет вычисление О = Ад. Аналогичные рассуждении приводят к построению матрицы С, и, в итоге, к стандартной матричной форме 3 = СОАд алгоритма вычисления (2.точечной циклической свертки. В ганой форме алгоритма все операции перестановки «омповент скрыты в матрицах предсложеннй и пастслажений. 7.2. Алгоритмы разложения Мы уже видели, нак гнездовой метод позволяет преобразовать алгоритм одномерной свертки в многомерные алгоритмы.
)(лз вычисления 3 (», у) =: д (х, у) д (х, у) (шод х"' — !) (глод у — !) мы объединяли алгоритмы для вычислений э (х) = д (х) д (х) (шад хж — !) и 3 (у) = д (у) д (у) (шад уж — !). В более обшей формулировке, для нестроевик алгоритма вычис. лева» 3 (х, у) = д (х, у) д (х, у) (шод р (х)) (пюд р (д)), где р (х) и ц (у) представляют собой мвогачлены степеней и' и н' соответственно, мы комбинировали загоритмы длн решения двух простых одномерных задач э(х) =-д(х) д(х) (пгад р (х)) н 5(д) =у(д) д(д) (мод 3(д)). Если каждый ив подалгарнтмов содержит соответственно М (и') н М (л') умножений, то полученный такам методам алгоритм решена» двумерной задачи содержит М (л') М (л") умножений. Используемый вдоль «аждого из направленай индивидуальный одномерный алгоритм был построен на основании китайской теоремы об остатках.
Это открывает еше одно направление воя ножных исследований. Можно попытаться использовать китайскую теорему об остатках дая разбиения двумерной задачи не подзадачи вычисления двумерных сверток меньших размеров. Н едполажим, чта р(х) = р' '(х) ра'(х), где мвагачлены р<зг(х) и рп>(х) взаимно просты. Вычисление произведения многочленов 3 (х, у) = у(х,у) д(х, д) (шод р (х)) (шадд(у)) можно разбить нз вычисления произведений зш' (х, у) =- д' ' (х, у) д' ! (х, у) (шад рш (х)) (шод д (уй и 3'"(х, у)=д!п(х, у)д!п(х, д) (пюдрг'г(х)) (шаде(у)). Кятайская теорема аб остатках позволяет восстановить пронзав. денис из этих фрагментов.
Если д(у) = дм'(у) д'и (у), то можно произнести факторизацию и по переменной у. Обе зтн возмож. насти позволяют разбить задачу на следующие фрагменты: Р'е'(х. у) =до'м(х у)д(аэ'(» у) (ягод р™(х)) (шоддн)(у)) Рлг(х, у) = дг лг(х, д)долг(х, д) (пюдрэ' (х)) (шоддпг(д)), Юз 7.7.Всю рити ии ю рв сэзр 7здрчив (х У) .У ''(», У)ба"(х, У) (тобРа'(х))(щоб 153(у)) У) У (»' У)б ' (х У) (тобрг 3(х)) (той уаг(у)) где уи" ( у) =у(х, у) ( .бр"(,)) (,буш(у)), и остальные мяогочлеиы определяются аналогично. Выходной многачлен з (х, у) можно восстановить по этим фрагментам, дважды применяя иитайскую теорему об остатках для многа.
членов. Пусть М, и Мг обозначают число умножений, необходимых для вычисления произведения миогочленов по модулю ргэг(х) 513 н р (х) соответственно, а Мэ н Мг — числа умножений, необходимых для вы«ислення произведении многочленов по модулю уаг(у) и угп (у) соответственно. тогда прямой метод вычисления произведения з (х, у] = у (х, у) б (х, у) (тоб р (х)) (тоб 4 (у)) требует М = (Мэ -г- Мг) (Мэ 1- Мг) умножений, а описанное использование китайской теоремы об остатках на двумерных фрагментах М =- МаМе г- МЗМ1 -1- М1Мз г МЗМ1 умножений, так чта число умножений ие уменьшается. Хотя описанный метод и не приводит к улучшениям по числу неабходимык умножений, он полезен в там отношении, что расширяет возможности рззбиення задачи на подзадачи и уменьшает число сложений. Имеется многа способов разбиения задачи вычисления лву.
мерной свертки с помощью китайской теоремы об остатках. На рис. 7 5 привеленм примеры характеристик, «аторые могут быть получены путем модифнкааии алгоритма Агарвала †' Кули с по. мощью описанных разбиений. Данные на рис. 7.5 следует сравнить с приведенными на рис 7 4 характеристиками. В качестве примере опишем построение алгорвтма 20.точечной циклической свертки. Сначала преобразуем свертку в двумерную (4 х 5).свертку з (х, у) = у (х, у) б (х, у) (пгоб х' — 1) (таб у' — 1). Разложим теперь зют алгоритм на двумерные фрагменты в виде 3' (к. У) .—.
у (х. У)б' (х, у) (той к — 1) (тобу — 1), 5 (х, у) =-у (к, у)бг '(х, у) (табх — 1) (глоду -1-у -1- дуб у+!) Дальнейшею разложении на двумерные фрагменты лелать не будем, а применим к вычислению этг (к, у) гнездовой алгоритм вычисления произведения многочленав по модулю х' — 1, напалм и м ог 2 322 гы М5* Пгэ гт 2 25М 1ММ ю гю 2М гю ам Р 7Э Х Гээтэ РЗКК. эуя для свертки многачлевов произведения по модулю у — 1, 3 для вмчислеиия У'3(х, у) — гнездовой алгоритм, основанный иа свертке миагочленов по мапулю х' — 1, вложив в нега умно. жение мпагочлеиов по модулю у' -г- у' -1- у' -1- у -1- 1.
Накоиед, произведение з(х, у) вы~велим по правилу з(х, у)=л'э'(у)553(х у]-1-а'3'(у)5'1'(х, у) (табуэ — 1), где огэг(у) и аг'3(у) вычисляются в соответствии с китайской теоремой об остаткак для миогочленав. Оии равны тем же многа. членам, кагорые должны использоваться для Ф ]у) и У (у) в одно. мерной задаче вычисления произведения мнагачленов по ма. дулю у' — 1. Как мы видим, вычисление разбит на те же палзадачн, что рассматривались и ранее, на сочетакпся они несковька иначе. Теперь мы пользуемся китайсиой теоремой об остатках после выполнения гнеэдавого алгоритма, перед которым была прове.
дена одна рслукпия миогочленов. Чтобы подсчитать числа неаб. хаднмых сложений, остановимся подробнее иа числе сложений, необходимом для выполнения 5.точечной пиклической свертки. Оно равно: умножение многа женое по модулю у — 1: 0 сложений, умножение мвогочлеиав па модулю у .1- уэ-г- уг-1- у-5- 1. 1б сложений, кнтайсиая теорема об остатках' 15 сложений.
и Иг ггг В2 га 5 55 га5 33 12М3 1М 3 25 мп гя 31' 1 и 13 гг 3 2 2 а 23 2 3 5 33 М 25 О 3 531 12М Я 5 2 ! Ог М 35 А Рэ Кгт -. и 2зт 74 и з ы выз 236 Гл.т.нь З юртн чн г Зк эр н Вычисления по модулю хг — 1 содержат 15 сложений Таким образом, перебирая все три составляющие, для полного числа сложений з рассматриваемом двумерном алгоритме получаем л (20) = (4.0 -1- 1 15) -1- (4 15 -1- 5.10) -1- (15 4) = 215, что меньше, чем 230 сложений, необходимых в чистом алгоритме Агарзала — Кули. Заметим, что метод разложения и гнездовой алгоритм не вызывают заметного усложнения организации вычислений Все изменения сводятся к повторным переходам от вычислений, связанных со сложениями по строкам, к вычислениям, связанным со сложениями по сталбдзм, и обратно.
Эта можно считать про. етым изменением последовательности обрагцений й вызываемым подпрограммам Чтабы иа осноаании китайской теоремы об остатках добиться дальнейшего уменьшении числа умножений, надо внести еще одну ипею надо подняться в таиае расширение поля, н котором задача начнет распадаться. Молгно допустить разложение многочлйна 4 (у) на взаимна простые множители, каэффицаенты которых зависят от неопределенной переменной х. (Говоря формально, можно рассмотреть разложение мгюгочлена д(у) в расширении поля, получаемом присоединением формальной переменной х ) Эта приведет к тому, что мнагочлен 4(у)может распасться иа миожи.
тели, степени которык меньше возникавших ранее в одномерных задачах степеней. Следовательно, могут быть построены алга. а ритмы с лучшими характеристниама Прн этом симвот х паявитс итси свертке по у, так что сама по себе свертка по у станавнтс» более сложной. Но прн переходе в алгоритм свертии по х возникающий прн разложении д (у) символ х может алгебранчески взвимодей. отказать с символом к в свертке по х, что упрощает двумерный алгоритм Поясним ндею на конкретном примере. Пусть надо вычислить двумерную циклическую свергну к(х, у) = у(х, у) б(х, у) (шобх' — 1) (жабу' — 1).
Разобьем задачу на две оодзадачи: згз~ (» у) = 5~4~ (х,у) Шз) (х, д) (аобу' — 1) (люб х' — 1) н з''(х, у) — д '(х, у)б (х, у) (жабу — 1) (юобхт-)-1). Р ешение первой подзадачи уже расснатрнвв.чось! 'алгоритм вы. численин мгой свертки содержит десять умножений, если его строить иа основании 4.точечного и 2.тачечнага алгоритмов пнклических сверток, солержаших 5 и 2 умножения соатаетстаенна. Если для решения второй подзадачи воспользоваться лучшими известными алгоритмами вычисления произведений по модулю уг — 1 и по модулю х' + 1 соотзетственно, требующими 15 умигь женнй, то получим в результате алгоритм, содержащий 25 умно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
