Курсовая работа: Прикладна теорія цифрових автоматів

ЗМІСТ

Введення

1. Вибір варіанта завдання

1.1. Граф-схема автомата Мура

1.2. Граф-схема автомата Мілі

2. Основна частина

2.1. Структурний синтез автомата Мура

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

2.1.2. Функції збудження тригерів та вихідних сигналів

2.1.3. Переведеня у базис

2.2.Структурний синтез автомата Мілі

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

2.1.2. Функції збудження тригерів та вихідних сигналів

2.1.3. Переведеня у базис

Висновок

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

1.ВИБІР ВАРІАНТА ЗАВДАННЯ

1.1. Граф-схема алгоритму

Граф-схема складається з чотирьох блоків E, F, G, H і вершин “BEGIN” та “END”. Кожен з блоків має два входи (А, В) і два виходи (C, D). Я вибираю блоки E, F, G, H з п’яти блоків з номерами 0, 1, 2, 3, 4 (вони подаються в п.5 на рис.3-7 у методичних вказівках) на підставі чисел А, В, С, А+В+С (де А – число, В – місяць народження, С – номер студента в журналі), за такими правилами:

- блок “Е” має схему блока за номером А(MOD 5);

- блок “F” має схему блока за номером B(MOD 5);

- блок “G” має схему блока за номером C(MOD 5);

- блок “H” має схему блока за номером (А+B+C)(MOD 5).

В моєму варіанті:

А=30;

В=06;

С=22.

“Е”: А(MOD 5)=30(MOD 5)=0;

“F”: B(MOD 5)=06(MOD 5)=1;

“G”: C(MOD 5)=22(MOD 5)=2;

“H”: (А+B+C)(MOD 5)=(30+06+22)(MOD 5)=58(MOD 5)=3.

Блоки E, F, G, H з’єднуються між собою згідно зі структурною схемою графа, яка показана на рис. 10 у методичних вказівках.

Згідно з моїм варіантом завдання, граф-схема автомата має такий вигляд:

BEGIN

END

Рис.1.1. Граф-схема алгоритму автомата Мілі

Y1, Y2

BEGIN

Y1, Y4

END

Рис.1.2. Граф-схема алгоритму автомата Мура

1.2. Тип тригера

Тип тригера вибирається за значенням числа A(MOD 3) на підставі табл.2 в методичних вказівках. Згідно з моїм варіантом завдання:

A(MOD 3)=30(MOD 3) =0.

Тому, згідно таблиці 2 у методичних вказівках, тип тригера в моєму завданні для синтезу автомата Мура – D, а для синтезу автомата Мілі – Т.

1.3. Серія інтегральних мікросхем

Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів для мого варіанта завдання – КР1533.

2. ОСНОВНА ЧАСТИНА

2.1. Структурний синтез автомата Мілі

2.1.1. Розмітка станів ГСА

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

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

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

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

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

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

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

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

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

Am Kam as Kas Xamas Yamas T1 T2 T3 T4 T5	a1 10110 a2 10010 1 Y1Y4 T3	a2 10010	a4	a6 00010	10000 X3	X3 Y2Y6	Y7 T1	T4	A	B
a3 00011 a4 00010 1 Y2Y6 T5	a4 00010 a5 00000 1 Y1Y8 T4	a5 00000 a8	a9	a11 01000	01001	10001 X4	X4X3	X4X3 Y4	Y3Y10	Y6
T1 T2	T2	T5	T5 C	D	E	a6 10000 a5	a7 00000	11001 X1	X1 Y1Y8
Y5Y9 T1	T2	T5 F	G	a7 11001 a9	a11	a11	a12 01001	10001	10001	11000 X4X3	X4X3
X4X1	X4X1 Y3Y10	Y6	Y6	Y2Y4 T1	T2	T2	T5 H	I
J	K	a8 01000 a9 01001 1 Y4Y5 T5	a9 01001 a10 00001 1 Y1Y2 T2

Табл.1. Таблиця переходів Т-тригера

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

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

Я буду кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що я синтезую автомат на базі Т-тригера.

Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата.

Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j) ¹ 0, ij. Для кожної пари вказуємо її вагу.

ijP(i, j)

1 2 1

2 4 1

2 6 1

3 4 1

4 5 1

5 8 1

5 9 1

5 10 1

5 11 1

6 5 1

6 7 1

7 9 1

7 11 2

7 12 1

8 9 1

9 10 1

10 3 1

10 7 1

10 4 1

10 5 1

T= 11 12 1

12 13 1

13 14 1

13 15 1

14 17 1

15 17 1

15 19 1

16 19 1

17 18 1

18 1 1

18 20 1

19 18 1

19 20 1

19 21 1

20 1 1

20 22 1

21 22 1

22 13 1

22 15 1

22 16 1

