Синтез керуючих автоматів

5


ВСТУП

Принцип мікропрограмного керування припускає, що цифровий пристрій складається з двох частин: операційний автомат (ОА) і керуючий автомат (КА). ОА виконує найпростіші операції (мікрооперації) типу зсув, алгебраїчне додавання, кон’юнкція, диз’юнкція і т.п. КА формує послідовність керуючих символів в ОА, під впливом яких ОА реалізує більш складні алгоритми. Такі послідовності операцій називаються мікропрограмами та, звичайно, записуються у вигляді граф-схеми алгоритму.

КА розділяються на дві великі групи: автомати з жорсткою логікою та автомати з програмованою логікою. У свою чергу автомати з жорсткою логікою підрозділяються на автомати, виконані за схемою Мілі (КА Мілі) і за схемою Мура (КА Мура), автомати з програмованою логікою – на автомати з примусовою адресацією та з природною адресацією.

В автоматах з жорсткою логікою схема автомата однозначно інтерпретує граф-схему мікропрограми. В автоматах із програмованою логікою граф-схема інтерпретується у вигляді програми, що зберігається в пам’яті автомата.

1. СИНТЕЗ ОПЕРАЦІЙНОГО АВТОМАТА

1.1 Аналіз вхідних даних

Загальна формула для обчислювання результату S має такий вигляд:

Формулі , та згідно з варіантом завдання:

Загальний алгоритм для обчислювання формули S приведений на рисунку 1.1.

Для обчислювання формули S використовується ІМp-модель (Individual Mutual with Parallel part - IMp).


Рис. 1.1 – Загальний алгоритм для обчислювання формули S

Схему взаємодії операційного та керуючої частин у цифровому просторі зображено на рисунку 1.2.


Рис. 1.2 – Структура цифрового пристрою

Структурна схема ІМp - моделі зображена на рисунку 1.3














Рис. 1.3 – Структура операційного пристрою

Пам’ять автомата складається з регістрів загального призначення R>1, >... , R>n>.

Локальні шини А>1>, А>2>, A>3> призначені для прийому інформації з пам’яті та передачі її на комбінаційні схеми (КС).

В даному випадку використовуються КС двох типів: одномісні та двомісні.

Рис. 1.4 – Приклад комбінаційних схем

Однак, у даному ОА використовуються лише деякі з них.

      Розробка функціонального алгоритму

Функціональна і структурна організація операційних пристроїв (ОУ) базується на принципі мікро програмного керування, сформульованому в 1951 році М. Уилксом. Відповідно до цього принципу будь-яка машинна операція розділяється на послідовність елементарних дій по обробці інформації – мікро операцій (МО). Порядок проходження мікро операцій визначається спеціальними логічними умовами (ЛУ), що у залежності від значень оброблюваної інформації приймають значення "істина" (1) або "неправда" (0). Алгоритм операцій в ОУ, записаний у термінах мікро операцій і логічних умов, що відбиває порядок проходження мікро операцій у часі, називається мікропрограмою.

Функція УА – це оперативна схема алгоритму, операторами якої є символи

, що ототожнюються з МО, виконуваними ОА, як логічні умови використовуються булеві перемінні . Найбільше часто операторна схема алгоритму представляється у виді граф-схеми алгоритму (ГСА).

Граф-схема алгоритму. Орієнтований зв'язаний граф – граф, що містить одну початкову вершину, одну кінцеву вершину, довільну безліч умовних і операторних вершин.

Будова ІМр автомата дозволяє паралельно виконувати одномісну та двумісну операції, тобто можливо виконувати за одне завантаження автомату завантаження двох операнд. Наприклад, у п’ятій вершині зроблено саме так.

Кожній дії, завантаженню автомата, відповідає Y[і].

Ідентичні дії відповідають однаковим командам, Y[і].

Логічні умови позначаються – XL, однаковим умовам відповідають однакові XL.

Функціональний алгоритм приведений на рисунку 1.5.

Рис. 1.5 – Функціональний алгоритм

      Розробка структурної схеми автомата

1.3.1. Визначення набору регістрів пам’яті:

Rg : {RA, RB, RC, RS>1>, RS>2>, RS>3>}

1.3.2. Набір комбінаційних схем:

Одномісні: КС1 : {L>1>, L>2>, L>3>, R>1>, R>2>, R>3>}

На шину C повинні поступати всі аргументи одномісних операцій.

Двомісні: КС2: {Sum, sub>}

Припустимо, що операція відіймання виконується наступним чином:

sub> := B - A, тому від’ємне завжди повинно знаходитись на шині B, а від’ємник на шині А. В іншій двомісній операції Sum порядок операндів значення не має.

Рис. 1.6 – Структурна схема автомата

1.3.3. Зв'язки між регістрами та локальними шинами

Наша схема має три шини: А та B – двомісні, та шина C – одномісна.

A {RA, RB, RC, RS>1>, RS>2>, RS>3>}

B {RA, RB, RC, RS>1>, RS>2>, RS>3>}

C {RA, RB, RC, RS>1>, RS>2>, RS>3>}

        Зворотні зв'язки шин Z1 та Z2 з регістрами пам’яті

Шини, що є результативними:

Z>1> – результати одномісних операцій, а Z>2> – двомісних операцій.

Z>1> {RA, RB, RC, RS>1>, RS>2>, RS>3>}

Z>2> {RA, RB, RC, RS>1>, RS>2>, RS>3>}

