Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 52
Текст из файла (страница 52)
чнслеаия четырех точек на вмходе секции фильтра с четырьмн Эзч Гп Э. Ар тра бэ гроз н зр араэс э «З эщ отводамн (4.фильтр.секции). В матрнчном виде зто вычисление за- писывается равенством Разбивая это вычисление на блока размерности два на два, полу. чаем ~э) ~п, п~ (сч о. = ~ ' ~. и, = ! ' ~, н, = ! ' '-И а-Г! где ~1-~ -~~'-" ' 1"] з э гн,-н.з э) Как н ранее, сумма Оч -1- О, должна быть вычнсленв заранее н не влияет на оцемку чнсла необходимых в алгоритме операций Алгоритм содержит четыре матрнчных сложения и трн матрнчнык умножения.
Остановимся сначала на сложениях матриц. Дза нз ннх нмеюг внд Теперь эта задача имеет точно такай же вяд, как и предыдунтэя задача. Скалярные величины заменнлясь матрнцамн, но алгорнтм «вляется системой тождеств н остается справедливым н в данном ' случае. Имеем Здесь имеется пять различных сложений. (Позже мы увндкм, как одного из ннх можно избежать, так что останется только четыре сложения ) Еще здесь имеется два сложения 2.точечнмх векторов, выполняемык после завершения умножения; для нх выполнения требуется четыре вещественных сложения. Каждое нз матричных умножениИ имеет тот же вид, что н 2-фильтр-секцня, н, следовательно, может быть вычкслево с помощью трек умножений н четырех сложений, Таким образом, алгоритм 4.фильтр.
секции всего содержит девять умножений н 2! сложение. Еслн влюритм кфильтр.секция используется повюрно для одновременного вычисления четырех отсчетов на выходе каждый раз, то одно нз сложений пропадает, так нак ц, — дч в одном пакете равно бз — Д, в следующем пакете.
Процесс итерации носит вполне общий характер. Если л четно, то матраца алгорнтма п.фильтр-секция разбивается на четыре ((э(2) х (л(2)).блока. Используя теперь алгоритм 2. фнльтр-секция, постронм алгоритм л.фильтр.секцнн в анде трехкратного обращення к алгоритму (я)2).фильтр.секця». Прн этом числп дополнительных сложений, необхолнмых для зычнсления матрицы О, — Ом равна л — 1, а число дополннтельных сложц нкй, веобходнмык для вмчнслення матрнпы О, — От, равно л)2 Эта пронсхалнт потому, что все рассматриваемые матрицы яп ляктся теплицеаыми ((л(2) х (п(2)).матрицами. Для вычисления матрнпы О, — О, надо выполнить вычитания тольно в первой строке и левом столбце. Пекоторые нз полученных при этом велнчин повторяются в матрице О, — О„ та» что для вычислена» пс следней требуется только я(2 вычитаний. Если алгоритм ясполь.
зуется в режиме повторения, то некоторые нз ранее вычисленных величин повторяются, так что для вычисления каждой нз матриц О, — Оэ н О, — О, в каждом новом,оакете требуется только «(2 сложений. Еще л дополнательных сложений требуется в вы. хадном векторе Подводя итог, получаем, по если алгоритм (п)2)-филыр-секпин содержит М умножений н А сложений, то построенный опнсанным образом алгоритм и-фнльтр-сенник будет содержать ЗМ умноженнй н 2л -~- ЗА сложений.
Если п = 2, то эта процедура может быть пронтерирована; алгоратм 2 .фильтр.секция строятся нэ алгоритмов 2 †'.фильтр. секции, которые, в сваю очередь, строятся из алгоритмов 2 фильтр. секции и т. д. Числа умножений в таком алгоритме равно 3" = льээ', а число сложений описывается рекурсией А (л) = = 2л -г- ЗА (л(2) прн А (1) = б. Если л не равно степенн двух, то в качестве блоков построения можно использовать секцнн фильтров другнх длин. Альтернитивной возможностью является дополненне числа отводов фильтра ао степени двух с помощью нулевык отводов.
зы 99 С р с и стэиттр е йв. Рн 3!Э Г 9 аР * тРз ф«гьтР жогрзз Ягги т йт Пг' т г М- эт Рз ггч ггг ггг Я гр 87 ыг Ягггг и из ггг тг Я гэги Яг гш гы Рзс 9.9. М п рн р г !З- КИО-9. Ра. Если и достаточна ослика, то рассматриваемый алгоритм с лсзм умножениями становится хуже алгоритма, основанного на БПФ н сопержашего О (л !о2 л) умножений Значение л, для кота.
рого зто происходит, можно сдвинуть, если итеративный алгоритм па основанию двз заменить итеративным алгоритмам по основанию четыре, содержащим в своей начальной форме семь умножений. Тогда число умножений растет как 7 " = и' "'. Для лальнейшей иллюстрации богатства конструктивных воь мажнастей рассмотрим несколько алгоритмов вычисления 16 от.
счетов фильтра с 16 атводамн. Структура алгоритмов показава на рнс. 9.5. Алгоритм! Выходы фильтра вычисляются стандартным способам Алгоритм содержит 16х)6 —. 256 умвожеввй и )бх!5 = = 240 сложений. Алгоритм 2. Алгорнтм 2.фильтр. секции, в катаром для вы. числения выходов трех секций с 8 отводами используется любой подходящий алгоритм и 4м8 дополнительных сложений. Если выходы трех фильтров с 8 отводами вычисляются стандартным способом, то каждый из них требует Вх 8 = 64 умножений и Вх 7 = 56 сложений. В общей сложности получаем алгоритм с Зх64 = 192 умножениями и 32+ ЗХЫ = 200 сложеннямн.
Алгоритм 3. Алгоритм 2-фильтРсекцик используется для сведения к трем бфильтр-секциям, каждая из которых реализуется в виде 4 х 4 = 16 сложений и трехкратного использования 4. фильтр.секций Если кажаая 4.фильтр.секция реализуется став. дартным «лгаритмом фильтрации, содержащим 16 умножений и 12 сложений, то такай алгоритм 1б.фильтр. секции в общей слож.
настя содержит 32 ф Зх!6+ 9х12 = 188 сложений и 9х16 = == 144 умножения. Аггаргипм 4 получается из алгоритма 3 мсдификанией алга. ритмов иля 4.фильтр.секпий, в которой они заменены 4х2 =.- 8 дополнительными сложениями и трехкратным использованием алгоритма 2.фильтр-секшги. Таиим образам, этги алгорнтм 16. фильтр. секции содержит 32 + Зх!6 -Р ОкВ = 152 сложении и 27.иратнсе вычисление Ьфильтр.сеянии. Стандартный алгоритм 2.фильтр. секции содержит два умножения и четыре слажеяия, так чта в общей сложности получаем 152+ 27х2 = 206 сложи иий и 27К4 = 108 умножений. Алгоритм 5 получается итеративным использованием фильтр.секции на всек этапах; такой алгоритм содержит 260 ело.
жений и 81 умножение. Нельзя сказать, какой из этих алгоритмов предпочтительнее других. Только детальный анализ алгоритма в контексте ега применения может сказать, по, например, алгоритм с 206 сложе. пиими и 108 умножениями предпочтительнее, чем алгоритм с 260 сложениями и 81 умножениями. Все что мы мажем слелзть, зто предложить конструктору различные альтернативы.
9.4. Симметрические и косасимыетрические фильтры Развитые в предыдущем разделе методы можно усилить, если коэффициенты задающего фиаьтр многочлена 7 (к) обладают дополнительным специальным свойством, а именно, ллз построения хороших алгоритмов кораткик секиий филыра можно воспальзозаться симнетрией коэффициентов мнагочлена фильтр» В мета дах, основанных на преобразовании Фурье, подобные тонкости использовать не удается. Р О Р 91 С Р О азйт о.
(б(, а о),а. ~1 е о -!г1 ,а, 3 1 о а, Π— ! о ВГ ОГ(о е о о ~а, 1 е~ (1~ где г о о 0-1-! )бб 0 3 1 1 1 1 (б 0-1 3 — 3 ! 1 бб 0 1 0 — 1 О 0 Ы О 0 — 1 0 1 1 Ы а 0 О 0 ы 01 — ! 0-10 О, О, С, О 1 Е Га] О, О, С, О, О, О, где 3 0 а О где бм3(х) —.-(б,-б„)х-! (б,— б,) йм' (х) = 51» -(- (Ь вЂ” 5.) =. 51». 91я Гл.
9. Азээт югра Оэатз э РР ОР а Мы построим алгоритм для малых симметрических н нососимметрических фильтров. Комбинируя этн нороткие секция, можно строить более длинные фильтры. Для увеличения рвзмерое фильтра, к сожалению, нельзн испольэовать итерацию, так как фмльтр перестает быть снмметричесиим. Возможен, однако, дру. гой метод. Как мы увидим, вычет симметрического многачлена по модулю симметрического многочлена столь тесно связан с симметрией многочленов, что китайская теорема об остатиах позволяет использовать зти свойства симметрии для построения алга. ритмов для длинных симметрических фильтров нз алгоритмов для коротких симметрячсскнх фильтров.
Фильтр с Е стволами, описываемый мнагочленам й (х), вазы. ваеюя симметритским фиттром, тли многочлен й (х) равен своему взаимному мнагачлену, т, е если й (х) —. хл — 'й (х-') или, эквивалентно, если 95 = йь,, Фильтр с Е отводами. описывае. мый мноючленом 5 (х), называеюя ластимметрическим фиттром, если многочлен й (х) равен своему взаимному миогочлену са зна. ком мянус, т. е. если й (х) = †хь †'й (х-'), нли, эквивалентно, если 53 = — й, 1 Р Мы яачнем рассмотрение симметрических филырои. Длн снмлгетрнчесиого фильтра с Е отводами имеется очевидный алгоритм, содержащий для вычисления каждого выходного отсчета (Š— !) сложений и только Е,'2 умножений, если Е четно, и (Е -3- !))2 умножений, если ). нечетио. В этом очевидном алгоритме перед умножением на общий множитель 53 складываются точки с индексами 1 и Š— 3 — !. Алгоритм Винограда для свертки в случае симметрического фильтра строится точно так же, квк н ранее Построим алгари и лля вычисления выхода симметрического фильтра с тремя ство.
дами, на вход иоторого падается 4 точечный вектор. Пусть й (х) -- й,х' -3- й,х -3- йм б (х) =- бэхэ -3- б,х' -)- б,х -3- б, ° (х) = й (х) б (х) (шоб (хл — х) (х — )) Поскольку беда (х) = 5, та приведение па такому модулю никак не сказывается на з(х). Простыми делителями модула являются четыре миагочлена первой степени, каждый из которых в алгоритме приводит к одному умножению. Имеетсн также простой делитель х' -1- (, который, «ак можно была бы ожидать, приводит к трем умножениям. Но, как мы увидим, в силу симметрии он вносит в алгоритм только два умножения.
Пусть зе (х) 5333 (х) 5333 (х) (шоб х' ф !) таким абрааом, дл» вычисления э!13 (х) нужно талька два умноже- ная. (3стальнан часть алгоритма остзется без изменений и в окан. чательном виде алгоритм записывается равенствам Этот алгоритм содержит шесть умножений н (4 сложений Вга можно использовать в методе перекрытия с суммированием для реализации симметричной З.фильтр-секции, содержащей 1,5 уыножений и 4.5 сложений на каждую точку на выходе. Даваемый теоремой 9.2.! принцип трансформаций позволяет преобразовать этот алюритм в алгоритм симметричной (4, 5). фильтр-секции, содержащий !.5 умножений я 4 сложения на каждую точку на выходе. Этот алгоритм дается равенствам 221 320 зг.
9. Аэ*мчктуаз 4 х тр в прг аз;зоывня ВЛ, йе шр геше н ааск З с вг ф зьтр Причина того, что в данном случае алгоритм для симыетриче. ского фильтра оказывается лучше, чем для несимметрвческога фильтра, кроется в том, что один коэффициент симметрического многочлена равен нулю. Это простейший пример общего фено- мена приведения симметричесного многочлена по модулю сим- мш рического миогочлеиа Пусть й (х) = йзхв Э йгхг ! йгх 4- йгх + йг и рассмотрим вьшеты йггз (к) =- й (к) (шод к' -1- 1), йггг (х) = й (х) (гной к' + х 1- 1), йггг (х) = й (х) (гной к* — к -1- 1), агп (к) = й (к) (птой к т 1). Легко проверить, что эти вычеты раппы йп! (к) = 2й, — йы йгт! (х) = (й + й — й,) х 4- (й -1-й — й) = -- (х ф 1) (й. -1- йг — й.), ймг (х) = ( — й, -'; йг з- йэ) к — ( — й,-Г йг+ й) = = (к — 1) ( — аг т- йг ч- аг), йм! (х) =.
й,к' Ш й,к' ф й,х = х (й,хг -1- й,х -1- й,). В каждом случае число независимых коэффициентов на два меньше, чем в соответствующем модуле шгп(х). В силу симмет рии опии нз независимых коэффипнентоа пропадает. Вообщ говоря. вычет представляется в виде произведения симметричес кого многочлена степени йей шпг(х) — 2 иг даполннтельны многочлен, не содержащий неопределенных козффипиентав. Так как нас интересуют только вычисления вида лиг (х) = йп'(к) Юп (х) (шод шпг(х)), то мы можем запрятать этот дополнительный множитель, спря.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
