Синтез комбінаційної схеми та проектування керуючого автомата Мура

Міністерство освіти і науки України

Одеський національний політехнічний університет

Кафедра інформаційних систем

Курсова робота
з дисципліни
“Схемотехніка еом”
Виконав: студент гр.
Керівник:
Загальна оцінка______________
Одеса 2002

Анотація
Курсовий проект з дисципліни “Схемотехніка ЕОМ” являє собою засіб перевірення накопичених теоретичних знань та їх застосування з метою набуття практичних навичок в даній галузі. Ця робота включає синтез комбінаційної схеми для булевої функції п’яти змінних та проектування керуючих автоматів Мілі і Мура, заданих граф-схемою. Побудова автоматів ведеться з урахуванням реальної серії елементів, тому має і практичне значення з можливістю використання отриманого результату у промислових цілях.

Міністерство освіти і науки України
Одеський національний політехнічний університет
Інститут комп’ютерних систем
Кафедра інформаційних систем
Завдання
до курсової роботи з дисципліни
“Схемотехніка ЕОМ”
студента гр. АІ-001 Ткаченко І.О.
Тема: “Синтез комбінаційної схеми та проектування керуючого автомата Мура”.

1.                Вхідні дані до проекту:
1.1            Булева функція п’яти змінних.
1.2            Граф-схема керуючих автоматів Мілі і Мура.
2.                Склад розрахунково-пояснювальної записки:
2.1            Синтез комбінаційної схеми для булевої функції.
2.2            Проектування автоматів.
3.                Графічний матеріал:
3.1            1 – граф - схема керуючого автомата (А3).
3.2            2 – граф - схема керуючого автомата (А3).
3.3            Лист 3 – принципова схема автомата Мура (А1).
3.4            Лист 4 – комбінаційна схема (А4).
Дата видачі завдання: “____” . “____” . 2002
Дата захисту роботи: “____” . “____” . 2002
Керівник: Ніколенко А.О.
Прийняв до виконання: Ткаченко І.О.

Зміст
Завдання на розробку
Зміст
Синтез комбінаційної схеми
Розрахування значень
Мінімізація БФ
Комбінаційна схема
Проектування автоматів
Вибір завдання
Автомат Мура
Автомат Мілі
Заключення
Перелік літератури

1 Синтез комбінаційної схеми
1.1 Визначення значень БФ
Булева функція 5 змінних F(x1,x2,x3,x4,x5) задається своїми значеннями, які визначаються 7-разрядовими двійковими еквівалентами чисел: по значенню чисел А (на наборах 0-6), В (на наборах 7-13), С (набори 14-20), по значенню (А+В+С) (набори 21-27) і на наборах 28-31 функції приймає невизначені значення.
А=13 еквівалентно 49₁₀=110001₂.
Проставляємо символ невизначеного значення Х110001.
В=07 еквівалентно 10₁₀=1010₂.
Проставляємо символ невизначеного значення ХХХ1010.
С=21 еквівалентно 23₁₀=10111₂.
Проставляємо символ невизначеного значення XХ10111.
А+В+С=41 еквівалентно 72₁₀=1001000₂.
Відповідно, значення функцій F(x1,x2,x3,x4,x5) на наборах від 0 до 31 буде мати вигляд:
Таблиця 1

№ набору	X1	X2	X3	X4	X5	F
0	0	0	0	0	0	X
1	0	0	0	0	1	1
2	0	0	0	1	0	1
3	0	0	0	1	1	0
4	0	0	1	0	0	0
5	0	0	1	0	1	0
6	0	0	1	1	0	1
7	0	0	1	1	1	X
8	0	1	0	0	0	X
9	0	1	0	0	1	X
10	0	1	0	1	0	1
11	0	1	0	1	1	0
12	0	1	1	0	0	1
13	0	1	1	0	1	0
14	0	1	1	1	0	X
15	0	1	1	1	1	X
16	1	0	0	0	0	1
17	1	0	0	0	1	0
18	1	0	0	1	0	1
19	1	0	0	1	1	1
20	1	0	1	0	0	1
21	1	0	1	0	1	1
22	1	0	1	1	0	0
23	1	0	1	1	1	0
24	1	1	0	0	0	1
25	1	1	0	0	1	0
26	1	1	0	1	0	0
27	1	1	0	1	1	0
28	1	1	1	0	0	X
29	1	1	1	0	1	X
30	1	1	1	1	0	X
31	1	1	1	1	1	X

