Прикладна теорія цифрових автоматів 3 (стр. 1 из 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) ставиться у відповідність ціле число 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 KamAs(y) XKasD1D2D3D4D5 | a13 | a17 a1(-)1 | 1 00011D4D5 | D4D5 | a1 a2(y2y4)110011 D1D4D5 |
| a2 | a18a3(y7)1 | X5 00110D3D4 | D3D4 | a3a4(y1y9)NX110101D1D3 D5 | a4 |
| a14a5(y1y8)1 | X200101D3D5 | D3D5 | a5a6(y4)X411001D1D2 D5 | a6a7(y4y5)101011D2 D4D5 | a7 |
| a15a8(y2y4)1 | 101100D2D3 | D2D3 | a8 | a22a9(y7)1 | X501010D2 D4 |
| D2D4 | a9a10(y1y9)NX101101D2D3D5 | a10 | a16a11(y1y8)1 | X201001 | D2D5 |
| D2D5 | a11a12(y4)X400111D3D4D5 | a12a13(y4y5)101110D2D3D4 | a3 | a18a14(y8)X1 | NX5NX611000D1D2 |
| D1D2 | a5 | a20a15(y3y10)NX4NX3 | X4NX310100 | D1D3 | D1D3 |
| a9 | a22a16(y8)X1 | NX5NX610010D1D4 | D1D4 | a11 | a24a17(y3y10)NX4NX3 |
| X4NX310001D1D5 | D1D5 | a21 | a20a18(y3y6)1 | NX4NX110000D1 | D1 |
| a18a19(y3)NX5X6 10110D1D3D4 | a19 | a14a20(y5y9)1 | NX201000D2 | D2 | a20 |
| a20a21(y6)X4X3 | NX4X100100D3 | D3 | a25 | a24a22(y3y6)1 | NX4NX100010 D4 |
| D4 | a22a23(y3)NX5X611010D1D2D4 | a23 | a16a24(y5y9)1 | NX200001D5 | D5 |
| a24 | a24 | a11a25(y6)X4X3 | NX4X1 | NX4X300000 |
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