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

АНОТАЦІЯ

Курсове проектування є завершальним етапом вивчення студентами спеціальних дисциплін, передбачених робочим планом за фахом АМ.

Задачі курсового проектування - закріплення, систематизація, поглиблення і розвиток теоретичних і практичних знань, отриманих у процесі вивчення дисципліни, а також придбання ними практичних навичок самостійного рішення загальнотеоретичних, практичних і методичних питань проектування програмних продуктів.

Основна мета курсового проектування складається у вивченні й аналізі питань, зв'язаних зі спеціальними аспектами досліджуваних дисциплін, удосконалюванні загальнотеоретичної підготовки студентів, а також самостійному застосуванні отриманих знань.

Метою курсового проекту є проектування керуючих автоматів Милі і Мура, по заданій графі-схемі алгоритму, і побудова їхніх принципових схем на елементах заданої серії.

У курсовому проекті були реалізовані необхідні вимоги, і виконаний синтез керуючих автоматів на елементах серії КР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) символом а₁ відмічаються початкова і кінцева вершини;

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, 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. Розмітка станів ГСА

На етапі одержання відміченої ГСА входи вершин, які слідують за операторними, відмічають символами a₁, a₂, ... за наступними правилами:

1) символом а₁ відмічають вхід вершини, яка слідує за початковою, а також вхід кінцевої вершини;

2) входи усіх вершин , які слідують за операторними, повинні бути відмічені;

3) входи різних вершин відмічаються різними символами;

4) якщо вхід вершини відмічається, то тільки одним символом.

За ціми правилами в мене вийшло 21 стани (а₂₁).

2.2.2. Таблиця переходів автомата

Для кожного стану a_i визначаю по ГСА всі шляхи, які ведуть в інші стани і проходять обов'язково тільки через одні операторну вершину. Виняток становить перехід в кінцевий стан (вершину).

Для мікропрограмних автоматів таблиці переходів-виходів будуються у вигляді списку, тому що велика кількість станів. Розрізняють пряму та зворотну таблицю переходів. Зворотна таблиця переходів будується для D-тригера. Для автомата Мілі я буду будувати зворотну таблицю переходів.

Кодування станів

Кодування станів буде проводитися за таким алгоритмом:

Кожному стану автомата а_m (m = 1,2,...,M) ставиться у відповідність ціле число N_m, рівне числу переходів у стан а_m (N_m дорівнює числу появ а_m у поле таблиці ).

Числа N₁, N₂, ..., 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 ЄСКД. Правила виконання електричних схем цифрової обчи слювальної техніки.

4. ГОСТ 2.743-82. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.