1.2 Мінімізація БФ
Отримуємо МДНФ і МКНФ булевой функції за допомогою метода карт Карно. Схеми карт Карно приведені нижче:
Таблиця 2 Карта Карно до МДНФ.

	000	001	011	010	110	111	101	100
00	X	1	0	1	1	X	0	0
01	X	X	0	1	X	X	0	1
11	1	0	0	0	X	X	X	X
10	1	0	1	1	0	0	1	1

В результаті мінімізації, отримаємо:
 _ _ _ _ _ _ _ _ _ _ _ _ _
Y=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄
Таблиця 3 Карта Карно до МКНФ

	000	001	011	010	110	111	101	100
00	X	1	0	1	1	X	0	0
01	X	X	0	1	X	X	0	1
11	1	0	0	0	X	X	X	X
10	1	0	1	1	0	0	1	1

В результаті мінімізації, отримаємо:
 _ _ _ _ _ _ _ _ _ _
y=(X₁+X₂+X₄+X₅)(X₁+X₃ +X₄ +X₅)(X₁+ X₃+ X₄+ X₅)(X₁+X₂+ X₄)(X₁+X₃+ X₄)
 _ _
(X₁+X₃+X₅)
1.3 Опис мінімізації БФ заданими методами
Для вибору мінімальної з МДНФ і МКНФ оцінимо складність схеми за допомогою ціни по Квайну. Ціна по Квайну визначається як сумарне число входів логічних елементів у складі схеми.
Такий підхід обумовлений тим, що
- складність схеми легко обчислюється по БФ, на основі яких будується схема: для ДНФ складність дорівнює сумі кількості літер, (літері зі знаком відповідає ціна 2), і кількість знаків диз’юнкції, збільшеного на 1 для кожного диз’юнктивного виразу.
- усі класичні методи мінімізації БФ забезпечують мінімальність схемі саме у змісті ціни по Квайну.
Схема с мінімальною ціною по Квайну часто реалізується з найменшим числом конструктивних елементів – корпусів інтегральних мікросхем.
Для даних функцій ми маємо:
C_кв (МДНФ)=19+6+5=30;
C_кв(МКНФ)=21+6+5=32.
Так як мінімальною ціною є C_кв(МКНФ), то для реалізації схеми будемо використовувати МДНФ.
1.4 Приведення БФ до заданого базису
Заданий базис: 3 І-НІ.
Приведемо вираз до заданого базису:
 _ _ _ _ _ _ _ _ _ _ _ _ _
Y=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄ =
=X₃(X₁X_4*X₄X_5*X₁X₂X₄)_*X₅(X₂X_4*X₁X₄)_*X₁X₃X₄
Для реалізації функції по останьому виразу необхідно 16 елементів 3І-НІ (Рис.1). Ранг даної схеми дорівнює 4, що негативно відображається на швидкості. Використав факторний алгоритм можливо покращити схему, збільшити швидкість його роботи.
Рис. 1 Функціональна схема для заданого базису


2. Проектування автоматів
2.1 Вибір завдання
Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: E, F, G, H. Студенти обирають граф-схему із п’яти блоків з номерами 0...4 на підставі чисел А, В, С та (А+В+С) за наступними правилами:
- блок "Е" – схема під номером (А) mod 5 = 13 mod 5 = 3;
- блок "F" – схема під номером (В) mod 5 = 7 mod 5 = 2;
- блок "G" – схема під номером (С) mod 5 = 21 mod 5 = 1;
- блок "H" – схема під номером (А+В+С) mod 5 = 41 mod 5 = 1.
Розташування обирається з використанням номера групи. Тип тригера знаходимо по таблиці на підставі числа (А) mod 3 = 13 mod 3 = 1.   

(A) mod 3	ТИП ТРИГЕРА
0	Т	D
1	D	JK
2	JK	T
автомат	Мілі	Мура

