Прикладна теорія цифрових автоматів (работа 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. Таблиця переходів автомата
Для кожного стану a>i> визначаю по ГСА всі шляхи, які ведуть в інші стани.
Я буду будувати зворотну таблицю переходів для автомата Мура, тому що я синтезую автомат на базі JK-тригера.
2.2.3. Кодування станів
Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виражень функцій збудження пам'яті і функцій виходів, у результаті чого складність комбінаційної схеми істотно залежить від обраного кодування.
Я буду кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що я синтезую автомат на базі JK-тригера.
Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата.
Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j) 0, ij. Для кожної пари вказуємо її вагу.
Кодування станів виконуємо за еврістичним алгоритмом. Для цього будуємо матрицю 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. Розмітка станів ГСА
На етапі одержання відміченої ГСА входи вершин, які слідують за операторними, відмічають символами a>1>, a>2>, ... за наступними правилами:
1) символом а>1> відмічають вхід вершини, яка слідує за початковою, а також вхід кінцевої вершини;
2) входи усіх вершин , які слідують за операторними, повинні бути відмічені;
3) входи різних вершин відмічаються різними символами;
4) якщо вхід вершини відмічається, то тільки одним символом.
За ціми правилами в мене вийшло 21 стани (а>21>).
2.2.2. Таблиця переходів автомата
Для кожного стану a>i> визначаю по ГСА всі шляхи, які ведуть в інші стани і проходять обов’язково тільки через одні операторну вершину. Виняток становить перехід в кінцевий стан (вершину).
Для мікропрограмних автоматів таблиці переходів-виходів будуються у вигляді списку, тому що велика кількість станів. Розрізняють пряму та зворотну таблицю переходів. Зворотна таблиця переходів будується для D-тригера. Для автомата Мілі я буду будувати зворотну таблицю переходів.
Кодування станів
Кодування станів буде проводитися за таким алгоритмом:
Кожному стану автомата а>m> (m = 1,2,...,M) ставиться у відповідність ціле число N>m>, рівне числу переходів у стан а>m> (N>m> дорівнює числу появ а>m> у поле таблиці ).
Числа N>1>, N>2>, ..., N>m> упорядковуються по убуванні.
Стан а>s> з найбільшим N>s> кодується кодом:
де
R-кількість елементівпам'яті.
Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.
Для станів, що залишилися, знову в порядку списку п.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 ЄСКД. Правила виконання електричних схем цифрової обчи слювальної техніки.
ГОСТ 2.743-82. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.