TC Moduł 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
TC M8 Slajd1.png

Minimalizacja liczby stanów automatu


TC M8 Slajd2.png

Jak wiadomo automat , w którym zbiór stanów wewnętrznych ma liczność może być zrealizowany na co najmniej przerzutnikach. Zatem każde zmniejszenie liczby stanów, ale takie, aby automat z punktu widzenia obserwatora zewnętrznego wykonywał taką samą pracę jest bardzo korzystne ze względu na złożoność (a tym samym koszt) jego realizacji. Proces redukowania liczby stanów automatu, ale w taki specjalny sposób, aby nie zmniejszyło to możliwości funkcjonalnych automatu nazywa się minimalizacją liczby stanów automatu. Przykład minimalizacji automatu podany jest na planszy. Automat opisany tablicą przejść wyjść z lewej strony planszy ma 6 stanów wewnętrznych, zatem wymaga do swojej realizacji 3 przerzutników. Automat ten można jednak zminimalizować (na razie nie wiadomo w jaki sposób) do postaci opisanej tablicą z prawej strony planszy. Zminimalizowany automat ma 3 stany, a więc do jego realizacji wystarczą tylko 2 przerzutniki.


TC M8 Slajd3.png

Proces minimalizacji automatu polega na wyznaczaniu relacji zgodności na zbiorze stanów wewnętrznych . Następnie dla tak wyznaczonych par zgodnych obliczane są Maksymalne Klasy Zgodności. W ostatnim etapie minimalizacji dokonuje się selekcji minimalnej liczby zbiorów zgodnych spełniających tzw. warunek pokrycia i zamknięcia.


TC M8 Slajd4.png

Dwa stany wewnętrzne , są zgodne, jeżeli dla każdego wejścia mają one niesprzeczne stany wyjść, a ich stany następne są takie same lub niesprzeczne.

Dwa stany wewnętrzne , są zgodne warunkowo, jeżeli ich stany wyjść są niesprzeczne oraz dla pewnego para stanów następnych do , (ozn. , ):

Stany , są sprzeczne, jeżeli dla pewnego ich stany wyjść są sprzeczne.

Dla automatu podanego na planszy, którego stany wewnętrzne są oznaczone liczbami naturalnymi 1 do 6, para 2, 4 jest zgodna, para 1, 3 jest zgodna warunkowo, a para 5, 6 jest sprzeczna.


TC M8 Slajd5.png

Ze względu na to, że para zgodna warunkowo może – po dalszej analizie – okazać się parą zgodną albo sprzeczną w obliczaniu wszystkich par zgodnych posługujemy się tzw. tablicą trójkątną.


TC M8 Slajd6.png

Przykładowa tablica trójkątna dla automatu o 5 stanach ma 4 kolumny oznaczone 1 do 4 oraz 4 wiersze oznaczone (od góry) 2 do 5. W rezultacie uzyskujemy tablicę, której kratki wypełniamy symbolami , gdy analizowana para jest zgodna, , gdy dana para jest sprzeczna lub w kratce zapisujemy parę (lub pary) stanów następnych w przypadku zgodności warunkowej.


TC M8 Slajd7.png

Sposób wypełnienia tablicy trójkątnej dla przykładowego automatu (jest to automat z planszy 2) wyjaśniamy na niniejszej planszy. Jak widać para 1, 2 jest zgodna, kratkę o współrzędnych 1, 2 wypełniamy znaczkiem ; para 1, 3 jest zgodna pod warunkiem zgodności pary 3, 6 i dlatego w odpowiedniej kratce wpisujemy 3, 6; z kolei para 1, 4 ma sprzeczne wyjścia, zatem wypełniamy ją symbolem itd.


TC M8 Slajd8.png

