Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 51
Текст из файла (страница 51)
Блок, формируемый на выходе сенник фильтре, помещается в выходной буфер с помощью такой же гехннкн, котора» используется и во входном буфере. Поскольку длк заполнения и очистки буферной памяти н для выполнения вычнсленнй требуется время, то метод перекрытия с накоплением всегда ярнводнт к некоторым аадержкам. В прнведенной на рнс 9.1 функциональной схеме эта задержка указана лля того, чтобы слелать эквнвалентнммн оба приведенных представлення. В методе перекрытия с накопленнем используются перекры. вающнеся блокн даннык я часть каждого выходного блока отбрасывается.
В основе метода лежит алгорнтм вычнслення пяклнческой свертки той же самой длнны, что и блоки входных данных Другой метод, известный под названием лешода лерекрьллня с срммнразалкдм, не использует перекрытия входных блоков дан. ных, но основан на алгарптме вычисления тинейной сверткн, длина которой существенно больше длины входных блоков. В нем нс.
пользуются все компоненты выходных блоков и некоторое полол. ннгельное множество вычнеленя», связывающнх вместе отдельные выходные блоки Оба этн метода иллюстрируются рис 9.2 Снова предположим, что у нас есть устройство вычнсленнв линейной свертки, выходная длина нотарой равна л. Пусть нвм надо умножить мнагочлен й (к), степень А которого меныпе л, намного. 'иен А (т), степень В которого балыпе и.
Величина В опять столь велика, что можно полагать ее равной бесконечности. По много. члену ц (х) постропм последовательность мнагочлевав степенн не более л — А — 1, определяя нх равенствами 4" = 4, ! О, ..., л — А — 1, 4"=Фе, ль 1=0, „л — А — 1, 4п=щт„, лп (=б...„л — А — 1. Отметнм, что так построенные мкогочлены не перекрываются. Тогда многочлен б (х) может быть залповы в виде А(х) = Е Цпз(л)«гг-мг-лг г г ЗОВ Гл В. Лрюмютра фюьтра и ир оар з а аюшьгз С ьч з ч. вг з е з сл, Л блч Е:Л)й сгзз' р з Л ыюз гмш гзл~ ж ч лю аььа г г -л! з-т я а ьн зми у г гм я С::2 сю С::2 6::Ц Рн. З.З.
О р за о гекпяян. з !я) = 21х)б)х) Е б!х)бн'!х)"" "'" "'. г=г Для каждого ! положим з!'! !х) = б !х) б!'! 1х). Тогда коэффициенты многочлена з (х) даются равенствами г=б,...,л — А — 1, аг = зг 1=0,..., л — А — 1, г=б,..., я — А — 1, з,.т !„л, = згм+з,".'!.ы лг, згт-зг — л! = Мо+з!'фг — лг н так далее. Этим исчерпываются все вычисления метода перекрытия с суммированием. Метод перекрытия с сучмиронаннем основывается на алгоритме вычисления линейкой свертки. Однако, поскольку бей й (х) = А и бей Д!н 1х) = и — А — 1, то при желании можно васоользоваться н циклической сверткой.
Циклическая свертка длины л на самом деле будет линейной сверткой; все выходные точки циклической свертки будут давать правильные значения коэффициентов линейной свертки. Отметим, что и метод перекрытия с накоплением, и метод пере. крытия с суммированием, для каждой вычисляемой л.точечной свертки используют л — А выходных отсчетов. Метод перекрытия с накоплением обладает тем небольшим преимушеством, что после вычисления сверток н» содержит сложений, н потому предпочтительнее.
С другой стороны, метод перекрытия с суммированием основан на вычислении линейной свертки, вход которой содержит тольно и — А ненулевых новффицнентов Это позволяет построить алгоритм линейной свертки с меньшим числом сложений. Например, в равд. ЗА были рассмотрены алгоритмы итеративного построения линейных сверток большой длины из линейных сверток малой длины. В частности, для построения 256-точечной линейной свертки была иснользована итерация 2.точечной линей. ной свертки Эта же задача может быть решена методом перекры. тня с суммированием. Параметры алгорятма: и =.
511 выходных точек; А = 255, что соответствует фильтру с 256 отводами; и— — А =- 256 входных точек. Каждая составляющая свертка дает пакет из 256 выходных точек, для вычисления которых в данной конструкции требуется 6561 умножений и !917! сложений, считая дополнительные сложения алгоритма перекрытия с суммирова. пнем. Таким образом, реализация вычислений на КИО-фильтре с 256 отводами требует 25,6 умножений на одну точку ва выходе.
зы 3!0 Гл. 9. Артптур ф тр а н р Зр ю а за Аггорн;и я р гчгз с «аиа фильтр 9.2. Алгоритмы длв коротких секций фильтра Цифровые КИС-фильтры можно строить, используя описанные в предыдущем разделе методы перекрытия Для применении зтнх методов нужны корошие алгоритмы для отдельных секций фильтра. Сейчас мы далям корашие алгорнтиы длн коротких секций фильтра, а в равд. 9,9 опишем способы их сочетанив для пастроени» длинных секций фильтра. Метод перекрытн» с накоплеииеы можно зависать в матричном виде.
Опуская отбрасываемые выходные коыпонеяты, получаем следующее матричное уравнение. Это уравнение описывает вычисление и «омпонент на выходе КИО фильтра с г отводами. Такое вы числение будем аазывать (г, л) фигьтр-сгяцтдг, илн, прн г = лт.фильтр.секцией Эта задача представляет собой задачу вычисления усеченной свертки.
Как будет доказано ниже, (г, л)-фильтр-секаия требует г ) л — ! умножений, и поэтому алгорити с г -г- и — ! умножениями на. зывается оптимальным, Этот термин, однако, может ввести в заблуждение, поскольку алгоритмы подобного сорта могут сакер. жать слишком много сложений, есаи г и л не мглы. Ыы будем пользоваться оптимзльнымн алгоритмами только при малых значениях г н и.
Алгоритм секционной фильтрапии можно получить из алгоритма вычисления линейной свергни. Основой преобразонания алгоритма для одной из этих задач в алгоритм для другой задачи является следующий общий принцип. Теорема 9.2.1 (Трансформацяанный принцип). Пусть задал алгоритм з = Тд = ССАд, где матрица б ятяется диагональной, а матрица А и С тдгржат только магме константы.
Тогда е —. А'ССЧ лггяюлсл алгоритмом вмчиглечия е = Т" !. Если игяодяиа алгоритм гычистиия гетнора з оптимален, то второй алгоритм дает олти. магьимд алгоритм гмчтггяия зеюнора е. Доказательство. Алгоритм представляет собой факторизацию матрицы в виде Т С С А. Так как матрица С является диагональной, то Тг = А"ССг и, следовательно, ТН АгбСгй Вторая часть утверждения следует отсюда очевидным образом, так как если существует алгоритм с наименьшим числом умноже. ннй для вычисления вектора е, то его трансформация дает алгоритм с тем же числам умножений для вычисления вектора з.
О Воспользуемс» трансформвниовими принципом для построения алгоритмов коротких фильтр.сепций. Начнем с алгоритма линейной свертки ~*1 ~" '1,,";! з дфа, ]й оч[г] Согласно теореме 9 2. ! теперь можно записать "г. г з] (дт )о г, г )Г,( 9 г о) (г, ! 9 -~ о) (П (е ~ 9[а,+г,] [о г е](У]' .'(ля построении алгоритма 2-фильтр секции заменим теперь (го гб на (з„з,) и ((„)г, А) на (д„йод ): [В [г.
г о] [г] ,гн () 1! ° (() -' '1)г) Згэ 93 Иерзр э * вш 69+э Р 4 3 3 1Ь 20 Ь 13 33 16.25 27.22 26.37 Я 70 1.33 2.76 5.06 42В 7 Ь9 7. 72 15 120 260 735 644 4060 5 25 В1 125 243 625 3 !Ь 27 32 61 3 9 16 21 32 31 5, = ~ Впьрь, А О э„71 19 ц ' 312 Гл 9. АР* т Р йы тв зР вар З Р»о я.э.хрэ р ш р х ы Э Эох 9,7.сев„З При желании этот алгоритм после переупорядочивания можно пе- реписатьь в виде Для 2.фильтр. секции этот алгорптм оптимален; он содержит три унножения и четыре сложения, не считая суммирования й, -~-2„ связывающего отводы фильтра.
Так же можно построить и другие алгоритмы коротких секций фильтра, Характеристики некоторых из таких алгоритмов приве. девы на рис. 9.3. 9.3. Итсрироваиие секций фильтра Итерируя алгоритмы дли коротких секций фильтров, можно получать алгоритмм для секций фнлыра большей длинм, на вы. ходе которых формируются длинные блоки отсчетов. Характери. стики тания итернроаанных секций фильтра затабулированы н рис. 9 4. Используя описанный в равд 92 метод переирытия с накоплением, можно строить каскады произвольного числа зги секций фильтра, иа выходе которых будет формироваться беско нечный поток данных В рассмотренных вами малых алгоритмах свертки не исполь.
эовалось свойство коммутативности умножения чисел поля. Лю' бой алгоритм линейной свертки, Н-1 Ш= Едй «б» в котором не используется ни деление, нн свойство коммутатив ности умножения, в такай же иере применим к элементам кольца, «ак к элементам воля. Пусть, например, надо вычислить свертку матриц в-г где теперь О, представляет собой 1-ю матрицу в списке из 97 ма. т, а С представляет собой!.ю матрицу в «писке иэ 5 матрип.
триц, а, р Построенные нами ранее алгоритмы свертки применимы в д в вином случае та» же, как и ранее Сложение превращается в сложение матриц, а умножение становится умножением матриц Построим итерацию 2-фидьтр секций для формирования сек. пий фильтра большей клины. Малый алгоритм возьмем в виде Алгоритм содержит 1,5 умножений иа каждый отсчет на выходе фильтра Его можно использовать повторно для вычисления двух отсчетов на выходе одновременно, и такое вычисление всегда будет содержать 1,5 умножений и 2 сложения на один вычет «а выходе. 2 филырпжкцня, однако, не имеет существенного значения для практических приложений, а используется для итеративного по. стйоения а.чгоритмов больших фильтров с 2 отводами, на выходе которых вычисляютсн одновременно 2" отсчетов дискретного сигнала. Для иллюстрации пдез рассмотрим построение алгоритма вы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