Кожний елемент, котрий діє у схемі може виконуватись тільки при наявності відповідного керуючого сигналу y>[n]>.

у>1>, у>2>, у>3> – завантаження початкових даних на шини.

у>4>> >– у>15> – завантаження даних у регістри пам'яті.

у>1>>6>–у>33> – завантаження з пам'яті на локальні шини А, B, C.

у>34>, у>39> – завантаження результатів одномісних операцій на шину Z>1>.

y>40>–у>41> – завантаження результатів двомісних операцій на шину Z>2>.

Отримані таким чином дані заносимо до таблиці 1.1

Табл. 1.1 –Таблиця мікрооперацій

Мікрооперація

A

B

C

Z>1>

Z>2>

Result

Y

формула

регістр

y

регістр

y

регістр

y

форм.

y

форм.

y

регістр

y

1

RA := <A>

RB := <B>

<B>

y>2>

<A>

y>1>

RA:=Z>2>

RB:=Z>1>

y>4>

y>7>

2

RC := <C>

<C>

y>3>

RC:=Z>2>

y>8>

3

RS>3> := RA + RB

RA

y>17>

RB

y>21>

RA+RB

y>40>

RS>3>:=Z>2>

y>14>

4

RS>2> := RA – RB

RB

y>20>

RA

y>18>

RA-RB

y>41>

RS>2>:=Z>2>

y>12>

5

RS>1> := L>3>(RS>2>)

RS>2>

y>28>

L>3>(RS>2>)

y>36>

RS>1>:=Z>1>

y>11>

6

RS>1> := RS>1> – RS>2>

RS>2>

y>29>

RS>1>

y>27>

RS>1>-RS>2>

y>41>

RS>1>:=Z>2>

y>10>

7

RS>2> := L>2>(RA)

RA

y>16>

L>2>(RA)

y>35>

RS>2>:=Z>1>

y>13>

8

RS>3> := L>1>(RB)

RB

y>19>

L>1>(RB)

y>34>

RS>3>:=Z>1>

y>15>

9

RS>1> := RS>2> – RS>3>

RS>3>

y>32>

RS>2>

y>30>

RS>2>-RS>3>

y>41>

RS>1>:=Z>2>

y>10>

10

RS>1> := L>2>(RA)

RA

y>16>

L>2>(RA)

y>35>

RS>1>:=Z>1>

y>11>

11

RS>1> := RS>1> – RA

RA

y>17>

RS>1>

y>27>

RS>1>-RA

y>41>

RS>1>:=Z>2>

y>10>

12

RS>1> := R>1>(RS>1>)

RS>1>

y>25>

R>1>(RS>1>)

y>37>

RS>1>:=Z>1>

y>11>

13

RS>1> := RS>1> – RB

RB

y>20>

RS>1>

y>27>

RS>1>-RB

y>41>

RS>1>:=Z>2>

y>10>

14

RS>3> := RB – RA

RA

y>17>

RB

y>21>

RB-RA

y>41>

RS>3>:=Z>2>

y>14>

15

RS>3> := R>1>(RB)

RB

y>19>

R>1>(RB)

y>37>

RS>3>:=Z>1>

y>15>

16

RS>2> := RA – RS>3>

RS>3>

y>32>

RA

y>18>

RA-RS>3>

y>41>

RS>2>:=Z>2>

y>12>

17

RS>2> := RA + RB

RS>3> := L>1>(RC)

RA

y>17>

RB

y>21>

RC

y>22>

L>1>(RC)

y>34>

RA+RB

y>40>

RS>2>:=Z>2>

RS>3>:=Z>1>

y>12> y>15>

18

RS>2> := RS>2> – RS>3>

RS>3>

y>32>

RS>2>

y>30>

RS>2>-RS>3>

y>41>

RS>2>:=Z>2>

y>12>

19

RS>2> := RS>2> – RC

RC

y>23>

RS>2>

y>30>

RS>2>-RC

y>41>

RS>2>:=Z>2>

y>12>

20

RS>3> := L>1>(RB)

RB

y>19>

L>1>(RB)

y>34>

RS>3>:=Z>1>

y>15>

21

RS>3> := RA – RS>3>

RS>3>

y>32>

RA

y>18>

RA-RS>3>

y>41>

RS>3>:=Z>2>

y>14>

22

RS>2> := L>3>(RS>3>)

RS>3>

y>31>

L>3>(RS>3>)

y>36>

RS>2>:=Z>1>

y>13>

23

RS>2> := RS>2> – RS>3>

RS>3>

y>32>

RS>2>

y>30>

RS>2>-RS>3>

y>41>

RS>2>:=Z>2>

y>12>

24

RS>2> := R>3>(RS>2>)

RS>2>

y>28>

R>3>(RS>2>)

y>39>

RS>2>:=Z>1>

y>13>

25

RS>3> := RC + RB

RB

y>20>

RC

y>24>

RB+RC

y>40>

RS>3>:=Z>2>

y>14>

26

RS>3> := L>1>(RS>3>)

RS>3>

y>31>

L>1>(RS>3>)

y>34>

RS>3>:=Z>1>

y>15>

27

RS>3> := RS>3> + RC

RS>3>

y>32>

RC

y>24>

RS>3>+RC

y>40>

RS>3>:=Z>2>

y>14>

28

RC := L>2>(RB)

RS>3> := RA – RB

RB

y>20>

RA

y>18>

RB

y>19>

L>2>(RB)

y>35>

RA-RB

y>41>

RC:=Z>1>

RS>3>:=Z>2>

y>9> y>14>

29

RS>3> := RS>3> – RC

RC

y>23>

RS>3>

y>33>

RS>3>-RC

y>41>

RS>3>:=Z>2>

y>14>

30

RS>3> := RC – RA

RA

y>17>

RC

y>24>

RC-RA

y>41>

RS>3>:=Z>2>

y>14>

31

RS>3> := R>2>(RS>3>)

RS>3>

y>31>

R>2>(RS>3>)

y>38>

RS>3>:=Z>1>

y>15>

32

RS>1> := L>1>(RS>1>)

RS>1>

y>25>

L>1>(RS>1>)

y>34>

RS>1>:=Z>1>

y>11>

33

RS>1> := RS>2> + RS>1>

RS>1>

y>26>

RS>2>

y>30>

RS>1>+RS>2>

y>40>

RS>1>:=Z>2>

y>10>

34

RS>1> := RS>2> – RS>1>

RS>1>

y>26>

RS>2>

y>30>

RS>2>-RS>1>

y>41>

RS>1>:=Z>2>

y>10>

35

RS>1> := L>2>(RS>3>)

RS>3>

y>31>

L>2>(RS>3>)

y>35>

RS>1>:=Z>1>

y>11>

36

RS>1> := RS>2> + RS>1>

RS>1>

y>26>

RS>2>

y>30>

RS>1>+RS>2>

y>40>

RS>1>:=Z>2>

y>10>

Рис. 1.7 – Структурна граф-схема операційного автомата

2. СИНТЕЗ КЕРУЮЧИХ АВТОМАТІВ З ЖОРСТКОЮ ЛОГІКОЮ

На практиці використовуються дві моделі МПА - автомат Милі й автомат Мура, розходження між якими полягає у функції виходу. В автоматі Милі вихідний сигнал залежить від поточного стану і вхідного сигналу, а в автоматі Мура  тільки від стану. Незалежно від типу МПА для їхнього синтезу використовується однакова методика, що включає наступні етапи:

1. Оцінка станів автомата на ГСА.

2. Побудова таблиці переходів.

3. Кодування станів УА.

4. Побудова прямої структурної таблиці.

5. Формування системи булевських функцій (СБФ) для вихідних сигналів і функцій збудження елементів пам'яті

6. Синтез схеми в заданому елементному базисі.

      Методика синтезу автомата Мура

На першому етапі початкова і кінцева вершини відзначаються окремим станом.

Побудова таблиці переходів зводиться, до формувань по відзначеної ГСА таблиці, що містить стовпці: a>m> - вихідний стан; a>s> - стан переходу; X(a>m>, a>s>) - кон’юнкція вхідних перемінних, визначальний перехід (a>m>, a>s>) і відповідна функції переходу іj, де Y> відзначений станом a>m>, Y – стан As, Y(a>m>) - вихідні сигнали; h=1, H - номер переходу.

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

Для цих цілей рекомендується використовувати алгоритми кодування.

Структурна схема автомата Мура (див. рис. 2.1):

1. Пам'ять – зберігає код стану (Q);

2. Дешифратор (ДС) – виконує перетворення коду в унітарний код, вказує на поточний стан.

На базі вектора станів А схема вихідних сигналів (СФВС) формує вихідні сигнали керуючого автомата y.

Автомат Мура має свою відмінність - вихідний сигнал y залежить не від вхідного Х, а від стану.

Автомат Мура, як і кожний інший автомат складається з двох частин: комбінаційна схема та пам'ять (тригер).

Для синтезу автомата Мура потрібно позначити кожну операторну вершину через a>[i]>, починаючи з “початок” - і закінчуючи “кінець” - , так як це зроблено на рисунку 2.2.

Записуємо до таблиці 2.2 отримані результати: поточний стан (мітка вершини та номер її значення в двійковій системі вираховування), наступний стан (мітка вершини та номер її значення в двійковій системі вираховування), вхідний сигнал Х, вихідний сигнал Y та функції збудження пам'яті у заданому тригері (згідно варіанта - у тригері RS).

Рис. 2.2 – Граф-схема автомата Мура

Табл. 2.1 – Структура переходів для автомата Мура

п/п

Поточний

стан

Наступний

стан

Вхідний сигнал

Х

Вихідний сигнал

y

S входи тригерів

R входи тригерів

A>m>

код

A>s>

код

1

a>0>

000000

a>1>

000001

1

-

S>6>

2

a>1>

000001

a>2>

000010

1

у>1> у>2> y>4> y>7>

S>5>

R>6>

3

a>2>

000010

a>3>

000011

1

y>3> у>8>

S>6>

4

a>3>

000011

a>4>

a>7>

a>10>

000100

000111

001010

X>3>

nX>3> X>4>

nX>3> nX>4>

у>1>>4> у>17> у>2>>1> y>40>

S>4>

S>4>

S>3>

R>5> R>6>

R>6>

5

a>4>

000100

a>5>

000101

1

y>12> у>1>>8> у>20> y>41>

S>6>

6

a>5>

000101

a>6>

000110

1

y>11> y>28> y>36>

S>5>

R>6>

7

a>6>

000110

a>14>

001110

1

y>10> y>27> y>29> y>41>

S>3>

8

a>7>

000111

a>8>

001000

1

y>13> y>16> y>35>

S>3>

R>4> R>5> R>6>

9

