Синтез автомата Мура

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

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

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

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

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

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

1.3 Розрахунки.

За варіантом завдання (А=9, В=2)знаходимо gi й zi:

i | gi | zi

0 | 9 | 2

1 | 3 | 10

2 | 12 | 4

3 | 7 | 13

4 | 1 | 8

5 | 13 | 2

6 | 8 | 14

7 | 5 | 9

8 | 1 | 6

9 | 15 | 2

10 | 12 | 0

11 | 11 | 13

12 | 9 | 12

Неповторювані значення gi: 9,3,12,7,1,13,8,5,15. Неповторювані значення zi: 2,10,4,13,8,14,9,6,0. Таким чином, для F1 одержуємо вираження:

Для мінімізації першої функції застосовуємо метод карт Карно.

Карта Карно – прямокутник з 2n клітками, кожна з яких відповідає своя кон’юнкція з n змінних й їхніх заперечень (доповнень).

Проставляючи одиниці у відповідних клітках, вибираємо потім мінімальну із всіх можливих комбінацію покриттів. Застосуємо карту Карно до заданої функції:

Малюнок 1.2.1 - карта Карно

На підставі обраної комбінації покриттів виписуємо мінімізований вираз для функції F1:

(1.3. 3)

На першому кроці алгоритму виписуємо комплекс K0-кубів заданої функції, упорядкованих по зростанню кількості одиниць:

m | К0-куби

0 | 0 | 0000 *

1 | 2 | 0010 *

4 | 0100 *

8 | 1000 *

2 | 10 | 1010 *

9 | 1001 *

6 | 0110 *

3 | 13 | 1101 *

14 | 1110 *

Таблиця 1.3.2 – К0-куби

Другий етап заснований на операції склеювання. Кожний з кубів перевіряється на “склеюваність” з усіма іншими. куби, що Склеюються, повинні відрізнятися не більш ніж на один розряд. Склеєний розряд надалі позначається як x. Куб, що брав участь в операції склеювання, відповідним чином позначається. Оскільки таких кубів мало, будемо відзначати не куби, що брали участь в операції склеювання. У результаті одержуємо комплекс

K1-кубів, також упорядкований по зростанню кількості одиниць у розрядах:

m | К1-куби

0 | 00X0 *

0X00 *

X000 *

1 | X010 *

0X10 *

01X0 *

10X0 *

100X *

2 | 1X10 *

1X01 *

X110 *

Таблиця 1.3.3 – К1-куби

Повторюємо вищеописану операцію для К1-кубів,після чого видаляємо з отриманого комплеку К2-кубів повторювані:

m | К2-куби

0 | 0XX0

X0X0

0XX0

X0X0

1 | XX10

XX10

Таблиця 1.3.4 - К2 кубів

Побудуємо таблицю покриття К0-кубів: |

0

0

0

1 | 0

0

1

1 | 0

1

0

0 | 0

1

1

1 | 1

0

0

1 | 1

1

0

1 | 0

0

0

0 | 0

1

0

1 | 1

1

1

1 | Імліканти

0XX0 | + | + | + | +

X0X0 | + | + | + | +

XX10 | + | + | + | +

Таблиця 1.3.5 – покриття К0-кубів

З таблиці видно, що всі імпліканти є екстремалями. Отже, вони всі увійдуть у запис функції у вигляді скороченої ДНФ:

Приведемо F1 до базису І-НЕ, а F2 – до базису АБО-НЕ:

Рисунок 2.1.6 – Схема на І-НЕ-елементах

Рисунок 2.1.7 – Схема на АБО-НЕ-елементах

Реалізуємо у вигляді комбінаційної схеми на логічних елементах у базисі І, АБО, НЕ для не парного варіанту функцію F2:

Обрахунок складності отриманих схем за Квайном.

Складність схеми на І-НЕ-елементах: N= 13;

Складність схеми на АБО-НЕ-елементах: N= 13;

Складність схеми на І, АБО, НЕ-елементах: N= 13;

Висновок до розділу:

Під час виконання поставленої задачі я навчився мінімізувати СДНФ методами карт Карно і Квайна-МакКласки, будувати комбінаційні схеми в заданому елементному базисі, а також визначати їх складність.

2.2 Завдання 2.

Будуємо таблиці переходів, виходів і загальну таблицю переходів автомата на основі заданих функцій:

(2.2.1)

(2.2.2)

(2.2.3)

S(j) X(j) | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8

X0 | S2 | S4 | S6 | S8 | S1 | S3 | S5 | S7 | S0

X1 | S3 | S5 | S7 | S0 | S2 | S4 | S6 | S8 | S1

X2 | S4 | S6 | S8 | S1 | S3 | S5 | S7 | S0 | S2

X3 | S5 | S7 | S0 | S2 | S4 | S6 | S8 | S1 | S3

Рисунок 2.2.1 – Таблиця переходів

S(j) X(j) | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8

X0 | W0 | W1 | W2 | W0 | W1 | W2 | W0 | W1 | W2

X1 | W1 | W2 | W0 | W1 | W2 | W0 | W1 | W2 | W0

X2 | W2 | W0 | W1 | W2 | W0 | W1 | W2 | W0 | W1

X3 | W0 | W1 | W2 | W0 | W1 | W2 | W0 | W1 | W2

Рисунок 2.2.2 – Таблиця виходів

S(j) X(j) | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8

X0 | S2

W0 | S4

W1 | S6

W2 | S8

W0 | S1

W1 | S3

W2 | S5

W0 | S7

W1 | S0

W2

X1 | S3

W1 | S5

W2 | S7

W0 | S0

W1 | S2

W2