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

о оь; 9'1]

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РСФСР ПО ДЕЛАМ НАУКИ И ВЫСШЕЙ ШКОЛЫ МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО ОБРАЗОВАНИЯ РСФСР

ТОМСКИЙ ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. В.В. КУЙБЫШЕВА

На правах, рукописи *ДК 719.513

КА1ШРОВА Лилия Фёдоровна

ПОСТРОЕНИЕ 'ПРОВЕРЯЮЩИХ ТЕСТОВ В ПРОЦЕССЕ ДЕКОМПОЗИЦИОННОГО СИНТЕЗА УПРАВЛЯЮЩИХ АВТОМАТОВ

Специальность 05.13.01 - Управление в технических

системах

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

Томск 1991

»

5 л / ■ у

' Л; /;'■■/

Работа выполнена в Таллиннском техническом университете

Научный руководитель:

кандидат технических наук, доцэнт Кеэваллик А.Э.

Доктор технических наук, профессор Сперанский

Официальные оппоненты:

'Ведущее предприятие:

Кандидат технических наук, доцент Матросова А,Ю. Институт проблем управления АН СССР (Москва)

Защита состоится

ИЮНЯ 1991 г. в /5" часов

на заседания специализированного совета Д.063.53.03 при Томском государственном университете им. В.В.Куйбышева по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться в научной библиотеке Томского государственного университета.

Автореферат разослан. М Ъй 1991 г.

Учёный секретарь

специализированного совета

Д. 063. БЗ. 03 I

кандидат физико-математических т __

Б.Е. Трцвоженко

«я£| ' -3-

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

Актуальность р а б ~> т ц, Одной из пачисйпих

>> > V

проблем,которые шзникзат при проектировании систем управления, является проблема синтеза упрагуяг/дего усройстпа с одновременной средствами тестирования. Поэтому ва;кно обеспечить контроль работоспособности систему ещё на ранних стадиях её проектирования. Модель конечного автомата и методп декомпозиционного синтеза устройства широко используются для целей проектирования и контроля систем управления. Тесты, построенные на основе контрольных экспериментов с автоматами, учитывая? ин^ормаига об объекте на разннх уровню: абстракции, обеспечивают высокую достоверность результатов проверки и уменьшают размерность ропаетх задач. Поэтому актуальными яаляются задач! приложения' теории экспериментов с автоматами для построения тестов в процессе декомпозиционного синтеза дискретна« управлявших устройств .

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

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

Научная новизна работы состоит в следующем: проведен анализ свойств микропрограммных автоматов, реализованных в базисе программирует!* логических устройств,и влияния неисправностей на их поведение;

предложен метод построения проверяющего теста для микропрограммного автомата и сети микропрограммных автоматов без зыходов.реали-зопаннчх на 1иг.!;

I-ok Д^кЛА .у 1Ь с о : ■ -

..■'.'] ¡'ocrrc":;.:;: . .-p--- i: .n j; •

, i>;•:: u'j::;'.;;'Oi.~ г л;.-

nnc .". It г: с /г; ;

;.iö-;c;; iincпо лп;\пр1ц1>>-иик)оте-Л для некогоршс специальны;; глйссои ьыг>..

преодолен метод щ>оо0раоосзш;л ирьмззолыюго конечного автомата о ««домат, обло?,а--.'Л1й короткой контрольной послёдоютчльностьа.

Ii р а к т и ч е с ко и з л а '«* е н и е р а б о т ы определяется тем, что

разработаны алгоритмы построения проверяющих тестов для ШТА и сети ЫПА без . выходов, реализованной на программируемых: логических мат -рицах;

предложены метод и алгоритмы построения тестов для автоматных сетей, компонентам» которых: являются автоматы Liypa или Мили. Тест является композицией контрольны: последовательностей компонент сети;

разработаны алгоритмы синтеза легко тестируемых автоматных

сетей:

предложена методика построения проверякаих тестов д,|Я ДУУ, ре -ялизовакиж в виде сети микропрограммны?: автоматов без еьпсодов. Методика использована при построении тестов, обиарукииа'оцих одиночные неисправности в ШМ и константные неисправности на линиях соединения оленинто?;

пзрот/.гльшие катода иогш придоквгте в авюматиаироврцной оке тепло деко:.и:оз;н-ионного синтеза ДУУ , шедренной б практику про-

В и с ,г, в.с :: и с ¡.- о з у л ь г а т о и. Результчтч ^neveiu'iV'.no'-iH работа т: нихиичрнуи прочтлгу в институте электроники к

