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

ЗМІСТ

Введення

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)(MOD5)=(30+06+22)(MOD 5)=58(MOD 5)=3.

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

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

/> /> /> /> /> /> /> /> /> /> />/>

BEGIN

/> /> /> /> /> /> /> <td/> /> />

/>/>/>/>

END

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

/> /> /> /> /> /> /> />

Y1, Y2

/> />

BEGIN

/> /> /> /> /> /> /> <td/>

Y1, Y4

/>/>

/>/>/>/>/>/>/>/>/>/>

/> /> /> /> /> /> /> /> /> <td/>

<td/>

/>/>/>/>

/>/>/>/>/>/>/>

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. Розмітка станів ГСА

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

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

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

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

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

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

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

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

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

Kam

Kas

Xamas

Yamas

10110

10010

Y1Y4

10010

00010

10000

Y2Y6

T4 A B

00011

00010

Y2Y6

00010

00000

Y1Y8

00000

a11

01000

01001

10001

X4X3

Y3Y10 Y6

T2 T5

D E

10000

00000

11001

X1 Y1Y8

Y5Y9

11001

a11 a11

a12

01001

10001 10001

11000

X4X3

X4X3 X4X1

X4X1

Y3Y10

Y6 Y6

Y2Y4

T2 T2

I J K

01000

01001

Y4Y5

01001

a10

00001

Y1Y2

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

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

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

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

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

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

i j P(i, j)

12 1

24 1

26 1

34 1

45 1

58 1

59 1

510 1

511 1

65 1

67 1

79 1

711 2

712 1

89 1

910 1

103 1

107 1

104 1

105 1

T=11 12 1

1213 1

1314 1

1315 1

1417 1

1517 1

1519 1

1619 1

1718 1

181 1

1820 1

1918 1

1920 1

1921 1

201 1

2022 1

2122 1

2213 1

2215 1

22 16 1

Далі, за допомогою програми ECODE3, виконую кодування станів автомата на ЕОМ. При цьому вказуюглибину кодування (від 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. Таблиця переходів Т-тригера

Qt+1

T 1 1 1 1 1 1

На підставі цієї таблиці я вказую у табл.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)символом а1 відмічаються початкова і кінцева вершини;

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

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

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

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

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

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

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

as(Y)

Kas

Xamas

a23

a24

a1(-)

00010

D4 U a12

a11

a2(Y1,Y2)

00100 1 1 D3 D3

a3(Y1,Y4)

11000

a4(Y3)

00111

a5(Y7)

01011

a6(Y4,Y5)

10011

X4X2

a7(Y2,Y6)

01000 X3

D2 a2 a5 a6

a8(Y1,Y8)

00000

X4X2X1

X1 1 1 a2

a9(Y5,Y9)

10000

X4X2X1

a10(Y4)

01110

a10

a11(Y4,Y5)

10110

a12(Y3,Y10)

00011

X4X3

F a8 a9

a13(Y6)

00001

X4X3

X4X3 X4X1 D5 D5

a13

a14(Y2,Y4)

00101

X4X1

a24

a25

a15(Y3,Y6)

01001

a14

a15

a16(Y7)

10001

D5 I

a16

a17(Y1,Y9)

11100

a15

a16

a18(Y8)

00100

X5X6

a15

a19(Y3)

10101

X5X6

a17

a18

a20(Y2,Y4)

01010

D4 N a18

a19

a21(Y3,Y6)

10010

a20

a21

a22(Y7)

01100

D3 P

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) ставиться у відповідність ціле число 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.

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

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

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

Qt+1

D 1 1 1 1 1 1

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

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

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

U=/>; A=/>;B=/>; W=/>;D=/>;

H=/>; I=/>; J=/>; L=/>; N=/>;

O=/>; P=/>; Q=/>; S=/>; C=/>;