Далі, за допомогою програми ECODE 3, виконую кодування станів автомата на ЕОМ. При цьому вказую глибину кодування (від 4 до 6) та вибираю те кодування, коефіцієнт якого ближче до 1 (у мене коефіцієнт кодування 1,26). Результати кодування заношу до таблиці 1. Ось кінцеві результати кодування:

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

Кількість переключень тригерів:

W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,18)*d(1,18) + P(1,20)*d(1,20) + +P(2,4)*d(2,4) + P(2,6)*d(2,6) + P(3,4)*d(3,4) + P(3,10)*d(3,10) + +P(4,5)*d(4,5) + P(4,10)*d(4,10) + P(5,6)*d(5,6) + P(5,8)*d(5,8) + +P(5,9)*d(5,9) + P(5,10)*d(5,10)+ P(5,11)*d(5,11) + P(6,7)*d(6,7) + +P(7,9)*d(7,9) + P(7,10)*d(7,10) + P(7,11)*d(7,11) + P(7,12)*d(7,12) + +P(8,9)*d(8,9) + P(9,10)*d(9,10) + P(11,12)*d(11,12) +P(12,13)*d(12,13) + +P(13,14)*d(13,14) + P(13,15)*d(13,15) + P(13,22)*d(13,22) +

+P(14,17)*d(14,17) + P(15,17)*d(15,17) + P(15,19)*d(15,19) + +P(15,22)*d(15,22) +P(16,19)*d(16,19) + P(16,22)*d(16,22) + +P(17,18)*d(17,18) + P(18,19)*d(18,19) +P(18,20)*d(18,20) + +P(19,20)*d(19,20) + P(19,21)*d(19,21) + P(20,22)*d(20,22) +

+P(21,22)*d(21,22) =

= 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 +1*1 + 1*2 + + 2*1 + 1*2 + 1*2 + 1*1 + 1*2 + 2*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + +1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 + 1*1 + 1*2 + 1*1 + +1*1+ 1*2 + 1*2 = 53

Мінімальна можлива кількість переключень тригерів:

Wmin = E P(i,j) = 42

Коефіцієнт ефективності кодування: 1.26

2.1.4. Структурний синтез автомата на підставі заданого типу тригерів

Таблиця переходів Т-тригера:

Табл.2. Таблиця переходів Т-тригера

Q^t	Q^t+1	T
0	0	0
0	1	1
1	0	1
1	1	0

На підставі цієї таблиці я вказую у табл.1 який тригер встановиться в 1, а який в 0.

2.1.5. Функції збудження тригерів та вихідних сигналів

Введемо слідуючі позначення:

А=; B=; C=; F=; G=;

L=; P=; Q=; R=; S=;

T=; U=; V=; Б=; Y=;

Z=; D=; E=; H=; I= ;

J= ; K=; O=; W=; X=;

Г=; Д=; M=; N=.

+ ;

;

2.2. Структурний синтез автомата Мура

2.2.1. Розмітка станів ГСА

Для автомата Мура на етапі одержання відміченої ГСА розмітка провадиться відповідно до наступних правил:

1) символом а₁ відмічаються початкова і кінцева вершини;

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

3) всі операторні вершини повинні бути відмічені.

Відповідно до цих правил я відмітив 25 станів, які показані на рис. 2.

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

Для кожного стану a_i визначаю по ГСА всі шляхи, які ведуть в інші стани.

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

Табл.3. Таблиця переходів D-тригера

as(Y)

Kas

Xamas

a23

a24

a1(-)

00010

a12

a11

a2(Y1,Y2)

00100

a3(Y1,Y4)

11000

a4(Y3)

00111

a5(Y7)

01011

a6(Y4,Y5)

10011

X4X2

a7(Y2,Y6)

01000

a8(Y1,Y8)

00000

X4X2X1

a9(Y5,Y9)

10000

X4X2X1

a10(Y4)

01110

a10

a11(Y4,Y5)

10110

a12(Y3,Y10)

00011

X4X3

a13(Y6)

00001

X4X3

X4X1

a13

a14(Y2,Y4)

00101

X4X1

a24

a25

a15(Y3,Y6)

01001

a14

a15

a16(Y7)

10001

a16

a17(Y1,Y9)

11100

a15

a16

a18(Y8)

00100

X5X6

a15

a19(Y3)

10101

X5X6

a17

a18

a20(Y2,Y4)

01010

a18

a19

a21(Y3,Y6)

10010

a20

a21

a22(Y7)

01100

a22

a23(Y1,Y9)

01101

a21

a22

a24(Y8)

10100

X5X6

X1D1

a21

a25(Y3)

11001

X5X6

2. 2.3. Кодування станів

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

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.

2.2.4. Структурний синтез автомата на підставі заданого типу тригерів

Таблиця переходів D-тригера:

Табл.2. Таблиця переходів D-тригера