Прикладна теорія цифрових автоматів 3

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

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Кафедра комп’ютерних інтелектуальних систем та мереж

Курсове проектування
з дисципліни
„Прикладна теорія цифрових автоматів”
Виконав: студент гр.
Одеса 2002

1.ВИБІР ВАРІАНТА ЗАВДАННЯ
Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: E, F, G, H. Студенти обирають граф-схему із п’яти блоків з номерами 0...4 на підставі чисел А, В, С та (А+В+С) за наступними правилами:
- блок "Е" – схема під номером (А) mod 5 = 27 mod 5 = 2;
- блок "F" – схема під номером (В) mod 5 = 6 mod 5 = 1;
- блок "G" – схема під номером (С) mod 5 = 13 mod 5 = 3;
- блок "H" – схема під номером (А+В+С) mod 5 = 46 mod 5 = 1.
Блоки E, F, G, H з’єднуються між собою згідно зі структурною схемою графа, яка показана на рис. 10 у методичних вказівках.
Розташування обирається з використанням номера групи. Тип тригера знаходимо по таблиці на підставі числа (А) mod 3 = 27 mod 3 = 0.   

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

Табл.1
З табл.1 отримуємо T-тригер для автомата Мілі та D-тригер для Мура.
Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів для мого варіанта завдання – КР1533.
Після відповідної розмітки будуємо граф-схему для обоіх автоматів:

2. ОСНОВНА ЧАСТИНА
2.1. Структурний синтез автомата Мура
2.1.1. Кодування станів
 Кодування станів буде проводитися за таким алгоритмом:
1.                 Кожному стану автомата а_m (m = 1,2,...,M) ставиться у відповідність ціле число N_m, рівне числу переходів у стан а_m (N_m дорівнює числу появ а_m у поле таблиці ).
2.                 Числа N₁, N₂, ..., N_m упорядковуються по убуванні.
3.                 Стан а_s з найбільшим N_s кодується кодом: де R-кількість елементів пам'яті.
4.                 Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.
5.                 Для станів, що залишилися, знову в порядку списку п.2. використовують коди з двома одиницями, потім із трьома і так далі поки не будуть закодовані всі стани.
У результаті виходить таке кодування, при якому чим більше мається переходів у деякий стан, тим менше одиниць у його коді. Вираження для функцій збудження будуть простіше для D-тригерів, тому що функції порушення однозначно визначаються кодом стану переходу.
Статистика:
a1 2стана
a2 1стан
a3 2стана
a4 1стан
a5 2стана
a6 1стан
a7 1стан
a8 2стана
a9 2стана
a10 1стан
a11 2стана
a12 1стан
a13 1стан
a14 2стана
a15 2стана
a16 2стана
a17 2стана
a18 2стана
a19 1стан
a20 2стана
a21 2стана
a22 2стана
a23 1стан
a24 2стана
a25 3стана
Результати кодування:
a1 00011
a2 10011
a3 00110
a4 10101
a5 00101
a6 11001
a7 01011
a8 01100
a9 01010
a10 01101
a11 01001
a12 00111
a13 01110
a14 11000
a15 10100
a16 10010
a17 10001
a18 10000
a19 10110
a20 01000
a21 00100
a22 00010
a23 11010
a24 00001
a25 00000
Табл.2. Таблиця переходів D-тригера

Am         Kam As(y)      X Kas D1D2D3D4D5	a13	a17         a1(-) 1	1        00011 D4D5	D4D5	a1           a2(y2y4) 1 10011    D1 D4D5
a2	a18 a3(y7) 1	X5 00110 D3D4	D3D4	a3 a4(y1y9) NX1 10101 D1 D3  D5	a4
a14 a5(y1y8) 1	X2 00101 D3 D5	D3 D5	a5 a6(y4) X4 11001 D1D2 D5	a6 a7(y4y5) 1 01011 D2  D4D5	a7
a15 a8(y2y4) 1	1 01100 D2D3	D2D3	a8	a22 a9(y7) 1	X5 01010 D2 D4
D2 D4	a9 a10(y1y9) NX1 01101 D2D3 D5	a10	a16 a11(y1y8) 1	X2 01001	D2 D5
D2 D5	a11 a12(y4) X4 00111 D3D4D5	a12 a13(y4y5) 1 01110 D2D3D4	a3	a18 a14(y8) X1	NX5NX6 11000 D1D2
D1D2	a5	a20 a15(y3y10) NX4NX3	X4NX3 10100	D1 D3	D1 D3
a9	a22 a16(y8) X1	NX5NX6 10010 D1 D4	D1 D4	a11	a24 a17(y3y10) NX4NX3
X4NX3 10001 D1 D5	D1 D5	a21	a20 a18(y3y6) 1	NX4NX1 10000 D1	D1
a18 a19(y3) NX5X6  10110 D1 D3D4	a19	a14 a20(y5y9) 1	NX2 01000 D2	D2	a20
a20 a21(y6) X4X3	NX4X1 00100 D3	D3	a25	a24 a22(y3y6) 1	NX4NX1 00010 D4
D4	a22 a23(y3) NX5X6 11010 D1D2 D4	a23	a16 a24(y5y9) 1	NX2 00001 D5	D5
a24	a24	a11 a25(y6) X4X3	NX4X1	NX4 X3 00000

2.1.2. Функції збудження тригерів та вихідних сигналів
Введемо слідуючі позначення:
Б= a20NХ4NХ1                                Х=a3X1
В= a14NХ2                                 Ц=a18NX5NX6
Г= a20Х4Х3                                 Ч=a5NX4NX3
Д=a20NХ4Х1                              Ш=a20X4NX3
Е=a18X5                                           Э=a9X1
Ж=a3NX1                                   Ю=a22NX5NX6
З= a24NХ4NХ1                          Я=a11NX4NX3
И=a14X2                                      Щ=a24X4NX3
К=a5X4                                         Ь=a18NX5X6
Л= a16NХ2                                  Ы=a22NX5X6
 П=a22X5
Р=a9NX1
Т=a16X2
У=a11X4
Виписуємо з таблиці вирази для тригерів:
D1=a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь
D2=К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы
D3=a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь
D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы
D5=a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л
Формуємо функції виходів автомата:
Y1=a4+a5+a10+a11
Y2=a2+a8
Y3=a15+a17+a18+a19+a22+a23
Y4=a2+a6+a7+a8+a12+a13
Y5=a7+a13+a20+a24
Y6=a18+a21+a22+a25
Y7=a3+a9
Y8=a5+a11+a14+a16
Y9=a4+a10+a20+a24
Y10=a15+a17
2.1.3. Переведеня у базис:
D1= a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь=
=Na1∙NЖ∙NК∙NЫ∙NХ∙NЦ∙NЧ∙NШ+NЭ∙NЮ∙NЯ∙NЩ∙Na21∙NБ∙NЬ
D2= К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы=
=NК∙Na6∙Na7∙Na15∙Na8∙NП∙NР∙Na10+NТ∙NХ∙NЦ∙Nа12∙Na19∙NВ∙NЫ
D3= a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь=
=Na2∙NЕ∙NЖ∙Na4∙NИ∙Na7∙Na15∙NР+NУ∙Na12∙NЧ∙NШ∙NГ∙NД∙NЬ
D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы
=Na13∙Na17∙Na1∙Na2∙NЕ∙Na6∙Na8∙NП+NУ∙Na12∙NЭ∙NЮ∙NЬ∙Na25∙NЗ∙NЫ
D5= a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л=
=Na13∙Na17∙Na1∙NЖ∙Na4∙NИ∙NК∙Na6+NР∙Na10∙NТ∙NУ∙NЯ∙NЩ∙Na23∙NЛ
Y1=a4+a5+a10+a11=Na4∙Na5∙Na10∙Na11
Y2=a2+a8= Na2∙Na8
Y3=a15+a17+a18+a19+a22+a23= Na15∙Na17∙Na18∙Na19∙Na22∙Na23
Y4=a2+a6+a7+a8+a12+a13= Na2∙Na6∙Na7∙Na8∙Na12∙Na13
Y5=a7+a13+a20+a24= Na7∙Na13∙Na20∙Na24
Y6=a18+a21+a22+a25= Na18∙Na21∙Na22∙Na25
Y7=a3+a9= Na3∙Na9
Y8=a5+a11+a14+a16= Na5∙Na11∙Na14∙Na16
Y9=a4+a10+a20+a24= Na4∙Na10∙Na20∙Na24
Y10=a15+a17= Na15∙Na17
Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами.
2.2. Структурний синтез автомата Мілі
2.2.1. Кодування станів
Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виражень функцій збудження пам'яті і функцій виходів, у результаті чого складність комбінаційної схеми істотно залежить від обраного кодування.
Мы повинні кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що у мене Т-тригер.
Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата.
Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j)  0, ij. Для кожної пари вказуємо її вагу.
║T║ =
 i │ j │ P(i,j)
 1 │ 2 │ 1
 1 │ 11 │ 1
 1 │ 12 │ 1
 1 │ 21 │ 1
 2 │ 3 │ 1
 3 │ 4 │ 1
 3 │ 13 │ 1
 3 │ 15 │ 1
 4 │ 5 │ 1
 5 │ 6 │ 1
 5 │ 7 │ 1
 5 │ 13 │ 1
 5 │ 18 │ 1
 6 │ 7 │ 1
 7 │ 8 │ 1
 7 │ 17 │ 1
 
 8 │ 9 │ 1
 9 │ 10 │ 1
 9 │ 14 │ 1
 9 │ 19 │ 1
 10 │ 11 │ 1
 11 │ 12 │ 1
 11 │ 14 │ 1
 11 │ 22 │ 1
 13 │ 15 │ 1
 13 │ 17 │ 1
 14 │ 19 │ 1
 14 │ 21 │ 1
 15 │ 16 │ 1
 15 │ 17 │ 1
 15 │ 18 │ 1
 16 │ 17 │ 1
 17 │ 18 │ 2
 19 │ 20 │ 1
 19 │ 21 │ 1
 19 │ 22 │ 1
 20 │ 21 │ 1
 21 │ 22 │ 2
