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

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

Стовпці МСА відмітимо всіма мітками A, що входять до ГСА, крім початкової 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)


Часткові МСА М15 наведені в табл.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щp1p2pA8+x1щp1p2p3A13+щp1p2щp3A14


A1®щp1щp3A+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


A0

_ _ _ _

x1p1p2p3+

_ _

+p1p2p3+

_ _

+p1p2p3


_ _ _ _

x1x2p1p2p3

_ _ _

x1x2p1p2p3





_ _

x1p1p2p3





_

x1p1p2p3

_ _

p1p2p3











A1


_ _ _

p1p2p3




_ _

p1p2p3

_ _

p1p2p3


















A2






_ _ _

p1p2p3












_

p1p2p3



_ _

p1p2p3




A3




_ _ _

p1p2p3







_ _

p1p2p3














A4





_ _ _

p1p2p3




















A5






_ _ _

p1p2p3



















A6


_

p1p2p3





_ _ _

p1p2p3





_ _

p1p2p3







_ _

p1p2p3




_ _

p1p2p3


A7






_ _

x3p1p2p3


_ _ _

p1p2p3

_ _ _

x3p1p2p3
















A8

















_

x2p1p2p3






_ _ _

p1p2p3+

_ _

+x2p1p2p3


A9








_

p1p2p3


_ _

p1p2p3















A10



_ _

p1p2p3






















A11























_ _

p1p2p3


A12













_ _

p1p2p3









_ _

p1p2p3



A13









_

p1p2p3














_ _

p1p2p3


A14















_ _ _

x1p1p2p3

_ _

x1p1p2p3









A15






_ _

x3p1p2p3

















_ _ _

x3p1p2p3


A16












_ _

p1p2p3













A17


_ _

p1p2p3




_

p1p2p3



















A18























_

p1p2p3


A19


_ _ _

x1x2p1p2p3


















_ _

x1x2p1p2p3

_ _ _

x1p1p2p3




A20

















_ _

p1p2p3








A21























_ _

p1p2p3


A22























_ _

p1p2p3


Таблиця 1.8

Об`єднана мінімізована МСА Мo




A1



A2


A3


A4


A5


A6


A7


A8


A9


A10


A11


A12


A13


A14


A15


A16


A17


A18


A19


A20


A21


A22


Ak


A0

_ _ _ _

x1p1p2p3+

_ _

+p1p2p3+

_ _

+p1p2p3


_ _ _ _

x1x2p1p2p3

_ _ _

x1x2p1p2p3





_ _

x1p1p2p3





_

x1p1p2p3

_ _

p1p2p3











A1


_ _

p1p3




_

p1p3

_

p1p3


















A2






_ _ _

p1p2p3












_

p1p2p3



_ _

p1p2p3




A3




_

p3








p3














A4






1




















A5







1



















A6


_

p1p2p3





_ _ _

p1p2p3





_ _

p1p2p3







_ _

p1p2p3




_ _

p1p2p3


A7







x3p3


_

p3

_

x3p3
















A8


















x2p2p3






_ _

p2p3+

_

+x2p2p3


A9









p2


_

p2















A10




1






















A11
























1


A12













_

p2p3









_

p2p3



A13










p3














_

p3


A14















_

x1


x1









A15







x3

















_

x3


A16













1













A17


_ _

p1p2p3




_

p1p2p3



















A18
























1


A19


_

x1x2



















x1x2

_

x1




A20


















1








A21
























1


A22
























1



A6®щp1p2p3A2+щp1щp2щp3A7+щp1щ

Подобные работы:

Актуально: