Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 5
Текст из файла (страница 5)
1.4. КЛО-фзгыр р .12 А р рг эмэфльтр. Для заданных двух последовательностей — цаследовательности данных б=(дь =.0,..., Д вЂ” Ц н последовательности фильтра й = )йь 1 = 0,..., 5 — Ц, где Дг — длина блока данных и Ь вЂ” длина фильтра, линейной саерткой называется новая последовательность ь = )гь 1= 0...., 1. — 'Д) — 2), элеМенты которой определяются ранено~вами и — г =о,,брдг .К «4 Гл. 1 Вз««« з длина выходного блока равна Е ф Дà — 1; последовательность з называется выходной илн сигнальной. В записи свертки подразумевается, что й, „ = О при «' — й < О. Так как все компоненты последовательности й умножаются на все компоненты последовательности б, то прямой метод вычислении сзертки содержит йгб умножений.
Имеется-очень разработанная теория построения КИ(У«фильтров, связанная с выборам длины Ь и весовых множителей (д). Этот асиент теории конструкпий фильтров мы не рассматриваем; предметом пашах исслеловзний являются быстрые алгоритмы вычисления выходной последовательности з по заданным последов«тельнастям филыра й и входа б Со сверткой тесно свнзана еще одна величина, которан называется корр««ячи«й и определяется равенствами и..« г« '— ««й «б»' « ""О' '''' Е+«У 2' » где б„« -- О при « -!. й >ж Ц Корреляцию можно вычислять как свертку, если прос о прочитзть одну нз определяющих ее последо- вательностей в обратном порядке. Все способы вычисления ли- нейной свертки легко преобразунггся н способы вычисления корреляции. Свертку можно записать танже через многочлевы.
Пусть я — « «--« б (х) — ~ б,хг и б (х) = «~ д,хд «=« -« «+яы Тогда «(х) — й(х) б(х), где з(х) = 2, «,хц Эти равенства легко «=« прозсрнются простым вычислением нозффициентав ароизведения й(Мб(х). Можно, нонсчно. записать таиже рааенсгво «(х) = -: б (х12 (х), из которого становится очевидной симметричная роль последовательностей й н д з определении свертки.
Таким образом, линейная свертка может быть записана в знвивалентном виде как щ= Е й«б«». Другой формой свертки, тесно связанной с линейной сверткой, является цнклическая свертка. Для заданных двух последова- тельностей (б«, « — — О, ..., и — 1) и (й„ « = О, ..., л — !( с одной и той же длиной блока и циклическая свертка («;, « = О, ..., л — 1) с длиной блока л определяется равенствами «;:= 2; би, нбм (--О,..., и — 1, 1А. Цифр з«» сар б ю сиги где двойные скобки означают, что вычисления над индексами производятся в арифметике по модулю л (см.
равд. 2.6). Иными словами, ((л — й)) = и — й (пюб и) и О < ((л — й)) < и. Заметим, что в циклической свертке при каждом «иаждое д«умножается на значимую величину йщ «и Это существенное отличие от линейной свертки, в которой б» часто умножается на член й, „, индекс которого выходит за диапазон определения последов».
тельвасти й, так что соответствуюгцая «омионента й« » равна нулю. Цинлическую свертку можно связать с линейной следующим образом. По определению циклияеской сйертки ««= 2«уд!««пщ 1=0. °, и — 1. Разделим эту сумму на дае, выделяя в первую сумму члены, ннлексы которых удовл«хворают условию « — й >ж О (нлн й < «), а во вторую — члены, индексы которых удовлетворяют условию 1 — й<О(илий>1): М = хю«а«-«б»+ лч«а»ь« — «б«. »«»«*« Полагая теперь в первой сумме д, „= О прн й > 1, а во второй б„„« =. О при й < 1, ьяякна изменить граннцм суммирования н получить связь циклической н линейной сверток в виде -г — г «« = Е й«м(«+ ~ й ь««б»=««+«„,ь ! =О,..., л — 1.
»-« »=« Скажем, что члены последовательности з, индексы котормх больше и — 1, «вкладываются«обратна в члены, индексы которых меньше л. Если второй член выписанной выше суммы равен нулю, то линейную свертку можно вычислять нак циклическую. Это возможно, если произведения й„„«б«раппы нулю для всех «н й Чтабы обеспечить зтн условия, можно так выбрать длину л цинличесной свертки, чтобы она была Оплыл~а, чем Л' -)- Š— 1 (попслияя пулями й и б до длины блона и).
Тогда для вычисления линейной свертки можно пользоваться алгоритмом вычисления циклической савраски н получать при этом правильный ответ Циклическую свергну можно также выразать в анде произведения многочленов. Пусть б (х) = 2„* б,хй й (х) = ~„" б,хг «-« « †« И Г.г.п ж 1» Избр» Ер З «' «г» Ряс. ».В. И о энне КИОфнлн р вз» форнярою цяяян ыкой егткя. н з (х) =- К (х) д (х). Цнклнвеская свертка вычисляется па много- члеяу з (х) яобрпгпым влажепвем» членов нысшего порядка. Это можно представить в виде записи з'(х) = з (х) (пюб х" — 1), где равенство по молулю х" — 1 означает, что з' (х) рюип остатку от деленна многачлена з (х) на многочлен х" — ! . Таким образом, з' (х) = К (х) й (х) (п»об х" — 1).
Для прнведення многочлена К (х) б (х) по модулю х" — 1 доста- точно заменить х" на 1, нлн, чтп эквивалентно, член х"Ы с поло- жнтельнмм » на член хг. Это соответствует формированию величин з! = зг + 3 -ьг, 1 = О, ° ° ., л — 1, н, следовательно, позволяет вычнслнть коэффициенты цикличе- ской сперткн. Так как з'(х) б (х) К (х) =- К (х) б (к) (»пай х" — !), то ясно, что векторы б п й игриот в определенны сперткн сим- метричную роль, так что цнклнческая свертка вадаегея двумя эквпвалептвымн равенствамн г э»= Е Кгг»»б»= » 4 — ! = х» бг»г-з»»й», 1=0,..., л — 1, з-э На рпс. ).б приведена схема КНО-фильтра, вычисляющего цпнлическую свертку, для чего последовательность б повторя. ется дважды.
На ныходе КНО.фильтра формируется последова- тельность яэ Зл — 1 компонент, среди которых солержатся л последовательных «оппонент, равных компонентам циклической сгмртнв. Более ва»хным длн пряложеняй является использование циклической свертки для вычисления длнвной лнпейной свертки. В быстрых алгоритмах вы ш*леняя длинной линей»юй свертки входная последовательность разбннаетсн па короткие секции, со держащие иногда несьолько сотен отгчетов Длл формирования потока данных на выходе секции обрабатывают я поочередяо-- зачастую методом циклической свертки., !акне способы вазываются методами с лергхрыюием, в этом названии отражается тот факт, что веперекрывающиеся секция в потоке входных данных првводят к перекрывающимся секциям в патоке выкадных даннык, а перекрывающнеся секции в потоке входных данных приводят к ненерекрывающнмся секциям в потоке выкодных Лап вы х Работа показанного на рпс.
15 звторегрессионпого фнлюра также может быть описана в терминах полвнамяа.тююй арнфметики. Но если КНО фильтр вычисляет праизведенне чногочленов, то авторегресснонный фильтр выполняет деленне многочленав А нченно. пря фвльтраппн конечной последовательност.я в авторегресспоннам фнлыре (с пулевым нвчвлы»мм состоявнем) на выходе фильтра формируется последовательность кам)фнцие»»тов многачлена-насей»го, получаемого прн деления многочлена, коэффициенты которого равны компонентам входной оослсдовательностн, на многочлсн, коэффицненты «оторого задаются весовымв ьгножителя»тн в отводах фильтра, к моменту завершения ввода входной последовзтельностн содержнмое фильтра равно коэффнцнентам многочлена.остатка от такого деления. Напомним, что автарегрессяонный фнльтр описывается равенством Рг = х» Ь»Р»- ф яг »-о где аг есть )-й снмвол на входе, а Ьг — весовой множитель в »-и отводе фильтра. Определнм многочлены а (х) = ~ а,х' п Ь (х) = Ь, Ь»х' »=0 г=о к запишем равенства ( а (х) .=- ») (х) Ь (х) -1- г (х), где Я (х) н г(х) обозначают соответственно частное и остаток в алгоратме деления »тногочлевов.
Тогда отсчет рг на ныходе фильтра равен в точности Ьму коэффициенту нногочлена-час»К ваго, а коэффипкепты многочлена-остатка г(х) будут запнганы в самых левых разрядах регистра сдвнга авторегре«оконного фильтра после того, как яа его вход будут поданы все п козффицнентоа аг делимого. Хз Гл 1. Введена Если раскрыт( !а о» о, — 1' 1 ж е( = ~~„(н(гц( — ~ в»(6»~ = 1-0 »-э в"-1 в»("-П ... 1. Если вектор вектор ч можно преобразования Другим очень важным в цифровой обработке сигналов андам вычисления является дискретное преобразованне Фурье (с этих пор называемая в дальнейшем просто преобразованием Фурье) Пусть ч = (сь 1 = О, ..., и — 1) обозначает вектор с вещественны»(я илн комплекснымя комсонектамн, Преобразоеаннеы Фурье вектора г называется вектор У длины п с коьпшекснымя кочповентамн, задаваемыми равенствами Р» = ~ вво„й=-б,..., и — 1, (-» где в=с-(ь(" н (=-у — !').
Иногда это определение запвсывается в матрнчном виде У .= Тч. эту запись, то ана прнннмает вяд 1 1 1 ... 1 1 в в" ... в" — 1 1 вз в( ... в'("-п Ч равен преобрааованню Фурье вектора т, та вычислять по вектору 7 с па»(ощью обратного Фурье, задаваемого равенством — 1 о, = — ~~ в — (»Р». »=» Доказательства этого факта дается следующими выкладками: — ! .-1 .-1 ~ в — («У»=- ~', в-'1 ~ вне(.= , -»и — п~ 1-» »-Е Если ( = (, то сумма по й, очевидно, равна л, а если ! не равно 1, та сумма приводится к виду — 1 Х „— ц — и (в- (( — п)1 — в ! — в — и — ц 1 о !5 И р» ам р * р евраапк«сяг»лз Так «ак в-" = 1, то справа стоит нуль.
Еледавательно, -э ~ в-ву» =- х„р( (лбц) = ло,. »-е 1-Е где бц =- 1 пря ( = ! н бп =. О в противном случае. Мелку цикляческай сырткой я преобразованием Фурье имеется очень важная связь, нагорая известна как югарела о сеерюхе я формулируется следующяы образом. Вектор е равен циклической свертке векторов ! н й, е,= ~)п( п(Е(, 1=0,..., л — 1, (=з тогда н только тогда, когда нх преобразоеання Фурье удовлетвоРяют Равенствам Е»=Е»б», й=б,, л — 1.
Вта у верждение вытекает нз того, что — 1 — 1 — ! б„в (»б дл вц а «)п( а( = — лгы (е (»б»Р», »,в( )ва ~ л л',( »-е »-е Поскольку е есть обратное преобразование Фурье от Е, та мы ванлючаем, что Е» =- О,Е». Можно также определить двумерные преобразования Фуры, которые полезны прп обработке двумерных таблна данных, н многомерные преобразования Фурье, которые попользуются прн обработке многомерных массивов данных. Двумерное преобразованне Фурье определяется равенствамн '-1 й'=О,..., л' — 1, у».= У Е в('»'р(ого( где в = е-(» (" п р е ('"(лй 1.5. История быстрых алгорнтмов обработки сигналов Историю быстрмх алгоритмов обработка сигналов прпнпто отсчнтывать с момента, когда е 1966 г.
Кули н Тычки опубликовали свой быстрый адгорнтм вычясленяя преобразавання Фурье (БПФ-»лгорнтм), хотя на самом деле эта нстарня началась намного зО Гк 1. пзед яне 31 > аньше Указанная публикация (5! появилась кан раз в нужный момент н послтжила катализатором применения метода цифровой обработки сигналов в новом контексте Векторе после огублико. еания этой работы Стогкем (6)заметил,что БПФ алгоритмы могут служить удобным способом вычисления сверток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
