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

АНОТАЦІЯ

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

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

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

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

Укурсовому проекті були реалізовані необхідні вимоги, і виконаний синтезкеруючих автоматів на елементах серії КР1533.

RESUME

Course designing is the closingstage of studying by students of the special disciplines stipulated by theworking plan on a speciality american.

Problems of course designing — fastening, ordering, a deepening and development of the theoretical andpractical knowledge received during studying of discipline, and also purchaseof practical habits of the independent decision of general-theoretical,practical and methodical questions of designing of software by them.

The basic purpose of coursedesigning develops in studying and the analysis of the questions connected tospecial aspects of researched disciplines, perfection of general-theoreticalpreparation of students, and also independent application of the receivedknowledge.

The purpose of the course projectis designing managing automatic devices of Mile and Mess, under the givencolumn — circuit of algorithm, and construction of their basic circuits onelements of the given series.

In the course project there wererealized necessary requirements, and the executed synthesis of managingautomatic 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

Результатикодування:

a110000

a200000

a301001

a401101

a501111

a601000

a700001

a801010

a900011

a1011010

a1111001

a1201011

a1300010

a1400111

a1500100

a1610111

a1710101

a1800101

a1900110

a2011101

a2101110

a2211100

a2311000

a2410100

a2501100

Підрахунокефективності кодування:

Кількістьперемикань тригерів:

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

X4,NX3

NX4,X1

NX4NX1

X4X3

01000

00001

00011

00001

Y3Y10

Y5Y9

J4 J5

A3 01001

NX4X3

NX3NX4

01101 00001 01000

Y3Y10

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

NX4X3

NX4NX3

11010

00010

01011

Y3Y10

A9 00011

A13

A12

A13

A14

X4X3

X4NX3

NX4X1

X4NX1

00010

01011

00010

00111

Y3Y10

Y1Y8

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

NX4X3

NX4NX3

10111

00111

00101

Y3Y10

A15 00100

A19

A18

A19

A21

X4X3

X4NX3

NX4X1

NX4NX1

00110

00101

00110

01110

Y3Y10

Y3Y6

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

NX5X6

NX5NX6

11100

01100

10100

J1 K4

A22

11100

A24

A23

NX1

10100

11000

Y1Y3

A23 11000 A1 1 10000 - K2 A24 10100

A15

NX2

10000

00100

Y5Y9

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

00011

01010

00101

A5 00000

NX4NX3

X4NX3

Y3Y10

Y4Y5

Y3Y10

A5 00010 A6 01100 1 Y1Y8 D2D3 A6 00000 A7 10001 X4 Y4 D1 D5

00110

00011

A8 00001

X4X3

NX4NX1

NX4X3

A8 00111 A9 10010 1 Y5Y9 D1 D4

00000

00101

A10 00010

NX4X3

X4X3

NX4X1

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

NX4NX3

X4NX3

Y4Y5

Y3Y10

A12

A13

01100

01001

A16 10000

NX4X3

X4X3

NX4X1

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

NX5NX6

D2 D5

10000

00000

00101

A21 01000

NX3NX4

NX4X3

Y4Y5

Y3Y10

Дляпідвищення функціональності схеми можна виділити однакові елементи:

Вихідністани автомата Мілі:

Миотримали усі необхідні вирази для принципової схеми. Будуємо її, користуючисьформулами для тригерів та вихідними станами (Лист 2).

Заключення

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

Синтезавтомата був виконаний з урахуванням серії КР1533, тому може бути зроблений таопробований в реальному житті. В цілому курсова робота довела свою важливість узакріпленні отриманих знань та набутті низки звичок щодо проектування цифровихавтоматів.

Перелік використаної літератури

1. Методичні вказівкидо курсової роботи по дисципліні “Прикладна теорія цифрових автоматів”. Одеса.ОГПУ. 1998р.

2. Мікросхеми серії1533(555). Стислі теоретичні дані. Одеса. Центр

НТТМ ОГПУ. 1975г.

3. ГОСТ 2.708-81ЄСКД. Правила виконання електричних схем цифрової обчи слювальної техніки.

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

еще рефераты

Еще работы по информатике, программированию

Реферат по информатике, программированию

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

31 Августа 2013

Реферат по информатике, программированию