a>8>

001000

a>9>

001001

1

y>15> y>19> y>34>

S>6>

10

a>9>

001001

a>14>

001110

1

y>10> y>30> y>32> y>41>

S>4> S>5>

R>6>

11

a>10>

001010

a>11>

001011

1

y>11> y>16> y>35>

S>6>

12

a>11>

001011

a>12>

001100

1

y>10> y>17> y>27> y>41>

S>4>

R>5> R>6>

13

a>12>

001100

a>13>

001101

1

y>11> y>25> y>37>

S>6>

14

a>13>

001101

a>14>

001110

1

y>10> y>20> y>27> y>41>

S>5>

R>6>

15

a>14>

001110

a>15>

a>17>

a>20>

001111

010001

010100

X>3>

nX>3> X>4>

nX>3> nX>4>

y>14> y>17> y>21> y>41>

S>6>

S>2> S>6>

S>2>

R>3> R>4> R>5>

R>3> R>5>

16

a>15>

001111

a>16>

010000

1

y>15> y>19> y>37>

S>2>

R>3> R>4> R>5> R>6>

17

a>16>

010000

a>25>

011001

1

y>12> y>18> y>32> y>41>

S>3> S>6>

18

a>17>

010001

a>18>

010010

1

y>12> y>15> y>17>

y>21> y>22> y>34> y>40>

S>5>

R>6>

19

a>18>

010010

a>19>

010011

1

y>12> y>30> y>32> y>41>

S>6>

20

a>19>

010011

a>25>

011001

1

y>12> y>23> y>30> y>41>

S>3>

R>5>

21

a>20>

010100

a>21>

010101

1

y>15> y>19> y>34>

S>6>

22

a>21>

010101

a>22>

010110

1

y>14> y>18> y>32> y>41>

S>5>

R>6>

23

a>22>

010110

a>23>

010111

1

y>13> y>31> y>36>

S>6>

24

a>23>

010111

a>24>

011000

1

y>12> y>30> y>32> y>41>

S>3>

R>4> R>5> R>6>

25

a>24>

011000

a>25>

011001

1

y>13> y>28> y>39>

S>6>

26

a>25>

011001

a>26>

a>28>

a>30>

011010

011100

011110

X>3>

nX>3> X>4>

nX>3> nX>4>

y>14> y>20> y>24> y>40>

S>5>

S>4>

S>4> S>5>

R>6>

R>6>

R>6>

27

a>26>

011010

a>27>

011011

1

y>15> y>31> y>34>

S>6>

28

a>27>

011011

a>32>

a>34>

a>35>

100000

100010

100011

X>2>

nX>2> X>1>

nX>2> nX>1>

y>14> y>24> y>32> y>40>

S>1>

S>1>

S>1>

R>2> R>3> R>5> R>6>

R>2> R>3> R>6>

R>2> R>3>

29

a>28>

011100

a>29>

011101

1

y>9> y>14> y>18>

y>19> y>20> y>35> y>41>

S>6>

30

a>29>

011101

a>32>

a>34>

a>35>

100000

100010

100011

X>2>

nX>2> X>1>

nX>2> nX>1>

y>14> y>23> y>33> y>41>

S>1>

S>1> S>5>

S>1> S>5>

R>2> R>3> R>4> R>6>

R>2> R>3> R>4> R>6>

R>2> R>3> R>4>

31

a>30>

011110

a>31>

011111

1

y>14> y>17> y>24> y>41>

S>6>

32

a>31>

011111

a>32>

a>34>

a>35>

X>2>

nX>2> X>1>

nX>2> nX>1>

y>15> y>31> y>38>

S>1>

S>1>

S>1>

R>2> R>3> R>4> R>5> R>6>

R>2> R>3> R>4> R>6>

R>2> R>3> R>4>

33

a>32>

100000

a>33>

100001

1

y>11> y>25> y>34>

S>6>

34

a>33>

100001

a>0>

000000

1

y>10> y>26> y>30> y>40>

R>1> R>6>

35

a>34>

100010

a>0>

000000

1

y>10> y>26> y>30> y>41>

R>1> R>5>

36

a>35>

100011

a>36>

100100

1

y>11> y>31> y>35>

S>4>

R>5> R>6>

37

a>36>

100100

a>0>

000000

1

y>10> y>26> y>30> y>40>

R>1> R>4>

2.2 Формування схеми автомата Мура

2.2.1 Функції збудження пам'яті та їх синтез у заданий базис:

2.2.2 Синтез дешифратора та його синтез у заданий базис:

Синтез дешифратора для автомата Мура розробляється так само, як і синтез для автомата Мілі(див. далі).

2.2.3 Рівняння вихідних сигналів та їх синтез у заданий базис:

      Методика синтезу автомата Мілі

Структурна схема автомата Мілі (зображена на рис. 2.3) включає ті ж етапи, що і синтез КА Мура. Відрізняється від схеми автомата Мура тим, що вихідні сигнали Y залежать від вхідних Х.

Порядок синтезу автомата Мілі:

1. Позначаємо вхід початкових та кінцевих станів;

2. Позначаємо вихід операторних вершин у паралельних гілках одним станом (див. рис. 2.4). Кожна операторна вершина відзначається окремим станом. Таблиця переходів автомата має наступні стовпці: a>m>, a>s> - вихідний стан і стан переходу.

Х (am,as) - кон’юнкція вхідних перемінних, визначальний перехід (a>m>, a>s>),

