191-003A (Прикладная теория цифровых автоматов)

14

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_qⁿ еÎ{0,1}, причому p⁰=ùр, p¹=р. Об'єднана ГСА повинна задовольняти сл³дуючим вимогам:

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₁₃

К³НЕЦЬ А_k

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

ПОЧАТОК A₀

1

0 1

X₁

2

A₁₃

3

A₉

4

A₈

5

1 X₂

6 0

A₁₇

7

A₆

8

A₂

9

A₁₈

К³НЕЦЬ A_k

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

ПОЧАТОК A₀

1

A₁

2

A₆

3

A₁₉

4

0 1

X₁

5

0 X₂

1

6

A₂₀

7

A₁₇

8

A₂

9

A₂₁

К³НЕЦЬ A_k

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

Стовпці МСА відмітимо всіма мітками A_i­, що входять до ГСА, крім початкової A₀. На перетині рядка A_i і стовпця A_j запишемо формулу переходу f_ij від оператора A_i до оператора A_j. Ця функція дор³внюº 1 для безумовного переходу або кон`юнкц³¿ логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з м³ткою A_i у вершину з м³ткою Aj.

За методикою об'єднання закодуємо МСА таким чином:

Таблиця 1.1

Кодування МСА

Частков³ МСА М₁-М₅ наведен³ в табл.1.2-1.6

Таблиця 1.2

Часткова МСА М₁

Таблиця 1.3

Часткова МСА М₂

Таблиця 1.4

Часткова МСА М₃

Таблиця 1.5

Часткова МСА М₄

Таблиця 1.6

Часткова МСА М₅

На наступному етапі побудуємо об'єднану МСА М₀, в як³й рядки відмічені всіма мітками А_i, крім А_k, а стовпці - всіма, крім А₀. На перетині рядка А_i і стовпця А_j запишемо формулу переходу, яка формується таким чином: F_ij=P₁f_ij¹+...+P_nf_ijⁿ (n=1...N). Де f_ijⁿ-формула переходу з вершини А_i у вершину А_j для n-о¿ ГСА. Наприклад, формула переходу А₀®А₁ буде мати вигляд F_0,1=ùx₁ùp₁ùp₂ùp₃+ ùp₁ùp₂p₃+ +p₁ùp₂ùp₃. У результаті ми отримаємо об'єднану МСА М₀ (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г₀ як ГСА Г_n, ми підставляємо певний набір P_n=1, при цьому зм³нн³ p₁..p_q не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину А_i перехід завжди здійснюється при незмінному значенні p_q, то це значення p_q в рядку А_i замінимо на “1", а його інверсію на “0". Наприклад, у вершину А₃ перехід здійснюється при незмінному значенні ùp₁ і ùp₂, отже в рядку А₃ ùp₁ і ùp₂ замінимо на “1", а p₁ і p₂ на “0". У результаті отримаємо формули F_3,4=ùp₃, F_3,11=p₃. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М₀ (табл.1.8).

По таблиці складемо формули переходу для об'єднаної ГСА Г₀. Формулою переходу будемо називати сл³дуюче вираження: A_i®F_i,1А₁+..+F_i,kА_k, де F_i,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо сл³дуючу систему формул:

A₀®ùx₁ùp₁ùp₂ùp₃A₁+ùp₁ùp₂p₃A₁+p₁ùp₂ùp₃A₁+x₁ùx₂ùp₁ùp₂ùp₃A₂+x₁x₂ùp₁ùp₂ùp₃A₃+

+ùx₁ùp₁p₂p_3­A₈+x₁ùp₁p₂p₃A₁₃+ùp₁p₂ùp₃A₁₄