Ogólnie: w tablicy trójkątnej należy wpisać wszystkie warunki oraz wykreślić klatki odpowiadające stanom o sprzecznych wyjściach. Następnie należy wykreślić wszystkie klatki, w których jako warunek (lub jeden z warunków) wpisana jest para odpowiadająca klatce wykreślonej na poprzednim etapie. Dla wszystkich nowo wykreślonych klatek należy sprawdzić, czy odpowiadające im pary stanów występują w niewykreślonych klatkach jako warunki. Czynność wykreślania klatek prowadzi się aż do uzyskania sytuacji, gdy wszystkie pary określające warunki odpowiadają klatkom niewykreślonym.

W tak uzyskanej tablicy wszystkie klatki niewykreślone, bez względu na ich zawartość, odpowiadają parom stanów zgodnych


TC M8 Slajd9.png

Dysponując zbiorem wszystkich par zgodnych przystępujemy do wyznaczenia rodziny Maksymalnych Klas Zgodności. Dla potrzeb obliczania rodziny MKZ możemy stosować jedną z trzech metod omówionych w module 6.


TC M8 Slajd10.png

W przypadku tak prostego automatu wystarczy metoda bezpośrednia. Stosowne obliczenia pokazane są na planszy. Najpierw z par tworzymy trójki: 1,2,3; 1,2,5; 1,3,5; 2,3,5. Z uzyskanych czterech trójek powstaje zbiór czteroelementowy: 1, 2, 3, 5. W celu uzyskania wszystkich zbiorów MKZ uzupełniamy tę „czwórkę” tymi parami zgodnymi, które nie zawierają się w dotychczas obliczonych zbiorach zgodnych (czyli w 1, 2, 3, 5).


TC M8 Slajd11.png

Zgodnie z dotychczasowymi informacjami kolejnym etapem minimalizacji jest selekcja zbiorów zgodnych spełniających odpowiedni warunek pokrycia i zamknięcia. Dla porządku na planszy zapisany jest cały algorytm minimalizacji. Skoncentrujmy się na wyjaśnieniu warunków pokrycia i zamknięcia.

Otóż pokrycie wymaga, aby każdy stan realizowanego automatu był elementem co najmniej jednej wybranej klasy. Natomiast zamknięcie wymaga, aby dla każdej litery wejściowej wszystkie następniki (stany następne) danej klasy były zawarte w jednej z wybranych klas.


TC M8 Slajd12.png

Minimalnym zbiorem klas stanów zgodnych, spełniającym warunek pokrycia jest zbiór .


TC M8 Slajd13.png

Zbiór ten nie jest jednak zamknięty, gdyż warunkami dla klasy i , które nie są spełnione, gdyż żadna z tych klas nie jest zawarta w żadnej z obu klas zbioru minimalnego.


TC M8 Slajd14.png

Ponieważ następnikami klasy są klasy i , więc spróbujmy rozbić klasę na klasy i . Na podstawie tablicy trójkątnej stwierdzamy, że klasy te nie mają warunków zamknięcia. Jeśli zatem utworzymy zbiór , to wszystkie klasy będące warunkami zamknięcia dla klas tego zbioru są zawarte w pewnych jego klasach. Zatem zbiór , jest zamknięty i pełny, a więc jest minimalnym zbiorem klas zgodnych dla tego automatu. Konstrukcja automatu minimalnego pokazana jest na planszy.


TC M8 Slajd15.png

Dokonamy minimalizacji liczby stanów automatu podanego w tablicy na planszy. Najpierw wypełniamy odpowiednią tablicę trójkątną. Następnie na podstawie par sprzecznych zaznaczonych krzyżykami eliminujemy pary zgodne warunkowo. Powstałe nowe krzyżyki zaznaczono kolorem czerwonym. W rezultacie uzyskujemy pary zgodne: , , , , , , , , , , , , , .


TC M8 Slajd16.png

Z uzyskanych par zgodnych obliczamy (najłatwiej metodą bezpośrednią) maksymalne klasy zgodności: , , , , , , , .


TC M8 Slajd17.png

