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

1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА

1.1. Побудова ГСА

По описах граф-схем, приведених в завданні до курсової роботи, побудуємо ГСА Г₁-Г₅ (мал. 1.1-1.5), додавши початкові і кінцеві вершини і замінивши кожний оператор Yi операторною вершиною, а кожну умову X_i - умовною.

1.2. Методика об'єднання ГСА

У ГСА Г₁-Г₅ є однакові ділянки, тому побудова автоматів за ГСА Г₁-Г₅ приведе до невиправданих апаратурних витрат. Для досягнення оптимального результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати число операторних і умовних вершин. Заздалегідь помітимо операторні вершини в початкових ГСА, керуючись слідуючими правилами:

1) однакові вершини Y_i в різних ГСА відмічаємо однаковими мітками A_j;

2) однакові вершини Y_i в межах однієї ГСА відмічаємо різними мітками A_j;

3) у всіх ГСА початкову вершину помітимо як А₀, а кінцеву - як A_k.

На наступному етапі кожній ГСА поставимо у відповідність набір змінних P_nО {P₁...P_q}, де q=]log₂N[, N -кількість ГСА. Означувальною для ГСА Г_n ми будемо називати кон`юнкцию P_n=p₁eЩ...Щp_qn еО{0,1}, причому p0=щр, p1=р. Об'єднана ГСА повинна задовольняти слідуючим вимогам:

1) якщо МК A_i входить хоча б в одну часткову ГСА, то вона входить і в об'єднану ГСА Г₀, причому тільки один раз;

2) при підстановці набору значень (е₁...e_n), на якому P_q=1 ГСА Г₀ перетворюється в ГСА, рівносильну частковій ГСА Г_q.

При об'єднанні ГСА виконаємо слідуючі етапи:

-сформуємо часткові МСА М₁ - М₅, що відповідні ГСА Г₁ - Г₅;

- сформуємо об'єднану МСА М₀;

- сформуємо системи дужкових формул переходу ГСА Г₀;

- сформуємо об'єднану ГСА Г₀.

1.3. Об'єднання часткових ГСА

Часткові МСА М₁-М₅ побудуємо по ГСА Г₁-Г₅ (мал.1.1) відповідно. Рядки МСА відмітимо всіма мітками A_i, що входять до ГСА, крім кінцевої A_k.

ПОЧАТОК A₀

1

0 X₁ 1

2

A₁

3

0

4 X₂ A₂ 1

5

A₃

6

A₄

7

A₅

8

A₆

9

A₇

10

A₈

КіНЕЦь A_k

Мал.1.1. Часткова граф-схема алгоритму Г₁

ПОЧАТОК A₀

1

A₁

2

A₇

0 3 1

X₃

4 5

A₉ A₆

6 7

A₁₀ A₁₂

8 9

A₃ A₂₂

10

A₁₁

КіНЕЦЬ A_k

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

ПОЧАТОК A₀

1

A₁₁

0 2 1

X₁

3 4

A₁₅ A₁₆

6

5 1

X₃ A₁₂

0

7 8

A₆ A₁₃

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать