Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 54
Текст из файла (страница 54)
Для фильтров прорежинании алгоритщг линейной свертки алтари~мы секционной фильтрации не связаны между соб оцисываечыи теоремой 9 2.1 трансформацианнмч принципа Трансформационный принцип преобразует алгоритм свертки дл прареживающего фильтра в алгоритм секционной фильтрлци для интерпсширующего филыра. Рассмотрим алгоритм линейной свертки для прореживающе в отношении 2: 1 филыра с пятью отводами, на вход которо подастся 5.точечнмй вектор. Необходимый выходной вект дается вычислением Алгоритм щписан в виде вы ~ислени» З.тачечяой линейной свертк 2 точечной линейной свертка и трех допалпктетьных слажени сочетаюшик результаты зтнх сверток. Таким образом, рассм треиный алгоритм прареживающей филырацни содержит васви умвожений н 26 сложений нв каждые пять точек иа вмходе. Ес этот алгоритм испааьзовать в методе перекрытия с суммиров пнем, ш для сочетания секций, каждая из которых содержит пя входных точек, потребуется еще четыре дааолпнтельпых слож кия.
Такой алгоритм будег содержать восемь умножений и 30 сл Эв Фщь рн позу в нтерпол кэз лений на наждые пять выходных точек (1,6 умножений и 6 ело. мений нв одну тачку на выходе). Теперь рассмотрим гакую же задачу для секции прореживаюгцего фильтра с пятью отвалами и тремя выходными отсчетами. Алгоритм для такой секция можно записать равенством В этом алгоритме с помощью трех дополнительных сложений сочетаются алгоритмы З-фильтр.секции и (3,2)-фильтр-секпии, твк что в общей сложности этот алгоритм прареживающей филь. травин содержит девять умножений и 26 сложений.
Посмотрим, какие алгоритмы получаются из построенных алгоритмов прн их трапа)юрлгации. Мы уаидич, чта в обоих слуыях зто приведет к алгоритмам интерполирующих фяльтров. Трансформация выписанного выше алгоритма линейной свертки дается равенствам Заменим теперь (ез, еа ез. е„г,) на(заза зз П зг) н ()э )а)* )з ) ) ио (З„ба ба бм 4). Тогда Мы палучкли уравнения для интерполирующега фильтр», по. ыыьку нулю теперь равны входные точки. Таким образом, ьрнпенение траисфармациовиага прииинпа к орорежнвв~ощей з отношении 2: 1 З.фильтр-секции привеяа к интерполирующей ь о.ношении 2: ! 5-фильтр.секшги.
Алгоритм содержит восетгь учиоукений. Ззб Гл З. Ар а мотре фзлюроз ° арюарзюзюеа Таким же образом. алгоритм прорежнвающсй 5-фильтр-сек цин, записываемый рзаеаством (т,г,з г г,а о о а1(х) г,) Г, ыажет быть трансформирован к алгоритчу ),' г. е М.( е 3 г г! о ,е г,г,' о е Этот алгорити является алгаритмои линейной свертки, входим элементы з которой через один разны нулю, -'алгоритм интер полирующей фильтрации, содерх ащий девять учноженнй. Следующим рассмотрим (на примере) алгоритм снмметричао прореживающей фильтрации. Пастроиьг алгоритм снммегрическа прорежиаающего в отношении 2: 1!5.фильтра Как и в преяыду шем примере, разобьем задачу на симметрическую ляаейну 8 точечцучо свертку и ситгтгетрачегкую линейную 7-точечиу свертку.
Согласно теореме 9.4.3 первая из них может быть зы чпслеиа с почощью алгоритма фильтршгии 8.точечного вход в фильтре с 7 отводачи. Для вычисления обеик линейнмх гиычетрических саерто воспользуеткя разработанным в предыдущем параграфе методом, Степень ъгногочлегта ш (х) = х (х — !) (х — 1) (х — ) (х' Г 1) (х' -1- х -'; 1) ~х' — х -1- !) (х' -1- 1 равна 14 и, следовательно, им южно воспользоваться для по строения засорить~а линейной фильтрации О.точечаого вход и фнштре с 7 отводзмк. В разд 9 4 было определено число умно женнй, саязаниых с использованием в качестве модуля каждог из указанных симметрических миогочлепое Это яриаодит к о З,З. Автекорреаяпи » вззимшв ксррелзо» щему числу умножений в алгоритме, равному 1б.
Аналогично, выбрасывая один линейный множитель, получаем алгоритм филь. грации 7-точечного входа в филырс с 7 отводами, содержащий 15 умножений. Следовательно, для решения рассматривгюмой задачи можно построить ачгоритм, содержащий Э! умножение О.О.
Автокорреляцня н взаимная корреляция Выражение вида ° — г уз ймьа» ! = О,..., 1,'- Аг — 2, ь=е называемое корреляцией, если й сонпадает с б, и взаимной кор- реляцией, если й н б различны, очень тесно связано со сверткоа Его можно сделать похожим на свертку, если просто прочитать одну из последовательностей в обратном порядке. В принципе, любой из рассмотренных изми метадон вычисления линейной свертки годится для вычисления корреляции.
Тем не менее, имеется одно практически существенное различие. Длина КИО- фильтра обычно намного меньше, чеи длина фильтруечой после. довательности данных, а входюций в корреляцию «филшр» й (х) иа самом деле представляет собой другую последовательность данных, длина которой примерна равна длине последовательности, обозначаемой многочленом б (х); часто длина записи обеих после. довательнсстей неопределена и весьма велика — возможно, не- сколько сотен отеч«юв. Хорошие алгоритмы разбивают й и б на секции.
й(ы начнем рассмотрение с вычисления автонорреляцнн и — 1 гг=-у- у. бабью 1=-0, ..., л(2 — 1, возможно, опуская в сумме деление на Аг. В интересующих нас задачах длина М блока данных значительно больше длины п(2 блока выходных данных, так что использование для вычислений преобразования Фурье длины Р( было бы слишком расточитель. иым. Разобьем сумму на части па я слагаемых в каждой иа частей, и будем решать задачу, используя преобразование Фурье длины л Запишем ь-г г=Ег)", где г-е и ! гз — ! ! = О, ..., л!2 — 1, г)п = -у- ~~ь Нзег гзбзег гзч.г ! О ! 1, 999 ( Ф!.ыл, ! = О, ..., л(2 — 1, ( О, ! л/2, ..., и — 1, Тогда )-) Бь= 2, Р!"а!", А=О, ..., )-з к„((з., Оп) Рп) ( ( 1(эР)ьы) Эхз Гэ.
9. Ар* к уэз физь эоз а аэюараз за 4 н Е (л/2) = А). Таким образом, задача свелась к вычисленн вектора г!') для 1 = О, ..., Б — 1, который мы будем находить используя БПФ н подходяшую пвклкческую свертку. Определим два вида блоков длины л — одын состоящий пал. пастью нз данных, н второй, состоящий наполавнну нз нулей. Позже будет наказано, как взбегать блоков первого вида. Пусть й) Ф й)ю л ! = О, ..., л — 1. )и — ) — 2«бэйач.), 1==0, ., л(2 — 1.
в-э Пусть Рп) н Рп' обозначают векторы, полученные преобразова. пнем Фурье кз векторов )Р'! н йп). Тогда согласно задаче 1.10, о) ою о) 5« = Оз Оь равно преобразованию Фурье днклической кор реляция — ! )и =- Е«.а«-ьюь =О, ..., л — 1, )-ч н половина из этих компонент дает искомые нами величины г, = — э,, 1=0, „и,'2 — 1. )и 1 )и л Таким образом, сначала мы вычисляем вектор а затем вычисляем его обратное преобразование Фурье а к полл. гаем г, = (1АУ! э! для ! = О, ..., л(2 — 1. Лля завершенн» списания алгоритма покажем, как исключит некоторые вычясленяя.
Вместо использования БПФ длн вычисле ння Бп) воспользуеыся формулой Этз формула является прямым следствием свойства аадержки лл преобрззовання Фурье; умножение в частотной областн на м соответствует вреыенному сдвягу па Ь позпций. Если 9 = л( то зто соответствуег умножению Рз)л на ( — Пз. Ва временнб 9 9 Д юзр эээ ч ю ю эрюэа з области происходит сдвиг ненулевых паюций вентора б )и.п э нулевые повадки вектора ош); во временнбй областн сумма равна йп), н, следовательно, в частотной области сумма равна 0 и), Такнм образом, это вычисление можно зепнсать з виде !.— ) Б,= 2; Р«о(Р«п+( — 1у'Рзп '1 ! з Алгоритм завершается вычислением обратного вреобразованн» Фу ье лак.схема вычислений в окончательном виде паназана па рнс.
9.6. Отметим, что каждый цикл содержит только олин БПФ. а.тгорктм, хотя в начальной точке я в последней точке алгоритма добавляется еже но одному БПФ. Таким образом, хотя вычисление одаой циклической свертки содержат тра преобразования Фурье, мм постровли алгоритм, который в среднем на цнкл содержит толька одно БПФ. Все Е циклов на рисунке показаны одннакавымн, хот» в по. следнем вэ нпх вычнсляется преобразование Фурье для нулевого вектора, добавленного в конец послеловательностн данных; это преобразование Фурье можно исключить, модифицирован по. следний цикл вычислений. Аналогичный метод прнменйм н к задаче вычисления взаимной корреляцни.
Обе последовательности данных разобьем на от. резки, комбнннруя коп)рые в частотной области, мы уменьшаем числа необходимых обратных преобразований Фурье. Теперь на одном очень подробном примере покажем, как можно использовать другие методы в рассмвтрнваемом способе — ! аычпслепня корреляций. Запнше» корреляцию 3, = х, Иьый„ а матричном анде, гас г намного больше а. й(ы опишем структуру алгоритма для частного случая л .=. 120 н г = ! 0 ООО. Основываясь па некотором опыте, примем пропзволь. ное решение разбить последовательность нз !20 выходных точек на четыре пакета по ЭО выходных точек в каждом, и организуем емчкслеаня, апнраясь ка 60.точечьый БПФ.алгоритм Винограда.
331 В таком блочном виде матричное уравнение «рияимает Форму где к й (х) и к й (х) дабаилены 20 нулевых компонент так, чтобы ° овсе значение г — )0 020 делилось иа 60. Каждый иа малых бчо. ков, например, первый )1„1.' ) г,) можно вычнслить, используя 60-точечный ВПФ.алгоритьг Винограда и взяв в качестве ответа первые 30 выходных тогек Теперь рассмотрим блочную структуру Гяй о, о о о о, о 'я,' о,.о,о )ь~,о, О, О Зле Гл В.
Лрх тра йилыра иреыраыва В с „ Рж В.а В и гии ыгв ж )о. о * о,о,о о, о, о ,о, о. о 'гч,) о,~ йо, 1о, о, о, о,) п11 эзб Заб Г 9. Лухяжюур ф ьту з в р бр аыяиз 9 7. Устроя зз а БПФ Тычка в силу его регулярности. Регулярность БПФ-алгоритча Кули †Тью очевидным образам вытекает нз его блок схемы, показанной на ряс. 9.8 для случая прореживаняя по времени. На всек шагах нтерацяи используется простое 2.точечное пре. образованпе Фурье. Основной зычяслптельный модуль состоит нэ 2-точечного днскретного преобразования Фурье и фазовраща. тела Показанная на рнс.
9 9 дааграмма этого модуля определилэ его название; он называется 2 точечной бабочкой Алгоритм Кули— Тьюкя по основанию дза с прареживаняем по частоте, показанный на ряс. 9.!О, также строится на основе подобной бабочки, дна. граммз которой приведена на ряс 9.11. Если 2 точечная бабочка запаяв, в виде лн программной реалязацин, в виде ли вппаратурваго модуля, то БПФ-алгорятм Куля †Тыч по основанию два с прорежяванием по времени своднтся проста к определенной псследоаателынюти прохождения входных данных через 2.точечную бабочку. При каждом таком орохожденнн вычисляется соответствующее преобразование Фурье, но нндексы данных переставляются. Нз рнс. 9.8 указана перестановка на входных данных, которая предопределяет вычнсленне выходных данных в естественном порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
