167 3

328

pracę układu, znaleźć można m. łn. w (4).

Tablice przejść i wyjść opisujące układy asynchroniczne są zawsze tablicami typu Moore’a.

9.3.Minimalizacja liczby stanów wewnętrznych [4]

Kolejnym etapem syntezy układów asynchronicznych jest minimalizacja liczby stanów wewnętrznych. Można to zrobić metodami dla układów synchronicznych, ale pewne cechy pierwotnych tablic przejść i wyjść powodują, że procedurę można znacznie uprościć. Te cechy to:

a)    tablice pierwotne są zawsze tablicami układu Moore'a,

b)    w każdym wierszu występuje tylko jeden stan stabilny,

c)    dany stan niestabilny może wystąpić tylko w tej kolumnie, w której występuje odpowiadający mu stan stabilny (czyli tylko w jednej kolumnie).

2 ostatniej cechy wynika, że warunkami dla zgodności warunkowej mogą być tylko pary stanów stabilnych w tej samej kolumnie. Dlatego dla celów minimalizacji automatów asynchronicznych wprowadza się pojęcie tzw. pseudorównoważności stanów.

Definicja 9. 1

Stany wewnętrzne A. i A. są pseucorćv;noważne (co oznaczymy jako P    ^J

A i = A. ) jeśli są zgodne ( A. = A_; ) oraz mają stany stabilne w jecnej kolumnie. Czyli

Aj) i V X,

-* a(Aj. x_k)

;]}■

(9.7)

Przypomnijmy, że stany A., A. są zgodne ( A. * A. ) jeśli dla

.    . ,    * o    ^x    J

Każdego stanu wejść sygnały wyjściowe odpowiadające A. i A. są .    *    J

mesprzeczne, a stany następne dla A. i Aj są niesprzeczne lub zgodne

(rozdz. 5.4.1, definicja 5.1, twierdzenie 5.1).

Pierwszym etapem minimalizacji będzie zatem znalezienie i

połączenie stanów pseudorównoważnych. ".'ależy tu oczywiście uwzględnić

możliwość pseudorównoważności warunkowej. Można to zrobić przy pomocy

tablicy trójkątnej, ale ze względów na małą zwykle ilość stanów pseudorównoważnych nie warto.

Przykład 9.2

Rozpatrzmy automat opisany tablicą przejść i wyjść z rys. 9.3a. Szukamy par stanów pseudorównoważnych; zgodnie z definicją •• spośród tych stanów, które są stabilne w tej samej kolumnie.

Stany 1 i 6 nie są pseudorównoważne ze względu na sprzeczność wyjść. Stany 4, 5 będą pseudorównoważne pod warunkiem pseudorównoważności stanów 7 i 9. Stan 10 nie jest pseudorównoważny ze stanami 4 ani 5 ze względu na sprzeczne wyjścia. Stany 7 i 9 są pseudorównoważne pod warunkiem 4 i 5 oraz 3 i 8. Stany 3 i 8 są pseudorównoważne. Zatem wszystkie warunki są spełnione, więc otrzymano zbiór maksymalnych grup stanów pseudorównoważnych

(9.8)

Po zastąpieniu każdej pary jednym stanem otrzymuje się tablicę z rys. 9. 3b.

Na etapie łączenia stanów pseudorównoważnych łączy się ze sobą także wszystkie stany zgodne warunkowo (o ile takie istnieją). Wobec tego po połączeniu stanów pseudorównoważnych w tablicy automatu

asynchronicznego nie może wystąpić zgodność warunkowa. W związku z tym dwa stany można uznać za zgodne jeśli tylko odpowiednie stany następne są takie same lub qo najmniej jeden-z nich jest nieokreślony.

Przy szukaniu maksymalnych grup stanów zgodnych pomocny jest graf zgodności (por. rozdz. 5.4). Na grafie tym wierzchołki odpowiadające stanom wewnętrznym łączymy ze sobą linią ciągłą, jeżeli odpowiednie dwa stany są zgodne i mają wyjścia niesprzeczne, lub linią przerywaną, jeżeli stany te są zgodne i mają wyjścia sprzeczne. Łącząc stany, które mają wyjścia niesprzeczne (połączone linią ciągłą na grafie) otrzymamy automat Moore’a, natomiast łącząc stany o sprzecznych sygnałąch wyjściowych (linia przerywana) - automat Mealy'ego.

Przykład 9.2 cd.

Na rys. 9.3c przedstawiono graf zgodności dla tablicy z rys. 9.3b.