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

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

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

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

По описах граф-схем, приведених в завданні до курсової роботи,

побудуємо ГСА Г1-Г5 (мал. 1.1-1.5), додавши початкові і кінцеві вершини і

замінивши кожний оператор Yi операторною вершиною, а кожну умову Xi -

умовною.

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

У ГСА Г1-Г5 є однакові ділянки, тому побудова автоматів за ГСА Г1-Г5

приведе до невиправданих апаратурних витрат. Для досягнення оптимального

результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати

число операторних і умовних вершин. Заздалегідь помітимо операторн( вершини

в початкових ГСА, керуючись сл(дуючими правилами:

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

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

мітками Aj;

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

Ak.

На наступному етапі кожн(й ГСА поставимо у

відповідність набір змінних Pn( {P1...Pq}, де q=]log2N[, N -к(льк(сть

ГСА. Означувальною для ГСА Гn ми будемо називати кон`юнкцию

Pn=p1e(...(pqn е({0,1}, причому p0=(р, p1=р. Об'єднана ГСА повинна

задовольняти сл(дуючим вимогам:

1) якщо МК Ai входить хоча б в одну часткову ГСА, то вона входить і в

об'єднану ГСА Г0, причому тільки один раз;

2) при підстановці набору значень (е1...en), на якому Pq=1 ГСА Г0

перетворюється в ГСА, рівносильну частков(й ГСА Гq.

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

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

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

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

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

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

Часткові МСА М1-М5 побудуємо по ГСА Г1-Г5 (мал.1.1) відповідно. Рядки

МСА відмітимо всіма мітками Ai, що входять до ГСА, крім кінцевої Ak.

ПОЧАТОК A0

1

0 X1 1

2

A1

3

0

4 X2

A2 1

5

A3

6

A4

7

A5

8

A6

9

A7

10

A8

К(НЕЦь Ak

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

ПОЧАТОК A0

1

A1

2

A7

0 3 1

X3

4 5

A9 A6

6 7

A10 A12

8 9

A3 A22

10

A11

К(НЕЦЬ Ak

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

ПОЧАТОК A0

1

A11

0 2 1

X1

3 4

A15 A16

6

5 1

X3 A12

0

7 8

A6 A13

К(НЕЦЬ Аk

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

ПОЧАТОК A0

1

0 1

X1

2

A13

3

A9

4

A8

5

1 X2

6 0

A17

7

A6

8

A2

9

A18

К(НЕЦЬ Ak

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

ПОЧАТОК A0

1

A1

2

A6

3

A19

4

0 1

X1

5

0 X2

1

6

A20

7

A17

8

A2

9

A21

К(НЕЦЬ Ak

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

Стовпці МСА відмітимо всіма мітками Ai, що входять до ГСА, крім

початкової A0. На перетині рядка Ai і стовпця Aj запишемо формулу переходу

fij від оператора Ai до оператора Aj. Ця функція дор(вню( 1 для безумовного

переходу або кон`юнкц(( логічних умов, відповідних виходам умовних вершин,

через які проходить шлях з вершини з м(ткою Ai у вершину з м(ткою Aj.

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

Таблиця 1.1

Кодування

МСА

|МСА |P1P2P3 |

|М1 |0 0 0 |

| |((p1(p2(p3) |

|М2 |0 0 1 |

| |((p1(p2p3) |

|М3 |0 1 0 |

| |((p1p2(p3) |

|М4 |0 1 1 |

| |((p1p2p3) |

|М5 |1 0 0 |

| |(p1(p2(p3) |

Частков( МСА М1-М5 наведен( в табл.1.2-1.6

Таблиця 1.2

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

| | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | Ak |

| A0 | (x1 |(x1(x2| x1x2 | | | | | | |

| A1 | | 1 | | | | | | | |

| A2 | | | | | | 1 | | | |

| A3 | | | | 1 | | | | | |

| A4 | | | | | 1 | | | | |

| A5 | | | | | | 1 | | | |

| A6 | | | | | | | 1 | | |

| A7 | | | | | | | | 1 | |

| A8 | | | | | | | | | 1 |

Таблиця 1.3

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

| | A1 | A3 | A6 | A7 | A9 | A10 | A11 | A12 | A22 | Ak |

| A0 | 1 | | | | | | | | | |

| A1 | | | | 1 | | | | | | |

| A3 | | | | | | | 1 | | | |

| A6 | | | | | | | | 1 | | |

| A7 | | | x3 | | (x3 | | | | | |

| A9 | | | | | | 1 | | | | |

| A10 | | 1 | | | | | | | | |

| A11 | | | | | | | | | | 1 |

| A12 | | | | | | | | | 1 | |

| A22 | | | | | | | | | | 1 |

Таблиця 1.4

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

| | A6 | A12 | A13 | A14 | A15 | A16 | Ak |

| A0 | | | | 1 | | | |

| A6 | | | | | | | 1 |

| A12 | | | 1 | | | | |

| A13 | | | | | | | 1 |

| A14 | | | | | (x1 | x1 | |

| A15 | x3 | | | | | | (x3 |

| A16 | | 1 | | | | | |

Таблиця 1.5

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

| | A2 | A6 | A8 | A9 | A13 | A17 | A18 | Ak |

| A0 | | | (x1 | | x1 | | | |

| A2 | | | | | | | 1 | |

| A6 | 1 | | | | | | | |

| A8 | | | | | | x2 | | (x2 |

| A9 | | | 1 | | | | | |

| A13 | | | | 1 | | | | |

| A17 | | 1 | | | | | | |

| A18 | | | | | | | | 1 |

Таблиця 1.6

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

| | A1 | A2 | A6 | A17 | A19 | A20 | A21 | Ak |

| A0 | 1 | | | | | | | |

| A1 | | | 1 | | | | | |

| A2 | | | | | | | 1 | |

| A6 | | | | | 1 | | | |

| A17 | | 1 | | | | | | |

| A19 | | x1(x2| | | | x1x2 | (x1 | |

| A20 | | | | 1 | | | | |

| A21 | | | | | | | | 1 |

На наступному етапі побудуємо об'єднану МСА М0, в як(й рядки

відмічені всіма мітками Аi, крім Аk, а стовпці - всіма, крім А0. На

перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка

формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn-

формула переходу з вершини Аi у вершину Аj для n-о( ГСА. Наприклад,

формула переходу А0(А1 буде мати вигляд F0,1=(x1(p1(p2(p3+ (p1(p2p3+

+p1(p2(p3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми

маємо можливість мінімізувати формули переходу таким чином: розглядаючи

ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому

зм(нн( p1..pq не змінюють своїх значень під час проходу по ГСА. Таким

чином, якщо у вершину Аi перехід завжди здійснюється при незмінному

значенні pq, то це значення pq в рядку Аi замінимо на “1", а його

інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при

незмінному значенні (p1 і (p2, отже в рядку А3 (p1 і (p2 замінимо на

“1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=(p3,

F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА

М0 (табл.1.8).

По таблиці складемо формули переходу для об'єднаної ГСА Г0.

Формулою переходу будемо називати сл(дуюче вираження:

Ai(Fi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з

мінімізованої МСА. У нашому випадку отримаємо сл(дуючу систему формул:

A0((x1(p1(p2(p3A1+(p1(p2p3A1+p1(p2(p3A1+x1(x2(p1(p2(p3A2+x1x2(p1(p2(p3A3

+

+(x1(p1p2p3A8+x1(p1p2p3A13+(p1p2(p3A14

A1((p1(p3A2+p1(p3A6+(p1p3A7

A2((p1(p2(p3A6+(p1p2p3A18+p1(p2p3A21

A3((p3A4+p3A11

A4(A5

A5(А6

Таблиця

1.7

Об`(днана МСА Мo

| | | | | | | | | | | | | | | | | | | | | | | | |

| |A1 |A2 |A3 |A4 |A5 |A6 |A7 |A8 |A9 |A10 |A11 |A12 |A13 |A14 |A15 |A16 |A17 |A18 |A19 |A20 |A21 |A22 |Ak |

| |_ _ _ | _ _ | _ | | | | |_ _ | | | | | _ |_ | | | | | | | | | |

| |_ |_ _ |_ _ | | | | |x1p1p| | | | |x1p1p2|_ | | | | | | | | | |

|A0 |x1p1p2|x1x2p1|x1x2p1| | | | |2p3 | | | | |p3 |p1p2| | | | | | | | | |

| |p3+ |p2p3 |p2p3 | | | | | | | | | | |p3 | | | | | | | | | |

| |_ _ | | | | | | | | | | | | | | | | | | | | | | |

| |+p1p2p| | | | | | | | | | | | | | | | | | | | | | |

| |3+ | | | | | | | | | | | | | | | | | | | | | | |

| |_ _ | | | | | | | | | | | | | | | | | | | | | | |

| |+p1p2p| | | | | | | | | | | | | | | | | | | | | | |

| |3 | | | | | | | | | | | | | | | | | | | | | | |

| | |_ _ _ | | | | _ _|_ _ | | | | | | | | | | | | | | | | |

|A1 | |p1p2p3| | | | | | | | | | | | | | | | | | | | | |

| | | | | | |p1p2p|p1p2| | | | | | | | | | | | | | | | |

| | | | | | |3 |p3 | | | | | | | | | | | | | | | | |

| | | | | | |_ _ _| | | | | | | | | | | |_ | | | _ _| | |

|A2 | | | | | | | | | | | | | | | | | |p1p2p| | | | | |

| | | | | | |p1p2p| | | | | | | | | | | |3 | | |p1p2p| | |

| | | | | | |3 | | | | | | | | | | | | | | |3 | | |

| | | | |_ _ | | | | | | |_ _ | | | | | | | | | | | | |

|A3 | | | |_ | | | | | | |p1p2p| | | | | | | | | | | | |

| | | | |p1p2| | | | | | |3 | | | | | | | | | | | | |

| | | | |p3 | | | | | | | | | | | | | | | | | | | |

| | | | | |_ _ | | | | | | | | | | | | | | | | | | |

|A4 | | | | |_ | | | | | | | | | | | | | | | | | | |

| | | | | |p1p2| | | | | | | | | | | | | | | | | | |

| | | | | |p3 | | | | | | | | | | | | | | | | | | |

| | | | | | |_ _ _| | | | | | | | | | | | | | | | | |

|A5 | | | | | | | | | | | | | | | | | | | | | | | |

| | | | | | |p1p2p| | | | | | | | | | | | | | | | | |

| | | | | | |3 | | | | | | | | | | | | | | | | | |

| | |_ | | | | |_ _ | | | | |_ _ | | | | | | | _ _ | | | |_ _ |

|A6 | |p1p2p3| | | | |_ | | | | |p1p2p| | | | | | |p1p2p3| | | |p1p2p3|

| | | | | | | |p1p2| | | | |3 | | | | | | | | | | | |

| | | | | | | |p3 | | | | | | | | | | | | | | | | |

| | | | | | | _ _| |_ _ _|_ _ _ | | | | | | | | | | | | | | |

|A7 | | | | | | | | |x3p1p2| | | | | | | | | | | | | | |

| | | | | | |x3p1p| |p1p2p|p3 | | | | | | | | | | | | | | |

| | | | | | |2p3 | |3 | | | | | | | | | | | | | | | |

| | | | | | | | | | | | | | | | | | _ | | | | | |_ _ _ |

|A8 | | | | | | | | | | | | | | | | |x2p1p2| | | | | |p1p2p3|

| | | | | | | | | | | | | | | | | |p3 | | | | | |+ |

| | | | | | | | | | | | | | | | | | | | | | | |_ _ |

Страницы: 1, 2