Абстрактный синтез автоматов
Принципы и порядок проектирования автомата управления, алгоритм его функционирования. Формальное описание функционирования автомата в виде графа переходов и набора булевых функций. Абстрактный синтез автомата Мура и анализ полученных результатов.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 22.10.2013 |
| Размер файла | 78,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Абстрактный синтез автоматов
Пусть алгоритм управления ОУ задан рис.
При составлении ГСА проектировщик глубоко изучил структуру ОУ с учетом смысла сигналов и логических условий б1, б2, б3).
Для проектирования автомата управления можно абстрагироваться от смысла (семантики) элементов множеств {c} и {б} и переходить к построению формального описания работы автомата.
Общая схема системы будет иметь вид рис., где обозначено:
X, Y - множества входных и выходных переменных ОУ;
с1, с2, …, ск - сигналы управления для ОУ (выходы схемы СА);
СА - схема автомата;
Z(t)=Z1, Z2, …, Zp - внутренние значения переменных автомата, формируемые схемой СА в момент t;
Z (t + 1) - значения переменных после подачи очередного импульса синхронизации, т.е. в момент времени t + 1;
ПА - память автомата;
СС - схема синхронизации;
ф - сигнал синхронизации;
- сигнал синхронизации, действующий после сигнала ф, т.е. Ш.
Рассмотрим вначале так называемый автомат Мура.
В автоматах Мура следующее состояние а (t + 1) определяется как система булевых функций F1, зависящая от номера (или кода) состояния автомата а(t) и множества логических сигналов {б},
а выходные сигналы A(t) задаются системой булевых функций F2, зависящих только от состояния а(t) и не зависящих от {б}.
Для формального описания функционирования автомата в виде графа переходов и набора булевых функций, определяющих выходные сигналы {c}. Произведем разметку ГСА, выполнив несколько этапов формальных действий.
Этап 1.
1. Отметим все операторы действия (кроме логических) с помощью последовательно занумерованных меток аi (i = 0, 1, 2, …). Справа рядом с отмеченным оператором на рис. 57 поставлен номер аi в кружочке.
2. Будем расставлять метки ai от оператора а0 (начало) до конца ак по наиболее длинному пути. Оператор окончания в ГСА также помечается меткой а0. В данной схеме оба пути (как при б2 = 0, так и при б2 = 1) одинаковы по длине. Поэтому предпочтем путь б2 = 0.
3. Далее так же отметим все не помеченные по пункту 2 операторы. На рис. 57 это метка а9 при б2 = 1.
Этап 2.
1. Отмеченные операторы соответствуют внутренним состояниям автомата бi (здесь i = ), через которые в дальнейшем определяются переменные Zj (j = 1, 2, …, p) в зависимости от выбранного проектировщиком способа кодирования множества состояний автомата {a}.
2. Выпишем систему булевых функций F2, соответствующих правилу формирования выходных сигналов {c} как функций состояний. Для данного примера получим:
3. Обозначим каждое состояние аi в виде вершины графа. (граф алгоритма переходов автомата из одно состояния в другое)
Соединим i и j вершины графа направленной стрелкой в том случае, если на ГСА есть путь от ai к aj (i, j = ). Для данного примера получим граф переходов автомата из состояния ai в другое aj в виде рис. 59. Переход из состояния ai в любое другое aj согласно графу рис. 59 происходит в момент t после поступления импульса синхронизации (обозначим ф), т.е. состояние а(t) сменится на a (t+1).
4. Выпишем систему булевых функций F1, определяющих переходы a(t)>a (t + 1). Тогда получим следующую запись по графу переходов:
5.
Сигнал ф не принято опускать как признак наличия «автоматного времени».
Формальный «закон» функционирования автомата Мура может быть задан не только графом переходов и системами F1 и F2.
Зная граф переходов, можно составить таблицу переходов с одновременным отображением в ней как переходов, так и выходных сигналов. Нетрудно видеть, что графу рис. 59 соответствует таблица 24.
|
a (t + 1) a(t) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
0 |
1 |
||||||||||
|
1 |
1 |
||||||||||
|
2 |
б1 |
||||||||||
|
3 |
б2 |
||||||||||
|
4 |
1 |
||||||||||
|
5 |
1 |
||||||||||
|
6 |
б3 |
||||||||||
|
7 |
1 |
||||||||||
|
8 |
1 |
||||||||||
|
9 |
1 |
Иногда в такой таблице (напоминающей МСА) в каждой клетке при наличии перехода по условию (без условия ставится 1) через черточку ставится обозначения сигналов управления. Впрочем, для автоматов Мура в таком обозначении нет необходимости, т.к. функции выходов F1 не зависят от б.
Можно записать обобщенно правило функционирования автомата Мура в виде:
A(t) = F1(a(t)); а (t + 1) = F2(a(t), {б}).
Таблица переходов автомата иногда задается в другом виде (табл. 25)
|
a(t) |
Условие перехода |
a (t + 1) |
c(t) |
A(t) |
|
|
0 |
1 |
1 |
- |
a0 |
|
|
1 |
1 |
2 |
C1 |
a1 |
|
|
2 |
1 3 |
C2 |
a2 |
||
|
3 |
4 9 |
C3C4 |
a3 |
||
|
4 |
1 |
5 |
C1C5 |
a4 |
|
|
5 |
1 |
6 |
C7 |
a5 |
|
|
6 |
3 7 |
C8 |
a6 |
||
|
7 |
1 |
8 |
C5C6 |
a7 |
|
|
8 |
1 |
0 |
C7C9 |
a8 |
|
|
9 |
1 |
5 |
C2C6 |
a9 |
автомат управление граф булевой
Абстрактный синтез автомата Мура завершается получением графа переходов или таблицы переходов с выпиской функций F1 и F2.
Размещено на Allbest.ru
...Подобные документы
Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение булевой функции для реализации функции j. Составление логической схемы автомата, кодирование данных.
курсовая работа [200,4 K], добавлен 27.04.2011Побудова графічної схеми алгоритму та розмітка станів автомата, графа та кодування, структурної таблиці. Синтез комбінаційних схем для функцій збудження тригерів і вихідних сигналів. Представлення функції в канонічних формах алгебр Буля, їх мінімізація.
курсовая работа [902,8 K], добавлен 27.08.2014Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "пси". Определение булевой функции для реализации функции "фи". Составление логической схемы автомата.
курсовая работа [96,7 K], добавлен 27.04.2011Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.
курсовая работа [862,4 K], добавлен 12.12.2012Способи формування функції виходу в автоматі Мілі та автоматі Мура. Кодування станів: кількість регістрів, побудова таблиці переходів. Структурна схема автомата: пам'ять, дешифратор, схема функцій збудження пам'яті. Методика синтезу керуючого автомату.
курсовая работа [410,2 K], добавлен 31.01.2014Синтез функциональной схемы электронных часов по описанию их дополнительных возможностей по отношению к возможности простого отображения времени. Граф управляющего автомата. Кодирование входных и выходных воздействий. Остановка часов, будильник.
реферат [481,3 K], добавлен 27.04.2011Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.
учебное пособие [1,3 M], добавлен 20.08.2014Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Алгоритм, использующий метод Магу-Вейссмана. Общие сведения, описание, вызов и загрузка, функциональное назначение и программный код программы. Описание логической структуры и инструкция пользователю, решение контрольных примеров раскраски графа.
курсовая работа [350,5 K], добавлен 20.12.2009Порядок составления гипотез и решения задач на вероятность определенных событий. Вычисление вероятности выпадения различных цифр при броске костей. Оценка вероятности правильной работы автомата. Нахождение функции распределения числа попаданий в цель.
контрольная работа [56,6 K], добавлен 27.05.2013Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Синтез вариационного исчисления и метода функций Ляпунова в основе принципа динамического программирования. Метод знакопостоянных функций Ляпунова в решении задач о стабилизации и синтезе управления для нелинейной и автономной управляемых систем.
курсовая работа [1,2 M], добавлен 17.06.2011Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
курсовая работа [192,1 K], добавлен 10.10.2011Построение сигнального графа и структурной схемы системы управления. Расчет передаточной функции системы по формуле Мейсона. Анализ устойчивости по критерию Ляпунова. Синтез формирующего фильтра. Оценка качества эквивалентной схемы по переходной функции.
курсовая работа [462,5 K], добавлен 20.10.2013Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011В работе представлено описание не п-разложимых w-насыщенных формаций с п-разложимой максимальной w-насыщенной подформацией. Исследование структурного строения и классификации частично насыщенных формаций конечных групп. Методы абстрактной теории.
курсовая работа [1,8 M], добавлен 21.12.2009Машина Тьюринга как абстрактный исполнитель, осуществляющий алгоритмический процесс. Внешний и внутренний алфавит. Главные функции, цели и возможности памяти и каретки. Описание работы машины. Общий вид решения, записанного с помощью конфигураций.
презентация [1,3 M], добавлен 01.02.2015Аппроксимация функций методом наименьших квадратов. Описание программного средства: спецификация переменных, процедур и функций, схемы алгоритмов. Реализация расчетов в системе Mathcad. Порядок составления графика в данной среде программирования.
курсовая работа [808,9 K], добавлен 09.05.2011Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.
контрольная работа [286,7 K], добавлен 28.02.2009
