Содержание к диссертации
Введение
Глава 1. Постановка задач диссертационного исследования. Исследование новой классификации автоматов. Выбор подклассов для исследования минимизации универсального тестирования 15
1.1. Постановка задач минимизации универсальных тестов 15
1.2. Описание используемой классификации конечных детерминированных автоматов 19
1.3. Выбор подклассов для исследования минимизации универсальных тестов 33
1.4. Некоторые замечания о выборе классов для исследования 47
Глава 2. Минимизация универсальных тестов в исследуемых подклассах 51
2.1. Исследование структуры универсальных тестов 51
2.2. Построение двух вариантов универсальных тестов для исследования .55
2.3. Сокращение универсальных тестов в выбранных подклассах 57
2.4. Минимальные универсальные тесты в подклассе линейных (4,2,2) -автоматов 61
Глава 3. Универсальное тестирование компоненты структурного автомата 63
3.1. Общие положения структурной теории автоматов 63
3.2. Задача тестирования компоненты структурного автомата 65
3.3. Трансляция универсального теста в последовательной композиции автоматов 68
Заключение 72
Список литературы 74
Приложение 1 79
Приложение 2 99
Приложениез 109
Приложение 4 114
Приложение 5 116
- Описание используемой классификации конечных детерминированных автоматов
- Некоторые замечания о выборе классов для исследования
- Построение двух вариантов универсальных тестов для исследования
- Задача тестирования компоненты структурного автомата
Введение к работе
Конечные автоматы являются одним из важнейших понятий современной математической кибернетики. Различные типы конечных автоматов являются математическими моделями технических устройств, социально-экономических, биологических и других дискретных динамических систем, а также используются для описания программ, алгоритмов и вычислительных процессов. Значение теории автоматов определяется тем, что применение конечных автоматов как математических моделей не ограничивается какой-либо определенной областью исследований, а может использоваться для решения проблем практически в любой области человеческой деятельности от исследования нервной системы человека до административного управления и от проектирования электронных устройств до лингвистики.
В современных информационных технологиях конечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения: программное обеспечение, используемое для разработки и проверки цифровых схем; лексические анализаторы стандартных компиляторов; программное обеспечение для сканирования (поиск заданных слов, фраз и других шаблонов) больших текстовых массивов, таких как наборы Web-страниц; программное обеспечение для проверки различного рода систем с конечным числом состояний (протоколы связи или защищенной передачи информации).
При разработке теоретических основ кибернетики многие сложные концепции и понятия были выработаны на базе теории конечных автоматов. Теория автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем. Универсальность теоретического и практического применения теории конечных автоматов определяет актуальность ее дальнейшего развития. Как показано выше, теория конечных автоматов имеет многочисленные приложения в технической и практической кибернетике и информатике, составляет важную часть дискретной математики и
4 математической кибернетики.
Впервые, автоматы, как абстрактные модели нейронных сетей, были введены в 1943 году в работе Мак-Калокка и Питтса [1]. В дальнейшее автоматы неоднократно использовались для описания нейронных сетей [2].
Определение конечного детерминированного автомата как совокупности пяти объектов: A = (S,X,Y,8,A,)> где S, X и Y - конечные непустые множества, а 8 и X (функции переходов и выходов соответственно) - отображения вида: 8: S х X -» S и A,: S х X -> Y, введено в работе [3]. Такой тип автоматов получил название автоматы типа Мили. Другой основной тип конечных детерминированных автоматов - автоматы типа Мура введены в работе [4]. Конечный автомат типа Мура есть пятерка: объектов: A = (S,X, Y,5, \х), где S, X
и Y - конечные непустые множества, а 8 и ц, (функции переходов и отметок состояния соответственно) - отображения вида: S:SxX-»S и u.:S-»Y. Равносильность двух этих типов автоматов показана во многих работах, например в работе [5]. Из работы Э. Мура [4] берет начало теория экспериментов с автоматами. В дальнейшем теория конечных автоматов и экспериментов с автоматами получила развитие во многих работах зарубежных и отечественных авторов (см., например [6 - 18]).
Процесс приложения входной последовательности к автомату, наблюдение реакций и построение заключений называется экспериментом. Если прикладываемая последовательность известна заранее, то такой эксперимент называется безусловным, в противном случае, если выбор последующего входного воздействия зависит от полученных выходных сигналов, эксперимент называется условным.
Эксперимент, требующий только одного экземпляра исследуемого автомата, называется простым. Эксперимент, требующий более одного экземпляра автомата, называется кратным.
Задачи распознавания состояния конечного детерминированного автомата условно разделить на два основных вида.
1) Диагностическая задача.
Задано:
A = (S, X, Y, 8, X) - известный конечный детерминированный автомат;
S0 с S - подмножество допустимых начальных состояний. Требуется:
- построить эксперимент, позволяющий определить, в каком именно из
допустимых начальных состояний находился автомат А до проведения
эксперимента, т. е. найти реХ*, которое удовлетворяет предикату
(VseS0)(Vs'eSoi){s*s'->^(s,p)*^(s,p)}.
2) Установочная задача.
Задано:
- A = (S,X, Y,5,A.) - известный конечный детерминированный автомат;
S0 с S - подмножество допустимых начальных состояний. Требуется:
построить эксперимент, позволяющий установить автомат А в
известное конечное состояние, т. е. найти реХ , которое удовлетворяет
предикату (Vs,s' є S0){8*(s,p) Ф 5*(s',p) -» A,*(s,p) ф A,*(s',p)}.
Из выше приведенных постановок задач ясно, что решение диагностической задачи является также и решением установочной задачи, так как знание начального состояния автомата и приложение конкретной входной последовательности однозначно определяют конечное состояние автомата.
Эдвард Ф. Мур в 1956 г. в работе [4] показал, что существует решение установочной задачи с помощью простого безусловного эксперимента, предложил метод решения установочной задачи и нашел оценку длины эксперимента. Поиск решения предлагается осуществлять путем построения установочного дерева.
Теория экспериментов с дискретными динамическими системами с памятью является одной из важных проблем технической кибернетики. Целью
эксперимента с реальной системой может быть построение математической модели системы, уточнение существующей модели системы или определение, какая модель из заданного семейства моделей является достаточно точной для данной системы. Последний тип эксперимента - задача диагностирования систем с памятью, - может решаться на основе методов теории экспериментов по распознаванию конечных автоматов в заданных семействах автоматов. Задача распознавания конечных автоматов, понимается как определение содержимого "черного ящика", т.е. расшифровки связей вход-выход, при условии, когда содержимое "черного ящика" принадлежит какому-либо известному семейству автоматов.
В 1962 году в работе [6] Артур Гилл свел задачу распознавания автомата в конечном семействе автоматов к установочной задаче. Задача распознавания автомат представляет собой определение (с точностью до изоморфизма), минимальной формы автомат путем проведения эксперимента.
На практике, часто возникает задача распознавания автомата, о котором известно, что он принадлежит к определенному конечному семейству автоматов, т.е. необходимо определить, каким из автоматов семейства а = {Аі}ІЄІ, где A, =(SifX,Y,5j,A,j)- конечный детерминированный автомат, является автомат A = (S,X,Y,5,A,). Решение этой задачи может быть найдено
приложением такого слова реХ*, которое удовлетворяет предикату
(Vi, j е I)(Vs є SjXVs' є Sj){i Ф j -> X*(s,p) * X)(s',p)}.
Критерием существования решения этой задачи является то, что семейство автоматов должно образовывать исключительный класс - ни одно состояние автомата А} недолжно быть эквивалентно никакому состоянию автомата Ар для любых i^j, т. е. выполняется условие:
(VijGlXVse^XVs'eSjMi^j^^ueX^X^^^^s'.u)}
Решение задачи распознавания автомата, предложенное А. Гиллом, сводится к замене семейства автоматов cc = {Aj}i6l, где Aj =(Si,X,Y,8j,X,j),
7
расщепляемым конечным детерминированным автоматом
a = ((JSi,X,Y,(j6i,|jA,i), в который каждый автомат семейства входит как
ІЄІ ІЄІ ІЄІ
изолированный подавтомат, и решению для этого расщепляемого автомата установочной задачи методом Мура. А. Гиллом из оценки Мура для установочной задачи получена оценка длины 1 простого безусловного эксперимента для решения задачи распознавания автомата в семействе автоматов: 1 < (2п - l)(Nn -1), где п - максимальное число состояний автоматов
семейства и N - число автоматов в семействе.
Метод решения задачи распознавания автомата в заданном семействе автоматов, предложенный А. Гиллом, имеет несколько существенных недостатков. Во-первых, так как для решения задачи необходимо построение установочного дерева, которое напрямую зависит от конкретных функций переходов и выходов автоматов заданного семейства, то построенный тест является неприменимым для тестирования другого, пусть даже очень близкого семейства автоматов. Во-вторых, отсутствует возможность сокращения длины теста, при условии, что автоматы исследуемого семейства обладают какими-либо специфическими свойствами.
В 1981-1982 годах на международных конференциях Твердохлебовым В. А. [19,20] был предложен метод универсального решения задачи распознавания автомат в заданном семействе автоматов.
Универсальным тестом в классе К(Х, п) семейств сравнимых конечных детерминированных автоматов с памятью по объему не превосходящих п
состояний будем называть слово р є X , которое для каждого семейства этого
класса, удовлетворяющего условию исключительности, удовлетворяет
условию: (Vi,jєI)(VsєS;)(Vs'єSj){i* j-> A,*(s,p)* A,*j(s',p)}.
Универсальный тест не зависит от конкретных свойств функций переходов и выходов автоматов семейства, а зависит только от входного алфавита X и от п - максимального числа состояний для любого автомата
8 семейства, при этом п является параметром теста.
В дальнейших работах Твердохлебова В. А. с 1982 г. по 2005 г. (см.,
например [21-23]) продолжено исследование универсальных тестов - найдены
оценки длины и методы построения универсальных тестов. Итоговые
результаты работ по универсальному тестированию конечных
детерминированных автоматов приведены в работе [23].
В работах Твердохлебовым В.А. были получены следующие результаты.
Доказано существование универсальных тестов в классе конечных детерминированных автоматов и найден критерий существования, совпадающий с критерием существования решения для задачи распознавания автомата по А. Гиллу.
Найдена оценка длины универсального теста: |р| < |Х|П п~ +п2 + п-2.
Разработан метод построения универсальных тестов, решен вопрос о наличии у каждого универсального теста его наименьшей по длине формы.
Показано, что универсальный тест может задаваться аналитической формулой для функции k-значной логики.
Как видно, из приведенной выше оценки, даже в случае сравнительно небольших размерности входного алфавита X и максимального числа состояний п универсальный тест имеет очень большую длину. Это делает его непригодным для практического использования. Так как оценка длины универсального теста не может быть понижена для общего случая, на основании результата Т. Хиббарда о достижимости оценки Э. Мура длины решения установочной задачи, универсальные тесты, предложенные Твердохлебовым В. А., получили только теоретическое значение. Однако практическое применение универсального тестирования могло бы значительно повысить эффективность процедур контроля и диагностирования технических систем.
Жизненный цикл технической системы можно представить как совокупность следующих этапов ее функционирования.
Функционирование системы в работоспособном состоянии, когда управление осуществляется в штатном режиме.
Контроль исправности состояния системы и принятие решение о возможности дальнейшей эксплуатации.
Диагностирование системы, т. е. локализация дефекта возникшего в системе по месту или функции.
Ремонт системы - восстановление ее работоспособности с первоначальной функциональностью.
Модернизация системы - восстановление ее работоспособности с улучшением технических характеристик системы и повышением ее функциональных возможностей.
Частичное восстановление системы - восстановление с ухудшением ее характеристик и функциональных возможностей.
Вывод системы из эксплуатации.
Взаимосвязь описанных выше этапов приведена на рис. 1.
вывод системы из эксплуатации
эксплуатация
модифицированной
[ модификация
(р,єХ\Р,)1
частичное восстановление функций системы
эксплуатация
системы с пониженной
функциональностью
системы
эксплуатация
эксплуатация і
IV.
Рис. 1. Схема функционирования технической системы при использовании в процедурах контроля и диагностирования частных тестов.
10 Точка 1 - точка начала контрольных процедур определяется:
расчетным путем, во время проектирования системы;
появлением в работе системы явных дефектов;
срабатыванием аварийной сигнализации и т.д.
Для выполнения процедур контроля используется некоторый тест
РіЄХ, направленный на выявление конкретного класса дефектов Fj. рі={{Аі1}іІєі1ЛАі2}і2ЄІ2,...,{Аік}ікЄІк} - множество подмножеств автоматов,
распознаваемых на слове р; є X*, жестко зависящим от распознаваемого класса
дефектов методом M(Fj) (Решение задачи распознавания автомата по А. Гиллу).
Любое слово из символов входного алфавита может рассматриваться как тест для системы, поэтому множество тестов бесконечно.
Точка 2 - точка принятия решения о дальнейшей эксплуатации системы. Если при проведении контрольных процедур было установлено, что система находится в работоспособном состоянии, то продолжается ее дальнейшая эксплуатация, иначе проводиться диагностика системы. В точке 3 анализируются результаты диагностирования, и принимается решение о возможности ремонта системы или о выводе ее из эксплуатации.
Подобное описание является устоявшимся представлением жизненных циклов сложных систем и отражено в работах многих авторов (см., например,
[25-29]). Недостатком такого подхода является то, что тест Pj є X строиться
методом M(Fi), зависящим от конкретного подкласса дефектов
Fi={{Ai,}iiev{Ai2}i2f2 (Aik}ikeik}> и не может быть использования для
проверки системы на другие неисправности. Поэтому изменение выбранного подкласса неисправностей (как во время проектирования системы, так и во время ее эксплуатации) требует нового применения метода для построения нового теста.
Описанный недостаток может быть устранен при использовании в процедурах контроля и диагностирования универсальных тестов. При
использовании универсального тестирования, схема жизненного цикла системы приобретает вид, представленный на рис. 2.
вывод системы из
модификация
частичное восстановление функций системы
эксплуатация
системы с пониженной
функциональностью
эксплуатация
модифицированной
системы 1
Рис. 2. Схема функционирования технической системы при использовании в процедурах контроля и диагностирования универсального теста
При универсальном тестировании в процедурах контроля и
диагностирования используется тест рєХ*- универсальный тест, на котором
распознаются все распознаваемые классы дефектов Fj, методом M(max|S|,|X|),
зависящим только от мощности входного алфавита и глубины памяти технической системы. Универсальное тестирование повышает надежность и эффективность управления системой в работоспособном состоянии. Повышение надежности осуществляется за счет замены наборов частных тестов (тестов, ориентированных на конкретное подмножество неисправностей) общим тестом, предельно расширяющим анализируемое множество неисправностей. Это позволяет увеличить продолжительность этапов эксплуатации системы и уменьшить количество этапов контроля и диагностирования. Эффективность управления повышает за счет сокращения временных интервалов для контроля и диагностирования на этапе эксплуатации системы, и за счет упрощения разработки процедур контроля и
12 диагностирования на этапе проектирования системы.
Как было замечено ранее, значительным недостатком универсальных тестов, предложенных В. А. Твердохлебовым, явилась их большая длина. Так, например, по полученной оценки, универсальный тест для относительно
простой дискретной технической системы с объемом памяти 25 и четырьмя
двоичными входами имеет длину 2 * 101270символов..
В диссертации предлагается новый подход к построению универсальных тестов, основанный на использовании специфических свойств диагностируемых систем, исследуется возможность сокращения универсального теста в некоторых специфических классах автоматов. Для выделения классов автоматов используется предложенная Твердохлебовым В. А. в работах [29,30] в 2003-2004 годах классификация автоматов по свойствам их функций переходов и выходов, основанная на фундаментальной классификации Поста для функций алгебры логики. Исследование сокращения оценки длины универсального теста выполнено в подклассах класса (4,2,2) -автоматов: линейных; самодвойственных; монотонных; линейных и самодвойственных; линейных и монотонных; монотонных и самодвойственных; линейных, самодвойственных и монотонных автоматов.
Диссертационная работа состоит из трех глав основного текста.
В первой главе предлагается новый подход к универсальному тестированию, основанный на специфических свойствах автоматов. Исследуется классификация автоматов на основе свойств Поста функций переходов и выходов комбинационных частей автоматов. Предложенная Твердохлебовым В.А. классификация автоматов не была исследована. В этой главе доказываются леммы, на основании которых выделяются пустые и непустые классы автоматов. Далее строится решетка подклассов в классе (4, 2, 2) - автоматов и рассматривается распределение автоматов по подклассам. Выделяются для исследования минимизации универсальных тестов семь подклассов и находятся их количественные характеристики. Все полученные
13 результаты сформулированы в виде лемм и теорем. Так же приведены описания алгоритмов, используемых для распределения автоматов по классам.
Во второй главе проводиться выбор двух вариантов универсальных тестов, которые используются для исследования сокращения оценки длины универсального теста в подклассах линейных; самодвойственных; монотонных; линейных и самодвойственных; линейных и монотонных; монотонных и самодвойственных; линейных, самодвойственных и монотонных (4, 2, 2) -автоматов. Дополнительно исследована структура универсальных тестов, показано, что по структуре они совпадают с последовательностями де Брюина. Доказаны леммы, позволяющие представлять последовательности де Брюина в двоичном алфавите функциями алгебры логики, полином Жегалкина которых имеет достаточно простую структуру. Сокращение универсальных тестов выполнено двумя методами: суффиксное и префиксное сокращение. Полученные оценки сформулированы в виде теорем. Так же в этой главе представлены минимизированные универсальные тесты для исследуемых подклассов. Более подробно рассмотрен подкласс линейных автоматов, для которого найдены минимальные по длине универсальные тесты.
В третье главе диссертационной работы рассмотрена задача тестирования автомата представленного последовательной композицией автоматов из исследованных подклассов. Задача тестирования композиции автоматов рассматривается как совокупность трех задач: задачи тестирования изолированной компоненты, задача управления и задача наблюдения. Для решения задачи тестирования изолированной компоненты используются полученные минимизированные универсальные тесты. Задачи наблюдения и управления могут быть решены при условии трансляции универсального теста внутрь композиции автоматов. Получены семейства автоматов, которые содержаться в исследуемых подклассах, и транслируют универсальные тесты. Полученные результаты сформулированы в виде лемм и теорем.
Большинство полученных в работе результатов носят количественный
14 характер. Поэтому для получения этих результатов использовался метод доказательного вычислительного эксперимента. В таких полных вычислительных экспериментах исключаются интерполяция и экстраполяция, вероятностные процедуры, основным является логический вывод на основе полного перебора исследуемых объектов. Такой подход обосновывается в работах академика А.П. Ершова и Н.Н. Моисеева (см., например [31,32]).
Доказательство результатов, полученных в работе, имеет классическую логическую форму, при этом при необходимости, ручной перебор вариантов по конечным множествам с проверкой эффективно проверяемого свойства заменен доказательным перебором с помощью ЭВМ.
Осуществление переборов с использованием ЭВМ принципиально расширяет возможности получения результатов, имеющих явную конструктивную форму. Количественные отношения, полученные в диссертации, требуют непосредственного использования вычислительных процедур большого объема, что возможно в рамках одного исследования только с использованием ЭВМ.
Описание используемой классификации конечных детерминированных автоматов
Для выделения классов автоматов обладающих специфических свойствами в диссертации используется впервые предложенная Твердохлебовым В. А. в работе [29] классификация автоматов по свойствам функций переходов и выходов. В этой классификации автоматов используется: - известная декомпозиция автомата на комбинационную часть и память в виде задержки сигнала на один такт (рис. 4); Комбинационная часть А, 5 4 s(t) s(t+l) Память Рис. 4. Декомпозиция автомата - кодирование состояний, входных и выходных сигналов двоичными последовательностями, при этом очевидно, что входной и выходной алфавиты автомата предполагаются допускающими кодирование с помощью двоичных символов; - представление функции переходов и выходов 8 и X автомата в виде наборов булевых функций 8 = 5,,52,...,5 , А, = Я,,Д2,...ДУ .
В зависимости от свойств Поста функций 8,-,1 i co и Л.:, 1 j v происходит отнесение автомата к тому или иному классу. Классификация функций алгебры логики впервые предложена Постом в работе [33] описана во многих источниках. Далее, на основании [34,35], кратко приведены основные определения необходимые для описания этой классификации. Обозначим через Ег множество из двух элементов 0 и 1, т.е. Е2 = {0, 1}. Для любого числа п, через Е2 будем обозначать n-ю декартову степень множестваЕг, т.е. Е2 =Е2 х...хЕ2. 4 у праз Определение 1.2.1. Булевой функцией или функцией алгебры логики f от п переменных будем называть отображение: f: Е\ - Е2. Булеву функцию от п переменных еще называют n-местной булевой функцией. Множество всех булевых функций обозначается Р2.
Для удобства наборы значений переменных располагаются в таблице по
правилам: если набор рассматривать как число в двоичном исчислении, то его значение соответствует порядковому номеру набора в таблице, причем нумерация начинается с нуля. Из представления булевой функции в виде столбца значений этой функции явно следует следующая теорема. Теорема 1.2.1. Число р2(п) всех булевых функций из Р2 зависящих от п переменных равно 22 . Определение 1.2.2. Пусть В = {fl(...), f2(...), ..., fn(...), ...} -некоторое множество функций, тогда формулой над В будем называть: Любую функцию из В. Если f(xj,x2,...,xn)eB и для любого і, 1 і п, Hi либо переменная, либо формула над В, то выражение вида f(Hl5H2,...,Hn) также называется формулой над В. Формулами над В являются только те объекты, которые можно построить только по пунктам 1 и 2 данного определения. Определение 1.2.3. Функция f, соответствующая формуле над В, называется суперпозицией функций из В. Определение 1.2.4. Под алгеброй логики будем понимать алгебру над множеством Р2 с операцией суперпозиции, A = (Р2, суперпозиция). Определение 1.2.5. Система функций В = {fl, f2, ...,fk, ...} из Р2 называется (функционально) полной, если любая булева функция может быть записана в виде формулы над В. Определение 1.2.6. Булевы функции, для которых выполняется равенство f(0,0, ...,0) = 0, называются сохраняющими 0. Класс всех булевых функций сохраняющих 0 обозначим К0.К -дополнение К0 до Р2. Определение 1.2.7. Булевы функции, для которых выполняется равенство f(l, 1,..., 1)= 1, называются сохраняющими 1. Класс всех булевых функций сохраняющих 1 обозначим К,. Kj -дополнение К, до Р2. Определение 1.2.8. Булева функция f(xi,...,xn) называется двойственной к функции f(x,...,xn) и обозначается - f (xj ...,хп). Если для функции f выполняется равенство f = f, то функция f называется самодвойственной. Класс всех самодвойственных булевых функций обозначим Ks. Kg дополнение Ks до Р2. На множестве наборов из Е2 введем отношение предшествования по следующему правилу: два набора а = (а,,...,ссп) и р = (Р,,...,РП) находятся в отношении а- р,если а, pj,...,ctn РП. Определение 1.2.9. Булева функция f(x, ...,хп) называется монотонной, если для любых двух наборов а и Р, а Р, выполняется неравенство 4a;-HPJ# Класс всех монотонных булевых функций обозначим Км. К -дополнение Км до Р2. Определение 1.2.10. Монотонной конъюнкцией от переменных ХІ, ..., хп называется любое выражение вида х «Xj -...-х , где s 1, 1 ij n , ij Ф\к, если j Ф k; либо просто 1. Определение 1.2.11. Полиномом Жегалкина над xl, ..., хп называется выражение вида Kj ФК2 ФК2 Ф...ФКт, где т 1 и все Kj различные монотонные конъюнкции от xl,..., хп, либо константа 0. Теореме 1.2.2. Любую булеву функцию f(x,...,xn) можно единственным образом представить в виде полинома Жегалкина над хь ..., хп. Определение 1.2.12. Булева функция f(x, ...,хп)называется линейной, п если её полином Жегалкина имеет следующий вид: f(x1}x2,...,xn) = а0 + ajXj, где at є {0,1),0 і n. Класс всех линейных булевых функций обозначим KL. К -дополнение KL до Р2. Сочетания пересечений определенных выше классов образуют 32 непересекающихся класса булевых функций. Для обозначения этих классов функций алгебры логики, будем использовать букву К с пятью нижними индексами по правилам: Kabcde =KanKbnKcnKdnKc ,где а = 010, b = 11Ї, с = S S, d = L L, е = М М. Не все из этих классов отличны от пустых, чтобы выделить непустые классы были доказаны следующие леммы. При дальнейших рассуждения предполагается, что функция алгебры логики зависит от любого числа переменных п, где п 2. Лемма 1.2.1. Если булева функция f не сохраняет 0 и не сохраняет 1, то она является немонотонной. Доказательство. По условию леммы f (0, 0,..., 0) = 1 и f (1,1,..., 1) = 0. Т.к. двоичные вектора а = (0,0, ...,0) и Р = (1,1, ...,1) находятся в отношении а - (3 и f (а) f (Р), то f- немонотонная.
Некоторые замечания о выборе классов для исследования
Конечный автомат представляет собой наиболее общую математическую модель последовательного цифрового устройства или цифровой системы. Под последовательностными устройствами в электронике понимают устройства, у которых, при одинаковых воздействиях на входах, на выходах могут возникать различные выходные сигналы. Простейшими последовательностными цифровыми устройствами, применяемыми в электроники, являются триггеры. Описание триггеров можно найти во многих работах, см., например [38-40]
Триггер - это устройство с двумя состояниями, каждое из которых при определенных условиях на входе устройства поддерживается постоянными. Почти все последовательностые устройства представляют собой комбинацию некоторого числа триггеров. Математической моделью триггера является конечный детерминированный автомат. Триггер, как конечный автомат, характеризуется следующими свойствами: - число состояний - два (единица или нуль), что соответствует оной внутренней переменной s; - число выходных переменных у - одно, значение переменной совпадает с состоянием триггера; - число входных переменных х - зависит от типа триггера.
В большинстве случаев в электронике применяются четыре основных типа триггера: RS, D, Т, JK - триггеры, отличающиеся по способу обработки входных сигналов. Простейшим триггером является RS - триггер. RS - триггер имеет два входа и два выхода. Входы и выходы триггера имеют свои обозначения. Один из входов триггера называется установочным входом и обозначается буквой S (от английского "set" - установить), а другой - входом сброса и обозначается буквой R (от "reset" - сбросить). Триггер имеет два симметричных выхода. На одном выходе (условно называемом прямым выходом) сигнал представляется без отрицания (выход Q), а на другом - с отрицанием (Q- инверсный выход). Таким образом, математической моделью RS - триггера является конечный детерминированный автомат из класса (2, 4, 2) - автоматов. Таблица переходов и выходов имеет вид (см. табл. 5), где в каждой клетке таблицы находится пара - новое состояние автомата и выходной сигнал:
Под а - понимается неопределенное состояние триггера, соответствующее недопустимым сочетанием входных сигналов: S = l и R = l. Для того, чтобы найти свойства функции переходов 5 и функции выходов Оконечного детерминированного автомата ARS, являющегося математической моделью RS - триггера, положим, для определенности, а = 0. Тогда функция переходов 5 представляется полиномом Жегалкина вида: 5(Q,S,R) = Q Є S Є QS Є QR Є SR Є QSR и 5 єКоїї . Функция I совпадает с функцией 5, следовательно, конечный детерминированный автомат
ARSeHoiLSM D - триггер называют триггером задержки или информационным триггером. Он имеет единственный входной сигнал D. Значение сигнала на выходе Q такого триггера в момент времени (t+І) равно значению сигнала на входе D момент времени t. Конечный детерминированный автомат AD, являющийся математической моделью D - триггера принадлежит классу (2, 2, 2) - автоматов. Таблица переходов и отметок этого автомата имеет вид (см. табл.6), где в каждой клетке таблицы находится пара - новое состояние автомата и выходной сигнал:
Функция переходов автомата AD имеет вид 6(Q,D) = D, а функция выходов вид A,(Q,D) = Q, очевидно, что Х,Ь є K01LSM, следовательно, AD є H01LSM. T - триггер имеет один вход Т. При подаче на вход триггера единичного сигнала, инвертируется внутренне состояние Q триггера. Математической моделью Т - триггера является конечный детерминированный автомат Ат из класса (2,2,2) - автоматов. Таблица переходов и выходов этого автомата имеет вид (см. табл. 7): Функция переходов 8 и функция выходов X автомата Ат совпадают и представляются следующим полиномом Жегалкина: (Q,T) = 5(Q,T) = QT. Очевидно, что А,,5еК0ц , следовательно, Ат єН0 . Ж - триггер имеет два входа J и К. Конечный детерминированный автомат Аж, задающий работы JK - триггера, принадлежит классу (2, 4, 2) автоматов и имеет следующую таблицу переходов и выходов (см. табл. 8): Таблица 8 По таблице переходов и выходов автомата Аж понятно, что его функции переходов и выходов совпадают и определяются полиномом Жегалкина вида: A,(Q,J,K) = QJQJQK, при этом Х.,5еК0 , следовательно
AJK6H0lLSM Описанные выше типы триггеров принадлежат классам (2,2,2) -автоматов и (2, 4, 2) - автоматов. Длина универсального теста по оценке полученной Твердохлебовым В.А. составляет: для класса (2, 2, 2) - автоматов -28 символов, а для класса (2, 4, 2) - автоматов 1020 символов. Исследование минимизации универсального теста в этих классах может не дать принципиального понижения длины, так как первоначальная длина универсального теста незначительна. Длина универсального теста в классе (4, 2, 2) - автоматов составляет 524306 символов, поэтому исследование сокращения этой оценки представляется более наглядным подтверждением возможности понижения оценки длины при универсальном тестировании в частных классах автоматов, обладающих специфическими свойствами.
Для D - триггера и Т - триггера легко строятся эквивалентные им (4,2,2) -автоматы, которые будут обладать теме же свойствами по используемой классификации. В дальнейшем класс (4, 2, 2) -автоматов будет рассмотрен как базисный класс при построении структурных автоматов. Вышеизложенными положениями определяется выбор класса (4; 2, 2) -автоматов, как исходного класса для исследования минимизации универсального тестирования в специфических подклассах.
Построение двух вариантов универсальных тестов для исследования
Универсальный тест в классе (4,2,2) - автоматов вида А = ((Е2)2,Е2,Е2,8Д), где Е2 ={0,1}, представляет собой последовательность двоичных символов, которая включает в себя все возможные слова длины l = n +n-l (при n = 4 - 1 = 19). Длина универсального теста для класса (4,2,2) - автоматов, по полученной В. А.Твердохлебовым оценке, составляет 524 306 символов.
Для построения последовательности включающего все слова длины n + п -1, в диссертационном исследоании используется известный алгоритма Липпела и Эпштейна для построения линейных последовательностей де Брюина, описанный в работе [44], разработан метод построения универсального теста, включающий следующие этапы: - На множестве X - входном алфавите определяется линейный порядок: X) - х2 - ...- хт. - Слово из старших по порядку "- " букв xmxm...xm длины п2 +п-1, где п - максимальное количество состояний автоматов из тестируемого семейства, полагается префиксом универсального теста. - Построенная часть универсального теста увеличивается добавлением справа на такую букву, которая вместе с п2+п-2 последними буквами образует слово длины п +п-1, не имеющее вхождение в уже построенную часть. При этом должно выполняться условие: добавляется буква, наименьшая по порядку среди букв, которые могут быть добавлены. Для построения первого варианта универсального теста р, порядок на множестве X = {0,1} задается по правилу -0 1. Второй вариант универсального теста р2 получен из pj заменой "1" на "0" и заменой "0" на "1". Построенные с помощью компьютерной реализации описанного выше метода, универсальные тесты были сохранены в текстовых файлах. Начальный отрезок первого варианта универсального теста приведен в приложении 3.
Использование двух вариантов универсального теста при исследовании сокращений тестов дополнительно увеличивает достоверность полученных результатов. 2.3. Сокращение универсальных тестов в выбранных подклассах Для минимизации универсального теста были выбраны два способа сокращения длины. Метод суффиксного сокращение универсального теста: - построенный вариант универсальный теста побуквенно, начиная с первой, прилагается поочередно ко всем парам автоматов из исследуемого подкласса, образующим исключительные классы; - по полученным выходным последовательностям определяется префикс универсального теста, на котором автоматы распознавались в паре; - из полученных префиксов выбирается префикс универсального теста максимальной длины. Эта длина устанавливается в качестве верхней оценки длины префикса универсального теста сохраняющего свойство универсальности в исследуемом подклассе.
Метод префиксного сокращения универсального теста: - для каждой пары автоматов из исследуемого подкласса, образующей исключительные классы выбирается конечный отрезок построенного универсального теста по следующему принципу: сначала к паре прилагается последний символ, если пара не распознается, то прилагается предпоследний и последний символы и т. д., до тех пор, пока пара автоматов не будет распознана; - длина полученного конечного отрезка универсального теста фиксируется для каждой пары автоматов; -из всех полученных длин выбирается наибольшая, которая является верхней оценкой длины суффикса универсального теста сохраняющего свойство универсальности в исследуемом подклассе. Для реализации этих методов была разработана компьютерная программа. В результате проведения исследования по сокращению длины построенных вариантов универсальных тестов в выбранных подклассах класса (4,2,2)-автоматов было установлено значительное сокращение оценки длины универсального теста. Полученные результаты представлены в следующих теоремах. Теорема 2.3.1. В подклассе HL линейных автоматов класса (4,2,2)-автоматов сохраняет свойство быть универсальным тестом в подклассе: - префикс 1-го варианта универсального теста, длиной 24 символа, - префикс 2-го варианта универсального теста длиной 24 символа, - суффикс 1-го варианта универсального теста, длиной 22 символа, - суффикс 2-го варианта универсального теста длиной 23 символа. Следствие 2.3.1. Наименьший тест pL из полученных минимизированных универсальных тестов в подклассе линейных автоматов HL класса (4,2,2) автоматов содержит 22 символа (pL = 22) и имеет вид: 1101111111111111111110.
Задача тестирования компоненты структурного автомата
В некоторых случаях определение работоспособности системы, математической моделью которой является структурный конечный детерминированный автомат, может быть проведено путем локализации дефекта в отдельной компоненте этой системы. Это возможно когда неисправность выражена не форме изменения структуры системы, а в изменении функционирования некоторой компоненты. При этом тестирование всей системы заменяется тестированием только выделенной компоненты. Выбор тестируемой компоненты производится на основании: -анализа статистических данных содержащих информацию о наиболее часто выходящих из работоспособного состояния элементах системы; -расширения диагностического ядра испытуемой системы (ядро диагностируется как изолированная компонента и последовательно наращивается расширением с использованием управления и наблюдения во внутренних узлах системы, рис.7).
В структурно заданной системе анализ функционирования отдельно рассматриваемой компоненты от функционирования других компонент представляет большие, часто практически непреодолимые трудности по ряду причин. Во-первых, тест на внутренних узлах системы являющихся входными узлами элемента не может быть сформировании из-за свойств функционирования других элементов системы. Во-вторых, построение вычислений для анализа сигналов в узлах системы могут иметь полиномиальную сложность, то есть в п узлах для двоичных сигналов возможен анализ 2П сочетаний сигналов (например, при п = 20 220 = 1048576). В-третьих, при проектировании системы, разработчик ориентируется на только некоторых подмножеств сочетаний сигналов в узлах схем, а остальные сочетания сигналов оказываются неопределенными.
Задача диагностирования компоненты внутри большой, многокомпонентной технической системы может быть представлена как комбинация следующих трех задач. Задано: Последовательность сигналов прикладывается к внутреннему входному узлу компоненты А (3). Ответная реакция наблюдается на внутреннем выходном узле компоненты А (4). Требуется: Найти последовательность р входных сигналов системы, формирующую на внутреннем входном узле компоненты (3) тест Т или его модификацию Т , обладающую свойством теста. Задача наблюдения, (рис. 10) Задано: Последовательность сигналов прикладывается к внутреннему входному узлу компоненты А (3). Ответная реакция наблюдается на внешнем выходном узле системы А (2).
Требуется: Найти последовательность Т входных сигналов компоненты, обладающую свойством теста для компоненты А такую, что диагностическая информация полученная в результате тестирования компоненты будет наблюдаема на внешнем выходном узле системы (2). В случае, когда область определения структурно заданной системы является конечной (например, комбинационные схемы, компонентами которых являются функции алгебры логики) то для решения задачи диагностирования можно использовать всю область определения. Когда тестируемая схема строиться из компонентов имеющих память, например, конечные детерминированные автоматы, то область определения такой схемы бесконечна и, следовательно, не представляется возможным ее использование в качестве решения задачи. В качестве компонент этой схемы будем рассматривать конечные детерминированные (4,2,2) - автоматы вида А; =((Е2) ,E2,E2,5j,A,j), где Е2={0,1}. Полученная схема - это структурный конечный детерминированный (64,2,2) - автоматом. Областью определения такого автомата состоит из всех возможных последовательностей 0 и 1 не нулевой длины и является бесконечной, поэтому использование области определения для решения задачи диагностирования компоненты не эффективно. Таким, образом, решение этой задачи можно получить только решением трех задач -тестированием изолированной компоненты, управления и наблюдения описанных выше.
Диагностируемая компонента может располагаться в различных частях структурной схемы многокомпонентной системы. Можно выделить три основных варианта расположения компоненты: Вариант 1) Входные узлы компоненты отождествлены с внешними входными узлами схемы, а выходные узлы компоненты являются внутренними узлами схемы (на рис. 11 - компонента Ai). Вариант 2) Выходные узлы компоненты отождествлены с внешними выходными узлами схемы, а входные узлы компоненты являются внутренними узлами схемы (на рис. 11 - компонента Аз). Вариант 3) Входные и выходные узлы компоненты являются внутренними узлами схемы (рис. 11 - компонента Аг). Возможны также комбинации этих вариантов, например, в первом варианте только некоторые входные узлы компоненты отождествлены с внешними входными узлами, а остальные узлы - внутренние. Если математической моделью компоненты является конечный детерминированный автомат, то задача диагностирования компоненты (Задача 1) при всех основных вариантах ее расположения, может быть решена с помощью метода универсального тестирования автоматов. Для этого необходимо найти решение задачи управления, которое формировало бы на входных узлах компоненты универсальный тест. Для конкретной структурной схемы приведенной на рис. 11 (если диагностируется компонента А2) это означает, что необходимо найти ограничения, налагаемые на компоненту А, и входное слово, что бы при приложении его к внешним входным узлам схемы, на внутренних входных узлах компоненты А2 формировался универсальный тест для (4,2,2)- автоматов. Определение 3.3.1. Будем говорить, что инициальный автомат (A,s0), где A = (S,X,Y,5,A.) транслирует универсальный тест р, если q = 6(s0,p) является универсальным тестом.