лнтс:;ы;с Л тс-:а;ц:;: г. Гиги, г; 'Гатлпш-ютоп ИУД Зет, НПО БП1, в jroiicvpy -кюг.сг.о:-: 6.?р "О ¡.олргг'ур'' г. лары;очч.

_ ¿г _

г

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

Публикации и апробации р а 5 о т и . Зсего по данной тематике опубликовано II печатных работ, в диссертационной работе использовано 9, перечень которых приввдбн в <онце автореферата.

Результаты работы докладывались на порвой Международной сонференции. молодах учбних "Проблеш проектирования 1! применения декретных систем в управлении" (Минск, 1977г.);

- IV,V и VII Всесоюзных совещаниях по технической диагностике I отказоустойчивости (Черкассы 1979г., Суздаль 1983 г., Саратов :990 г.

- постоянно действующем семинаре в НШПШ(Донецк, 1984г.);

- всесоюзном совещании по отказоустойчивости и надб^юсти Ленинград, 1986 г.)

- постоянно действующем семинаре "Теория автоматов и еб грилокеш1яи ( Рига, 1986 г.);

научно - технической конференции "Пути повышения фиктивности использования вычислительной • техники" (Таллинн, 96Эг.);,

Международной конференции по отказоустойчивым ■ычислителышм системам (Варна, 1990г.);

- постоянно действующем семинаре 'Теория проектирования декретных устройств " в ТТУ (Таллинн, 1991 г.).

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

-в -

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

В заключении сформулированы основные результаты, приведенные i раооте. В приложении приведены акты о внедрении. Работа содержи: 180 страниц машинописного текста-

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

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

Глава 2.П ос троение проверяющего теста ДУУ, реализованного на ПЛМ.

В первом разделе данной главы описывается метод- построения проверяющего , теста для микропрограммного автомата, реализованного на одной ПЛМ. Рассмотрим МПА А=( (O.D^.S, (0,1 )M,ft>,A), котором можно сопоставить множество интервалов переходов U=iu1,.. .ut>, гл u1, 1=1, ...,t,содержит только существенные переменные. Пару (ulte

назовём обобщённым переходом автомата, если из состояния а существует переход под действием и1.

Допустим, что размерность автомата А такова, что его можно реализовать на одной ГОШ (Ь,М,я,т) с памятью. Здесь Ь--число входов, М-число выходов, д-число термов, . - число разрядов регистра в цепи обратной связи. Будем рассматривать неисправности в точках пересечения линий ГОШ. Появление соединения в точке пересечения линий, где его по должно быть,назовём неисправностью типа ПС (появление соединения). Нарушение соединения в точке пересечения линий ПЛМ, если оно там было, назовём неисправностью типа- НС (нарушение соединения).

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

Во втором разделе этой главы приводится алгоритм построения проверяющего теста для МПА,- ,: реализованного на одной ПЛМ.

В третьем разделе главы рассматривается сеть микропрограммных полуавтоматов, построенная путём декомпозиционного синтеза микропрограммного автомата А.

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

- а -

теста для сети МППА-ов относительно неисправностей в компонентах сети, реализованной на ПЛМ.

Глава 3. Построение проверяющего теста для автоматной сети.

В первом разделе рассматриваются последовательные сети, состоящие из двух компонент. Показывается, что рабочая область сети содержит не все переходи, заданные в описании второй компоненты. Анализируются проблемы, которые возникают при построении провряющего теста сети кал композиции контрольных последовательностей e'j компонент. Основной из mix является то, что на входы второй компоненты в общем случае невозможно подать контрольную последовательность, так как она не всегда является допустимым выходным словом первой компоненты.

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

V з^з^ S (X.i(at)!i VV'* где 1-номер компонентного автомата. ' Показано, что для этого класса сетей существует проверяющий тест, являющийся композицией контрольных последовательностей компонентных автоматов сети.

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

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

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

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

Глава 4. Методы построения контрольных тоследовательносгей.

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

Пусть А=(Х,3,У,бД)- контрол1фуемый конечный автомат, таеющий диагностическую последовательность <1 длины г, тс-разбиение ¡а множестве состояний автомата А, (тс)- фактор-граф графа 1ереходов автомата А, порождаемый разбиением г. Допустим, что 1-ому Злоку. разбиения % можно сопоставить множество 1 (х ) слов длины г в выходном алфавите У, определяемое некоторой циклической [•-последовательностью • •-Уг • Причем 12(1)1 = 1^1.

Автомат АеЖтсЛ) (обозначение А(1С,Г)), где - класс

автоматов,для которого выполняются следующие условия:

1. На множестве Э состояний любого автомота АСЯ(1С,Т) существу-гс разбиение тс, порождающее эйлеров фактор-граф СА(тс).

2. Р выходном алфавите У существует множество Т циклических г*~ юслодсв:.!'!'-! ли юстей.

3. Мевду множествами г и Т существует взаимно-однозначное отображение Г: *=» |1с1| = |г(,с^)|.

В первом разделе раасматривается метод построения контрольной последовательности для автоматов класса 9Цтс,Т), доказывается, что верхняя оценка Ь на длину к онтрольной последовательности удовлетворяет следующему неравенству: ' I $ п + г (I тс! + (ш-1 )п) + (пИ )£ 1тс11г и, следовательно, пропорциональна величине £ ',к±)г

Предлагается алгоритм построения разбиения тс на множестве состояний Б, порождающего эйлеров фактор-граф.

Допустим, что 91{1с)-класс автоматов, удовлетворяющий условию I. Автомат АеИ(тс), если и только если на множестве состояний £ существует разбиение % такое, что граф Сд(,гс)-связный и V те (£ - ^)=0),

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

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

