на тему рефераты Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
на тему рефераты
на тему рефераты
МЕНЮ|
на тему рефераты
поиск
Прикладная теория цифровых автоматов

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

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", а його

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



© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.