Введение к работе
Актуальность проблемы. Сложность современных систем логического
іравления, таких как протоколы вычислительных сетей, интегральные
:емы и т.п., постоянно возрастает, технологии производства систем
)стоянно меняются и совершенствуются, и, как результат, методы синтеза
ічественньїх проверяющих тестов не успевают за этими процессами.
споліізование математических моделей при синтезе проверяющих тестов
ззволяет автоматизировать процесс построения тестов с гарантированной
хлнотой, т.е. тестов, обнаруживающих все наиболее вероятные
:исправности для данной технологии производства. Однако, если описание
ютемы произвольное, то может оказаться, что известные методы не могут
>іть использованы даже с применением средств вычислительной техники
і-за громадного объема необходимых вычислений. В этом случае
юбходимо минимизировать тесты, доставляемые формальными методами,
(хранив при этом возможность обнаружения наиболее вероятных
:исправностей в системе.
Одной из наиболее широко распространенных математическігх моделей )и синтезе проверяющих тестов для систем логического управления шяются логические сети или сети из конечных автоматов. Поэтому задача инимизации проверяющих тестов для систем логического управления гтодами теории конечных автоматов является актуальной.
Одним из подходов позволяющих упростить и минимизировать юверяющие тесты, доставляемые формальными методами, является раничение множества возможных проверяемых систем. Такой прием пользуется, в частности, при контролепригодном проектировании, когда эоверяемая система в процессе проектирования обеспечивается іециальньїми свойствами, которые улучшают ее тестопригодность. гстопригодность может быть значительно повышена за счет специального юпределения ситуаций, в которых поведение эталонной системы не іределено.
Другой подход основан на модульном строении большинства систем, эичем, в современных системах модули могут быть изготовлены по пличным технологиям. В этом случае инженер по тестам обычно нерирует тесты, обнаруживающие неисправности в каждой компоненте :зависимо от неисправностей в других модулях. Как известно, тесты,
построенные для одиночных неисправностей, обнаруживают большо количество и кратных неисправностей, поэтому на практике инженер част ограничивается предположением, что не более чем одна компонент системы может быть неисправной.
Цель работы. Минимизация проверяющих тестов для частнчны автоматов на основе доопределения неопределенных переходов і минимизация полных проверяющих тестов без потери полноты теста дл. сетей из конечных, в том числе и недетерминированных, автоматов прі условии, что неисправности возможны не более чем в одной компонент сети.
Для достижения поставленной цели необходимо решить следуюши задачи.
-
Охарактеризовать влияние различных параметров автоматов на длин; проверяющего теста. На основе проведенных исследований разработат технологию доопределения неопределенных переходов таким образом чтобы полученный автомат имел самый короткий тест среди все: возможных доопределений.
-
Проверяющий тест можно сократить без потери его полноты, если ДВі его последовательности обнаруживают одно и то же множеств! неисправностей. Таким образом, при сокращении проверяющих тестов дл: компонент автоматной сети необходимо полностью охарактеризоваті множество неисправностей в компоненте, обнаружнмых каждой тестовоі последовательностью. Ввиду большого количества неисправностей данна: характеризация не должна основываться на явном переборе все: проверяемых компонент. На основе полученных результатов разработат: технологию минимизации полных проверяющих тестов для компоненть сети из детерминированных автоматов.
-
Исследовать возможности минимизации полных проверяющих тесто: для сетей из недетерминированных автоматов.
Методы исследования. Для реализации поставленной цели в работі используются методы теории конечных автоматов, математической логики технической диагностики, а также компьютерные эксперименты для оценкі предлагаемых способов минимизации.
Научная новизна работы состоит в следующем.
1. Показано, что длина проверяющего теста для конечного автомата в
юновном определяется мощностью множества различимости автомата, т.е.
шелом последовательностей, по реакции на которые можно различить
іюбьіе два состояния автомата. В частности, наиболее короткие
іроверяющие тесты можно построить для автоматов, обладающих
щнородной диагностической последовательностью. Полученные результаты
іают возможность выбрать параметры ff-метода, который является основой
іри построении тестов для детерминированных автоматов, таким образом,
тобы получить более короткий тест.
2. Сформулированы необходимые и достаточные условия
уществования для частичного автомата доопределения с однородной
иагностической последовательностью. Для случая, когда такое
оопределение невозможно, разработана технология доопределения
астичного автомата таким образом, что каждое состояние в
оопределенном автомате имеет однородный идентификатор. Проведенные
омпьютерные эксперименты показали, что при таком доопределении
втомат в большинстве случаев имеет самый короткий тест среди всех
озможных доопределений.
3. Разработана технология сокращения проверяющих тестов для
омпоненты многомодульной системы, в которой каждый модуль описан
энечным автоматом, и неисправности возможны не более чем в одной
эмпоненте сети. Показано, что каждой тестовой последовательности можно
оставить в соответствие регулярное множество входо-выходньгх
оследовательностен проверяемой компоненты. Две тестовые
оследовательности обнаруживают одно и то же множество неисправных
эмпонент, если и только если соответствующие регулярные множества
эвпадают.
4. Показано, что технология, основанная на сравнении регулярных
ножеств, содержащих входо-выходные последовательности компоненты,
Знаружимые каждой тестовой последовательностью, может быть
зпользована для сокращения проверяющих тестов для сетей с
^детерминированными компонентами как относительно редукции, так и
гносительно эквивалентности.
Достоверность полученных результатов. Все научные положения и лводы, содержащиеся в диссертации, основаны на утверждениях.
доказанных с использованием аппарата математической логики, теории автоматов и технической диагностики. Эффективность предложенных методов подтверждена компьютерными экспериментами.
Практическая ценность. Разработанные технологии могут быть использованы в современных комплексах синтеза проверяющих тестов и диагностики систем логического управления. Технология доопределения поведения системы может быть использована на этапе контролепригодного проектирования с целью получения тестопригодной реализации. Методы сокращения тестов для автоматных сетей могут быть эффективно использованы при построении тестов контроля функционирования при эксплуатации системы. В этом случае тесты, используемые при проектировании и производстве, должны быть сокращены с сохранением возможности обнаружения наиболее вероятных неисправностей. Другое применение данная технология находит при тестировании компоненты системы, когда тестируемый модуль напрямую недоступен для наблюдения и управления.
Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках следующих проектов.
1. Грант МО РФ (МОПО) 1998-2000 гг., раздел "Автоматика и
телемеханика. Вычислительная техника", научно-исследовательская работа
"Разработка математических и программных средств для проектирования
оптимальных контроллеров методами структурной теории автоматов"
-
Программа МО РФ " Научные исследования высшей школы в области производственных технологий", раздел "Интеллектуальные системы автоматизированного проектирования и управления производством", НИР "Разработка интеллектуальной системы автоматизированного проектирования и тестирования цифровых контроллеров" (2000).
-
Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1997-2000 гг.", раздел "Информационные технологии, электроника и связь", проект 95-1-21 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".
4. Госбюджетная тема "Диаконт" 1996-2000 гг., выполняемая на базе Гибнрского физико-технического института при Томском госуниверситете, тучно-исследовательская работа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред, ібьектов и технических систем", раздел "Разработка методик и аппаратуры ^следований".
Результаты проведенных исследований включены в курсы лекций по ехнической диагностике и по теории автоматов, которые читаются на адиофизическом факультете Томского госуниверситета.
Апробация работы. Результаты, вошедшие в работу, обсуждались на аседаниях совместного семинара кафедры математической логики и роектирования радиофизического факультета ТГУ, кафедры рограммирования факультета прикладной математики и кибернетики ТГУ
лаборатории синтеза дискретных автоматов Сибирского фнзико-ехнического института при ТГУ. Кроме того, они докладывались на онференциях, в том числе и международных, в гг. Еври (Франция), Оттаве Канада), Минске, Екатеринбурге, Томске, что подтверждается ублнкациями докладов и тезисов докладов.
Структура и объем диссертации. Диссертация состоит из ведения, 4 глав, заключения и списка используемой литературы. ,иссертацня содержит 18 рисунков и 5 таблиц. Объем диссертации эставляет 99 стр., в том числе: титульный лист - 1 стр., оглавление - 4 стр., сновной текст - 82 стр., библиография из 63 наименовании - 7 стр., риложение - 5 стр.