Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 39
Текст из файла (страница 39)
жений, — тот же результат, который получится, если использо. вать па обоим измерениям алгоритм 4.точечной циклической свертке. Вместо этога рассмотрим разложение у' — 1 = (у — 1) (у -1- 1) (у — х) (у -!. к) (шоб к' -1- 1). Такая запись осмысленна, поскольку по модулю х' 4 1 выпал. няется равенство хэ = — 1. Теперь можно построить алгоритм эычясления по модулю у' — 1 с четырьмя умножениями. Каждое из умножений предстакляет собой умножение многочленаз ат к первой степени по модулю х' + 1.
На умножения ыногочленоя первой степени в любам случае входят в алгоритм. Используя разложение у' -1- 1 =- (у — х)(у + х), мы как бы частично умень. шаем аависимость по д, переноси ее в зависимость по к и перекладывая часть работы в вычисления цо х, которые приходится выполнять в любам случае, Этот путь позволяет вычислить Вн (х, у) эа 12 умножений, так чта исходный алгоритм иикличесиой (4 к 4).свертки будет содержать 22 умножения. Идею можно продолжить дальше, авода еще больше формаль.
эых переменных в качестве корней много'глена у" Э 1. В пределе этот яшах приезды к вычислению прюбразования Фурье в поле разложения этого чнагочлена, записанном н полиномнальном представлении. Мы сейчас оставим эту тему, но встретимся с ней в измененном виде позже в раэд. 7.5 прн рассмотрении полино. мнальных представлений полей расширения. 7.4.
Итеративные алгоритмы Итеративнме метадм построения алгоритмов свертки базируются на том, что малые алгоритмы свертки, независимо от того, в каком именно поле Р онн были построены, иа самом деле преть ставляют собой некоторые тождества, справедливые в любам со. лержащем поле у кольце. Окончательный алгоритм не предпола.
гает коммутатнвности унноженн» н не содержит делений, за исключением деления на некоторые малые константы. В качестве операций над входными иеременнымн допускаются только ело. женил, вычитания и умаожения Сначала рассмотрим линейную одномерную 4.то«ечную свертку а(х) = д (х) д (х), где степень многочленов д (х) и д (к) равна трем Расставим скобки по правилу: д (х) = (д х + д ) х 4 (дгх 4 дэ) б (х) = (б,х -1 б,) х* -1- (б,х -1- 4,). 232 Гг 7 В ср эаюр и о ер э~и 232 74 И ерыве и р» Определим следующие многочлены ат двух перемениыхг й (9, г) = (949 ф 8,) г -)- (йлр ф 8,), 8 (у, г) =.
(Игэ .~- бг) г -1- (Длу -1- 8,), г (9, г) .= д (у, г) й (р, г). Тогда искомая свертка получается иэ многочлена г(р, г) по пра. зилу э (х) = з (х, «'). В сокращенной форме эти вычисления могут быть записаны ра. венством г,(р) г* + э,(у) г -1- г,(р) = (й,(у) г -4- 9,(р)) (бл(а) г -1- дт(у)), в ктором асе ноэффнциенты предсювлнют собой миагачлены ст р первой степени. ' Алгоритм 2.точечной линейной свертки записывается в виде о г, а"! '4.) г 'г .о о 1~ г с Зти тоншества справедливы лаже тогда, когда входные перемен. ные являются элементамн кольца многочленав. Соответственно :(г! = -~ ~ 11 гам г(~ и ~ г(!) чай, с а Ч, гчо с Здесь нмеются тра умножения мнагачленов н три сложения много. членов, исключая сложения, относящиеся к «оэффнпнентам мно.
гочлена д (х). Каждое произведение многочленов само ивляется 2.точечной лимейнай сверткой и, следовательно, требует три умножения и три слаженна. Таким образам, полное числа умно. женнй в итеративном алгоритме 4.точечной линейной свергни равно 9, тогда кзк оптимальный алгоритм содержит талька семь умножений. Преимущество ишративнога алгоритма состоит в уменьшении числа сложений: исключая сложения, касающиеся коэффициентов многочлена й (х), он содержит всего 15 сложений. Полученный алгоритм 4.точечной свертки можно итернровать опять и построить алгоритм 16-точечной свертки, содержащий 81 умножение и 195 сложений (5.06 умножений и 12 19 сложений на одну компоненту на выходе).
Этот алгоритм можно в свою оче. редь итернровать опять длн построения 256-точечной свертки алгоритма с 6561 умножениями и 18 915 сложениями (25.68 умно. жений н 75.89 слоткений нз одну компоненту на выходе). В общем случае для вычислеяня з (х) = 8 (х) 8 (х) ыожна на пользовать итерацию, если число коэффициентов многочлена 8 (к) и числа коэффициентов мнагочлена б (х) имеют общий делитель. Пуст дедА(х) = ММ вЂ” 1 и бейб(х) = М).— !. Преобразуем миогачлен б (х) в многачлен от двух неремениых 8 (р. г). полагая э — г м — ~ 8(Р, г) = 2~ ~ ~',длгг,ьу')г', 4=4 4 =е где старый индекс 1 связав с парой (й, !) новых индексов равен.
ствам ! — М)+ й, 1 —. О,, У вЂ” 1, )г = О,, М -- 1 Аиа. лщячна, многоччен й (х) также преобраауем в многочлен сч двух пейеменных 9 (у, г), полагая г — \ я-г 9(у, г) = Х ~ Х. ймг!.48') г', где 1=4И1фй, 1=0, ..., Š— 1 и 2=0, ..., М вЂ” ! Вы. числим произведение г (р, г) =. 9 (р, г) 8 (у, г) Тогда я (х) можно вычислить согласно равенству л (х) = г (к, х" ), для чего требуются только сложения Зтот двуыерный алгоритм свертки основан на алгоритме линейной свертки последователь.
настей длины 5 П Х н алгоритме М.точечной линейной свертки. Число необходимых умножений равно праиаведению чнсел необ. ходймых умножений в двух составляющих малых алгоритмах линейных свертан. Одни цз двух составлнюшнх алгоритмов может быть построен с помощью итерации В общем случае этот процесс можно исполь. зовагь любое числа раз.
Болю того, даже если числа каэффицяеи. тов многочленав 8 (х) и 8 (х) не имеют общего делителя, то это легка подправить, авеле в один из них члены с аулевымн каэф. фициентами, н воспользоваться нтерацаей. Итерацию можно испольэовать н для вычвслени» пронзав. денни г (х) 9 (х) 8 (х) (щоб ш (х)), Простейший способ состоит в вычислении линейной свертки с по.
следуюшггы привелением па модулю многочлена ж (х) Но обычно удается побиться лучшего, если усложнить процедуру. 3(ы рассмотрпм только слугай, когда ш (х) равна х" -1- 1, причем я представлает собой некоторую степень двойки. Зта важный случай, так «ак х- — ! =-(х" — !)(х -1- !), так чта произведение многочленов па модулю л -';- ! возникает и тогда, когда нала вычислить 2паочечаую циклическую свертку, аэиравсь иа китайскую теорему об остатках. Э40 Гх ? Б рм' л ?р не э 241 ? 4. М Э *лгаэн Т(л» вычисления з (х) .—.
у (х) Д (х) (пюб х' 1- 1) — 1 заменим ыногочлен У(х) = 2,' Фхг ат одной переменной много. 4=4 членом от двух переменных, полагая л =. л'п2 б(у, г) =- ~ ~ Агчмг-упг?2 ?.-а г=э Исходный многачлен получается нз этого многочлена подстановкой у =. х и г = х"Т Аналогична определиы у (у, г) и положим з (у, г) = у (у, г) д (у, г) (шоб г ' ' 1). Искоыый многочлен з(х) получается из этого многачлена по правилу 4(х) =- з(х, х"') (шайх' с !), не требующему никаннх умножений Следовательно, наша задача свелась к вычислению многа?лена г (у, г).
Рассмотрим линейную свертку з (у) — у(у) б (у), в яатдрой коэффициенты ынагочлевов 4 (у), у (у) в б (у) в свою очередь пред. ставлпюг собой многочлены от г и умножение этих многочленов ат г понимается как умножение по модулю г" ф 1 Возможно, эту процедуру легче понять, если выбрать л = 2 и заменить г на ). Тогда проделанный шаг обозначает замену про. изведения вещественных многочаеиов па модуаю х" 1 нроизведением комплексных многочленав по модулю х™ й 1. Преимущество, даваемое таким шагам, состоит в воэможности прнменени» алгоритма Кука †Таа с карпами в точках -1-).
В общем случае можно г понимать как парень степеви и" из — 1. Воспользуемся алгоритмом Кука †Таа, допуская в качестве екарверл степени формальной переиенной г. (Формальное утвер. ждевие состоит н том, что ыы выбираем корин в расширении полн, получаемом присоединением г.) Тогда при приведении по мад лю у у — г' коэффициенты многочленов у (у) и б (у) становятся много. членами от г Так ках они уже являются многочленамн от г, то вроделанный шаг не приводит к накаму бы та ни была усложн« нию, если пазабститьсн о там. чтобы степень этих многочленов от г не начинала превышать свою первоначальную границу.
Эта приводит к некоторому неравенству, связывающему делители л' и л числа л. Алгоритм Кука †Таа можно использовать для вычисления линейной свертки, если коран выбранного многочлева распоп р ° а жены в точках шг при 1 меньпшх л". Степень нногочлека л?(у) = у(у — «) П (у — г4)(у-г г4) 4-4 равна 2л' !. 2, так что его можно испольэовать для вычисления свертки з(у) степени не более 2л" ф 1. Если степень мнагочлена з (у) меньше, то часть множителей можно из т (у) отбросить.
Мы будем пользоватьсн многачленам т (у), удовлетворяющим условию бей т (у) =- бей 4(у) -4- ! = 2п' — 1. Так как все входящие в т (у) множители являются многочле нами первой степени, то для вычислении каждого иэ коэффи. цнентав многочлева з (у) треб)ется талька одно умножение, кото. рае, конечна, представляет собой умножение многочленов ат г по модулю г"'.
1 Итеративный алгоритм првменим, егли 2л' — 1 ( 2л" -4- 1. Если эта условие выполнено, то вычисление произведения мяагочленов по модулю х" -. '1 разбивается на вмчисления 2л' — 1 произведений мнагочленов по мадуаю х"' -1- !. В свою очередь, это произведение повторением описанной вропедуры может быть разбита на еще более мелкие подзадачи так, как зто показано на рис. 7.6.(На диаграмме выпущены детали, связанные с крн. терием выбора разложения л'и" = и и с об?цимн правилами предсложений и постсложений.) Число необхалимых в алгоритме умножений н сложений описывается рекуррентными равенствами М (п) = (2л' — 1) М (л"), А (л) = (2п' — 1) А (л") —, А, (и) ф А, (л), где А, (л) обозначает числа предсложевий, связанных с приведе.
пнем б (у) па модулю множителей маогачленз т (у), а А, (л) обо. значает число сложений, необходимых для восстановления много. члена з(у) пп ега вычетам Истинные значения величин А,(л) и А,(л) эаиисят от выбора 2п — 1 множителей разложения многочлена гл (у). Например, вычисление произведения миоючленов по модулю х' -(- 1 можно свести к вычислению трех произведений мне«тле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
