Эксперименты с линейными автоматами

Теория экспериментов с автоматами представляет собой фундамент многих современных методов и средств технической диагностики цифровой аппаратуры. Одной из существенных причин, порождающих сложности при решении упомянутых проблем, является отсутствие, как правило, информации о начальном, промежуточном или конечном состоянии устройства. Для снятия указанной неопределенности и служат так называемые синхронизирующие, установочные и диагностические последовательности, подаваемые при проведении соответствующего эксперимента на входы устройства. В настоящее время теория экспериментов для автоматов общего вида достаточно хорошо развита, и ей посвящен ряд работ. Это работы Мура Э. [26], Гилла А. [11], Глушкова В. М. [14], Яблонского C.B. [46], Богомолова A.M. [2]-[5], Твердохлебова В. А. [40], Грунского И. С. [3]-[4], Кудрявцева В. Б. [23], Скобелева В. Г. [30], Спивака М. А. [39] и др. Полученные результаты позволяют сделать вывод о значительной трудоемкости методов синтеза упомянутых последовательностей. Кроме того, их длины для реальных устройств, описываемых автоматными моделями, очень велики. Вместе с тем, среди реальных устройств существуют такие классы, специфика которых позволяет существенно упростить процедуры синтеза упомянутых последовательностей, причем длины их оказываются значительно короче в сравнении с длинами экспериментов для автоматов общего вида. Так, например, такая ситуация имеет место для устройств, математическими моделями которых являются линейные и билинейные автоматы [8], [10], [12], [44], [45].

Линейные и билинейные автоматы являются математической моделью устройств, широко используемых для кодирования и сжатия информации, в качестве сигнатурных анализаторов, а также при синтезе схем встроенного контроля и систем автоматического управления [1], [15],.

25], [28]. Работы по теории экспериментов с такими автоматами практически отсутствуют, хотя, как уже было отмечено, многие известные результаты и методы для автоматов общего вида могут быть сделаны более эффективными для линейных и билинейных автоматов. Эксперименты с такими автоматами изучались в работах Сперанского Д. В. [33]-[38].

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

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

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

— получение условий существования обобщенных синхронизирующих, установочных, диагностических последовательностей для линейных автоматов (ЛА), разработка методов их построения и оценка длин;

— получение условий существования и построение синхронизирующих, установочных и диагностических последовательностей для сетей из ЛА;

— получение условий восстановления входных сигналов для сетей из ЛА с потерей информации;

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

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

В работе впервые получены следующие результаты:

— получены условия существования обобщенных установочных и диагностических последовательностей для ЛАна их основе предложены методы построения этих последовательностей;

— найдены оценки длин обобщенных установочных и диагностических последовательностей для ЛА;

— получены условия существования синхронизирующих, установочных и диагностических последовательностей Для последовательных, параллельных и параллельно-последовательных сетей из ЛА;

— найдены оценки длин синхронизирующих, установочных и диагностических последовательностей для последовательных, параллельных и параллельно-последовательных сетей из ЛА;

— получены условия распознавания входного слова для трех видов соединений ЛА в сеть, а именно: параллельного, последовательного и параллельно-последовательного;

— получены условия существования синхронизирующих, установочных и диагностических последовательностей для класса билинейных дискретных систем (БС) без запаздывания;

— предложены методы нахождения этих последовательностей;

— получены условия существования синхронизирующих, установочных и диагностических последовательностей для класса билинейных дискретных систем с запаздыванием и методы их построения, а именно: показано, что БС с запаздыванием можно представить как БС без запаздывания и использовать уже полученные результаты.

Полученные нетривиальные окончательные результаты имеют теоретическое значение и могут быть использованы при синтезе схем встроенного контроля и систем автоматического управлений.

Диссертация выполнена в течение 1996;1999 г. г., тема диссертации утверждена на заседании Ученого совета университета (прот. № 3 от 13.11.96). Исследования проводились в рамках следующих грантов: 1) «Разработка методов теории конечных автоматов и формальных языков» -грант Министерства общего и профессионального образования РФ, 19 981 999 г. г.- 2) «Неклассические задачи и средства исследования свойств конечных автоматов» — грант РФФИ № 98−01−113.

Основные результаты получены автором самостоятельно и обсуждались с научным руководителем.

Результаты работы докладывались и обсуждались на международной конференции «Проблемы и перспективы прецизионной механики и машиностроения в управлении» (Саратов, 1997), международной конференции «Математика в индустрии» (Таганрог, 1998), международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 1999), конференции сотрудников механико-математического факультета СГУ, посвященной 90-летию университета (Саратов, 1999), семинарах в Саратовском государственном университете.

По результатам работы опубликовано 7 работ. Одна из них в соавторстве с научным руководителем, остальные самостоятельно.

Диссертация содержит 92 машинописные страницы, состоит из введения, трех основных разделов и списка литературы.

Заключение

.

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