Прикладна теорія цифрових автоматів 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-тригера. Для автомата Мілі я буду будувати зворотну таблицю переходів.

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

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

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

Числа N1, N2, ..., Nm упорядковуються по убуванні. 

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