А ГЧ»

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

А л. « Л

Автоматы А и А-автоматы Мура, автомат А отличается от А

- 1Г -

л л * «V

определением множества У: если то Автомат Л не имеет

диагностической последовательности в то время как автомат А (А) может об иметь.

Предлагается метод построения контрольной последовательности

для автомата А и доказывается, что еб длина не превосходит

следующей величины: 1x1

т1 1^1011^1+1), где 1шл1=1Ха1 ¿=1

В следующем пункте главы приводятся алгоритмы построения

»V Л

сменных автоматов А, А и алгоритмы построения контрольных последовательностей.

Глава' 5. Построение легкотестируемых

элементов автоматных сетей. В разделе I, главы 5 рассматривается ДУУ," которое можно описать любым автоматом А класса 21(т,п,р). Здесь же показывптся, что автомат А(тс,Т) преобразуется в контролируемый автомат добавлением одного символа во входной алфавит автомата, реализующего исходный. Если А не является автоматом класса Я(тс,Т),

, л

то доказывается, что существует автомат А(тс,Т)еа(пи-у,п,р),

АЛ Л

реализующий А такой, что АеЗЦтс). При этом для разбиения % в автомате А выполняется следующее условие:

V 1С (£ (^--фаПс^).

Таким образом, любой автомат Аеа(т,п,р) преобразуется в контролируемый автомат класса ЗЦтс.Т), длина Ъ контрольной последовательности которого удовлетворяет следующему неравенству: К 2п + 2(Ь0 +т)п где 1; -максимальная полустепень захода некоторой вершины

графа переходов автомата А.

Во втором разделе этой главы рассматриваются алгоритмы синтеза автоматов, имеющих минимальную длину контрольной последовательности в классе автоматов 91(1с,!Р),

Метод построения контролируемых автоматов, рассмотренный в разделе один не накладывает ограничений на число контрольных точек в синтезируемом автомате. В разделе три рассматривается метод синтеза контролируемых ДУУ, при некоторых ограничениях на число дополнительных входов и выходов, называемых контрольными точками, в синтезируемых автоматах. Пусть Аей^.Т), введём тройку чисел Оп',п',р'), задающую допустимое число дополнительных символов входного, выходного и внутреннего алфавитов в синтезируемом автомате А.

В разделе 4 рассматривается алгоритм синтеза контролируемого автомата при ограничениях на число вводимых контрольных точек автомата.

В разделе 5 излагаются методы синтеза контролируемых асинхронных автоматов классов, рассмотренных в главе два. При синтезе контролируемых асинхронных автоматов предполагаем, что число дополнительных контрольных входов и выходов & синтезируемом автомате не превышает заданной величины." Одним из критериев синтеза полагаем критерий минимальности контрольной последовательности синтезируемого автомата.

Методы синтеза контролируемых асинхронных автоматов можно разделить на два класса:

I. Методы преобразования автомата А в контролируемый автомат А'>А, для которого существует контрольная последовательность, идентифицирующая состояния автомата Л и переходы между ними.

■ 2. Методы преобразования автомата А в контролируемый автомат

', ''УМ:' опЧ'ЧМ ¡¡'.Т.'МПК^РШШ Ко'ПССОЬ. I ¡'".'Ли' ¡1;.;;

¡г.ч\\'.' ■!■ I |!'"'0Т1-, ч?» Л' ",;!1')".1И!'1ПП'ПУ1.'Т ■ = ; :

", ■". ' 'и!/■,<■■■':,'

¡> ;-;|1Ь':м '\'!',"!т> 1) н-чтсно-и-Ь(А' >.',-V":"■;"тп; Л

