Синтез цифрового автомата

 

При сравнении  произведений π-разбиений и τ-разбиений автоматов видно, что автоматы непосредственно не влияют на входные сигналы друг друга. Однако, при рассмотрении ортогональных π-разбиений видно, что на входной сигнал автомата С влияют D и E совместно, на входной сигнал автомата D – С и E совместно, а на входной сигнал автомата E – C и D совместно. Следовательно, составляющая входного сигнала .

Для составления  таблиц переходов автоматов C,D и E примем следующие обозначения:

E{e1=1234; e2=56}

C{c1=1256; c2=34}

D{d1=135; d2=246}

U={u₁=x₁,x₂; u₂=x₃; u₃=x₄; u₄=x₅}

V={v₁=x₁; v₂=x₂,x₃; v₃=x₄; v₄=x₅}

W={w₁=x₁; w₂=x₂,x₃; w₃=x₄; w₄=x₅}.

 

Таблицы заполняем  по следующему алгоритму на примере  первой ячейки:

c1*d1*e1=1. По сигналу u1(x1,x2) автомат E перейдет в состояния e₁, что мы и запишем в первую ячейку таблицы переходов автомата E.

 

Таким образом  заполняются все ячейки всех трёх автоматов:

 

 

 

δ	e1	e2		δ	c1	c2		δ	d1	d2
c1*d1, u1	e1	e1		e1*d1, v1	c2	c2		e1*c1, w1	d1	d2
c1*d2, u1	e2	e1		e1*d2, v1	c1	c1		e1*c2, w1	d2	d1
c2*d1, u1	e1	e1		e2*d1, v1	c2	c1		e2*c1, w1	d1	d2
c2*d2, u1	e1	e1		e2*d2, v1	c2	c1		e2*c2, w1	d1	d1
c1*d1, u2	e1	e1		e1*d1, v2	c2	c1		e1*c1, w2	d2	d1
c1*d2, u2	e1	e2		e1*d2, v2	c2	c1		e1*c2, w2	d1	d1
c2*d1, u2	e1	e1		e2*d1, v2	c2	c1		e2*c1, w2	d1	d1
c2*d2, u2	e1	e1		e2*d2, v2	c1	c1		e2*c2, w2	d1	d1
c1*d1, u3	e1	e1		e1*d1, v3	c2	c1		e1*c1, w3	d2	d1
c1*d2, u3	e1	e1		e1*d2, v3	c1	c2		e1*c2, w3	d2	d2
c2*d1, u3	e2	e1		e2*d1, v3	c1	c1		e2*c1, w3	d1	d1
c2*d2, u3	e1	e1		e2*d2, v3	c1	c1		e2*c2, w3	d1	d1
c1*d1, u4	e2	e1		e1*d1, v4	c1	c1		e1*c1, w4	d1	d2
c1*d2, u4	e1	e1		e1*d2, v4	c1	c1		e1*c2, w4	d1	d1
c2*d1, u4	e1	e1		e2*d1, v4	c1	c1		e2*c1, w4	d1	d2
c2*d2, u4	e1	e1		e2*d2, v4	c1	c1		e2*c2, w4	d1	d1
				e1*d1, v5	c1	c1
				e1*d2, v5	c2	c1
				e2*d1, v5	c1	c1
				e2*d2, v5	c2	c1

 

 

 

Определение выходных сигналов осуществляется по произведению состояний компонентных автоматов E, C и D и входным сигналам в соответствии с таблицей выходов автомата B.

 

 

 

g	c1*d1*e1	c1*d1*e2	c1*d2*e2	c2*d1*e1	c2*d2*e2
	1	2	3	4	5
x1	y2	y1	y1	y2	y1
x2	y1	y1	y1	y1	y1
x3	y2	y2	y2	y2	y1
x4	y2	y2	y1	y2	y2
x5	y2	y2	y2	y2	y1

 

 

 

 

 

 

 

 

 

 

Глава II. Структурный синтез цифрового автомата.

2.1  Кодирование автомата.

На основании  таблиц переходов и логической функции  строится структурная схема сети автоматов. Структурный автомат представляет собой композицию комбинационной (логической) схемы и элементов памяти, связанных со схемой.  Входными переменными схемы являются входные переменные автомата - сигналы приходящие на блоки Ue, Vc, Wd. Выходы схемы Fe, Fc, Fd  определяют переход автомата в следующее состояние.

Переход от абстрактного автомата к структурному осуществляется через c помощью кодирования входов, выходов и состояний абстрактного автомата.

Кодирование входных  переменных состоит в сопоставлении  каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …,xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор. Для этого необходимо, чтобы выполнялось условие N£2n, где N – число символов входного алфавита.

Кодировать  таблицы переходов и выходов будем в соответствии с условиями:

c₁d₁= e₁c₁= e₁d₁= 00  u₁₌w₁= 00  v₁=  000

c₁d₂= e₁c₂= e₁d₂= 01 u₂₌w₂= 01 v₂= 001

c₂d₁= e₂c₁= e₂d₁= 10 u₃₌w₃= 10 v₃= 010

c₂d₂= e₂c₂= e₂d₂= 11 u₄₌w₄= 11 v₄= 011

v₅= 111

 

 

Получим закодированные таблицы переходов компонентных автоматов:

 

δ	0	1		δ	c1	c2		δ	d1	d2
0000	1	1		00000	0	0		0000	1	0
0100	0	1		01000	1	1		0100	0	1
1000	1	1		10000	0	1		1000	1	0
1100	1	1		11000	0	1		1100	0	0
0001	1	1		00001	0	1		0001	0	1
0101	1	0		01001	0	1		0101	1	1
1001	1	1		10001	0	1		1001	1	1
1101	1	1		11001	1	1		1101	0	0
0010	1	1		00010	0	1		0010	0	1
0110	1	1		01010	1	0		0110	0	0
1010	0	1		10010	1	1		1010	1	1
1110	1	1		11010	1	1		1110	0	0
0011	0	1		00011	1	1		0011	1	0
0111	1	1		01011	1	1		0111	1	1
1011	1	1		10011	1	1		1011	1	0
1111	1	1		11011	1	1		1111	0	0
				00111	1	1
				01111	0	1
				10111	1	1
				11111	0	1

 

 

 

 

 

 

 

Теперь получим  закодированную таблицу переходов  выходных сигналов, для этого примем следующие обозначения:

 

x₁= 000   b₁= 000    y₁= 1   y₂=0

x₂= 001  b₂= 001

x₃= 010  b₃= 010

x₄= 011  b₄= 100

x₅= 111  b₅= 011

b₆= 111

 

g	000	001	010	100	011	111
	1	2	3	4	5	6
000	0	0	0	0	1	1
001	1	0	1	1	1	0
010	0	0	0	0	1	0
100	0	0	1	0	0	0
011	0	0	0	0	0	0

 

При синтезе  цифровых автоматов применяются  триггеры счета или триггеры типа «линия задержки»

Закодируем полученные нами таблицы переходов компонентных автоматов с помощью триггера счета. Для этого проведем инверсию столбцов «1»:

δ	0	1		δ	c1	c2		δ	d1	d2
0000	0	1		00000	1	0		0000	0	0
0100	1	1		01000	0	1		0100	1	1
1000	0	*		10000	1	*		1000	0	0
1100	0	*		11000	1	*		1100	*	*
0001	0	1		00001	1	1		0001	1	1
0101	0	0		01001	1	1		0101	0	1
1001	0	*		10001	1	*		1001	0	1
1101	0	*		11001	0	*		1101	*	*
0010	0	1		00010	1	1		0010	1	1
0110	0	1		01010	0	0		0110	1	0
1010	1	*		10010	0	*		1010	0	1
1110	0	*		11010	0	*		1110	*	*
0011	1	1		00011	0	1		0011	0	0
0111	0	1		01011	0	1		0111	0	1
1011	0	*		10011	0	*		1011	0	0
1111	0	*		11011	0	*		1111	*	*
				00111	0	1
				01111	1	1
				10111	0	*
				11111	1	*

 

 

 

 

 

 

 

 

2.2 Определение функций логики

2.2.1 Определение функции выхода

Данная функция  определяется из таблицы выходов:

g	000	001	010	100	011	111
	1	2	3	4	5	6
000	0	0	0	0	1	1
001	1	0	1	1	1	0
010	0	0	0	0	1	0
100	0	0	1	0	0	0
011	0	0	0	0	0	0

 

Функция выхода определяется из кодированной таблицы  выходов по следующей методике: если обозначить кодирующие переменные входа как а1, а2 и а3,  
состояний – как t1 , t2, t3, выхода – как g,  то функция выхода будет иметь вид:

2.2.2 Определение функции возбуждения триггеров.

Опять обозначим  кодирующие переменные входа как  a1, a2 и a3, состояний – как t, заменив в матрице выходов состояния на их коды, получим описание функций u(t1), u(t2), u(t3).

 

 

 

 

2.3 Упрощение логических функций.

Для упрощения  функций u(t1), u(t2) и u(t3) используем карты Карно:

 

 

 

	0			0		0	0
	0			0		0	1
	0			0		1	0
	0			1		0	0