Xreferat.com » Рефераты по технологии » Прикладная теория цифровых автоматов

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

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


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


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


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


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

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. Об'єднання часткових ГСА

Часткові МСА М15 побудуємо по ГСА Г15 (мал.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

Похожие рефераты: