Конечный автомат задан графом, определенным в задаче 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = { q1, q2 , …, qn }. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X= { x1, x2, x3, x4 }. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.
Автомат позволяет вырабатывать выходные сигналы Y= { y1, y2, y3 }:
y1 - переход из состояния qi в состояние qi (петля);
y2 - переход из состояния qi в qj при i<j;
y3 - переход из состояния qi в qj при i>j.
Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл.1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.
Таблица 1
№ варианта | ||||||||||
Тип элементов | И НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | И НЕ | И ИЛИ НЕ | И НЕ | ИЛИ НЕ | И ИЛИ НЕ | И НЕ |
Тип триггера | D | JK | T | D | RS | RSD | D | JK | T | D |
Решение:
Множество вершин X = {x1, x2, x3, x4, x5, x6},
Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = { q1, q2, q3, q4, q5, q6 }. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X= { x1, x2, x3, x4 }.
Автомат позволяет вырабатывать выходные сигналы Y= { y1, y2, y3 }.
На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:
Гq1 = { q1 (x1/y1), q3 (x2/y2), q2 (x3/y2)},
Гq2 = { q4 (x3/y2), q1 (x4/y3), q3 (x1/y2)},
Гq3 = { q1 (x1/y3), q5 (x2/y2), q2 (x3/y3), q4 (x4/y2)},
Гq4 = { q2 (x1/y3), q6 (x2/y2), q3 (x3/y3), q5 (x4/y2)},
Гq5 = { q3 (x4/y3), q4 (x1/y3), q6 (x2/y2)}, Гq6 = { q4 (x3/y3), q5 (x4/y3)}.
Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл.2.
Таблица 2
X | Q | q1 | q2 | q3 | q4 | q5 | q6 |
X1 | q1/y1 | q3/y2 | q1/y3 | q2/y3 | q4/y3 | ─ | |
X2 | q3/y2 | ─ | q5/y2 | q6/y2 | q6/y2 | ─ | |
X3 | q2/y2 | q4/y2 | q2/y3 | q3/y3 | ─ | q4/y3 | |
X4 | ─ | q1/y3 | q4/y2 | q5/y2 | q3/y3 | q5/y3 |
Осуществим структурный синтез автомата, заданного табл.1. В качестве элементов памяти используем D-триггеры, в качестве элементной базы используем логические элементы И-НЕ.
Количество букв входного алфавита n = 4
Количество входов p ≥ log2 n = log2 4 = 2;
Количество букв выходного алфавита m = 2
Количество выходов e ≥ log2 m = log2 3 = 2;
Количество состояний r = 6
Количество триггеров z ≥ log2 r = log2 6 = 3.
Приступаем к кодированию:
x | u | u1 | u2 | |
x1 | ||||
x2 | ||||
x3 | ||||
x4 |
v1 | v2 | ||
y1 | |||
y2 | |||
y3 |
q | w | w1 | w2 | w3 | |
q1 | |||||
q2 | |||||
q3 | |||||
q4 | |||||
q5 | |||||
q6 |
На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.
Таблица 3
u1u2 | w1w2w3 | ||||||
001/10 | 000/01 | 001/00 | 010/00 | 100/00 | ─ | ||
000/01 | ─ | 011/01 | 110/01 | 110/01 | ─ | ||
010/01 | 100/01 | 010/00 | 000/00 | ─ | 100/00 | ||
─ | 001/00 | 100/01 | 011/01 | 000/00 | 011/00 |
Используя таблицу переходов D-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через D1, D2, D3, соответственно.
Таблица 4
u1 | u2 | w1 (t) | w2 (t) | w3 (t) | w1 (t+1) | w2 (t+1) | w3 (t+1) | v1 | v2 | D1 | D2 | D3 |
* | * | * | * | * | * | * | * | |||||
* | * | * | * | * | * | * | * | |||||
* | * | * | * | * | * | * | * | |||||
* | * | * | * | * | * | * | * | |||||
* | * | * | * | * | * | * | * | |||||
По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров D1, D2, и D3, зависящих от набора переменных u1, u2, w1 (t), w2 (t), w3 (t). В результате получим систему логических функций для построения комбинационной части автомата:
.
.
.
.
.
Минимизируем функции согласно картам Карно:
После минимизации имеем набор функций в базисе И-НЕ
=
.
.
.
Функциональная схема структурного автомата: