Синтез комбінаційної схеми

2.1 Вибір вихідних  даних

 

Граф схема складається з  чотирьох блоків E,F,G,H і вершин BEGIN та END.

Вони обираються наступним чином:

- блок E 17 mod 5 = 2;

- блок F 7 mod 5 = 2;

- блок G 1 mod 5 = 1;

- блок H 25 mod 5 = 0.

Блоки E, F, G, H з’єднуються між собою схемою яка має вигляд :

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2 – Алгоритм

Граф-схема алгоритму  показана в додатку 1.

Тип тригера обирається за формулою: 17mod4=1.

Отже для автомата Мілі використовуємо D тригер, а для Мура – JK. Серія інтегральних мікросхем для побудови принципових мікросхем КР 555.

 

2.2 Структурний синтез автомата  Мілі.

 

2.2.1 Розмітка ГСА для автомата Мілі.

 

Для автомата Мілі розмітка ГСА позначається буквою bi. Відмічаються входи в вершини, які слідують за операторними. Виходячи з цього ми отримуємо для автомата Мілі 21 стан.

 

2.2.2 Кодування станів.

 

Оскільки ми використовуємо D тригер, а його особливістю є те, що вихід тригера такий же як стан у момент часу (t+1), то для оптимального кодування будуємо таблицю переключення автомата, тобто записуємо скільки разів автомат переключається у певний стан.

Таблиця 8 – Переключення автомата

Стан	Кількість переключень
b0	6
b1	1
b2	2
b3	1
b4	2
b5	2
b6	1
b7	2
b8	1
b9	2
b10	2
b11	2
b12	2
b13	1
b14	1
b15	2
b16	2
b17	2
b18	2
b19	2
b20	1

Оптимальне кодування станів буде таким:

Таблиця 9 – Оптимальне кодування станів

Стан	Кількість переключень		Кодування
b0	6		00000
b2	2		00001
b4	2		00010
b5	2		00100
b7	2		01000
b9	2		10000
b10	2		00011
b11	2		00110
b12	2		01100
b15	2		11000
b16	2		10001
b17	2		10010
b18	2		10100
b19	2		01010
b1	1		01011
b3	1		01001
b6	1		00101
b8	1		00111
b13	1		01110
b14	1		11100
b20	1		10110

 

2.2.3 Таблиця переходів автомата  Мілі.

 

На основі ГСА і закодованих  стані будуємо таблицю10 переходів автомата.

Останній стовбець таблиці  10 заповнюється за допомогою оберненої таблиці переходів D- тригера .

Таблиця 10 – Переходи автомата

b(t)	K(b(t))	b(t+1)	K(b(t+1))	x	y	ФЗ
b0	00000	b1	01011	1	y2y4	D2D4D5
b1	01011	b2	00001	1	y7	D5
b2	00001	b3	01001	|x1	y1y9	D2D5
		b9	10000	x1	y8	D1
b3	01001	b4	00010	1	y2y4	D4
b4	00010	b5	00100	1	y7	D3
b5	00100	b6	00101	|x1	y1y9	D3D5
		b11	00110	x1	y8	D3D4
b6	00101	b7	01000	1	y3y6	D2
b7	01000	b2	00001	x5	y7	D5
		b8	00111	|x5x6	y3	D3D4D5
		b9	10000	|x5|x6	y8	D1
b8	00111	b10	00011	1	y3y6	D4D5
b9	10000	b4	00010	x2	y2y4	D4
		b10	00011	|x2	y3y6	D4D5
b10	00011	b5	00100	x5	y7	D3
		b11	00110	|x5|x6	y8	D3D4
		b12	01100	|x5x6	y1y8	D2D3
b11	00110	b7	01000	x2	y3y6	D2
		b12	01100	|x2	y1y8	D2D3
b12	01100	b13	01110	x4	y4	D2D3D4
		b16	10001	|x3	y3y10	D1D5
b13	01110	b14	11100	1	y4y5	D1D2D3
b14	11100	b15	11000	1	y1y2	D1D2
b15	11000	b0	00000	|x4x2	y4y5	-
		b20	10110	x4	y3	D1D3D4
		b18	10100	|x1|x2|x4	y5y9	D1D3
		b0	00000	x1|x2|x4	-	-
b16	10001	b15	11000	1	y1y2	D1D2
b17	10010	b0	00000	|x3	y2y6	-
		b19	01010	x3	y7	D2D4
b18	10100	b16	10001	x4|x3	y3y10	D1D5
		b17	10010	x3x4	y6	D1D4
		b17	10010	|x4x1	y6	D1D4
		b0	00000	x1|x3|x4	y2y6	-
		b19	01010	x1|x3x4	y7	D2D4
b19	01010	b0	00000	x1	-	-
		b18	10100	|x1	y5y9	D1D3
b20	10110	b0	00000	1	y2y6	-

Побудуємо на основі останньої колонки Таблиці 13 функції збудження і приведемо їх до базису І-НІ:

D1=| (| (b2x1) | (b7|x5|x6) |(b12|x3) |b13|b14|(b15x4) |(b15|x1|x2|x4) |b16|(b18|x3x4) | (b18x3x4) |(b18|x4x1) |(b19|x1))

D2=|(|b0|(b2|x1) |b6|(b10|x5x6) |(b11x2) |b11|(b12x4) |b13|b14|b16|(b17x3) |(b18|x1x3|x4))

D3=|(|b4|b5|(b7|x5x6) | (b10x5) |(b10|x5|x6) |(b10Vx5x6) |(b11|x2) |(b12x4) |b13|(b15x4) |(b15|x1|x2) |(b19|x1))

D5=|(|b0|b1|(b2|x1) |(b5|x1) |b5x7) |(b7|x5x6) |b8|(b9|x2) |(b12|x3) |(b18|3x4))

На основі передостанньої колонки  Таблиці 10 будуємо функції виходу:

Y1=|(|(b2|x1) | (b5|x1) | (b10|x5x6) | (b11x2) |b14|b16)

Y2=|(|b0|b3| (b9x2) |b14|b16|(b17|x3) |(b18|x1|x3|x4) |b20)

Y3=|(|b|(b7|x5x6) |b8| (b9|x2) |(b11x2) |(b12|x3) |(b15x4) |(b18|x3x4))

Y4=|(|b0|b3|(b9x2) |(b12x4) |b13|(b15|x4x2))

Y5=|(|b13|(b15x2|x4) |(b15|x1|x2|x4) |b19)

Y6=|(|b6|b8|(b9|x2) |(b11x2) |(b16|x3) |(b18x3x4)(b18x1|x4) |(b18|x1|x3|x4) |b20)

Y7=|(|b1|b4|(b7x5) |(b10x5) |(b17x3) |(b18|x1x3|x4))

Y8=|(| (b2|x1) |(b5x1) |b7|x5|x6) |(b10|x5|x6) |(b11|x2))

Y9=|(|(b2|x1) |(b5|x1) |(b15|x1|x2|x4) |(b19|x1))

Y10=|(|(b12|x3) |(b18x4|x3))

 

За отриманими функціями збудження  та виходу будуємо схему автомата Мілі. Вона представлена у додатку 2.

2.3 Структурний  синтез автомата Мура.

 

2.3.1 Розмітка ГСА для автомата  Мура.

 

Для автомата Мура розмітка ГСА позначається буквою аi (Додаток 1).

Відмічаються всі операторні вершини, вершина початку та кінця позначається а₀. Таким чином для автомата Мура ми отримали 23 стани.

 

2.3.2 Кодування станів.

 

Для оптимального кодування станів автомата використовуємо евристичний метод. Для цього будуємо матрицю Т. Перший стовбець цієї матриці номер вихідного стану, другий – номер стану в який переключається автомат, а третій кількість переходів між даними станами.

Матриця Т:

i	j	P(i,j)
1	2	2
2	3	1
3	5	1
3	6	1
4	3	1
4	6	4
4	7	2
4	8	1
6	8	1
5	9	1
7	9	1
8	10	1
9	11	1
9	12	1
9	13	1
10	11	1
10	12	2
11	4	1
12	4	1
12	13	1
13	15	1
13	17	1
13	18	2
14	17	1
14	18	1
14	22	1
14	23	1
15	16	1
16	19	1
17	19	2
18	22	1
18	23	1
19	21	1
19	20	1
19	1	1
19	14	1
20	1	2
21	22	1
22	1	1
23	14	1
23	1	1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Оптимальне кодування станів буде таким:

Таблиця 11 – Оптимальне кодування станів

a0	00011
a1	00111
a2	01111
a3	11111
a4	01101
a5	01011
a6	11100
a7	11011
a8	11101
a9	10011
a10	11001
a11	10111
a12	10101
a13	00000
a14	10001
a15	10010
a16	10000
a17	00101
a18	00010
a19	01010
a20	00110
a21	00100
a22	00001

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3.3 Таблиця переходів автомата  Мура.

 

На основі ГСА і закодованих стані будуємо таблицю13 переходів автомата.

Останній стовбець таблиці  12 заповнюється за допомогою оберненої таблиці переходів JK- тригера ( таблиця 12 ).

 

Таблиця 12 – Обернена таблиці переходів JK- тригера

Q(t)	Q(t+1)	J	K
0	0	X	0
0	1	1	X
1	0	X	1
1	1	0	X