Прикладна теорія цифрових автоматів 2 АНОТАЦІЯ Курсове проектування є завершальним етапом вивчення студентами спеціальних дисциплін, передбачених робочим планом за фахом АМ. Задачі курсового проектування - закріплення, систематизація, поглиблення і розвиток теоретичних і практичних знань, отриманих у процесі вивчення дисципліни, а також придбання ними практичних навичок самостійного рішення загальнотеоретичних, практичних і методичних питань проектування програмних продуктів. Основна мета курсового проектування складається у вивченні й аналізі питань, зв'язаних зі спеціальними аспектами досліджуваних дисциплін, удосконалюванні загальнотеоретичної підготовки студентів, а також самостійному застосуванні отриманих знань. Метою курсового проекту є проектування керуючих автоматів Милі і Мура, по заданій графі-схемі алгоритму, і побудова їхніх принципових схем на елементах заданої серії. У курсовому проекті були реалізовані необхідні вимоги, і виконаний синтез керуючих автоматів на елементах серії КР1533. RESUME Course designing is the closing stage of studying by students of the special disciplines stipulated by the working plan on a speciality american. Problems of course designing - fastening, ordering, a deepening and development of the theoretical and practical knowledge received during studying of discipline, and also purchase of practical habits of the independent decision of general-theoretical, practical and methodical questions of designing of software by them. The basic purpose of course designing develops in studying and the analysis of the questions connected to special aspects of researched disciplines, perfection of general-theoretical preparation of students, and also independent application of the received knowledge. The purpose of the course project is designing managing automatic devices of Mile and Mess, under the given column - circuit of algorithm, and construction of their basic circuits on elements of the given series. In the course project there were realized necessary requirements, and the executed synthesis of managing automatic devices of elements of series KR1533. ЗМІСТ Введення 1. Вибір варіанта завдання 1.1. Граф-схема алгоритму 1.2. Тип тригера 1.3. Серія інтегральних мікросхем 2. Основна частина 2.1.Структурний синтез автомата Мура 2.1.1. Розмітка станів ГСА 2.1.2. Таблиця переходів автомата 2.1.3. Кодування станів 2.1.4. Функції збудження тригерів та вихідних сигналів 2.2. Структурний синтез автомата Мілі 2.2.1. Розмітка станів ГСА 2.2.2. Таблиця переходів автомата 2.2.3. Кодування станів 2.2.5. Функції збудження тригерів та вихідних сигналів Закінчення Список використаної літератури 1 Введення Метою курсового проекту по дисципліні "Прикладна теорія цифрових автоматів" є закріплення основних теоретичних знань і практичних навичок у ході самостійної роботи. У ході роботи необхідно :1. спроектувати керуючий автомат Милі по заданої граф - схемі алгоритму. Побудувати принципову схему автомата з використанням елементів серії КР1533.2. спроектувати керуючий автомат Мура по заданої граф - схемі алгоритму. Побудувати принципову схему автомата з використанням елементів серії КР1533. Керуючий автомат генерує послідовність керуючих сигналів, запропоновану мікропрограмою, і відповідну значенням логічних елементів, тобто задає порядок виконання дій в операційному автоматі, що випливають з алгоритму виконання операцій. Кінцевий автомат, що інтерпретує мікропрограму роботи операційного пристрою, називається мікропрограмним автоматом. На практиці найбільше поширення одержали два класи автоматів - автомати Милі і Мура. Основна відмінність автомата Мура від автомата Милі полягає в тім, що вихідний сигнал в автоматі Мура залежить тільки від поточного стану автомата й у явному виді не залежить від вхідного сигналу. 1.1 Вибір завдання. 1.1 Вибір граф-схеми алгоритму Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: E, F, G, H. Студенти обирають граф-схему із п’яти блоків з номерами 0...4 на підставі чисел А, В, С та (А+В+С) за наступними правилами: - блок "Е" – схема під номером (А) mod 5 = 16 mod 5 = 1; - блок "F" – схема під номером (В) mod 5 = 01 mod 5 = 1; - блок "G" – схема під номером (С) mod 5 = 26 mod 5 = 1; - блок "H" – схема під номером (А+В+С) mod 5 = 43 mod 5 = 3. Розташування обирається з використанням номера групи. 1.2 Вибір типа тригера Тип тригера знаходимо по таблиці 1 на підставі числа (А) mod 3 = 27 mod 3 = 0. Таблиця 1 Для вибору варіанта тргера (A) mod 3 ТИП ТРИГЕРА 0 Т D 1 D JK 2 JK T автомат Мілі Мура Отримуємо D-тригер для автомата Мілі та JK-тригер для Мура. 1.3. Вибір ссерії інтегральних мікросхем Для парних номерів за списком (26) - серія КР1533. Після відповідної розмітки будуємо таблиці переходів для обох автоматів. 2 ОСНОВНА ЧАСТИНА 2.1.Структурний синтез автомата Мура 2.11. Розмітка станів ГСА Для автомата Мура на етапі одержання відміченої ГСА розмітка провадиться відповідно до наступних правил: 1) символом а1 відмічаються початкова і кінцева вершини; 2) різні операторні вершини відмічаються різними символами; 3) всі операторні вершини повинні бути відмічені. Відповідно до цих правил я відмітив 25 станів. 2.1.2. Таблиця переходів автомата Для кожного стану ai визначаю по ГСА всі шляхи, які ведуть в інші стани. Я буду будувати зворотну таблицю переходів для автомата Мура, тому що я синтезую автомат на базі JK-тригера. 2 .2.3. Кодування станів Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виражень функцій збудження пам'яті і функцій виходів, у результаті чого складність комбінаційної схеми істотно залежить від обраного кодування. Я буду кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що я синтезую автомат на базі JK-тригера. Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата. Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j) ¹ 0, ij. Для кожної пари вказуємо її вагу. Кодування станів виконуємо за еврістичним алгоритмом. Для цього будуємо матрицю D. ║T║ = i │ j │ P(i,j) 1 │ 2 │ 1 1 │ 23 │ 1 1 │ 24 │ 1 2 │ 6 │ 1 2 │ 7 │ 2 2 │ 9 │ 1 3 │ 4 │ 1 3 │ 6 │ 1 3 │ 7 │ 1 3 │ 11 │ 1 3 │ 12 │ 1 4 │ 5 │ 1 5 │ 8 │ 1 6 │ 8 │ 1 7 │ 9 │ 1 8 │ 10 │ 1 8 │ 12 │ 1 8 │ 13 │ 1 9 │ 12 │ 1 9 │ 13 │ 2 9 │ 14 │ 1 10 │ 11 │ 1 13 │ 14 │ 1 14 │ 16 │ 1 14 │ 18 │ 1 14 │ 19 │ 1 15 │ 18 │ 1 15 │ 19 │ 2 15 │ 21 │ 1 15 │ 24 │ 1 15 │ 25 │ 2 16 │ 17 │ 1 17 │ 20 │ 1 18 │ 20 │ 1 19 │ 21 │ 1 20 │ 22 │ 1 21 │ 22 │ 1 21 │ 24 │ 1 21 │ 25 │ 1 22 │ 23 │ 1 22 │ 24 │ 1 Далі згідно правил алгоритму будуємо матрицю М i │ j │ P(i,j) 18 │ 19 │ 2 16 │ 18 │ 1 3 │ 16 │ 1 7 │ 18 │ 1 5 │ 7 │ 1 5 │ 14 │ 1 14 │ 16 │ 1 14 │ 18 │ 1 3 │ 14 │ 1 5 │ 19 │ 1 16 │ 19 │ 1 4 │ 5 │ 1 5 │ 6 │ 1 16 │ 17 │ 1 17 │ 18 │ 1 2 │ 3 │ 1 3 │ 4 │ 1 6 │ 7 │ 1 7 │ 8 │ 1 8 │ 9 │ 1 9 │ 20 │ 1 20 │ 22 │ 1 22 │ 23 │ 2 13 │ 22 │ 1 11 │ 13 │ 1 11 │ 15 │ 1 15 │ 20 │ 1 15 │ 22 │ 1 9 │ 15 │ 1 11 │ 23 │ 1 20 │ 23 │ 1 10 │ 11 │ 1 11 │ 12 │ 1 20 │ 21 │ 1 21 │ 22 │ 1 1 │ 13 │ 1 9 │ 10 │ 1 12 │ 13 │ 1 1 │ 2 │ 1 Визначемо розрядність кода для кодування станів автомата R = ] log2 N [ = ] log2 23 [ = 5 Результати кодування: a1 10000 a2 00000 a3 01001 a4 01101 a5 01111 a6 01000 a7 00001 a8 01010 a9 00011 a10 11010 a11 11001 a12 01011 a13 00010 a14 00111 a15 00100 a16 10111 a17 10101 a18 00101 a19 00110 a20 11101 a21 01110 a22 11100 a23 11000 a24 10100 a25 01100 Підрахунок ефективності кодування: Кількість перемикань тригерів: W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,23)*d(1,23) + P(1,24)*d(1,24) + P(2,6)*d(2,6) + P(2,7)*d(2,7) + P(2,9)*d(2,9) + P(3,4)*d(3,4) + P(3,6)*d(3,6) + P(3,7)*d(3,7) + P(3,11)*d(3,11) + P(3,12)*d(3,12) + P(4,5)*d(4,5) + P(5,8)*d(5,8) + P(6,8)*d(6,8) + P(7,9)*d(7,9) + P(8,10)*d(8,10) + P(8,12)*d(8,12) + P(8,13)*d(8,13) + P(9,12)*d(9,12) + P(9,13)*d(9,13) + P(9,14)*d(9,14) + P(10,11)*d(10,11) + P(13,14)*d(13,14) + P(14,16)*d(14,16) + P(14,18)*d(14,18) + P(14,19)*d(14,19) + P(15,18)*d(15,18) + P(15,19)*d(15,19) + P(15,21)*d(15,21) + P(15,24)*d(15,24) + P(15,25)*d(15,25) + P(16,17)*d(16,17) + P(17,20)*d(17,20) + P(18,20)*d(18,20) + P(19,21)*d(19,21) + P(20,22)*d(20,22) + P(21,22)*d(21,22) + P(21,24)*d(21,24) + P(21,25)*d(21,25) + P(22,23)*d(22,23) + P(22,24)*d(22,24) = 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 1*1 + 1*2 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 1*2 + 1*1 + 2*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*3 + 1*1 + 1*1 + 1*1 = 54 Мінімально можлива кількість перемикань тригерів Wmin = E P(i,j) .Коефіціент ефективності кодування: 1.20 Табл.2. Таблиця переходів JK-тригера Am Kam As X Kas Yamas J1K1J2K2J3K3J4K4J5K5 A1 10000 A2 1 00000 Y5Y9 K1 A2 00000 A6 A7 A9 A7 X4,NX3 NX4,X1 NX4NX1 X4X3 01000 00001 00011 00001 Y3Y10 Y6 Y5Y9 Y6 J2 J5 J4 J5 J5 A3 01001 A4 A7 A6 X4 NX4X3 NX3NX4 01101 00001 01000 Y4 Y6 Y3Y10 J3 K2 K5 A4 01101 A5 1 01111 Y4Y5 J4 A5 01111 A8 1 01010 Y1Y8 K3 K5 A6 01000 A8 1 01010 Y1Y8 J4 A7 00001 A9 1 00011 Y5Y9 J4 A8 01010 A10 A13 A12 X4 NX4X3 NX4NX3 11010 00010 01011 Y4 Y6 Y3Y10 J1 K2 J5 A9 00011 A13 A12 A13 A14 X4X3 X4NX3 NX4X1 X4NX1 00010 01011 00010 00111 Y6 Y3Y10 Y6 Y1Y8 K5 J2 K5 J3 A10 11010 A11 1 11001 Y5Y4 K4J5 A11 11001 A3 1 01001 Y1Y8 J1 A12 01011 A3 1 01001 Y1Y8 K4 A13 00010 A14 1 00111 Y1Y8 J3 J5 A14 00111 A16 A19 A18 X4 NX4X3 NX4NX3 10111 00111 00101 Y4 Y6 Y3Y10 J1 K5 K4 A15 00100 A19 A18 A19 A21 X4X3 X4NX3 NX4X1 NX4NX1 00110 00101 00110 01110 Y6 Y3Y10 Y6 Y3Y6 J4 J5 J4 J2 J3 A16 10111 A17 1 10101 Y4Y5 K4 A17 10101 A20 1 11101 Y2Y5 J2 A18 00101 A20 1 11101 Y2Y5 K1 K2 A19 00110 A21 1 01110 Y3Y6 J2 A20 11101 A22 1 11100 Y7 K5 A21 01110 A22 A25 A24 X5 NX5X6 NX5NX6 11100 01100 10100 Y7 Y3 Y8 J1 K4 K4 J1 K4 A22 11100 A24 A23 X1 NX1 10100 11000 Y8 Y1Y3 K2 K3 A23 11000 A1 1 10000 - K2 A24 10100 A1 A15 X2 NX2 10000 00100 - Y5Y9 J3 K1 2.1.4. Функції збудження тригерів та вихідних сигналів Виписуємо з таблиці вирази для тригерів (та виконуємо необхідні перетворення для представлення їх в рамках потрібної серії): Формуємо функції виходів автомата: Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами (Лист 1). 2.2 Автомат Мілі. Структурний синтез автомата Мілі 2.2.1. Розмітка станів ГСА На етапі одержання відміченої ГСА входи вершин, які слідують за операторними, відмічають символами a1 , a2 , ... за наступними правилами: 1) символом а1 відмічають вхід вершини, яка слідує за початковою, а також вхід кінцевої вершини; 2) входи усіх вершин , які слідують за операторними, повинні бути відмічені; 3) входи різних вершин відмічаються різними символами; 4) якщо вхід вершини відмічається, то тільки одним символом. За ціми правилами в мене вийшло 21 стани (а21 ). 2.2.2. Таблиця переходів автомата Для кожного стану ai визначаю по ГСА всі шляхи, які ведуть в інші стани і проходять обов’язково тільки через одні операторну вершину. Виняток становить перехід в кінцевий стан (вершину). Для мікропрограмних автоматів таблиці переходів-виходів будуються у вигляді списку, тому що велика кількість станів. Розрізняють пряму та зворотну таблицю переходів. Зворотна таблиця переходів будується для D-тригера. Для автомата Мілі я буду будувати зворотну таблицю переходів. Кодування станів Кодування станів буде проводитися за таким алгоритмом: 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-тригерів, тому що функції порушення однозначно визначаються кодом стану переходу. Табл.3. Таблиця переходів D-тригера Am Kam As Kas X Y ФЗ A19 11110 A1 00011 NX1 D4D5 A1 10110 A2 00101 1 Y5Y9 D3 D5 A21 00001 A3 00110 1 Y1Y8 D3D4 A3 00011 A4 01010 X4 Y4 D2 D4 A3 A4 A2 00011 01010 00101 A5 00000 NX4NX3 1 X4NX3 Y3Y10 Y4Y5 Y3Y10 A5 00010 A6 01100 1 Y1Y8 D2D3 A6 00000 A7 10001 X4 Y4 D1 D5 A2 A2 A3 00110 00110 00011 A8 00001 X4X3 NX4NX1 NX4X3 Y6 Y6 Y6 D5 D5 D5 A8 00111 A9 10010 1 Y5Y9 D1 D4 A6 A9 A9 00000 00101 00101 A10 00010 NX4X3 X4X3 NX4X1 Y6 Y6 Y6 D4 D4 D4 A18 01111 A11 10100 NX5X6 Y3 D1 D3 A10 00010 A12 11000 1 Y1Y8 D1D2 A11 01011 A13 00111 1 Y5Y9 D3D4D5 A12 01100 A14 01011 X4 Y4 D2 D4D5 A14 A12 A13 01110 01100 01001 A15 00100 1 NX4NX3 X4NX3 Y4Y5 Y3Y10 Y3Y10 D3 D3 D3 A12 A13 A13 01100 01001 01001 A16 10000 NX4X3 X4X3 NX4X1 Y6 Y6 Y6 D1 D1 D1 A15 01000 A17 01110 1 Y2Y4 D2D3D4 A16 01101 A18 10011 1 Y3Y6 D1 D4 A17 11000 A19 10101 1 Y7 D1 D3 D5 A19 A18 11110 01111 A20 01001 X1 NX5NX6 Y8 Y8 D2 D5 D2 D5 A7 A6 A9 10000 00000 00101 A21 01000 1 NX3NX4 NX4X3 Y4Y5 Y3Y10 Y3Y10 D2 D2 D2 Для підвищення функціональності схеми можна виділити однакові елементи: Виписуємо з таблиці вирази для тригерів (та виконуємо необхідні перетворення для представлення їх в рамках потрібної серії): Вихідні стани автомата Мілі: Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами (Лист 2). Заключення В ході проекту ми отримали комбінаційну схему булевої функції в заданому базисі та побудували принципову схему керуючого автомата Мура. Синтез автомата був виконаний з урахуванням серії КР1533, тому може бути зроблений та опробований в реальному житті. В цілому курсова робота довела свою важливість у закріпленні отриманих знань та набутті низки звичок щодо проектування цифрових автоматів. Перелік використаної літератури 1. Методичні вказівки до курсової роботи по дисципліні “Прикладна теорія цифрових автоматів”. Одеса. ОГПУ. 1998р. 2. Мікросхеми серії 1533(555). Стислі теоретичні дані. Одеса. Центр НТТМ ОГПУ. 1975г. 3. ГОСТ 2.708-81 ЄСКД. Правила виконання електричних схем цифрової обчи слювальної техніки.