Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 16
Текст из файла (страница 16)
л — 1 нз которых обе вещественные последовательности вычисляются немедленна. 32. А юр Кую — тоою 33 34 Г . 3 Б тр о ахи ритин коро киэ гз рюк Используя описанную идею, процедуру нв рис. 3.1 можно заменить более эффективной процедурой одновременного вычисли ния двух вещественных свертан, представленной на рис.
3.2. 3.2. Алгоритм Кука — Тооыа Алгоритм Кука — Тоама является алгоритмом вычислеаия линейной свертки, который был разработан как метод умножения двух мвогочленов. Запишем линейную сиертку в виде произведе. ния двух многачленав з (х) — К (х) д (х), где дей и (х) .— — АГ -- 1 и дей К (х) = У. — 1. Степеогь многочлена 3 (х) равна АГ -1- 1.
— 2, так что этот ииогочлен однозначно апре. деляетс» своими значениями в Аг -( ь — 1 разтичных точках Пусть Рш Ро ..., О,н, — множество из Е -1- Ф вЂ” ! различных вещественных чисел. Ясли нам известны 4(й,) для А .— О, ..., )4 — А — 1, та з(х) можно вычислить по ннтерполяциониой фор. муае Лагранжа Согласно теореме 2.7.10, многочлен — Г( (* — бу) 5 (х) — — ~' 3 (04) П (Рг — РУ) г-а Г 4 является единственным многачленои стснеаи л — 1, принима- ющем значения з(рь) при х = Ро для всех й = О, ..., л — 1.
Идея алгоритма Кука — Тоома состоит в том, чтобы саачала вмчислить величины з (Оь) для й = О, ..., л — 1, а затем восполь- зоваться интерноляцией Лагршгжа Алгоритм Кука — Тоама приведен аа рис. 3.3. Умножения Лаются равенствами 3(04) 3(рь)д(рэ), А=.О, ..., СЯМ вЂ” 2, Всего имеется (. + Аà — 1 таких раееаств, тзк что здесь мы имеем ь -1- У вЂ” 1 умножений, и. если разумно выбирать точка Рь, то полное числа умножений будет исчерпываться этими уыножш ииячи.
Имеются еще и другие умножения, а именно те, которые входит в вычисление величин д (Рь) и й (Оь), к те. которые уча. ствуют в интерноляцноиной формуле Лагранхга. Но эти умноже. яия представляют собой умножейия на малые константы, и мы не буден нх учитывать при подсчете полного числа умножений '), хотя полностью их игнорировать нельзя. Р .
З.з. С ру ура оэгоретнэ Куно-тго *. Простейшим,.примером является линейная (2х2).свертка: д (х) = дгх .4 '3,, К (к) = дтх -1- Ко и з (х) = д (х) д (х) К та. кому внфлению сводижя прохождение двух отсчетов данных через К -фильтр с двумя отводами. Очевидный алгоритм выполнений таиого вычисления содержит четыре умножения и одно слоигение, но мы построим алгоритм с тремя умножениями, тремя сложениями.
Может показаться, что эта задача слишком мала для кзких.либо практических применений Но иа самом деле хорапгий алгоритм решения этой задачи является хорошвм бло. коч, из которого можно строить тщательно проработанные алга. ритмы. Таким образом, рассматриваемый пример представляет собой нечто большее, чем простую иллюстрацию алгоритма Кука — Тоомв; он важен практически '). В качестве первой попытки опишем алгоритм с тремя умно. жениями н пятью сложениями, а затем его улучшим. Так кзк '! и ро, ош ю то ш 0933! я Кую Ошм), шш б о о оое и (2х2)- оор яр .я уш ие о иро ' еж»ои щищо А Крауо !ДАН, !4309321,293,294), о люри о ои в зу шож г =див,г, - да„г = рй 1 д,) ( 3, -1- а), 4 = ! — 4, — 4„. - Про жрш.
Зз Г. 3. Б р Р Р" """ Р степень многочлена х (х) равна двум, то надо выбрать три тачки. Выберен их рваными Р,.-О, Р, = ! и Р, —.. — ! Тогда 6 (Р.) = дм й (Рэ) = а. ! (Р ) = 64 т 65 й (Вг) =- й. -! 64 6 (Рз) = 6 — 64 й (Рз) =- й — аг 4(РР) = 6(Р.) 6 (РР), з (Рг) = й ((35) ! (134), х (Рэ) — й (1)э) 6 (Рэ), так что требуются три умножения. Если КИС.фильтр задается фиксированным многачленом й (М, та константы й (Рь) не надо нзждый раз вычислять заново; нх можно вычислить заранее адии раз и запомнить. Коэффициенты нногачлеиа й (к) в запоминании ие нуждаются.
Наконеп, согласно интерпаляцнонной формуле ЛагРанжа з (к) = к (Ре) Е, (к) -1- з (Рг) Сг (к) -, 'з (Рз) 44 (х), где интерполядвонные многочлены равны ! „(х) — — х' -1- 1, !., (Х) = (И2) (хз ш к). тн (х) — (312) (х' — «). Это завершает описание алгоритма Кука — роома для вычисле. иия э(х!. Но вычисления можно организовать в более компактной форме. Леленин на 2 можно «похоронить» так, чтобм они не были видны. для этого просто заменим константы й (Рь) ноныыи, по- глогцающимк этот делитель. Пусть Сэ = й С вЂ” (!12) (йэ 1 й) С* (!12) (йэ — йд Так иак в большинстве случаев миогочлен й (х) фиксирован. то эти константы можно вычислить заранее, и ничто ие мешает нам определить их таким образам. Тогда ьэ (х) = — ьк '", 1, !.1 (х) ° к 1- к, ьэ (х) = кз — х.
Построенный алгоритм показан нз рнс. 3.4, а и в компактной форме может быть записан в магри'гно-векторггых обозначениих в виде з =- С ВВ21-(Абй, где точкой обозначено покомпанентное умаоженве векторов Вй и Аб Матричная запись дает удобную форму обозрения алто. ритма, но вычисления, конечно, проводятся не посредством умножения матриц Умножение на матрицы А и С выполняется как серия сложевий Возможная последовательность вычислений показана на рис. 3 4, Ь. ~:И 1'1 Ь~П,-Х О, =,Г, - 4, л 5 . О,п, 5, О,п.
З„з ~~ ъ,,1,1 ) Р«Э.4 Ашер т Кркэ — т и эн е «зч сй й Р З.эш Р" Алгоритм Куку †' Тоома можно рассматривать как факторизацию матрицы.Я рассматриваемом примере свертка может быть записан» в ни~6 ИНР 1:1(:) или, нратко, и — -- Тб. Р!а рис. 3.4с алгоритм Куке — Тоома для этой свертки переписан с иснользованнем диагональной ма.
трнцы, таиже обозначенной С н содержащей элементы вектора С. Алгоритм теперь имеет форму з —. ССА6, что позволяет интерпретировать его как факториэаш5ю матриши Т = ССА, где А — матрипа предсложеннй, С есть матрица постсложений, а С вЂ” диагональная матрица, ответственная за все умножения. Число умножений равно размерности матрицы С. Такое прелставление алгоритма очень полезно длн обозрения его структуры. 33 Гк 3. Вис р е кгорктнн карша х р ек 3.2. Амари Кук — Та а В общем случае линейная свертка может быть выражена в виде л = Тб, где б — входвой вектор длины А', з — выходной еентор длины У -)- С вЂ” 1 и Т предстзвляет собой ((У -1- ). — 1) х У).матрицу, элементами которой являются компоненты вектора й.
Алгоритм Кука — Таама в такой форме представляет собой алгоритм факторизации катрины Т = ССА, где б — диагональная матрица, а матрицы А н С сопержат толька малые целые числа. Алгоритм Кунз — Таама можно модифицировать и другому варианту, содержащему та же число умножений, на меньшее число сложений Заметим, что з,, =- йл лбн л. Для вычнсле.
нин этого коэффициента угеобходйыо одно умножение. Степень модифицнровзииого мнагочлена з(х) — а„„,клен-г —.. 3(х) б(х) — з„„ыхлтн-г ранна 1. †, У вЂ” 3, так что использующее идеи алгоритма Кука— Таама вычисление этого мвогочлеиа требует С -)- У вЂ” 2 умножений.
Общее число умножений опять равна С -г У вЂ” 1, иа сложе. вий теперь будет меньше Рассмотрим пощдение этой модификации алгоритма Кука— Таама при вычислении линейной (2х2)-свертки. Выберем 3, =- О н )), = — 1. Тогда б (Р ) — 1, й (Р 1 .= й б (Ол) = б — аы й (3 ) =. йл — й н 1(3н) = й (Ве) б (Вф — й б Ой 1(3,) =-3(3,) 3(3,) -йбЯ, где 1 (х) = 3 (х) б (х) — й,б,хй Согласна иитерполяциоиной фор.
муле Лагранжа, з (х) — р,,б,х' = 1(3л) 1., (х) -1- 1(3,) 1 (х), где С, (х) = х -1- 1 и Сл (х) =- — х. Объединение всех этих фрагментов дает искомый алгоритм ')1 к(к) = йлблх' .1- ( — (3, — бл) (йл — 11,) ф йлбл ф йы(,) к -1- й,д,. Алгоритм содержит три сложения и три умножения Его матрич. ння форма выписана нз рнс. 3.5, «отарый полезна сравнить с рис. 34. ') из ринам Э юр, аз юг р А К р нуа (лззх), зкаюр н рнс. 33. и у а рн Ку — т ы км аа 12х21.
р» н. Алгоритм Кука — Таама эффективен па числу умножений; но если объем задачи растет, то число необходимых сложений также начинает быстро расти. Это праисхолит потому, что хора. ший амбар чисел Вл в виде О, 1 и — 1 уже сделан, и с росталгэадачи мы должны использовать также л 2, 3 н другие малые целые числа. При этом матрицы А и С будут содержать зти числа. Кгл печно, умножения на иих можно заменять соответствующим числам сложений, иа зто резонно делать только в случае, когда выбираемые ислн нлы Г)оэтаму алгоритм Кука — Таама стннавятся слишком громазлок при вмчистеиии сверток, больших чем Зх4 или 4х4 Для бблыпвх задач надо пользоваться описываемыми в следующем разделе алгоритмами Виаоградз вычислю няя сверток или нтерировать малые алгоритмы Кука — Таама, используя изучаемые в гл.
7 гнездовые методы. Имеешься еще адик подход к пониманию алгоритма Кука— Тааиа, и эта альтернатива перекидмвает мссгин к следующему з,э Р . 3.3. Дру ансщ ор ща Кука — Т м. 9! 90 Гл. 3 ам рме лт р м иор *«тр 33 Ллг а В о«р д и и.чит тратя«х з ртея разделу Вместо тато чтобы выбирать множества различных чисел (Рл, Ол,, Р„,л,), выберем множества многочленов (х — Ом х — Рл... х — Ос+и-л!.
Тогда можно, как на рис. 3.6, записать й(Рь) =))„л„(й(х)), й(Р ) = К„а„(б(»Д. Зто просто несколько более сложный способ сктать та же, что говорилось и раньше. Преииувгество, реализуемое в следующем разделе, состоит в замене многочленав первой степени миагочле. нами более высоких степеней, что увелнчввает конструктивные «озможностн.
С этой более изощренной точки зрения интерполяционную формулу Лагранжа можно рассматривать как некоторую форму обращения питай«кой теоремы аб остатках для того частного случая, когда в качестве многочленов-модулей вибравы только многочлени первой степени. В более об~ллем случае иитерполяпианную формулу Лагранжа приходится отвергнуть, отдавая преимущество китайской теореме об остагиах. З.З. Алгоритмы Винограда вычисления коротких сверток Предположям, что требуется вычислить 3 (х) = й (х) б (х) (шоб т (х)), где т (х) — фиксированный моогочлсн степени и над полем Р, а й(х) и ц (х) — многочлеиы над этим же полем, прияем ах степени меньше л. Задача вмчисления линейной свертки 3 (х) = й (х) б (х) мажет быть вложена в зту задачу, если в качестве л выбрать целое число, большее степени мнагочлена 3 (х), а в качестве т (х)— произвольный многочлен этой степени л. Тогда аздача а (х) —.
й (х) б (т) (пюб т (х]) становится тривиальной перефармулиравкой задачи вин»слепня линейной свертюг, так как привелелне па модулю т (х) нг меняет 3 (х), коль скоро степень т (х) больше степени э(х). Зто позволяет включить задачу о линейной свертке н общую задачу, рассматриваемую в паннам разделе. Выбирая т (х) равнмм х" — 1, мы л включаем сюда тякже задачу вычисления циклической свертки, 3 (х) =а(х) б(х) (шоб х" — 1). Ми хотим заменить задачу вычисления 5 (х) = й (х) б (х) (шаб т (х)) некоторым множеством задал с меньшим числолг вычислений. Чтобы разбить задачу на подзадачи, разложим многочлен гп (х) иа взаимно просгме над некоторым падполем паля Р многачлены: т(х) = т"л(х)т(г)(х) ... тщ — и (х). Обычно если Р— поле веществевных или кампленсных чисел, то и качестве подпола разложении выбирается поле рацианальнмх чисел, и ыы будем ссылаться на такой выбор, хат» теории допусиает н другие нодполя.(Если свертка вычисляетсв в конечном поле ОР (р"), то в качестве подпали разложения обычно выбираетсн простое па»ноле ОР (РЦ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
