Читайте также:
|
|
5.2.1. Абстрактный синтез автомата Мура
Для синтеза схемы конечного автомата Мура необходимо иметь таблицу соответствия, которая получается на основе словесной формулировки работы синтезируемого автомата.
Пример 5.. Получена следующая таблица соответствия: U 0 U 1 U 2 U 0 U 1 U 2 U 3 U 0 – V 0 V 1 V 2 V 0 V 2 V 1 V 1 V 0. Аналогично, как и при синтезе автомата Мили, каждому переходу таблицы соответствия присваивается внутреннее состояние и получается таблица 5.21.
Таблица 5.21.
Таблица соответствия
U 0 | – | а 0 | – | V 0 |
U 1 | – | а 1 | – | V 1 |
U 2 | – | а 2 | – | V 2 |
U 0 | – | а 3 | – | V 0 |
U 1 | – | а 4 | – | V 2 |
U 2 | – | а 5 | – | V 1 |
U 3 | – | а 6 | – | V 1 |
U 0 | – | а 7 | – | V 0 |
Для синтеза схемы автомата Мура строится отмеченная таблица переходов. Отмеченная таблица переходов отличается от совмещенной таблицы переходов и выходов автомата Мили тем, что выходами автомата отмечаются все столбцы таблицы переходов. В клетках этой таблицы ставятся только внутренние состояния автомата, число строк и столбцов будет таким же, как и в совмещенной таблице переходов и выходов автомата Мили.
Таблица 5.22.
Отмеченная таблица переходов
V 0 | V 1 | V 2 | V 0 | V 2 | V 1 | V 1 | V 0 | |
а 0 | а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | |
U 0 | а 0 | а 3 | а 3 | а 7 | а 7 | |||
U 1 | а 1 | а 1 | а 4 | а 4 | ||||
U 2 | а 2 | а 2 | а 5 | а 5 | ||||
U 3 | а 6 | а 6 |
Для минимизации отмеченной таблицы переходов (для объединения столбцов) существуют два условия:
- необходимое условие заключается в том, что внутренние состояния, которыми обозначены столбцы, могут объединяться между собой, если они отмечены одинаковыми выходами;
- достаточное условие позволяет объединять столбцы только в том случае, если после переобозначения внутренних состояний в объединяемых клетках будут находиться одинаковые внутренние состояния, или одна клетка заполнена, а другая пустая, или обе клетки пустые.
При минимизации отмеченной таблицы переходов все символы внутренних состояний развиваются на R группы, количество которых равно числу попарно различимых выходных символов. В каждую группу вносятся только те символы внутренних состояний аi, которые отмечены одинаковыми выходными символами Vj. В отмеченной таблице переходов 5.22 . Переобозначив внутренние состояния символом g по необходимому условию получаем
х 0 – а 0 а 3 а 7, отмеченные выходом V 0
х 1 – а 1 а 5 а 6, отмеченные выходом V 1
х 2 – а 2 а 4, отмеченные выходом V 2
После переобозначения внутренних состояний строится таблица 5.23 для проверки выполнения достаточного условия.
Таблица 5.23.
Отмеченная таблица переходов
V 0 | V 1 | V 2 | V 0 | V 2 | V 1 | V 1 | V 0 | |
а 0 | а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | |
g 0 | g 1 | g 2 | g 0 | g 2 | g 1 | g 1 | g 0 | |
U 0 | g 0 | g 0 | g 0 | g 0 | g 0 | |||
U 1 | g 1 | g 1 | g 2 | g 2 | ||||
U 2 | g 2 | g 2 | g 1 | g 1 | ||||
U 3 | g 1 | g 1 |
В полученной таблице 5.23 проверяется выполнение достаточного условия. В строке U 1 ранее намеченные к объединению столбцы а 0 и а 3 по достаточному условию не объединяются в клетке столбца а 0 и строки U 1 стоит внутреннее состояние х 1, а клетке строки U 1 и столбца а 3 внутреннее состояние х 2.
По аналогичным причинам не объединяются столбцы а 1 а 5 и а 2 а 4, поэтому необходимо произвести новое переобозначение внутренних состояний
g 0 – а 0 а 7
g 1 – а 1
g 2 – а 5 а 6
g 3 – а 2
g 4 – а 4
g 5 – а 3
Для проверки выполнения достаточного условия строится таблица 5.24. Из таблицы 5.24 следует, что достаточные условия выполняются. Минимальная таблица переходов автомата Мура представлена таблицей 5.25.
Таблица 5.24.
Отмеченная таблица переходов
V 0 | V 1 | V 2 | V 0 | V 2 | V 1 | V 1 | V 0 | |
а 0 | а 1 | а 2 | а 3 | а 4 | а 5 | а 6 | а 7 | |
g 0 | g 1 | g 3 | g 5 | g 4 | g 2 | g 2 | g 0 | |
U 0 | g 0 | g 5 | g 5 | g 0 | g 0 | |||
U 1 | g 1 | g 1 | g 4 | g 4 | ||||
U 2 | g 3 | g 3 | g 2 | g 2 | ||||
U 3 | g 2 | g 2 |
Таблица 5.25.
Минимальная таблица автомата Мура
V 0 | V 1 | V 2 | V 0 | V 2 | V 1 | |
g 0 | g 1 | g 3 | g 5 | g 4 | g 2 | |
U 0 | g 0 | g 5 | g 5 | g 0 | ||
U 1 | g 1 | g 1 | g 4 | g 4 | ||
U 2 | g 3 | g 3 | g 2 | g 2 | ||
U 3 | g 2 |
5.2.2. Структурный синтез автоматов Мура
Кодирование входов, выходов и внутренних состояний осуществляется так же, как и для автоматов Мили
Для кодирования внутренних состояний необходимо построить граф автомата (рис. 5.9).
Рис. 5.9. Граф автомата Мура
После кодирования входов, выходов и внутренних состояний строится структурная таблица переходов автомата Мура.
Таблица 5.26.
Структурная таблица переходов
у 1 у 2 | ||||||
Q 1 Q 2 Q 3 х 1 х 2 | ||||||
Из структурной таблицы 5.26 следует, что синтезируемый автомат Мура имеет два входа х 1 х 2, два выхода у 1 у 2 и три элемента памяти Q 1 Q 2 Q 3.
Уравнения выходов получаются непосредственно из структурной таблицы переходов следующим образом. Из столбцов где у 1 равен единице в уравнение у 1 в качестве слагаемых берутся коды внутренних состояний, которыми обозначены столбцы таблицы переходов. Аналогично записывается уравнение для у 2
.
Как видно из уравнений выходы у 1 у 2 автомата Мура формируются только элементами памяти, а выходы автомата Мили формируются как элементами памяти, так и входами х 1 х …
Для получения уравнений возбуждения элементов памяти необходимо выбрать элементы автоматики и телемеханики, которые будут использоваться в качестве элементов памяти в автомате Мура.
Если в качестве элементов памяти будет использоваться реле, то таблица переходов автомата Мура 5.26 одновременно будет и таблицей возбуждения.
Для получения минимальных уравнений возбуждения элементов памяти необходимо таблицу 5.26 преобразовать к виду таблицы минимизации на пять переменных. Для этого надо последние две строки поменять местами и добавить два столбца с недостающими кодами 010 и 101.
Таблица 5.27.
Преобразовательная таблица переходов
q 1 q 2 q 3 х 1 х 2 | ||||||||
Получение уравнения возбуждения элемента памяти Q 1
Таблица 5.28.
Таблица минимизации
011 | ||||||||
.
Аналогично получаются уравнения возбуждения элементов памяти Q 2 и Q 3.
Таблица 5.29.
000 | ||||||||
.
Таблица 5.30.
.
Схема электрическая функциональная автомата Мура на релейно-контактных элементах показана на рисунке 5.1.
Рис. 5.10. Схема электрическая функциональная автомата Мура
Дата добавления: 2015-07-25; просмотров: 98 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
СИНТЕЗ КОНЕЧНЫХ АВТОМАТОВ МИЛИ | | | ЗАДАЧИ АНАЛИЗА |