Y>h> - вихідний сигнал на переході (a>m>, a>s>).

Для синтезу логічної схеми в заданому базисі необхідно перетворити СБФ за правилами Де-Моргана з урахуванням обмежень елементного базису - числа входів і навантажувальної здатності.



Рис. 2.5 – Граф-схема автомата Мілі

Табл. 2.2 – Структура переходів для автомата Мілі

п/п

Поточний

стан

Наступний

стан

Вхідний сигнал

Х

Вихідний сигнал

y

S входи тригерів

R входи тригерів

A>m>

код

A>s>

код

1

a>0>

00000

a>1>

00001

1

у>1> у>2> y>4> y>7>

S>5>

2

a>1>

00001

a>2>

00010

1

y>3> у>8>

S>4>

R>5>

3

a>2>

00010

a>3>

00011

1

у>1>>4> у>17> у>2>>1> y>40>

S>5>

4

a>3>

00011

a>4>

a>6>

a>8>

00100

00110

01000

X>3>

nX>3> X>4>

nX>3> nX>4>

y>12> у>1>>8> у>20> y>41>

y>13> y>16> y>35>

y>11> y>16> y>35>

S>3>

S>3>

S>2>

R>4> R>5>

R>5>

R>4> R>5>

5

a>4>

00100

a>5>

00101

1

y>11> y>28> y>36>

S>5>

6

a>5>

00101

a>11>

01011

1

y>10> y>27> y>29> y>41>

S>2> S>4>

R>3>

7

a>6>

00110

a>7>

00111

1

y>15> y>19> y>34>

S>5>

8

a>7>

00111

a>11>

01011

1

y>10> y>30> y>32> y>41>

S>2>

R>3>

9

a>8>

01000

a>9>

01001

1

y>10> y>17> y>27> y>41>

S>5>

10

a>9>

01001

a>10>

01010

1

y>11> y>25> y>37>

S>4>

R>5>

11

a>10>

01010

a>11>

01011

1

y>10> y>20> y>27> y>41>

S>5>

12

a>11>

01011

a>12>

01100

1

y>14> y>17> y>21> y>41>

S>3>

R>4> R>5>

13

a>12>

01100

a>13>

a>14>

a>16>

01101

01110

10000

X>3>

nX>3> X>4>

nX>3> nX>4>

y>15> y>19> y>37>

y>12> y>15> y>17>

y>21> y>22> y>34> y>40>

y>15> y>19> y>34>

S>5>

S>4>

S>1>

R>2> R>3>

14

a>13>

01101

a>20>

10100

1

y>12> y>18> y>32> y>41>

S>1>

R>2> R>5>

15

a>14>

01110

a>15>

01111

1

y>12> y>30> y>32> y>41>

S>5>

16

a>15>

01111

a>20>

10100

1

y>12> y>23> y>30> y>41>

S>1>

R>2> R>4> R>5>

17

a>16>

10000

a>17>

10001

1

y>14> y>18> y>32> y>41>

S>5>

18

a>17>

10001

a>18>

10010

1

y>13> y>31> y>36>

S>4>

R>5>

19

a>18>

10010

a>19>

10011

1

y>12> y>30> y>32> y>41>

S>5>

20

a>19>

10011

a>20>

10100

1

y>13> y>28> y>39>

S>3>

R>4> R>5>

21

a>20>

10100

a>21>

10101

1

y>14> y>20> y>24> y>40>

S>5>

22

a>21>

10101

a>22>

a>23>

a>24>

10110

10111

11000

X>3>

nX>3> X>4>

nX>3> nX>4>

y>15> y>31> y>34>

y>9> y>14> y>18>

y>19> y>20> y>35> y>41>

y>14> y>17> y>24> y>41>

S>4>

S>4>

S>2>

R>5>

R>3> R>5>

23

a>22>

10110

a>25>

11001

1

y>14> y>24> y>32> y>40>

S>2> S>5>

R>3> R>4>

24

a>23>

10111

a>25>

11001

1

y>14> y>23> y>33> y>41>

S>2>

R>3> R>4>

25

a>24>

11000

a>25>

11001

1

y>15> y>31> y>38>

S>5>

26

a>25>

11001

a>26>

a>0>

a>27>

11010

00000

11011

X>2>

nX>2> X>1>

nX>2> nX>1>

y>11> y>25> y>34>

y>10> y>26> y>30> y>41>

y>11> y>31> y>35>

S>4>

S>4>

R>5>

R>1> R>2> R>5>

27

a>26>

11010

a>0>

00000

1

y>10> y>26> y>30> y>40>

R>1> R>2> R>4>

28

a>27>

11011

a>0>

00000

1

y>10> y>26> y>30> y>40>

R>1> R>2> R>4> R>5>

2.4 Формування схеми автомата Мілі

2.4.1 Функції збудження пам'яті та їх синтез у заданий базис:

2.4.2 Синтез дешифратора та його синтез у заданий базис.

Методика синтезу дешифратора до автомата Мілі:

    таблиця істинності (Карта Карно);

    Карта Карно для одержання мінімізованої функції збудження;

    запис формул функцій збудження;

    побудова схеми.

Оскільки на кожнім наборі вхідних перемінних активний тільки один біт, то Карту Карно можна зобразити одну загальну для усіх вихідних сигналів. При цьому в осередках Карти Карно записуються не одиниці, а імена відповідних функцій.

Табл. 2.3 – Карта Карно до дешифратора автомата Мілі

