Задача 4. Элементы математической логики и теории автоматов

 

Конечный автомат задан графом, определенным в задаче 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = {q ₁, q ₂ ,…, q_n}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X ={x ₁, x ₂, x ₃, x ₄}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.

Автомат позволяет вырабатывать выходные сигналы Y ={y ₁, y ₂, y ₃}:

y ₁ - переход из состояния q_i в состояние q_i (петля);

y ₂ - переход из состояния q_i в q_j при i < j;

y ₃ - переход из состояния q_i в q_j при i > j .

Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл.1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.

 

Таблица 1

№  варианта	11	12	13	14	15	16	17	18	19	20
Тип элементов	И НЕ	И ИЛИ НЕ	И НЕ	ИЛИ НЕ	И НЕ	И ИЛИ НЕ	И НЕ	ИЛИ НЕ	И ИЛИ НЕ	И НЕ
Тип триггера	D	JK	T	D	RS	RSD	D	JK	T	D

 

Решение:

Множество вершин X = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆ },

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q ₁, q ₂, q ₃, q ₄, q ₅, q ₆}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X ={x ₁, x ₂, x ₃, x ₄}.

Автомат позволяет вырабатывать выходные сигналы Y ={y ₁ , y ₂, y ₃}.

На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:

 

Г q₁ = {q₁ (x₁/y₁), q₃ (x₂/y₂), q₂ (x₃/y₂)},

Г q₂ = {q₄ (x₃/y₂), q₁ (x₄/y₃), q₃ (x₁/y₂)},

Г q₃ = {q₁ (x₁/y₃), q₅ (x₂/y₂), q₂ (x₃/y₃), q₄ (x₄/y₂)},

Г q₄ = {q₂ (x₁/y₃), q₆ (x₂/y₂), q₃ (x₃/y₃), q₅ (x₄/y₂)},

Г q₅ = {q₃ (x₄/y₃), q₄ (x₁/y₃), q₆ (x₂/y₂)}, Г q ₆ = {q ₄ (x ₃ / y ₃), q ₅ (x ₄ / y ₃)}.

 

Обобщенная таблица переходов и выходов соответствующего конечного автомата представлена в табл.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 ≥ log₂ n = log₂ 4 = 2;

Количество букв выходного алфавита m = 2

Количество выходовe ≥ log₂ m = log₂ 3 = 2;

Количество состояний r = 6

Количество триггеровz ≥ log₂ r = log₂ 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). Функции возбуждения трех триггеров обозначены через D₁, D₂, D₃, соответственно.

 

Таблица 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 и функций возбуждения триггеров D₁, D₂, и D₃, зависящих от набора переменных u₁, u₂, w₁ (t), w₂ (t), w₃ (t). В результате получим систему логических функций для построения комбинационной части автомата:

 

.

.

.

.

.

 

Минимизируем функции согласно картам Карно:

 

 

 

 

 

 

 

 

 

 

 

После минимизации имеем набор функций в базисе И-НЕ

 

=

.

.

.

 

Функциональная схема структурного автомата: