автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Рекурсивная цифровая фильтрация со стохастическим округлением

МИНИСТЕРСТВО НАУКИ, ВЫСШЕЙ - ШКОЛЫ И ТЕХНИЧЕСКОЙ ПОЛИТИКИ РОССИЙСКОЙ ФЕДЕРАЦИИ РОССИЙСКИЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ

На правах рукописи

РЕТИНСЯАЯ Ирина Владимировна

УДК 681.51.09

РЕКУРСИВНАЯ ЦИФРОВАЯ ФИЛЬТРАЦИЯ СО СТОХАСТИЧЕСКИМ ОКРУГЛЕНИЕМ

Специальность 05.13.17 - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - 1992 г.

, • ' ч >

^ . ' .-■■ у' :')

Работа выполнена в Московском Лесотехническом институте. Научный руководитель - доктор технических наук,профессор,

лауреат Государственной премии Домрачев В. Г.

Официальные оппоненты: - доктор технических наук,

профессор Баранов Л А. - кандидат технических наук , старший научный сотрудник Бельгий В. В.

ведущая организация - НИИ "Квант"

(¿Н)иЛ 1992г. в час.

Защита состоится "7 " (¿гугСР1' 1992г. в / • час. на заседании специализированного соЕ&та

по адресу:

МоскЕа, ул. Иепкина ,д 22 .РосНИИ ИТ и АП. С диссертацией мо.тао познакомиться в библиотеке института.

Автореферат разослан

Ж 992г.

Ученый секретарь специализированного совета

д. т. н. , профессор Зайцева К. Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Важнейшими видами обработки информации являются различные преобразования цифровых рядов и их совокупностей. Такие преобразования необходимы, например, для усиления составляющих, несущих полезную информацию, ослабления помех и разделения сигналов. Эти процедуры объединяются понятием цифровой фильтрации. При фильтрации цифровых рядов основные трудности связаны с большим объемом используемой информации. В связи с этим важное значение имеет экономия времени обработки. Эта задача требует создания экономичных алгоритмов фильтрации.

В настоящее время большое распространение получила линейная цифровая фильтрация, которая осуществляется с помощью рекурсивных и нерекурсивных алгоритмов, а так;«е с использованием быстрого преобразования ^урье. Каждый из перечисленных алгоритмов цифровой фильтрации имеет свои достоинства и недостатки.

Рекурсивные фильтры, с помощью которых осуществляется линейная цифровая фильтрация, рассматриваемые в диссертационной работе, обладают рядом преимуществ, т.к. позволяют значительно сократить объем вычислений и требуют гораздо меньшего объема памяти для хранения коэффициентов по сравнению с другими алгоритмами преобразования сигналов. Это позволяет значительно сократить габариты аппаратуры и время~'обработки.

Однако рекурсивные фильтры используются в настоящее время недостаточно широко. Это объясняется наличием в них полом-тельной обратной связи. На практике это приводит к искажению их характеристик, а в некоторых случаях к потере фильтром устойчивости из-за накопления ошибок округления.

Предлагаемые в диссертации методы и алгоритмы рекурсивной

фильтрации с вероятностным округлением позволяют расширить область использования рекурсивных цифровых фильтров, значительно сократить время 'вычислений, что' является актуальной задачей в сеязи с увеличением объемов обработки цифровой информации.

Целью работы является разработка методов и алгоритмов рекурсивной цифровой фильтрации сигналов, устойчивых,« ошибкам округления.

Для достижения поставленной цели решались следующее взаимосвязанные задачи:

- проведение анализа факторов, влияющих на величину ошибок округления в рекурсивных фильтрах и методов оценки этих ошибок;

- теоретическое обоснование и разработка методов и алгоритмов одномерной рекурсивной фильтрации, устойчивой к ошибкам округления;

- исследование методом имитационного моделирования предложенных алгоритмов фильтрации-.

- разработка методов и алгоритмов расчета коэффициентов двумерных рекурсивных фильтров для реализации на ПЭВМ;

- разработка и исследование алгоритмов двумерной рекурсивной фильтрации, устойчивых к ошибкам округления.

Методика исследования основана на использовании операционного исчисления, методов нелинейного программирования, статистических методов и методов имитационного моделирования на ПЭВМ.

Нзучная новизна работы заключается в следующем:

- получены оценки ошибок для рекуррентной мультипликативной процедуры, включающей алгоритм вероятностного округления :

- разработаны метод и алгоритмы одномерной рекурсивной фильтрации с вероятностным округлением коэффициентов, устойчи-

вкй к ошибкам округления;

- доказано, что параметры, характеризующие величину ошибки округления, при использовании предложенных методов и алгоритмов с вероятностным округлением,, уменьшаются по сравнению с,традиционными алгоритмами округления;

- разработаны алгоритм расчета на ПЭВМ коэффициентов двумерного рекурсивного фильтра с процедурным заданием условий устойчивости;

- предложены пути снижения влияния ошибок округления на работу двумерных рекурсивных фильтров, уменьшающие дисперсию результирующей ошибки.

Практические результаты диссертационной работы представляют собой :

-алгоритмы и программы одномерной и двумерной рекурсивной цифровой фильтрации, устойчивой к ошибкам округления;

-пшют прикладных программ для расчета коэффициентов двумерных рекурсивных фильтров.

Полученные в работе результаты могут также найти применение в радио-, гидро- и звуколокации, при сжатии данных в телеметрии, при обнаружении сигналов и фазовой подстройке частоты дальней космической связи, при анализе речи в системе синтетической телефонии, при обработке фото-телевизионной информации, при моделировании динамических систем на ЭЕМ, при обработке сигналов е метеорологии, медицине, геофизических исследованиях и т. д.

Реализация и внедрение. Разработанные алгоритмы преобразования сигналов с использованием стохастического округления и методики расчета двумерных рекурсивных Фильтров для измерителей перемещений использовались при отработке перспективных требований к цифровым преобразователям угла в

интересах Министерства Обороны. Результаты диссертационной работы использовались.' при создании трактов измерения параметров движения микропроцессорного поездного устройства автоведения поездов метрополитена. Способ вероятностного округления при цифровой фильтрации применен также в программе управления прицельного торможения поезда метрополитена в микропроцессорных поездных устройствах автоведения. Результаты внедрения подтверждены документально. ■

Апробация работы. Основные результаты работы докладывались на научно-технической конференции "Технические средства автоматизации научных исследований" (М. 1977), научно-технической конференции "Устройства обработки информации" (М. 1983), на международной конференции и школе-семинаре "САПР-92" (Симферополь, 1992), а также неоднократно докладывались на ежегодных научных конференциях ГАНГ им. И. М. Губкина и ШТК

Публикации. По теме диссертации опубликованы 8 печатных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения и приложения. Основной текст работы изложен на 120 страницах машинописного текста, содержит также 40 страниц рисунков, 10 таблиц. Список литературы включает 72 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулирована цель исследования, обоснована структура работы и ее краткое содержанке.

В первой главе сделан обзор источников ошибок округления при реализации различных алгоритмов одномерной рекурсивной

фильтрации. В ней также рассмотрены способы оценки ошибок округления и приемы, используемые для снижения их влияния на работу реальных фильтров.

В общем случае цифровые рекурсивные фильтры задаются с помощью разностного уравнения:

Существуют три источника ошибок в цифровых фильтрах, возникающие из-за ограниченной длины машинного слова :

1) квантование (или округление) входного сигнала на ряд дискретных уровней;

1

2) квантование коэффициентов (1Л и с^ фильтра по сравнению с точными расчетными значениями;

3) накопление ошибок за счет неизбежного- округления результатов арифметических операций.

Из-за наличия указанных Еыше ошибок вместо точной последовательности -С > на выходе фильтра получается

некоторая искаженная последовательность { >.

Способ реализации заданной точной характеристики фильтра"! "а именно, прямой,~ канонический или параллельный, существенно влияет на величину результирующей ошибки. Кроме того, существенное значение имеет способ представления чисел.

Как при использовании спецпроцессоров, так и при реализации алгоритмов рекурсивной фильтрации на ЭВМ требуется определить минимально возможную разрядность коэффициентов, при которой характеристика фильтра искажается в допустимых пределах. Эта оценка проводится с помощью интеграла

где

я*, 4- коэффициенты фильтра.

Ч,' - входные и выходные }-тые отсчеты.

где т- теоретическая, а

искаженная за счет

округления, коэффициентов передаточные функции. Другой способ оценки - по математическому ожиданию и дисперсии ошибки

ошибки использован в последующих главах диссертационной'работы для оценки погреиности при реализации предложенных в ней новых устойчивых алгоритмов фильтрации. И, наконец, способ оценки ошибки с помощью имитационного моделирования на ЭВМ "точного" фильтра и "реального" позволяет надежно оценить параметры ошибки при различной разрядности коэффициентов фильтра во всех случаях, когда аналитическая оценка с помощью первых двух способов затруднена. Ошибки округления результатов арифметических операций, когда на вход фильтра подается сильно коррелированный входной сигнал, приводят к появлению эффекта-"мертвой зоны". Эффект заключается в том, что сигнал не достигает нужного установившегося значения при переходе с одного уровня на другой. Известные способы борьбы с этим эффектом не позволяют устранить его полностью. Округление коэффициентов фильтра, имеющего полюса, расположенные близко к единичной окружности, может привести к неустойчивости фильтра. Смещение полюса можно определить следующим образом:

Минимальное число разрядов для построения фильтра нижних частот Ь -того порядка с частотой дискретизации 1/Т с

вычисления п-ного члена

Такой способ оценки

т * с

полисами. расположенными на расстоянии в

. по условию:

где квадратная скобка означает целую часть числа. В диссертационной работе предлагается алгоритм фильтрации с вероятностным округлением коэффициентов фильтра, позволяющий значительно снизить пЛ1-п без потери фильтром устойчивости.

В главе 2 предлагаются и исследуются методы и алгоритмы использования вероятностного округления при реализации одно-, мерных рекурсивных фильтров. На основе подходов, выработанных в главе 1, делаются аналитические оценки ошибок для предложенных алгоритмов. Проводится сравнительное моделирование реальных фильтроз различных- порядков, использующих алгоритмы вероятностного округления и детерминированного округления и изучение их характеристик.

Процедура вероятностного округления состоит в том, что при округлении числа в двоичном представлении

отбрасываемая его часть заменяется единицей переноса с

го разряда. Показано, что при вероятностом округлении сшибка в среднем всегда равна нулю, при детерминированном округлении

что выполняется далеко не всегда Последнее и приводит к накоплению ошибок при детерминированном округлении.

Процедура вероятностного округления может быть реализована аппаратно или же программно на ЭВМ. На примере рекуррентной процедуры в диссертационной работе показаны преимущества использования вероятностного округления в алгоритмах с обратной связью. При детерминированном округлении относительная ошибка округления растет в процессе вычислений, при вероятностном округлении - остается на одном уровне.

В диссертационной работе предлагается и исследуется метод рекурсивной фильтрации, устойчивый к ошбкам округления, на примере одномерного фильтра первого порядка.

Л п

вероятностью, численно равной а , где п - номер округляемо- '

лишь в том случае, когда

- 8 -

Суть алгоритма состоит в следующем. Коэффициенты фильтра хранятся с достаточно высокой точностью в двух регистрах: в первом регистре записываются старшие значащие цифры коэффициента, во втором - младшие или "хвост" числа Перед каждым умножением -на значения входного или выходного сигнала коэффициенты фильтра округляются до некоторого малоразрядного числа, которое помещается в один регистр. Округление производится по одному из алгоритмов вероятностного округления, описанных в диссертации, причем для сравнения со случайным числом используется "хвост" числа, хранящийся во Етором регистре. Затем все действия выполняются с малоразрядными числами.

Рассмотрен простейший фильтр первого порядка с уравнением

Математическое ожидание абсолютной ошибки вычисления п-ного члена ряда, преобразуемого фильтром с учетом того, что случайной является только величина входного сигнала {х>, при детерминированном округлении равна п

-п[х] у,,.

где ¿~- ошибки округления коэффициентов фильтра а и Ь.

При вероятностном округлении математическое ожидание абсолютной ошибки вычисления п - ного члена ряда г, ]=0.

Аналитические оценки, математического ожидания и дисперсии ошибки при вероятностном и детерминированном округлении и случайном входном сигнале совпадают с результатами моделирования указанных алгоритмов фильтрации на ЭВМ. При смещении входного сигнала математическое ожидание ошибки п - ного члена выходного ряда растет пропорционально смещению, при вероятностном округлении - остается практически на одном уровне. Исследование устойчивости фильтра показало, что математическое ожидание системной функции фильтра первого порядка при вероятностном

округлении его коэффициентов с точностью до величин второго порядка малости равно значению передаточной функции, полученному для точного значения коэффициента.

Имитационное моделирование на ЭВМ подтвердило этот вывод и показало, что при уменьшении числа остающихся разрядов фильтр с детерминированиям округлением становится неустойчивым уже при разрядности коэффициентов 7-8, в то время, как фильтр с вероятностным округлением не теряет устойчивости даже при округлении до 2-3 разрядов. Кроме того, как показали результаты моделирования, происходит меньшее общее искажение частотной характеристики при вероятностном, чем при детерминированном округлении.

Эффект "мертвой зоны" , рассмотренный в первой главе, полностью устраняется при использовании вероятностного округления результатов арифметических операций, так как в этом случае „. ? л-к , с-

где & - ошибка округления произведений на 1-том шаге.

Исследование режекторных фильтров, весьма чувствительных к ошибкам округления, показало, что при округлении до малого числа разрядов при детерминированном округлении не происходит подавления нужной частоты. При вероятностном округлении, несмотря на . некоторое искажение частотной характеристики, нужная частота подавляется. Кроме того, при вероятноетом округлении для передаточной функции, имеющей полюса, близко расположенные к единичной окружности, может быть получена амплитудно-частотная характеристика с большей глубиной подавления, чем при использовании полноразрядных чисел.

В главе 3 рассматриваются способы реализации методов рас-

чета коэффициентов двумерных рекурсивных фильтров, минимизирующие среднеквадратическую ошибку частотной характеристики фильтра Предлагается реализация метода расчета коэффициентов рекурсивного фильтра по известным коэффициентам нерекурсивного фильтра Для передаточной функции вида

' Г

'гП './

где ) Н^ */V^ - размерности матриц коэффициентов,