W celu sprawdzenia warunku pokrycia i zamknięcia tworzymy tablicę następników stanów zawartych w poszczególnych klasach zgodności. Zbiory następników odczytujemy z tablicy przejść wyjść i zapisujemy w dwóch wierszach w zależności od wartości sygnału wejściowego . Przykładowo dla zbioru zgodnego stany następne przy są odpowiednio Parser nie mógł rozpoznać (błąd składni): {\displaystyle 3, 3, –\,} natomiast przy stany następne dla


TC M8 Slajd18.png

Na tej planszy tablicę następników zapisujemy w formie uproszczonej. Na przykład poprzednio obliczone następniki: Parser nie mógł rozpoznać (błąd składni): {\displaystyle 3, 3, –\,} zapiszemy po prostu jako .

Analizując wypisane w tak zmodyfikowanej tablicy następniki łatwo zauważyć, że zbiory , oraz spełniają warunek pokrycia i zamkniętości. Na planszy podana jest również konstrukcja tablicy przejść-wyjść automatu minimalnego o stanach wewnętrznych .


TC M8 Slajd19.png

Celem kolejnego przykładu jest omówienie całego procesu syntezy automatu tj. począwszy od etapu syntezy abstrakcyjnej. Naszym zadaniem będzie zaprojektowanie układu sekwencyjnego tzw. detektora sekwencji. Opis działania tego układu podany jest na planszy.

Celem etapu syntezy abstrakcyjnej jest zapisanie działania automatu w formie tablicy lub grafu przejść wyjść. Zazwyczaj konstruowanie grafu jest wygodniejsze. W przypadku detektora sekwencji w pierwotnym grafie wyróżnić należy stanów. Przykładowo: w stanie po pojawieniu się sygnału wejściowego automat przechodzi do stanu , a po pojawieniu się automat przechodzi do stanu . W obu przypadkach generowany na wyjściu automatu sygnał może być dowolny, co symbolicznie zaznaczono „kreską”. Właściwa sekwencja jest wykrywana po przejściu przez stany i tylko wtedy na wyjściu automatu generowany jest sygnał o wartości . W pozostałych przypadkach odpowiedź automatu jest .


TC M8 Slajd20.png

Na podstawie uzyskanego w ten sposób grafu automatu łatwo utworzyć odpowiednią tablicę przejść wyjść. Łatwo spostrzec, że w utworzonej tablicy stany i (zacienione na czerwono) są sobie równoważne i w takim razie można je zredukować do jednego stanu. W tej sytuacji upraszcza się zarówno tablica przejść wyjść automatu jak też jego graf.


TC M8 Slajd21.png

I jest zrozumiałe, że dalszej syntezie poddamy taki częściowo już zminimalizowany automat. Po wypełnieniu odpowiedniej tablicy trójkątnej i wykreśleniu zgodnej warunkowo pary stwierdzamy, że w tym automacie jest dużo par zgodnych. Ale pary sprzeczne są tylko dwie. Warto więc liczyć maksymalne klasy zgodne metodą wg par sprzecznych.


TC M8 Slajd22.png

Obliczone pary sprzeczne zapisujemy w postaci wyrażenia boolowskiego typu iloczyn (koniunkcja) dwuskładnikowych sum , które po wymnożeniu uzyskuje postać

Odejmując od zbioru wszystkich stanów zbiory zapisane poszczególnych składnikach uzyskujemy rodzinę wszystkich MKZ:


TC M8 Slajd23.png

Warunek pokrycia spełniają dwa zbiory: oraz . Niestety nie spełniają one warunku zamknięcia. Dobierając trzeci zbiór, a mianowicie uzyskujemy spełnienie obu warunków. Na tej podstawie tworzymy tablicę przejść wyjść automatu minimalnego.


TC M8 Slajd24.png

Dla tak uzyskanego automatu należy dokonać kodowania stanów a następnie wykonać syntezę kombinacyjną. Warto jednak zauważyć, że uzyskany automat minimalny był już realizowany na planszach od do w module .