Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов

• Автор: Ветрова, Мария Викторовна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Томск
• Количество страниц: 152 с. : ил.

ВВЕДЕНИЕ.

1. ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ, ОБЗОР ЛИТЕРАТУРЫ.

1.1. Устройства управления техническими объектами.

1.1.1. Синтез цифровых устройств управления

1.1.2. Контроллеры.

1.1.3. Корректировка алгоритма управления

1.2. Основные определения и обозначения.

1.2.1. Конечные автоматы.

1.2.2. Отношения между автоматами

1.2.3. Полностью определенные формы автомата.

1.2.4. Синхронная композиция конечных автоматов.

1.2.5. Пример конечноавтоматного компенсатора.
1.2.6. Синтез компенсаторов и автоматные уравнения.
1.3. Известные методы решения автоматных уравнений для топологии контроллера.
1.3.1. Алгоритм нахождения наибольшего решения автоматного уравнения
1.3.2. Алгоритм решения автоматного уравнения на основе отношения моделирования
1.3.3. Сложность решения автоматного уравнения для топологии контроллера
Ф 1.3.4. Синтез оптимальных компенсаторов.
1.3.5. Синтез тестов для конечноавтоматных компенсаторов
1.4. ВЫВОДЫ ПО ГЛАВЕ
2. СИНТЕЗ ОПТИМАЛЬНОГО КОМПЕНСАТОРА ДЛЯ АБСТРАКТНЫХ АВТОМАТОВ.
2.1. Эквивалентность разрешимости уравнений для топологии КОНТРОЛЛЕРА и последовательной топологии
2.2. Синтез наибольшего решения для полностью определенных детерминированных автоматов.
2.3. Синтез наибольшего согласованного конечноавтоматного
компенсатора
2.4. Минимальные детерминированные редукции недетерминированных АВТОМАТОВ.
2.4.1. Редукции и подавтоматы
2.4.2. гнесовместимые состояния.
2.4.3. Сохраняемое покрытие автомата.
2.4.4. Достаточное условие эквивалентности минимальной редукции некоторому подавтомату исходного автомата
2.4.5. Алгоритм построения редукции недетерминированного автомата с наименьшим числом состояний, эквивалентной подавтомату.
2.5. Выводы по главе
3. СИНТЕЗ ОПТИМАЛЬНОГО КОМПЕНСАТОРА ДЛЯ ПОСЛЕДОВАТЕЛЬНОЙ КОМПОЗИЦИИ АВТОМАТОВ
3.1. Синтез компенсатора для последовательной композиции
АБСТРАКТНЫХ АВТОМАТОВ.
3.2. Синтез компенсаторов для микропрограммных автоматов
3.2.1. Микропрограммные автоматы и композиции микропрограммных автоматов
3.2.2. Наибольший микропрограммный компенсатор
3.2.3. Оптимальный микропрограммный компенсатор.
3.2.4. Эксперименты по синтезу оптимальных компенсаторов для микропрограммных автоматов.
3.3. Синтез компенсатора для структурных автоматов
3.3.1. Решение уравнения для последовательной композиции комбинационных схем
3.3.2. Структурные автоматы и последовательная композиция структурных автоматов
3.3.3. Решение уравнения для последовательной композиции автоматов с памятью.
3.4. Выводы ПО ГЛАВЕ.
4. СИНТЕЗ ТЕСТОВ ДЛЯ КОНЕЧНОАВТОМАТНЫХ КОМПЕНСАТОРОВ .
4.1. Синтез проверяющих тестов при безусловном эксперименте с проверяемым автоматом
4.1.1. Отличающий автомат
4.1.2. Описание отличающего автомата.
4.1.3. Построение проверяющего теста.
4.1.4. Сокращение длины проверяющего теста.
4.2. Результаты экспериментов
4.3. Метод тестирования на основе условного эксперимента с проверяемым автоматом
4.4. Сокращение функции неисправности
4.5. Выводы по главе.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Иными словами, компенсатор можно синтезировать для последовательной композиции, которая иногда оказывается более надежной, например, в смысле отказоустойчивости . Однако конечноавтоматный компенсатор для последовательной композиции может оказаться более сложным. Поэтому предлагается ограничить наибольшее решение уравнения таким образом, чтобы всякая его редукция была автоматомкомпенсатором. Технология такого ограничения предлагается в разделе 2. В разделе 2. В случае, когда поведение корректируемой системы описано частичным автоматом, в качестве компенсатора можно выбирать только автоматы, поведение которых согласовано с корректируемым автоматом. Иными словами, выходные последовательности автоматакомпенсатора должны быть допустимыми для системы, поведение которой корректирует компенсатор. В разделе 2. Как известно , построение такой редукции тесно связано с понятием сохраняемого покрытия в недетерминированном автомате и, кроме того, такая редукция является подавтоматом автомата, множеством состояний которого являются подмножества состояний исходного автомата . В разделе 2. Результаты проведенных компьютерных экспериментов показывают, что предложенный метод является эффективным, т. В третьей главе рассматривается синтез оптимального конечноавтоматного компенсатора для последовательной композиции, для абстрактных, микропрограммных и структурных автоматов. В разделе 3. На основе предложенной формулы исследован ряд частных случаев на предмет существования или не существования конечноавтоматного компенсатора. В практических ситуациях для описания поведения цифровых устройств управления используют так называемые микропрограммные автоматы, которые отличаются от абстрактных автоматов тем, что имеют структурные входной и выходной алфавиты, т. Кроме того, все переходы обычно описываются на множествах интервалов входных и выходных переменных. В англоязычной литературе микропрограммному описанию автомата можно соотнести описание в так называемом Iформате . Синтезу компенсаторов для микропрограммных автоматов посвящен раздел 3. Вводится понятие недетерминированного микропрограммного автомата. Предлагаются алгоритмы нахождения наибольшего решения уравнения для микропрограммных автоматов и нахождения оптимального автоматакомпенсатора, как оптимального подавтомата наибольшего решения. Компьютерные эксперименты, проведенные на контрольных примерах из сети ИНТЕРНЕТ , показали, что предложенные алгоритмы достаточно эффективны. В структурном автомате входные и выходные символы, а также состояния автомата, являются двоичными векторами. В этом случае функции переходов и выходов можно представить как соответствующие системы булевых функций, что во многих случаях обеспечивает более компактное представление автомата. Иногда такое представление автомата называют каноническим . В разделе 3. В первой части раздела 3. Четвертая глава посвящена синтезу условных проверяющих тестов для недетерминированного автомата относительно редукции. Как было отмечено выше, синтезированный конечноавтоматный компенсатор желательно обеспечить набором проверяющих тестов. Согласно результатам раздела 1. Таким образом, в процессе тестирования необходимо определить, является ли синтезированный автоматкомпенсатор редукцией заданного недетерминированного автомата. Потому тесты для автоматакомпенсатора нужно строить как тесты для недетерминированного эталона наибольшего решения уравнения относительно отношения редукции . Методы синтеза таких проверяющих тестов в последнее время активно развиваются . Однако, как следует из результатов проведенных экспериментов, эти методы доставляют очень длинные и часто избыточные тесты. Поэтому в данной работе мы предлагаем метод синтеза теста, основанный на условном эксперименте с проверяемым автоматом. При условном эксперименте каждая следующая тестовая последовательность выбирается на основе реакций проверяемого автомата на предыдущие последовательности. Как известно , условные тесты обычно короче безусловных тестов. В разделе 4. В разделе 4. Проведенные эксперименты показали, что для автоматов, число состояний и входных символов которых больше , тесты являются слишком длинными. В параграфах 4.