Підраховуємо вагу всіх компонентів всіх пар
 P(1) = 4
P(2) = 2
P(3) = 4
P(4) = 2
P(5) = 5
P(6) = 2
P(7) = 4
P(8) = 2
P(9) = 4
P(10) = 2
P(11) = 5
P(12) = 2
P(13) = 4
P(14) = 4
P(15) = 5
P(16) = 2
P(17) = 5
P(18) = 3
P(19) = 5
P(20) = 2
 P(21) = 5
 P(22) = 3
Далі згідно правил алгоритму будуємо матрицю М
 i │ j │ P(i,j)
 17 │ 18 │ 2
 15 │ 17 │ 1
 3 │ 15 │ 1
 7 │ 17 │ 1
 5 │ 7 │ 1
 5 │ 13 │ 1
 13 │ 15 │ 1
 13 │ 17 │ 1
 3 │ 13 │ 1
 5 │ 18 │ 1
 15 │ 18 │ 1
 4 │ 5 │ 1
 5 │ 6 │ 1
 15 │ 16 │ 1
 16 │ 17 │ 1
 2 │ 3 │ 1
 1 │ 2 │ 1
 1 │ 11 │ 1
 1 │ 21 │ 1
 21 │ 22 │ 2
 19 │ 21 │ 1
 9 │ 19 │ 1
 11 │ 14 │ 1
 14 │ 19 │ 1
 14 │ 21 │ 1
 9 │ 14 │ 1
 11 │ 22 │ 1
 19 │ 22 │ 1
 10 │ 11 │ 1
 11 │ 12 │ 1
 19 │ 20 │ 1
 20 │ 21 │ 1
 1 │ 12 │ 1
 3 │ 4 │ 1
 6 │ 7 │ 1
 7 │ 8 │ 1
 8 │ 9 │ 1
 9 │ 10 │ 1
Визначемо розрядність кода для кодування станів автомата
R = ] log2 N [ = ] log2 22 [ = 5
Результати кодування:
 b1 01011
 b2 01111
 b3 00111
 b4 01101
 b5 00101
 b6 01100
 b7 00100
 b8 10100
 b9 10000
b10 11000
b11 11010
b12 01010
b13 00110
b14 11001
 b15 00011
b16 00010
b17 00000
b18 00001
b19 10001
b20 10101
b21 10011
b22 10010
Підрахунок ефективності кодування:
Кількість перемикань тригерів:
 W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,11)*d(1,11) + P(1,12)*d(1,12) + P(1,21)*d(1,21) + P(2,3)*d(2,3) + P(3,4)*d(3,4) + P(3,13)*d(3,13) + P(3,15)*d(3,15) + P(4,5)*d(4,5) + P(5,6)*d(5,6) + P(5,7)*d(5,7) + P(5,13)*d(5,13) + P(5,18)*d(5,18) + P(6,7)*d(6,7) + P(7,8)*d(7,8) + P(7,17)*d(7,17) + P(8,9)*d(8,9) + P(9,10)*d(9,10) + P(9,14)*d(9,14) + P(9,19)*d(9,19) + P(10,11)*d(10,11) + P(11,12)*d(11,12) + P(11,14)*d(11,14) + P(11,22)*d(11,22) + P(13,15)*d(13,15) + P(13,17)*d(13,17) + P(14,19)*d(14,19) + P(14,21)*d(14,21) + P(15,16)*d(15,16) + P(15,17)*d(15,17) + P(15,18)*d(15,18) + P(16,17)*d(16,17) + P(17,18)*d(17,18) + P(19,20)*d(19,20) +
 P(19,21)*d(19,21) + P(19,22)*d(19,22) + P(20,21)*d(20,21) + P(21,22)*d(21,22) =
 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 = 52
Мінімально можлива кількість перемикань тригерів
Wmin = E P(i,j) = 40
Коефіціент ефективності кодування: 1.30
Табл.3. Таблиця переходів Т-тригера

Am	Kam	As	Kas	X	Y	ФЗ
b1	01011	b2	01111	1	Y2Y4	T3
b2	01111	b3	00111	1	Y7	T2
b3	00111	b4 b13	01101 00110	NX1 X1	Y1Y9 Y8	T2       T4                      T5
b4	01101	b5	00101	1	Y1Y8	T2
b5	00101	b6 b7 b18	01100 00100 00001	X4 NX4NX3 NX4X3	Y4 Y3Y10 Y6	T2            T5                       T5 T3
b6	01100	b7	00100	1	Y4Y5	T2
b7	00100	b8	10100	1	Y2Y4	T1
b8	10100	b9	10000	1	Y7	T3
b9	10000	b10 b14	11000 11001	NX1 X1	Y1Y9 Y8	T2      T2            T5
b10	11000	b11	11010	1	Y1Y8	T4
b11	11010	b12 b1 b22	01010 01011 10010	X4 NX4NX3 NX4X3	Y4 Y3Y10 Y6	T1       T1                 T5      T2
b12	01010	b1	01011	1	Y4Y5	T5
b13	00110	b5 b17	00101 00000	X2 NX2	Y1Y8 Y5Y9	T4T5            T3  T4
b14	11001	b11 b21	11010 10011	X2 NX2	Y3Y10 Y6	T4T5    T2        T4
b15	00011	b3 b13 b16	00111 00110 00010	X5 NX5NX6 NX5X6	Y7 Y8 Y3	T3            T3      T5                       T5
b16	00010	b17	00000	1	Y5Y9	T4
b17	00000	b7 b18 b18 b15	00100 00001 00001 00011	X4NX3 X4X3 NX4X1 NX4NX1	Y3Y10 Y6 Y6 Y3Y6	T3 T5 T5 T4T5

2.2.2. Функції збудження тригерів та вихідних сигналів
Введемо слідуючі позначення:
A=b3NX1 П=b21Х4NX3
Б=b5X4                                         Р= b5NX4Х3
H=b9X1 С=В15Х5
Г=b11X4                                      Т= b17Х4NX3
Д=b13X2                                      У= b19NX5X6
Е=b13NX2                                 Ф= b21NX4NX1
Ж=b14X2                                         Х= b3Х1
З=b14NX2                                   Ц= b5NX4NX3
И=b15NX5NX6                          Ч= b11NX4NX3
К=b17NX4NX1                           Ш= b15NX5X6
Л=b9NX1                                      Щ= b17X4X3
М=b11NX4X3                             Э= b17NX4X1
O= b19NX5NX6                           Ю= b21X4X3
Я= b21NX4X1                                 В=В19Х5
 Виписуємо з таблиці вирази для тригерів:
 T₁=b7+Г+Ч+П