000 001 011 010 110 111 101 100

00

01

11

10

а>0>

а>1>

а>3>

а>2>

а>6>

а>7>

а>5>

а>4>

а>8>

а>9>

а>11>

а>10>

а>14>

а>15>

а>13>

а>12>

а>24>

а>25>

а>27>

а>26>

*

*

*

*

а>16>

а>17>

а>19>

а>18>

а>22>

а>23>

а>21>

а>20>

...

...

...

Електрична схема дешифратора зображена на рисунку 2.6.

Рис. 2.6 – Дешифратор. Функціональна схема.

2.4.3 Рівняння вихідних сигналів та їх синтез у заданий базис:

3. Синтез автоматів з програмованою логікою

3.1 Синтез автомата з примусовою адресацією команд

ПЗУ – зберігаємий набір команд, кожна з котрих несе інформацію про набір вихідного сигналу, про поточний такт та адресу мікрокоманд, котрі повинні бути виконані у наступному такті.


Рис. 3.1 - Формат МК


Рис. 3.2 - Структурна схема АПЛ з примусовою адресацією мікрокоманд

Аналіз рисунка 3.2:

    СФВС - дозволяє декодувати інформацію, що утримується в полі Y.

    САХ - являє собою мультиплексор на інформаційні входи якого подаються вхідні сигнали, а на адресні, код з поля Nх при цьому на А>0> завжди подається сигнал "0", у такий спосіб формується сигнал Z, що забезпечує передачу на адресний вхід пам'яті А або А>0>, або А>1>.

Для того щоб сформувати вміст ROM по граф-схемі мікрокоманд необхідно:

    відзначити номера мікрокоманд;

    закодувати вихідні сигнали і сформувати мікрокоманди по заданому форматі;

    сформувати таблицю вмісту ROM.

Рис. 3.3 – Граф-схема автомата з примусовою адресацією команд

Для скорочення довжини слова ROM будемо використовувати принцип максимального кодування вихідних сигналів.

Табл. 3.1 – Максимальне кодування вихідних сигналів

№ п/п

Макрокоманда

Мікрооперації

Код

1

Y>0>

-

000000

2

Y>1>

y>1> y>2> y>4> y>7>

000001

3

Y>2>

y>3> y>8>

000010

4

Y>3>

y>14> y>17> y>21> y>40>

000011

5

Y>4>

y>11> y>16> y>35>

000100

6

Y>5>

y>10> y>17> y>27> y>41>

000101

7

Y>6>

y>11> y>25> y>37>

000110

8

Y>7>

y>10> y>20> y>27> y>41>

000111

9

Y>8>

y>13> y>16> y>35>

001000

10

Y>9>

y>15> y>19> y>34>

001001

11

Y>10>

y>10> y>30> y>32> y>41>

001010

12

Y>11>

y>12> y>18> y>20> y>41>

001011

13

Y>12>

y>11> y>28> y>36>

001100

14

Y>13>

y>10> y>27> y>29> y>41>

001101

15

Y>14>

y>14> y>17> y>21> y>41>

001110

16

Y>15>

y>15> y>19> y>34>

001111

17

Y>16>

y>14> y>18> y>32> y>41>

010000

18

Y>17>

y>13> y>31> y>36>

010001

19

Y>18>

y>12> y>30> y>32> y>41>

010010

20

Y>19>

y>13> y>28> y>39>

010011

21

Y>20>

y>12> y>15> y>17> y>21> y>22> y>34> y>40>

010100

22

Y>21>

y>12> y>30> y>32> y>41>

010101

23

Y>22>

y>12> y>23> y>30> y>41>

010110

24

Y>23>

y>15> y>19> y>37>

010111

25

Y>24>

y>12> y>18> y>32> y>41>

011000

26

Y>25>

y>14> y>20> y>24> y>40>

011001

27

Y>26>

y>14> y>17> y>24> y>41>

011010

28

Y>27>

y>15> y>31> y>38>

011011

29

Y>28>

y>9> y>14> y>18> y>19> y>20> y>35> y>41>

011100

30

Y>29>

y>14> y>23> y>33> y>41>

011101

31

Y>30>

y>15> y>31> y>34>

011110

32

Y>31>

y>14> y>24> y>32> y>40>

011111

33

Y>32>

y>11> y>31> y>35>

100000

34

Y>33>

y>10> y>26> y>30> y>40 >y>0>

100001

35

Y>34>

y>10> y>26> y>30> y>41 >y>0>

100010

36

Y>35>

y>11> y>25> y>34>

100011

Табл. 3.2 – Структура переходів для автомата з примусовою адресацією команд

Адреса

а>1>2>3>4>5>6>

Y

0..5

X

6..8

FA>0>

9..14

FA>1>

15..20

Перехід

000000

000001

000

000001

*

b>0> → b>1>

000001

000010

000

000010

*

b>1> → b>2>

000010

000011

011

000011

001011

b>2> →

000011

000000

100

000100

001000

b>3> →

000100

000100

000

000101

*

b>4> → b>5>

000101

000101

000

000110

*

b>5> → b>6>

000110

000110

000

000111

*

b>6> → b>7>

000111

000111

000

001110

*

b>7> → b>14>

001000

001000

000

001001

*

b>8> → b>9>

001001

001001

000

001010

*

b>9> → b>10>

001010

001010

000

001110

*

b>10> → b>14>

001011

001011

000

001100

*

b>11> → b>12>