Отримуємо D-тригер для автомата Мілі та JK-тригер для Мура. Для парних номерів за списком (21) - серія КР555.
Після відповідної розмітки будуємо таблиці переходів для обох автоматів.
2.2           Автомат Мура:
Будуємо таблицю переходів для автомата Мура.
Кодування станів виконуємо за еврістичним алгоритмом. Для цього будуємо матрицю Т.
║T║ =
 i │ j │ P(i,j)
 1 │ 2 │ 1
 1 │ 24│ 1
 1 │ 25│ 1
 2 │ 4 │ 1
 2 │ 6 │ 1
 2 │ 7 │ 1
 3 │ 5 │ 1
 3 │ 6 │ 1
 3 │ 7 │ 1
 3 │ 13 │ 1
 3 │ 14 │ 1
 4 │ 6 │ 1
 4 │ 7 │ 1
 5 │ 6 │ 1
 5 │ 7 │ 2
 6 │ 8 │ 1
 6 │ 9 │ 1
 7 │ 8 │ 1
 8 │ 10 │ 1
 9 │ 11 │ 1
 10│ 11 │ 1
 10│ 13 │ 1
 10│ 14 │ 1
 11│ 12 │ 1
 11│ 13 │ 1
 12│ 15 │ 1
 13│ 15 │ 1
 15│ 17 │ 1
 15│ 19 │ 1
 15│ 20 │ 1
 16│ 19 │ 1
 16│ 20 │ 2
 16│ 22 │ 2
 16│ 26 │ 1
 17│ 18 │ 1
 18│ 21 │ 1
 19│ 21 │ 1
 20│ 22 │ 1
 21│ 23 │ 1
 21│ 25 │ 1
 21│ 26 │ 1
 22│ 25 │ 1
 22│ 26 │ 2
 23│ 24 │ 1
Підкрашуємо вагу всіх компонентів всіх пар
P(1) = 3
P(2) = 4
P(3) = 5
P(4) = 3
P(5) = 3
P(6) = 6
P(7) = 5
P(8) = 3
P(9) = 2
P(10) = 4
P(11) = 4
P(12) = 2
P(13) = 4
P(14) = 2
P(15) = 5
P(16) = 4
P(17) = 2
P(18) = 2
P(19) = 3
P(20) = 3
P(21) = 5
P(22) = 4
P(23) = 2
P(24) = 2
P(25) = 3
P(26) = 3
Далі згідно правил алгоритму будуємо матрицю М
 ║M║ =
 i │ j │ P(i,j)
 5 │ 7 │ 2
 3 │ 7 │ 1
 3 │ 6 │ 1
 2 │ 6 │ 1
 2 │ 7 │ 1
 3 │ 13 │ 1
 4 │ 6 │ 1
 5 │ 6 │ 1
 6 │ 8 │ 1
 13 │ 15 │ 1
 3 │ 5 │ 1
 4 │ 7 │ 1
 6 │ 9 │ 1
 7 │ 8 │ 1
 10 │ 13 │ 1
 10 │ 11 │ 1
 11 │ 13 │ 1
 15 │ 19 │ 1
 15 │ 20 │ 1
 16 │ 20 │ 2
 16 │ 22 │ 2
 22 │ 26 │ 2
 19 │ 21 │ 1
 21 │ 25 │ 1
 21 │ 26 │ 1
 1 │ 2 │ 1
 2 │ 4 │ 1
 3 │ 14 │ 1
 8 │ 10 │ 1
 12 │ 15 │ 1
 15 │ 17 │ 1
 16 │ 19 │ 1
 16 │ 26 │ 1
 18 │ 21 │ 1
 20 │ 22 │ 1
 21 │ 23 │ 1
 22 │ 25 │ 1
 1 │ 25 │ 1
 9 │ 11 │ 1
 10 │ 14 │ 1
 11 │ 12 │ 1
 1 │ 24 │ 1
 17 │ 18 │ 1
 23 │ 24 │ 1
