ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 681.3.06(075.8)
УСТОЙЧИВОСТЬ КОНВЕЙЕРНЫХ РЕКУРСИВНЫХ ФИЛЬТРОВ
© 2005 г. И.И. Левин1, Е.А. Семерников'
В статье исследуется передаточная функция конвейеризованного фильтра второго порядка. Выявлены причины потери фильтрами устойчивости в процессе конвейеризации. Сформулирована методика построения устойчивого конвейеризованного фильтра второго порядка с сохранением избирательных свойств исходного фильтра.
Многие алгоритмы цифровой обработки сигналов используют цифровые фильтры с конечными и бесконечными импульсными характеристиками. Для реализации фильтров с бесконечными импульсными характеристиками используются рекурсивные фильтры, в которых выходной сигнал зависит не только от входного сигнала, но и от предыдущих значений выходного сигнала. Одним из преимуществ рекурсивных фильтров перед нерекурсивными является меньшее на порядок количество коэффициентов, описывающих фильтр, и, как следствие, меньшее количество вычислительных операций при технической реализации фильтра.
Цифровая обработка сигналов в реальном масштабе времени требует постоянного увеличения скорости вычислений, что приводит к необходимости распараллеливания вычислительного процесса. Наиболее эффективным методом распараллеливания является конвейеризация вычислений [1]. Однако конвейерный способ организации параллельных вычислений предполагает введение в операционные устройства дополнительных регистров, что приводит к задержке появления результата формируемого устройством. В вычислениях без обратных связей (нерекурсивных вычислениях) задержка появления результата в отдельных операционных устройствах приводит лишь к увеличению латент-ности появления конечного результата. Введение же конвейерных регистров в вычислитель-
1 Южный научный центр РАН, г. Таганрог.
ные устройства, выполняющие рекурсивные вычисления, может приводить к нарушению межитерационного информационного предшествования и, следовательно, к искажению алгоритма работы.
Известные методы распараллеливания рекурсивных схем, в частности автоподстановка, замена переменных, метод опережающих вычислений и др. позволяют корректно ввести дополнительные конвейерные регистры в вычислительные устройства, не нарушая алгоритма функционирования. Однако вопросы устойчивости конвейеризованных вычислительных схем с обратными связями, выполняющих рекурсивные вычисления, до настоящего времени подробно не исследовались. Некоторые специалисты только указывают на проблему потери устойчивости рекурсивных схем при распараллеливании [2, 3].
Известно [4—8], что рекурсивный фильтр произвольного порядка может быть представлен в виде каскадного включения фильтров первого и второго порядка. Причем, фильтры второго порядка в таком представлении обязательны. В отличие от рекурсивных фильтров первого порядка, не теряющих устойчивости при распараллеливании, фильтры второго порядка зачастую теряют устойчивость. Потеря устойчивости даже одного из фильтров приводит к неработоспособности не только отдельного каскада, но и всей каскадной схемы. В этом плане вопросы обеспечения устойчивости при распараллеливании рекурсивных фильтров второго порядка, решаемые в данной статье, являются актуальной задачей для многих применений.
РЕАЛИЗАЦИЯ ЦИФРОВЫХ ФИЛЬТРОВ
Цифровые фильтры описываются разностными уравнениями следующего вида к м
Уп = Х^-.-Хя.Л-о Л = 0,1,...,
¿=0 ¿=1
где хя и уп - входная и выходная цифровые последовательности; bi и аг- вещественные коэффициенты нерекурсивной и рекурсивной части фильтра (для определенности будем полагать коэффициенты постоянными в течение всей работы фильтра). Значение тах{К, М) - определяет порядок фильтра.
Передаточной функцией Н(г) цифрового фильтра называется отношение 2-преобразова-ния реакции фильтра У(г) = Z{yn} к 2-преобразо-ванию входного сигнала Х(г) = Х{хп) при нулевых начальных условиях.
XЪ?
Н{г) = *=0
м
1+1 а,!-1 ¿=1
(П
Передаточная функция цифрового фильтра представляет собой дробно-рациональную функцию, числитель и знаменатель которой являются многочленами от г-' порядков /? и М с вещественными коэффициентами Ъ{ и щ. Передаточная функция, как и любая дробно-рациональная функция, характеризуется особыми точками -полюсами и нулями. Полюсами называют значения 2, при которых знаменатель Н(~) равен нулю, нулями называют значения 2, при которых Н{2) равно нулю.
Фильтр называется устойчивым, если при любых начальных условиях и любом ограниченном входном сигнале хп, выходной сигнал уп также остается ограниченным, т.е. из условия |лп| < 5 при всех п следует, что |у„|< Д причем В < °° и О < < <*> - константы, не зависящие от п [4, 5].
Для устойчивости рекурсивного цифрового фильтра порядка М необходимо и достаточно [6, 5], чтобы все полюсы его передаточной функции лежали внутри единичной окружности комплексной 2-плоскости \р11 < 1, I = 1,2,..., М.
Передаточная функция фильтра может быть представлена различными эквивалентными математическими выражениями, отражающими различные подходы к построению цифровых фильтров, например в виде отношения полиномов числителя и знаменателя, разложенных на
множители первой и второй степени
— 1=0
- '=1
т= « 1 +
Я/2
ТКЬш+Ьиг )
_ _
П(1 + а1кг-1+а2к2~2) ¿=1
(2)
где и рк - г-й нуль и к-й полюс передаточной функции, Ь^, Ьи, Ьъ, а[к, аи - вещественные коэффициенты, /? и М - четные числа.
При К = М передаточная функция (2) принимает вид:
К к (Ьаь + 1 + Ьцг2 2 )
я(г)=пя^)=п\Г -1-^Г' (3)
*=1 к=1 (1 + а1к2 +а2к1 )
где К = М/2 - количество множителей второго порядка.
Выражение, стоящее под знаком произведения в (3), описывает работу рекурсивного фильтра второго порядка, а весь фильтр, имеющий передаточную функцию вида (1), может быть построен путем каскадного соединения К фильтров второго порядка [6]. Поэтому без потери общности будем рассматривать конвейерную реализацию рекурсивного фильтра второго порядка.
Разностное уравнение и передаточная функция Нн{1) цифрового рекурсивного фильтра второго порядка имеют вид:
Уп = V* + Ь1Хп-1 + Ь2Хп-2 " а\Уп-1 ~ а2Уп-2 (4)
Ь0+Ь1-2~1+Ь2'2~2 _ Ни{2)~—--—-
1 + а-у ■ 2 +а2-2
= (1-г1г-1Х1-г2г-1)
(г-р^а-р^-1)
(5)
где и уп - входная и выходная цифровые последовательности; Ь{ и а, - вещественные коэффициенты нерекурсивной и рекурсивной частей фильтра.
Схема вычислений, соответствующая уравнению (4), представленная в виде графа потоков данных (ГПД) [2, 9], показана на рисунке 1.
Быстродействие операционного устройства, выполняющего действия, предписанные ГПД, определяется временем вычислений (периодом
итерации) в рекурсивной части фильтра [2], так как нельзя начать следующую итерацию, пока не завершатся все вычисления в текущей итерации.
КОНВЕЙЕРИЗАЦИЯ РЕКУРСИВНОГО ЦИФРОВОГО ФИЛЬТРА
С целью ускорения вычислений целесообразно использовать конвейерное построение устройств суммирования 7 и умножения 8 и 9. Однако простое введение дополнительных конвейерных регистров в циклы обратной связи дополнительно к регистрам 9 и 10 приведет к нарушению межитерационного информационного предшествования и, как следствие, к искажению алгоритма работы фильтра.
Для корректного введения в рекурсивный фильтр дополнительных конвейерных регистров можно применить метод опережающих вычислений (look-ahead computation) и метод ресинхронизации (retiming) [3, 2]. Метод опережающих вычислений основывается на эквивалентных преобразованиях разностного уравнения, описывающего рекурсивный фильтр, и позволяет добавить в циклы конвейерные регистры, а ресинхронизация позволяет оптимально разместить конвейерные регистры по вычислительному устройству.
Представим разностное уравнение (4) в виде
Уп = г)п~а1уп_1-а2уп^2, (6)
где vn = bQxn + VB-i + Ь2хп_2.
Используем метод опережающих вычислений. На основании (6) запишем:
Уп-1 = ^пА-ЩУп-2 ~а2УП-3' (7)
Уп-2 = vn-2 ~а1Уп-ъ -а2Уп~4- (8)
Уп-d = vn-d - aiyn-d-i - агУп-л-2-
Подставим (7) в (6):
Уп = +К-<*2)уя-2 +а1а2Уп-з- (9)
Подставим (8) в (9):
Уп = %~ + («I2 " вгН-2 "
-(а?-2а1а2)уя^-(а?а2-а%)уя_4. (10)
Продолжая этот процесс, можно получить разностное уравнение от любых индексов переменной у.
Обозначив коэффициенты при через Д, а при у„^1_1 и уп^_2 через К\а и можно записать
общий вид уравнений вида (9) и (10):
л
Уп=*>п + X + К1лУп-Л-Х + К2*УП-*-2'{\ 1)
1=\
Параметр с1 характеризует уровень конвейе-ризованности фильтра и соответствует количеству дополнительных конвейерных регистров (задержек), включаемых в циклы рекурсивной части фильтра. Коэффициенты Ка1 и Кл для любого сI можно получить описанным выше способом.
Разностному уравнению (11) соответствует ГПД, показанный на рисунке 2.
Используя метод ресинхронизации можно распределить й дополнительных конвейерных регистров 17,18,... ,19 по вычислительным устройствам 14, 15 и 16 так, чтобы минимизировать время вычислений в рекурсивной части фильтра [3,2].
Для вычисления коэффициентов К\а и К2Л можно получить рекурсивные формулы.
Запишем уравнение (11) для уровня конвейеризации ^ = /-1
Уп=*>п+А 1 + А2 ■ *>п-2 + •.. + Д-1 • +
+ (12)
Запишем уравнение вида (6) для уп_(
УпЧ = ь^-ау^-а2уп_,_2. (13)
Рис. 2. ГПД конвейеризованного рекурсивного фильтра
Подставим (13) в (12) и после преобразований получим
У« = *>*+А1 • Ц.-1 + А2 • Ъ-2 + ''. ■+ Д-1 • »,-1+1 +
Отсюда, параметры уравнения (11) для ( = = 1, 2,... определяются следующим образом
А
при начальных условиях /С10 = — К20 = -а2.
Коэффициенты Д, ЛГ2, можно также выразить через Д, Дч и Д_2
Д ■Д_1-а2-Д_2; (14)
Ю^-^-Д-^-Д^; (15)
/а,=-я2-Д, (16)
при начальных условиях Д, = 1, А_1 = 0.
Очевидно, что метод опережающих вычислений изменяет структуру конвейеризуемого фильтра с передаточной функцией (5). Для того чтобы разобраться в сути этих изменений, необходимо понять, как изменяется передаточная функция фильтра вследствие конвейеризации.
Из рисунка 2 видно, что в приведенной структуре можно выделить три последовательно включенных фильтра:
1) нерекурсивный фильтр с передаточной функцией
Нх{2) = Ь0 + Ь1- г"1 + Ь2 ■ 2~2 =
= (1-112~1)(1-22 -2"1);
2) нерекурсивный фильтр с передаточной функцией
Н2(
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.