Т₂=b2+А+b4+Б+b6+Л+Н+М+З+О+П
 Т₃=b1+Р+b8+Е+С+И+Т+У+b20
Т₄ =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22
 Т₅=Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22
 Формуємо функції виходів автомата:
 Y1=А+b4+Л+b10+Д
 Y2=b1+b7
 Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22
 Y4=b1+Б+b6+b7+Г+b12
 Y5=b6+b12+Е+b16+b20
 Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22
 Y7=b2+b8+С+В
 Y8=Х+b4+Н+b10+Д+И+О
 Y9=А+Л+Е+b16+b20
 Y10=Ц+Ч+Ж+Т+П
 2.2.3. Переведеня у базис:
 T₁=b7+Г+Ч+П= Nb7∙NГ∙NЧ∙NП
Т₂=b2+А+b4+Б+b6+Л+Н+М+З+О+П=
 =Nb2∙NА∙Nb4∙NБ∙Nb6∙NЛ∙NН∙NМ+NЗ∙NО∙NП
 Т₃=b1+Р+b8+Е+С+И+Т+У+b20=
 =Nb1∙NР∙Nb8∙NЕ∙NС∙NИ∙NТ∙NУ+b20
Т₄ =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22=
=NА∙Nb10∙NД∙NЕ∙NЖ∙NЗ∙Nb16∙NК+Nb18∙Nb20∙NФ∙Nb22
 Т₅=Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22=
 =NХ∙NБ∙NЦ∙NH∙NЧ∙Nb12∙NД∙NЖ+NИ∙NШ∙NЩ∙NЭ∙NK∙NЮ∙NЯ∙Nb22
 

 Y1=А+b4+Л+b10+Д= NА∙Nb4∙NЛ∙Nb10∙NД
 Y2=b1+b7= Nb1∙Nb7
 Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22=NЦ∙NЧ∙NЖ∙NШ∙NТ∙NК∙Nb18∙NУ+
 +NП∙NФ∙Nb22
 Y4=b1+Б+b6+b7+Г+b12=Nb1∙NБ∙Nb6∙Nb7∙NГ∙Nb12
 Y5=b6+b12+Е+b16+b20= Nb6∙Nb12∙NЕ∙Nb16∙Nb20
 Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22= NМ∙NЗ∙NЩ∙NЭ∙NК∙Nb18∙NЮ∙NЯ+
 +NФ∙Nb22
 Y7=b2+b8+С+В= Nb2∙Nb8∙NС∙NВ
 Y8=Х+b4+Н+b10+Д+И+О= NХ∙Nb4∙NН∙Nb10∙NД∙NИ∙NО
 Y9=А+Л+Е+b16+b20= NА∙NЛ∙NЕ∙Nb16∙Nb20
 Y10=Ц+Ч+Ж+Т+П= NЦ∙NЧ∙NЖ∙NТ∙NП
Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами.

Висновок

В ході проекту ми отримали комбінаційну схему булевої функції в заданому базисі та побудували принципову схему керуючого автомата Мура.
Синтез автомата був виконаний з урахуванням серії КР 555, тому може бути зроблений та опробований в реальному житті. В цілому курсова робота довела свою важливість у закріпленні отриманих знань та набутті низки звичок щодо проектування цифрових автоматів.

Перелік використаної літератури
1. Методичні вказівки до курсової роботи по дисципліні “Прикладна теорія ци фрових автоматів”. Одеса. ОГПУ. 1998р.
2. Мікросхеми серії 1533(555). Стислі теоретичні дані. Одеса. Центр НТТМ ОГПУ. 1975г.
3. ГОСТ 2.708-81 ЄСКД. Правила виконання електричних схем цифрової обчи слювальної техніки.
4.                   ГОСТ 2.743-82. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.