Визначемо розрядність кода для кодування станів автомата
R = ] log2 N [ = ] log2 26 [ = 5
Результати кодування:
 a1 10101
 a2 00101
 a3 00010
 a4 00111
 a5 00000
 a6 00011
 a7 00001
 a8 01011
 a9 10011
a10 01010
a11 11010
a12 11110
a13 10010
a14 01000
a15 10110
a16 00100
a17 10111
a18 11111
a19 10100
a20 00110
a21 11101
a22 01100
a23 11001
a24 10001
a25 11100
a26 01101
Підрахунок ефективності кодування:
Кількість перемикань тригерів:
W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,24)*d(1,24) + P(1,25)*d(1,25) + P(2,4)*d(2,4) + P(2,6)*d(2,6) + P(2,7)*d(2,7) + P(3,5)*d(3,5) + P(3,6)*d(3,6) + P(3,7)*d(3,7) + P(3,13)*d(3,13) + P(3,14)*d(3,14) + P(4,6)*d(4,6) + P(4,7)*d(4,7) + P(5,6)*d(5,6) + P(5,7)*d(5,7) + P(6,8)*d(6,8) + P(6,9)*d(6,9) + P(7,8)*d(7,8) + P(8,10)*d(8,10) + P(9,11)*d(9,11) + P(10,11)*d(10,11) + P(10,13)*d(10,13) + P(10,14)*d(10,14) + P(11,12)*d(11,12) + P(11,13)*d(11,13) + P(12,15)*d(12,15) + P(13,15)*d(13,15) + P(15,17)*d(15,17) + P(15,19)*d(15,19) + P(15,20)*d(15,20) + P(16,19)*d(16,19) + P(16,20)*d(16,20) + P(16,22)*d(16,22) + P(16,26)*d(16,26) + P(17,18)*d(17,18) + P(18,21)*d(18,21) + P(19,21)*d(19,21) + P(20,22)*d(20,22) + P(21,23)*d(21,23) + P(21,25)*d(21,25) + P(21,26)*d(21,26) + P(22,25)*d(22,25) + P(22,26)*d(22,26) + P(23,24)*d(23,24) = 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 2*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 1*1 = 60
Мінімально можлива кількість перемикань тригерів:
 Wmin = E P(i,j) = 48
Коефіціент ефективності кодування: 1.25

Am(y) Kam As X Kas ФВ A1(-) 10101 A2 1 00101 K1 A2(y2y5) 00101 A4 A6 A7 X5 NX5X2 NX5NX2 00111 00011 00001 J4 K3J4 K3 A3(y3) 00010 A5 A6 A7 X5 NX5X2 NX5NX2 00000 00011 00001 K4 J5 K4J5 A4(y7) 00111 A6 A7 X2 NX2 00011 00001 K3 K3K4 A5(y5y9) 00000 A6 A7 X2 NX2 00011 00001 J4J5 J5 A6(y3y4y5) 00011 A8 A9 NX4 X4 01011 10011 J2 J1 A7(y1y2) 00001 A5 A8 NX6 X6 00000 01011 K5 J2J4 A8(y2) 01011 A10 1 01010 K5 A9(y2y4) 10011 A11 1 11010 J2K5 A10(y3y6) 01010 A11 A13 A14 X5 NX5NX6 NX5X6 11010 10010 01000 J1 J1K2 K4 A11(y7) 11010 A12 A13 NX1 X1 11110 10010 J3 K2 A12(y1y9) 11110 A15 1 10110 K2 A13(y8) 10010 A15 A3 X2 NX2 10110 00010 J3 K1 A14(y3) 01000 A3 1 00010 K2J4 A15(y1y8) 10110 A17 A20 A19 X4 NX4X3 NX4NX3 10111 00110 10100 J5 K1 K4 A16(y5y9) 00100 A19 A20 A20 A22 X4NX3 X4X3 NX4X1 NX4NX1 10100 00110 00110 01100 J1 J4 J4 J2 A17(y4) 10111 A18 1 11111 J2 A18(y4y5) 11111 A21 1 11101 K4 A19(y3y10) 10100 A21 1 11101 J2 A20(y6) 00110 A22 1 01100 J2K4 A21(y1y8) 11101 A23 A26 A25 X4 NX4X3 NX4NX3 11001 01101 11100 K3 K1 K5 A22(y5y9) 01100 A26 A25 A26 A16 X4X3 X4NX3 NX4X1 NX4NX1 01101 11100 01101 00100 J5 J1 J5 K2 A23(y4) 11001 A24 1 10001 K2 A24(y4y5) 10001 A1 1 10101 J3 A25(y3y10) 11100 A1 1 10101 K2J5 A26(y6) 01101 A16 1 00100 K2K5