различные формы ее реализации существенно влияют на величину результирующей ошибки округления и требуемые объемы памяти для хранения коэффициентов и результатов промежуточных операций.

Для двумерных рекурсивных фильтров в настоящее время не существует надежного критерия определения устойчивости, так как в общем случае нельзя разложить на множители двумерный полином 8(2/,г,,). Условие устойчивости двумерного фильтра требует, чтобы коэффициенты К разложения частотной характеристики фильтра г.о отрицательны).! степеням 2 , и являлись абсолютно суммируемыми, то-есть, чтобы

СО С!

I

И К

I < Со

_ П |

т- < п--/

Задача расчета двумерного рекурсивного фильтра состоит в выборе коэффициентов а-, Ь./ таким образом, чтобы частотная характеристика полученного в результате расчета фильтра аппроксимировала бы некоторую заданную характеристику наилучшим образом, а сам фильтр был бы устойчивым.

Целесообразно использовать при .расчете коэффициентов фильтра методы оптимизации. При этом функция цели задается ' как сумма квадратов отклонений заданной и полученной

- 11 -

амплитудных характеристик фильтра в Биде:

Г (г) t [Кт1-Х„Х

т-! п-н и ■>

где Ч - заданная характеристика фильтра. Ограничения, обеспечивающие устойчивость фильтра, задаются процедурно. При этом единичная окружность разбивается на некоторое, экспериментально подбираемое число точек с модулем г1 , равным единице, а на корни уравнений • 3(24 2^) накладывается ограничение: модуль полученных корней не должен превышать единицы. Поскольку начальная точка не является допустимой, так как в общем случае невозможно задать изначально коэффициенты устойчивого фильтра, поиск решения ведется по методу скользящего допуска

Для многих видов двумерных фильтров в настоящее время существует методшса получения коэффициентов нерекурсивного фильтра. Допуски, дан некоторый желаемый оператор нерекурсивного фильтра ВСг^г^) и требуется найти коэффициенты А - такого рекурсивного фильтра

чтобы удовлетворялось следующее равенство:

Степень приближения будет задаваться по критерию минимума среднеквадратической ошибки.

г," V

После нахождения коэффициентов В • А_ находятся как

Л- Л # /?;/<-/ .

Л '''с/ ^

Реализованные по описанной методике алгоритмы позволили рассчитать коэффициенты фильтров, использованные для исследования ошибок округления в следующей глаЕе.

В главе 4 исследуется возможность использования вероятностного округления для уменьшения влияния ошибок округления и предлагается алгоритм округления, уменьшавший дисперсию ошибки округления при цифровой двумерной фильтрации.

Как и для одномерных фильтров, рассматриваются различные источники ошибок округления. Аналитическую оценку ошибки округления произведений для двумерных рекурсивных фильтров можно получить для наиболее простых случаев, например, для фильтра первого порядка. В общем случае получить такую оценку невозможно ввиду сложности алгоритмов фильтрации. Наиболее реален путь моделирования фильтра на ЭЕ!.1 При этом округление коэффициентов фильтра до нужного числа разрядов производится программным путем, а реальный фильтр представляется в виде параллельного соединения идеального и паразитного фильтра, определяющего ошибку округления. Тогда 2 - преобразование вводного

сигнала записывается в виде:

гдес^л^;Дг- погрешности коэффициентов ЬЛ1 фильтра

соответственно, НгГ)[г, ] - передаточная функция фильтра с коэЭДициентами, заданными с максимально возможной точностью.

Для того, чтобы уменьшить ошибку округления коэффициентов фильтра, существует несколько путей.

Во-первых, увеличение разрядности спецпроцессора, проектируемого для целей фильтрации, что приводит к увеличению объема аппаратуры и времени обработки сигналов.

/

Во-вторых, тщательное изучение и усложнение форм реализации фильтров с целью уменьшения результирующей ошибки округления коэффициентов. В конечном итоге последнее также приводит к некоторому увеличению объема аппаратуры и времени, затрачиваемому на получение одного выходного отсчета

В-третьих, применение способов округления коэффициентов фильтра, отличных от традиционных способов округления по дополнению и округления отбрасыванием.

В диссертации предлагается для двумерных рекурсивных фильтров применить вероятностный способ округления следующим образом. Пусть_ коэффициенты фильтра а, - ,Ь/ хранятся с достаточной точностью, оцениваемой в 15-18 двоичных разрядов. Перед каждым умножением они округляются по вероятностному алгоритму до значительно меньшего числа разрядов, а затем все действия производятся с малоразрядными числами.

Результаты имитационного моделирования двумерного рекурсивного фильтра с передаточной функцией

позволяют сделать еывод, о том, что применение вероятностного округления дает очень малую среднюю ошибку по сравнению с детерминированным округлением, однако дисперсия ошибки остается сравнимой с дисперсией ошибки при детерминированном округлении. В диссертации предлагается также для уменьшения ошибок применить способ округления, являющийся симбиозом-метау алгоритмами детерминированного и вероятностного округления.

Полученные результаты указывают на то, что дисперсия ошибки в этом случае уменьшается еще в несколько раз по сравнению с вероятностным округлением, хотя математическое ожидание ошибки несколько возрастает.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработаны метод и алгоритм использования вероятностного округления в рекуррентной мультипликативной процедуре. Сделаны оценки математического ожидания и дисперсии ошибки для детерминированного и вероятностного округления применительно к указанной процедуре. Результами моделироваши на ЭВМ подтверждены аналитические еыводы об устойчивости рекуррентной процедуры с вероятностным округлением к ошибкам округления и неустойчивости такого же вычислительного процесса с детерминированным округлением.

2. Разработан метод и алгоритм одномерной рекурсивной фильтрации с 1 использованием вероятностного округления коэффициентов фильтра Сделаны оценки математического ожидания и дисперсип ошибки фильтра первого_ порядка с вероятностным округлением. Проведено исследование предложенного алгоритма фильтрации путем моделирования на ЭВМ. Анализ переходных характеристик и автокорреляционных функций различных фильтров, а гакхе их устойчивости показата значительное преимущество ?~1гаритма фильтрации с вероятностным округлением.

3. Исследован эффект '"мертвой зоны", связанный.с ошибками округления результатов арифметических операций. Доказано экспериментально и аналитически, что применение вероятностного округления полностью устраняет этот паразитный эффект.

4. Проведено экспериментальное исследование путем моделирования на ПЭВМ одномерных фильтров Еторого порядка с с вероятностным и детерминированным округлением коэффициентов. Показано, что при вероятностном округлении, используя фильтр с

полюсом, близко расположенным к границе единичной окружности, может быть получена' амплитудно-частотная характеристика фильтра с глубиной подавления, большей, чем при использовании полноразрядных чисел. При этом достигается значительный выигрыш в габаритах аппаратуры и скорости фильтрации.

5. Доказано, что при уменьшении разрядности коэффициентов фильтра параметры амплитудно-частотной характеристики при вероятностном округлении изменяются значительно меньше, чем при детерминированном округлении. Показано, что границы устойчивости одномерных фильтров второго порядна раздвигаются в случае использования вероятностного округления его коэффициентов.

6. На основе анализа алгоритмов двумерной рекурсивной фильтрации и методов определения устойчивости двумерных рекурсивных фильтров разработана процедура реализации алгоритма определения устойчивости двумерных фильтров, используемая при расчете его коэффициентов.

7. Ка основе идеи метода наименьших квадратов- разработаны и реализованы на ПЭВМ две модификации алгоритма расчета коэффициентов двумерного рекурсивного фильтра как задачи нелинейного программирования к метод расчета коэффициентов рекурсивного фильтра по известным коэффициентам нерекурсивного фильтра.

3. Проведен анализ ошибок округления в двумерных рекурсивных фильтрах и предложена схема представления реального фильтра, которую следует использовать для оценки результирующей ошибки.

9. Предложены две модификации двумерной рекурсивной фильтрации, позволяющие снизить математическое ожидание и дисперсию ошибки, вызванной округлением коэффициентов фильтра.

10. Результаты диссертации использованы при отработке перспективных требований к цифровым преобразователям угловых, перемещений в интересах'Министерства Ооороны и при создании

измерительных трактов в микропроцессорных поездных устройствах для метрополитенов.

Ш теме диссертации опубликованы следующие работы:

1. Гладкий ЕС., Ретинская Я В. -Программное моделирование процедуры вероятностного округления чисел.-Программирование, Акад. наук СССР, Ы-1975, с 90-93.

2. Ретинская II В., Михалева Г. В., Надирадзе И. А. Случайный.поиск и метод скользящего допуска в решении задачи оптимизации разработки газовых и газоконденсатных месторождений. - Труды МШХ и ГП им. И. М. Губкина. - вып. 140-11:1978, с. 190-196.

3. Михалева Г. В., Ретинская И. В. Цифровая обработка сигналов с применением вероятностного округления.- Вопросы кибернетики N54 НСКП "Кибернетика"Акад. наук СССР. 1979, с 87-94.

4. Ретинская /1. В. Оценка искажений системной функции цифрового фильтра при вероятностном квантовании его -коэффициентов, -рук. депон. во ВШИОЭКГ- М: 1979, январь.

5. Ретинская И. В. К и.ализу ошибок округления при цифровой фильтрации рядов. - З^отоды прикладной матем. в нефт. и газ. проы. -М.: .1978, с 196-201.

6.'. Ретинская И. В. Метод расчета двумерных рекурсивных фильтров, -рук. деп. во ВНИИЭГАЗПРОМ. - М.: 1980, март.

■ 7. Ретинская И. а Моделирование цифровых фильтров при проектировании информационных систем. -Тезисы доклада международной конференции "САПР-92". Воронеж, 1992.

8. Ретинская И. а Споесб оценки оптимальной разрядности цифрового фильтра в информационных системах. -Тезисы доклада

4

международной конференция "САПР-92". Воронеж. 1992.

Ч

Соискатель ^ч'^с^/М (