ПГ.ОДЯ'Г Г Го аТП'ои.ТШ С ЧИСЛ».* 00'_Г1 ОЯЧ;!и НО 'ЧлЛЬУММ ''•:!! ! о'!.

Во мором мучио, класс немспраи««. питоротоп -»(А*) ограничивается множеством асинхронных евтопптоп, ваюдеЯ чпгоюат телеку !С ' 13^1, для каждого яеХ. Иряводптоя алгортш сштеяэ контролируешь автонатсп-

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

1. рассмотрен »«ифопрогракмшй автомат, реализованный п базисе ПЛМ. Исследовано влияний неисправностей в 11ЧМ ла класс неисправных автоматов. Цредлсяэн иэтод построешш нровзряюгцег'о теста для ША, являющегося тпоторт отрезком контрольной последовательности ,'Я1Д. Показано, что дама теста суиестнотто корочо длили контрольной даследовотедшости автомата.

2. Разработан метод построения ирешряупего теста Длм авточятаой сети, получовией в рэзультато докогжоаяшошого сянтзза

КИКрОПрОТ'рпм^ЮГЭ ОВТОВаТЭ. 1{ОМ1ГОП9!1Т:1"Л СЙП ЯРДЯПГСЯ

мйкроярограшнн-? автоматы без рнходоз. Сеть "реялчзонаиа и базвео

3. Исслолошю потдот;о исслодов'зтвлыюЯ вптемзтле-й чети, кешенентакк шторой являются автоматы Мура, либо Мядп. Уекпз'Я'с-, что рабочая обдасть второй келктопентн мояег кз содортатт. п-» переходи, гкегки'ся у этого автеичто.

Уотпловил;;:!, что .'лпомлтнал ептъ, гтосгрееш'-зя ггут" • •

дадоИПОРЙЦШЬКТЭ ПТ'П'ОЧ ?"!1ГрСГ!!'ОГр::Г,:Г1НОГО ЯВТШПТЯ, КО«ПОП°ЧТ;^'Л'

которой лв.МИД ¡»-, сОла^оо г сгоИотялмл тестнруегот;;, г;'1:;

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

Исследованы возможности минимизации контрольной последовательности для коночных, в частном случае, микропрограммных автоматов. Определён класс автоматов, для которого контрольная последовательность существенно короче, чем для произвольных автоматов.

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

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

Результаты диссертации опубликованы в следующих работах:

1. Каширова Л.Ф. К синтезу контролируемых автоматов. - В кн.: IV Всес. совещ. по технической диагностике. М.: Ин-т проблем управления, 1979, с. 149-151.

2. Каширова Л.Ф. Синтез автоматов с укороченной контрольной последовательность». Материалы ' Всесоюзной конференции "Автоматизация проектирования ЭВМ". Киев.,Наукова Думка 1979г.

3. Каширова Л.Ф. Построение контролируемых автоматов Л. //Автоматика и телемеханика, Ш1, 1983г. с.141-146.

4. Каширова Л.Ф. Построение контролируемых, автоматов.II. //Автоматика и телемеханика, №2, 1983г. с. 115-122.

" 5. Евтушенко Н.В., Каширова Л.Ф. Синтез легко-контролируемых элементов дискретных сетей. // Автоматика и вычислительная техника. Ж. 1987г. с.78-83.

- 1<Г -

6. Евтушенко Н.В., Наширова Л.Ф. Построение проверяющих последовательностей для последовательных сетей. Вычислительные сети.// Рига. Зинатне. 1988.С.153-163.

7. Каширова Л.Ф., Круус М.Э., Эллервеэ П.О. Построение контрольной последовательности для управляющих автоаматов, реализованных на программируемых логических матрицах.// Труды таллиннского технического университета. 1989г. №696. с. 33-42.

8. Кеэваллик А.Э., Каширова Л.Ф., Круус М.Э., Эллервеэ П.О. Построение проверяющего теста в процессе декомпозиционного синтеза управляющего автомата, реализованного на ПЛМ. VII Всесоюзно совещание по технической диагностике и отказоустойчивости. Тезисы . докладов. '//Москва-Саратов. 1990г.

9. Кеэваллик А.Э., Каширова Л.Ф., Круус М.Э. Построение проверяющих тестов для автоматных сетей.//Труды Таллинского технического университета. 1990г.Л 697. с..5"-<?<Э.

Подписано х печати <5.0$,9?

Бумага типографе кал w . Формат 60x8^ 1/Тб П.л. ( ,уч-изд.л. 0,д? заказ к ДлД Тираж 100

. _ , ;

УОП ТГУ, Никитина,'».