АНОТАЦІЯ

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

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

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

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

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

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

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

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

2. Числа N₁, N₂, ..., N_m упорядковуються по убуванні.

3. Стан а_s з найбільшим N_s кодується кодом: де 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. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.