Міністерство освіти і науки України ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ Кафедра комп’ютерних інтелектуальних систем та мереж
Курсове проектування
з дисципліни
„Прикладна теорія цифрових автоматів”
Виконав: студент гр.
Одеса 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) ставиться у відповідність ціле число Nm, рівне числу переходів у стан аm (Nm дорівнює числу появ аm у поле таблиці ).
2. Числа N1, N2, ..., Nm упорядковуються по убуванні.
3. Стан аs з найбільшим Ns кодується кодом: де 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. ............
