Скачать .docx  

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

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