001100

001100

000

001101

*

b>12> → b>13>

001101

001101

000

001110

*

b>13> → b>14>

001110

001110

011

001111

011000

b>14> →

001111

000000

100

010000

010101

b>15> →

010000

001111

000

010001

*

b>16> → b>17>

010001

010000

000

010010

*

b>17> → b>18>

010010

010001

000

010011

*

b>18> → b>19>

010011

010010

000

010100

*

b>19> → b>20>

010100

010011

000

011010

*

b>20> → b>26>

010101

010100

000

010110

*

b>21> → b>22>

010110

010101

000

010111

*

b>22> → b>23>

010111

010110

000

011010

*

b>23> → b>26>

011000

010111

000

011001

*

b>24> → b>25>

011001

011000

000

011010

*

b>25> → b>26>

011010

011001

011

011011

100000

b>26> →

011011

000000

100

011100

011110

b>27> →

011100

011010

000

011101

*

b>28> → b>29>

011101

011011

010

100010

100110

b>29> →

011110

011100

000

011111

*

b>30> → b>31>

011111

011101

010

100010

100110

b>31> →

100000

011110

000

100001

*

b>32> → b>33>

100001

011111

010

100010

100110

b>33> →

100010

000000

001

100011

100101

b>34> →

100011

100000

000

100100

*

b>35> → b>36>

100100

100001

000

000000

*

b>36> → кінець

100101

100010

000

000000

*

b>3>>7> → кінець

100110

100011

000

100111

*

b>3>>8> → b>3>>9>

100111

100001

000

000000

*

b>3>>9> → кінець

Табл. 3.3 – Таблиця кодів станів автомата з примусовою адресацією команд

№ п/п

Стан

Код

1

b>0>

000000

2

b>1>

000001

3

b>2>

000010

4

b>3>

000011

5

b>4>

000100

6

b>5>

000101

7

b>6>

000110

8

b>7>

000111

9

b>8>

001000

10

b>9>

001001

11

b>10>

001010

12

b>11>

001011

13

b>12>

001100

14

b>13>

001101

15

b>14>

001110

16

b>15>

001111

17

b>16>

010000

18

b>17>

010001

19

b>18>

010010

20

b>19>

010011

21

b>20>

010100

22

b>21>

010101

23

b>22>

010110

24

b>23>

010111

25

b>24>

011000

26

b>25>

011001

27

b>26>

011010

28

b>27>

011011

29

b>28>

011100

30

b>29>

011101

31

b>30>

011110

32

b>31>

011111

33

b>32>

100000

34

b>33>

100001

35

b>34>

100010

36

b>35>

100011

37

b>36>

100100

38

b>37>

100101

39

b>38>

100110

40

b>39>

100111

Табл. 3.4 – Таблиця вхідних сигналів автомата з примусовою адресацією команд

№ п/п

Вхідний стан

Код

1

Х>0>

000

2

Х>1>

001

3

Х>2>

010

4

Х>3>

011

5

X>4>

100

Рівняння вихідних сигналів та їх
синтез у заданий базис:


      Синтез автомата з природною адресацією команд

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

0 Y


    операторна

1 Nx b


    умовна


А

ROM

D




С


РГМК


СТ



Х



+1


Рис. 3.4 – Структурна схема автомата з природною адресацією

Аналіз схеми:

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

При цьому схема аналізу Х формує Z, що змушує адресу, що зберігається в лічильнику збільшитися на одиницю.

Якщо в регістрі МК умовна МК, то вихідний сигнал не формується, а схема аналізу Х формує Z, у залежності від значення Z:

якщо Z=1, то до значення лічильника команд додається 1,

якщо Z=0, то в лічильник попадає адреса мікрокоманди з поля b.

Порядок формування змісту ROM такий же як в автоматі з примусовою адресацією мікрокоманд.

Рис. 3.5 – Граф-схема автомата з природною адресацією команд

Табл. 3.5 – Структура переходів для автомата з природною адресацією команд

№ п/п

Адреса b

b>1> b>2> b>3> b>4> b>5> b>6>

0

1 . . . 6

Перехід

1

1 ... 3

4 . . . 9

1

000000

0

000001

b>0> → b>1>

2

000001

0

000010

b>1> → b>2>

3

000010

0

000011

b>2> → b>3>

4

000011

1

011

010010

b>2> →

5

000100

0

001011

b>4> → b>5>

6

000101

0

001100

b>5> → b>6>

7

000110

0

001101

b>6> → b>7>

8

000111

0

001110

b>7> → b>14>

9

001000

1

011

011100

b>8> →

10

001001

0

010111

b>9> → b>10>

11

001010

0

011000

b>10> → b>11>

12

001011

0

011001

b>11> → b>12>

13

001100

1

011

100111

b>12> →

14

001101

0

011110

b>13> → b>14>

15

001110

0

011111

b>14> → b>15>

16

001111

1

010

101110

b>15> →

17

010000

0

100011

b>16> → b>17>

18

010001

0

100001

b>17> → кінець

19

010010

1

100

010111

b>18> →

20

010011

0

001000

b>19> → b>20>

21

010100

0

001001

b>20> → b>21>

22

010101

0

001010

b>21> → b>22>

23

010110

1

000

000111

b>22> → БП b>7>

24

010111

0

000100

b>23> → b>24>

25

011000

0

000101

b>24> → b>25>

26

011001

0

000110

b>25> → b>26>

27

011010

0

000111

b>26> → b>27>

28

011011

1

000

000111

b>27> → БП b>7>

29

011100

1

100

100001

b>28> →

30

011101

0

010100

b>29> → b>30>

31

011110

0

010101

b>30> → b>31>

32

011111

0

010110

b>31> → b>32>

33

100000

1

000

001011

b>32> → БП b>11>

34

100001

0

001111

b>33> → b>34>

35

100010

0

010000

b>34> → b>35>

36

100011

0

010001

b>35> → b>36>

37

100100

0

010010

b>36> → b>37>

38

100101

0

010011

b>37> → b>38>

39

100110

1

000

001011

b>38> → БП b>11>

40

100111

1

100

101011

b>39> →

41

101000

0

011100

b>40> → b>41>

42

101001

0

011101

b>41> → b>42>

43

101010

1

000

001111

b>42> → БП b>15>

44

101011

0

011010

b>43> → b>44>

45

101100

0

011011

b>44> → b>45>

46

101101

1

000

001111

b>45> → БП b>15>

47

101110

1

001

110000

b>46> →

48

101111

0

100010

b>47> → кінець

49

110000

0

100000

b>48> → b>49>

50

100001

0

100001

b>49> → кінець

Табл. 3.6 – Таблиця кодів станів автомата з природною адресацією команд

№ п/п

Стан

Код

1

b>0>

000000

2

b>1>

000001

3

b>2>

000010

4

b>3>

000011

5

b>4>

000100

6

b>5>

000101

7

b>6>

000110

8

b>7>

000111

9

b>8>

001000

10

b>9>

001001

11

b>10>

001010

12

b>11>

001011

13

b>12>

001100

14

b>13>

001101

15

b>14>

001110

16

b>15>

001111

17

b>16>

010000

18

b>17>

010001

19

b>18>

010010

20

b>19>

010011

21

b>20>

010100

22

b>21>

010101

23

b>22>

010110

24

b>23>

010111

25

b>24>

011000

26

b>25>

011001

27

b>26>

011010

28

b>27>

011011

29

b>28>

011100

30

b>29>

011101

31

b>30>

011110

32

b>31>

011111

33

b>32>

100000

34

b>33>

100001

35

b>34>

100010

36

b>35>

100011

37

b>36>

100100

38

b>37>

100101

39

b>38>

100110

40

b>39>

100111

41

b>40>

101000

42

b>41>

101001

43

b>42>

101010

44

b>43>

101011

45

b>44>

101100

46

b>45>

101101

47

b>46>

101110

48

b>47>

101111

49

b>48>

110000

50

b>49>

110001

Табл. 3.7 – Таблиця вхідних сигналів автомата з природною адресацією команд

№ п/п

Вхідний стан

Код

1

Х>0>

000

2

Х>1>

001

3

Х>2>

010

4

Х>3>

011

5

X>4>

100

Рівняння вихідних сигналів та їх синтез у заданий базис:


Синтез мультиплексора

Табл. 3.8 – Карта Карно до мультиплексора

00

01

11

10

0

1

x>0>

x>1>

x>3>

x>2>

x>4>

*

*

*

4. ПОРІВНЯЛЬНА ХАРАКТЕРИСТИКА АВТОМАТІВ

4.1 Порівняльна характеристика автоматів з жорсткою логікою

Розрахуємо усі дані по формулам:

N - кількість великих елементів.

N>вх> – кількість входів на великі елементи.

n – кількість малих елементів.

n>вх> - кількість входів на малі елементи.

N>тр> – кількість тригерів у схемі

Для Мілі:

N = N вх =

n = n вх =

R схеми =N тр =

=

N вх= n вх=

Для Мура:

N = N вх =

n = n вх =

R схеми =N тр =

=

N вх= n вх=


Табл. 4.1 – Таблиця обліку апаратурних витрат автоматів з жорсткою логікою

R схеми

Тригер

DC

Мура

Мілі

З таблиці 4.1 видно, що R схеми у Мура менше, але входів на DC більше.

Тригерів однакова кількість.

4.2 Порівняльна характеристика автоматів з програмованою логікою

Для примусової адресації:

Nслів= Nбіт=

t= Q=

Nкорпусів=

Rg=N= DC=

Для природньої адресації:

Nслів= Nбіт=

t= Q=

Nкорпусів=

Rg=N= DC=


Табл.4.2 Таблиця обліку апаратурних витрат автоматів з програмованою логікою

ПЗУ

Регістр лічильник

Комбінаційна частина

DC

Примусова

Природна

У автомата з природною адресацією МК більш мінімальні апаратні витрати (корпусів), ніж у автомата з примусовою адресацією.

Тригерів однакова кількість. Кількість входів на DC однакова.

Комбінаційна частина у АПЛ з природною адресацією більша,
ніж у примусової.

ВИСНОВОК

операційний керуючий автомат програмований логіка

Виконано курсовий проект з дисципліни „Прикладна теорія цифрових автоматів” на тему „Синтез керуючих автоматів”.

Були синтезовані основні типи автоматів з жорсткою та програмованою логікою. Хоча всі приведені автомати справилися з поставленою задачею і в достатній мірі реалізували схему керуючого автомата, але є деякі позитивні і негативні особливості синтезу кожного з автоматів. Наприклад, автомати з жорсткою логікою мають досить велику комбінаційну частину, але вони не потребують елементів ROM, це робить ці автомати дуже оптимальними за ціною затрат.

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