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

Посмотреть архив целиком

15



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ùp2p3A12­+p1ùp2ùp3A19+ùp1p2ùp3Ak


A7®x3p3A6+ùp3A8+ùx3p3A9


A8®x2p2p3A17+ùp2ùp3Ak+ùx2p2p3Ak


A9®pA8+ùp2A10


A10®A3


A11®Ak


A12®ùp2p3A22+p2ùp3A13


A13®p3A9+ùp3Ak


A14­®ùx1A15+x1A16


A15®x3A6+ùx3Ak


A16®A12


A17®p1ùp2ùp3A+ùp1p2p3A6


A18®Ak


A19®x1ùx2A2+x1x2A20+ùx1A21


A20­®A17


A21®Ak


A22®Ak



При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx1ùx1, де А і В -деякі вирази, а x1 і ùx1-логічн³ умови переходу. Формули переходу для вершин А3, А4, А5, А9, А10, А11, А13, А14, А15, А16, А18, А20, А21, А22 вже є елементарними (розкладеними), а в інших є вирази виду Аn®xj(А) +ùxjpi(В). Тут pi відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднан³й ГСА бути не повинно. Для їх усунення скористаємося сл³дуючим правилом: додавання виразу [PqАn] не змінить формулу, якщо набір Pq не використовується для кодування ГСА або вершина Аn в³дсутня в ГСА з кодом Pq. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A8®x2p2p3A17+ùp2ùp3Ak+ùx2p2p3A спрощується таким чином A8=p3(x2p2A17+ùx2p2Ak)+ùp3ùp2Ak=p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak=




1 Xj 0


Pi 0

1





Мал.1.6 Приклад чекаючо¿ вершини Pi



=[ùp3p2(x2A17+ùx2Ak)]+p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak+[p3ùp2Ak]=ùp2Ak+p2(x2A17+ùx2Ak). Тут вершина А8 не зустр³чаºться у ГСА ,в кодах яких присутн³ комб³нац³¿ ùp3p2 ³ p3ùp2. Нижче наведено розклад ус³х неелементарних формул переходу.


A0=p1(ùp2ùp3A1)+ùp1(ùx1ùp2ùp3A1+ùp2p3A1+x1ùx2ùp2ùpA2+x1x2ùp2ùp3A+

+ùx1p2p3A8+x1p2p3A13+p2ùp3A14)=p1(ùp2ùp3A1)+[p1ùp2ùp3A1]+

+ùp1(p2(ùx1p3A8+x1p3A13+ùp3A14)+ùp2(ùx1ùp3A1+p3A1+x1ùx2ùp3A2+

+x1x2ùp3A))=p1(ùp2A1)+[p1p2A1]+ùp1(p2(p3(ùx1A8+x1A13)+ùp3A14)+

+ùp2(ùp3(ùx1A1+x1x2A3+x1ùx2A2­)+p3A1))= p1A1+ùp1(p2(p3( ùx1A8+

+x1A13)+ùp3A14)+ùp2(ùp3(ùx1A1+x1(x2A3+ùx2A2))+p3A))


A1=ùp(p3A7+ùp3A2)+p1ùp3A6+[p1p3A6]= ùp(p3A7+ùp3A2)+p1A6


A2=p1(ùp2p3A21)+ùp1(ùp2ùp3A6+p2p3A18)= p1(ùp2p3A21)+[p1ùp2p3A21]+

+ùp(ùp2ùp3A6+[p2ùp3A6]+p2­p3A18+[p3ùp2A18])=p1(ùp2A21)+ùp1(ùp3A6+

+p3A18)=p1(ùp2A21)+[p1p2A21]+ùp1(ùp3A6+p3A18)=p1A21+ùp1(ùp3A6+

+p3A18)


A6=p1(ùp2ùp3A19)+[p1ùp2p3A19]+ùp1(p2p3A2+ùp2ùp3A7+ùp2p3A12+p2ùp3Ak)=

=p1ùp2A19+[p1p2A19]+ùp1(p2(p3A2+ùp3Ak)+ùp2(ùp3A7+p3A12­))=p1A19+

+ùp1(p2(p3A2+ùp3Ak­)+ùp2(ùp3A7+p3A12))


A7=p3(x3A6+ùx3A9)+ùp3A8


A8=p3(x2p2A17+ùx2p2Ak)+ùp3ùp2Ak=p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak=

=[ùp3p2(x2A17+ùx2Ak)]+p3p2(x2A17+ùx2Ak)+ùp3ùp2Ak+[p3ùp2Ak]=ùp2Ak+

+p2(x2A17+ùx2Ak)


A12=ùp2p3A22+p2ùp3A13+[p2p3A22]+[ùp2ùp3A13]=p3A22+ùp3A13


A17=p1ùp2ùp3A2+[p1ùp2p3A2]+ùp1p2p3A6+[ùp1ùp2p3A]=p1ùp2A2+[p1p2A2]+

+ùp1p3A6+[ùp1ùp3A6]=p1A2+ùp1A6­


A19=x1(ùx2A2+x2A20)+ùx1A21

Об'єднану ГСА Г0 (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку Аi відповідною операторною вершиною Yt, а кожний вираз Xi і Pj відповідними умовними вершинами.











































Случайные файлы

Файл
133091.rtf
103074.rtf
80969.rtf
13623.rtf
30429.rtf