Абстрактный синтез конечного автомата (стр. 2 из 3)

2. СТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА

2.1 Кодирование состояний, входных и выходных сигналов

Для кодирования состояний, входных и выходных сигналов конечного автомата, необходимо вычислить число элементов памяти:

а) рассчитаем число элементов памяти: Н = ] log₂h [, где h - число состояний после минимизации D = {

}

H = ] log₂ 12 [ = 4

б) рассчитаем число входных (L) и выходных (М) шин:
L = ] log₂n[

М =] log₂m [,

где n, m - число букв входного и выходного алфавитов

Z = {0, 1} L = ] log₂ 2 [ = 1

W = {0, 1} M = ] log₂ 2 [ = 1

Из приведённого выше следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим их Q₀, …, Q₃. Закодируем состояния (таблица 5) случайными кодами.

Таблица 5. Таблица кодированных состояний

d(t-1)	Q₀	Q₁	Q₂	Q₃
d₀	0	0	0	0
d₁	0	0	0	1
d₂	0	0	1	0
d₃	0	0	1	1
d₄	0	1	0	0
d₅	0	1	0	1
d₆	0	1	1	0
d₇	0	1	1	1
d₈	1	0	0	0
d₉	1	0	0	1
d₁₀	1	0	1	0
d₁₁	1	0	1	1

2.2 Формирование функций возбуждения и выходных сигналов структурного автомата

По минимизированному графу переходов абстрактного автомата (Приложение 2) можно составить таблицу переходов, выходных сигналов и сигналов возбуждения D-триггеров автомата Мили (таблица 6), Т-триггеров автомата Мили (таблица 7), RS-триггеров (таблица 8), JK-триггеров (таблица 9).

D-триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт. Состояние, в которое переходит триггер, совпадает с поступившим на его вход сигналом D(t).

Таблица 6. Таблица переходов, выходных сигналов и сигналов возбуждения D-триггеров

Номер перехода	Исходное состояние	Код исходного состояния	Следующее состояние	Код следующего состояния	Входной набор	Выходные сигналы		Сигналы возбуждения
Номер перехода	Исходное состояние	Код исходного состояния	Следующее состояние	Код следующего состояния	Входной набор	0	1	D₃	D₂	D₁	D₀
1	d₀	0000	d₁d₂	00010010	01	d₀0d₀1	d₀1	d₀0
2	d₁	0001	d₃d₄	00110100	01	d₁0d₁1	d₁1	d₁0	d₁0
3	d₂	0010	d₇d₈	01111000	01	d₂0d₂1	d₂1	d₂0	d₂0	d₂0
4	d₃	0011	d₅	0101	1	d₃1	d₃1	d₃1
5	d₄	0100	d₆	0110	1	d₄1	d₄1	d₄1
6	d₅	0101	d₁₁	1011	0Ú1	d₅0	d₅1	d₅0Úd₅1	d₅0Úd₅1	d₅0Ú d₅1
7	d₆	0110	d₁₁	1011	0	d₆0	d₆0	d₆0	d₆0
8	d₇	0111	d₉	1001	1	d₇1	d₇1	d₇1
9	d₈	1000	d₁₀d₅	10100101	01	d₈0d₈1	d₈0	d₈1	d₈0	d₈1
10	d₉	1001	d₁₁	1011	0	d₉0	d₉0	d₉0	d₉0
11	d₁₀	1010	d₁₁	1011	1	d₁₀1	d₁₀1	d₁₀1	d₁₀1
12	d₁₁	1011	d₀	0000	-	-	-	-	-	-	-

Из таблицы следует, что выходные сигналы автомата Мили описываются следующими выражениями:

= d₂0 Úd₂1 Úd₅0 Úd₆0 Úd₈0 Úd₈1 Úd₁₀1= d₂Úd₅0 Úd₆0 Úd₈Úd₁₀1

= d₀0 Úd₀1 Úd₁0 Úd₁1 Úd₃1 Úd₄1 Úd₅1 Úd₇1 Úd₉0= d₀Úd₁Úd₃1 Úd₄1 Úd₅1 Úd₇1 Úd₉0

Также следует, что сигналы возбуждения D-триггеров автомата Мили описываются следующими выражениями:

D₃ = d₂1 Úd₅0 Úd₅1 Úd₆0 Úd₇1 Úd₈0 Úd₉0 Úd₁₀1= d₂1 Úd₅Úd₆0 Úd₇1 Úd₈0 Úd₉0 Úd₁₀1

D₂ = d₁1 Úd₂0 Úd₃1 Úd₄1 Úd₈1

D₁= d₀1 Úd₁0 Úd₂0 Úd₄1 Úd₅0 Úd₅1 Úd₆0 Úd₈0 Úd₉0 Úd₁₀1=

=d₀1 Úd₁0 Úd₂0 Úd₄1 Ú d₅Úd₆0 Úd₈0 Úd₉0 Úd₁₀1

D₀= d₀0 Úd₁0 Úd₂0 Úd₃1 Úd₅0 Úd₅1 Úd₆0 Úd₇1 Úd₈1 Úd₉0 Úd₁₀1=

=d₀0 Úd₁0 Úd₂0 Úd₃1 Úd₅Úd₆0 Úd₇1 Úd₈1 Úd₉0 Úd₁₀1

Функциональная схема автомата Мили на D-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 3.

Таблица 7. Таблица переходов, выходных сигналов и сигналов возбуждения T-триггеров

Номер перехода	Исходное состояние	Код исходного состояния	Следующее состояние	Код следующего состояния	Входной набор	Выходные сигналы		Сигналы возбуждения
Номер перехода	Исходное состояние	Код исходного состояния	Следующее состояние	Код следующего состояния	Входной набор	0	1	T₃	T₂	T₁	T₀
1	d₀	0000	d₁d₂	00010010	01	d₀0d₀1	d₀1	d₀0
2	d₁	0001	d₃d₄	00110100	01	d₁0d₁1	d₁1	d₁0	d₁1
3	d₂	0010	d₇d₈	01111000	01	d₂0d₂1	d₂1	d₂0	d₂1	d₂0
4	d₃	0011	d₅	0101	1	d₃1	d₃1	d₃1
5	d₄	0100	d₆	0110	1	d₄1	d₄1
6	d₅	0101	d₁₁	1011	0Ú1	d₅0	d₅1	d₅0Úd₅1	d₅0Úd₅1	d₅0Úd₅1
7	d₆	0110	d₁₁	1011	0	d₆0	d₆0	d₆0	d₆0
8	d₇	0111	d₉	1001	1	d₇1	d₇1	d₇1	d₇1
9	d₈	1000	d₁₀d₅	10100101	01	d₈0d₈1	d₈1	d₈1	d₈0	d₈1
10	d₉	1001	d₁₁	1011	0	d₉0	d₉0
11	d₁₀	1010	d₁₁	1011	1	d₁₀1	d₁₀1
12	d₁₁	1011	d₀	0000	-	-	-	-	-	-	-

Из таблицы следует, что сигналы возбуждения T-триггеров автомата Мили описываются следующими выражениями:

T₃= d₂1 Úd₅0 Úd₅1 Úd₆0 Úd₇1 Úd₈1= d₂1 Ú d₅Úd₆0 Úd₇1 Úd₈1

T₂= d₁1 Úd₂0 Úd₃1 Úd₅0 Úd₅1 Úd₆0 Úd₇1 Úd₈1= d₁1 Úd₂0 Úd₃1 Úd₅Úd₆0 Úd₇1 Úd₈1

T₁= d₀1 Úd₁0 Úd₂1 Úd₃1 Úd₄1 Úd₅0 Úd₅1 Úd₇1 Úd₈0 Úd₉0= d₀1 Úd₁0 Úd₂1 Úd₃1 Úd₄1 Úd₅Úd₇1 Úd₈0 Úd₉0

T₀= d₀0 Úd₂0 Úd₆0 Úd₈1 Úd₁₀1

Функциональная схема автомата Мили на T-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 4.

Таблица 8. Таблица переходов и сигналов возбуждения RS-триггеров

Номер перехода	Сигналы возбуждения
Номер перехода	R₃	S₃	R₂	S₂	R₁	S₁	R₀	S₀
1	d₀1	d₀0
2	d₁1	d₁0	d₁1
3	d₂1	d₂0	d₂1	d₂0
4	d₃1	d₃1
5	d₄1
6	d₅0Úd₅1	d₅0Úd₅1	d₅0Úd₅1
7	d₆0	d₆0	d₆0
8	d₇1	d₇1	d₇1
9	d₈1	d₈1	d₈0	d₈1
10	d₉0
11	d₁₀1
12	-	-	-	-	-	-	-	-

Из таблицы следует, что сигналы возбуждения RS-триггеров автомата Мили описываются следующими выражениями: