Математические основы теории систем (стр. 5 из 5)
Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний 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 ≥ log2n = log2 4 = 2;
Количество букв выходного алфавита m = 2
Количество выходовe ≥ log2m = log2 3 = 2;
Количество состояний r = 6
Количество триггеровz ≥ log2r = log2 6 = 3.
Приступаем к кодированию:
| x | u | u1 | u2 | |
| x1 | 1 | 0 | 5 | |
| x2 | 1 | 1 | 4 | |
| x3 | 0 | 0 | 5 | |
| x4 | 0 | 1 | 5 | |
| v1 | v2 | ||
| y1 | 1 | 0 | 1 |
| y2 | 0 | 1 | 9 |
| y3 | 0 | 0 | 9 |
| q | w | w1 | w2 | w3 | |
| q1 | 0 | 0 | 1 | 3 | |
| q2 | 0 | 1 | 0 | 3 | |
| q3 | 0 | 0 | 0 | 4 | |
| q4 | 1 | 0 | 0 | 4 | |
| q5 | 0 | 1 | 1 | 3 | |
| q6 | 1 | 1 | 0 | 2 | |
На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.
Таблица 3
| u1u2 | w1w2w3 | 001 | 010 | 000 | 100 | 011 | 110 |
| 10 | 001/10 | 000/01 | 001/00 | 010/00 | 100/00 | ─ | |
| 11 | 000/01 | ─ | 011/01 | 110/01 | 110/01 | ─ | |
| 00 | 010/01 | 100/01 | 010/00 | 000/00 | ─ | 100/00 | |
| 01 | ─ | 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 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | * | * | * | * | * | * | * | * |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | * | * | * | * | * | * | * | * |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 | * | * | * | * | * | * | * | * |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | * | * | * | * | * | * | * | * |
| 1 | 1 | 1 | 1 | 0 | * | * | * | * | * | * | * | * |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров D1, D2, и D3, зависящих от набора переменных u1, u2, w1 (t), w2 (t), w3 (t). В результате получим систему логических функций для построения комбинационной части автомата:
. 
. 
. 
. 
.Минимизируем функции согласно картам Карно:
После минимизации имеем набор функций в базисе И-НЕ
= 
. 
. 
.Функциональная схема структурного автомата:
