Podręcznik
3. Minimalizacja stanów automatu
Jak wiadomo automat A = áS,V,Y,d,lñ, w którym zbiór S stanów wewnętrznych S ma liczność |S| może być zrealizowany na co najmniej p = élog2÷S÷ù 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 w tabl. 4.18. Automat opisany tablicą przejść wyjść (tabl. 4.18a) 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 podanej w tabl. 4.18b. Zminimalizowany automat ma 3 stany, a więc do jego realizacji wystarczą tylko 2 przerzutniki.
Proces minimalizacji automatu polega na wyznaczaniu relacji zgodności na zbiorze stanów wewnętrznych S. 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.
Dwa stany wewnętrzne Si, Sj są zgodne, jeżeli dla każdego wejścia v mają one niesprzeczne stany wyjść, a ich stany następne są takie same lub niesprzeczne.
Dwa stany wewnętrzne Si, Sj są zgodne warunkowo, jeżeli ich stany wyjść są niesprzeczne oraz dla pewnego v Î V para stanów następnych do Si, Sj (ozn. Sk, Sl):
(Si, Sj) ¹ (Sk, Sl)
Stany Si, Sj są sprzeczne, jeżeli dla pewnego v Î V ich stany wyjść są sprzeczne.
Dla automatu z tabl. 4.18a, 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.
Tablica 4.18
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ą. Przykładowa tablica trójkątna (tabl. 4.19) 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 v, gdy analizowana para jest zgodna, x – gdy dana para jest sprzeczna lub w kratce zapisujemy parę (lub pary) stanów następnych w przypadku zgodności warunkowej.
Tablica 4.19
|
2 |
|
|
|
|
|
3 |
|
|
|
|
|
4 |
|
|
|
|
|
5 |
|
|
|
|
|
|
1 |
2 |
3 |
4 |
Sposób wypełnienia tablicy trójkątnej dla przykładowego automatu (podanego w tabl. 4.20) wyjaśniamy w tabl. 4.21. Jak widać para 1, 2 jest zgodna, kratkę o współrzędnych 1, 2 wypełniamy znaczkiem v; 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.
Tablica 4.20
Ogólnie, w tablicy trójkątnej należy wpisać wszystkie warunki oraz wykreślić kratki odpowiadające stanom o sprzecznych wyjściach. Następnie należy wykreślić wszystkie kratki, w których jako warunek (lub jeden z warunków) wpisana jest para k,l odpowiadająca klatce (k,l) 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 kratkach jako warunki. Czynność wykreślania klatek prowadzi się aż do uzyskania sytuacji, gdy wszystkie pary określające warunki odpowiadają kratkom niewykreślonym.
Tablica 4.21
|
2 |
v |
|
|
|
|
|
3 |
3,6 |
4,6 |
|
|
|
|
4 |
´ |
v |
´ |
|
|
|
5 |
2,4 |
v |
v |
´ |
|
|
6 |
´ |
3,4 |
v |
1,2; 3,5 |
´ |
|
|
1 |
2 |
3 |
4 |
5 |
W tak uzyskanej tablicy wszystkie kratki niewykreślone, bez względu na ich zawartość, odpowiadają parom stanów zgodnych. Z tabl. 4.21 odczytujemy, że wszystkie pary zgodne dla automatu z tabl. 4.20 są następujące:
(1,2) (1,3) (1,5) (2,3) (2,4) (2,5) (3,5) (3,6) (4,6)
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 dwóch metod omówionych w rozdz. 2.
W przypadku tak prostego automatu wystarczy metoda bezpośrednia. Stosowne obliczenia przebiegają następująco. 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). W rezultacie uzyskujemy rodzinę MKZ = {{1,2,3,5}, {2,4}, {3,6}, {4,6}}.
Zgodnie z dotychczasowymi informacjami kolejnym etapem minimalizacji jest selekcja zbiorów zgodnych spełniających odpowiedni warunek pokrycia i zamknięcia. Skoncentrujmy się na wyjaśnieniu warunków pokrycia i zamknięcia.
Tablica 4.22
|
|
a |
b |
c |
d |
|
1,2,3,5 |
4,6 |
3,6 |
2,4 |
2 |
|
4,6 |
3 |
6 |
1,2 |
3,5 |
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.
Minimalnym zbiorem klas stanów zgodnych, spełniającym warunek pokrycia dla automatu z tabl. 4.20 jest zbiór {{1,2,3,5}, {4,6}}. Zbiór ten nie jest jednak zamknięty, gdyż warunkami dla klasy {1,2,3,5} są {3,6} i {2,4}, które nie są spełnione (tabl. 4.22), gdyż żadna z tych klas nie jest zawarta w żadnej z obu klas zbioru minimalnego. Ponieważ następnikami klasy {4,6} są klasy {1,2} i {3,5}, więc spróbujmy rozbić klasę {1,2,3,5} na klasy {1,2} i {3,5}. Na podstawie tablicy trójkątnej stwierdzamy, że klasy te nie mają warunków zamknięcia. Jeśli zatem utworzymy zbiór {{1,2}, {3,5}, {4,6}}, to wszystkie klasy będące warunkami zamknięcia dla klas tego zbioru są zawarte w pewnych jego klasach. Zatem optymalny zbiór MKZopt = {{1,2}, {3,5}, {4,6}} jest zamknięty i pełny, a więc jest minimalnym zbiorem klas zgodnych dla tego automatu. Konstrukcja automatu minimalnego pokazana jest w tabl. 4.23.
Tablica 4.23
|
a) |
|
|
|
|
|
|
|
|
|
|
b) |
|
|
|
|
|
|
|
|
|
|
|
a |
b |
c |
d |
a |
b |
c |
d |
|
|
a |
b |
c |
d |
a |
b |
c |
d |
|
A |
1,2 |
4 |
3 |
4 |
2 |
0 |
1 |
1 |
1 |
|
A |
C |
B |
C |
A |
0 |
1 |
1 |
1 |
|
B |
3,5 |
6 |
6 |
2 |
– |
0 |
1 |
1 |
– |
|
B |
C |
C |
A |
– |
0 |
1 |
1 |
– |
|
C |
4,6 |
3 |
6 |
1,2 |
3,5 |
0 |
0 |
0 |
1 |
|
C |
B |
C |
A |
B |
0 |
0 |
0 |
1 |
W kolejnym przykładzie dokonamy redukcji stanów dla automatu podanego tablicy 4.24.
Tablica 4.24
|
x S |
0 |
1 |
0 |
1 |
|
1 |
5 |
4 |
0 |
0 |
|
2 |
2 |
7 |
1 |
1 |
|
3 |
– |
1 |
– |
0 |
|
4 |
– |
3 |
– |
0 |
|
5 |
2 |
– |
1 |
– |
|
6 |
6 |
– |
1 |
– |
|
7 |
– |
8 |
– |
0 |
|
8 |
– |
– |
– |
1 |
W tab. 4.25 zaznaczono pary sprzeczne (´), pary zgodne (v) oraz pary zgodne warunkowo (np. 1,4). Po sprawdzeniu zgodności warunkowej wykreślono pary 1,7; 3,7 oraz 4,7.
Tablica 4.25
Następnie stosując algorytm wyznaczania MKZ wg par zgodnych uzyskuje się:
|
S1 = Æ |
{1} |
|
S2 = Æ |
{2}{1} |
|
S3 = {1} |
{1,3}{2} |
|
S4 = {1,3} |
{1,3,4}{2} |
|
S5 = {2,3,4} |
{3,4,5}{2,5}{1,3,4} |
|
S6= {2,3,4,5} |
{3,4,5,6}{2,5,6} |
|
S7= {5,6} |
{5,6,7} |
|
S8= {2,5,6} |
|
MKZ = {1,3,4},{2,5,6,8},{3,4,5,6},{5,6,7}
Warunek pokrycia spełniają klasy {1,3,4}, {2,5,6,8}, {5,6,7}. Warunek zamknięcia jest sprawdzany w tab. 4.26.
Tablica 4.26
|
x S |
0 |
1 |
0 |
1 |
|
1,3,4 |
5--- |
413 |
0 |
0 |
|
2,5,6,8 |
226- |
7--- |
1 |
1 |
|
5,6,7 |
--26 |
--8 |
1 |
0 |
Przyporządkowując odpowiednio nazwy stanów A, B, C otrzymujemy tablicę przejść-wyjść (tab. 4.27) automatu minimalnego.
Tablica 4.27
|
x S |
0 |
1 |
0 |
1 |
|
A 1,3,4 |
B/C |
A |
0 |
0 |
|
B 2,5,6,8 |
C |
C |
1 |
1 |
|
C 5,6,7 |
B |
B |
1 |
0 |
|
|
S |
y |
||
Treścią kolejnego przykładu będzie zadanie nieco obszerniejsze – obejmujące dwa etapy syntezy tj. syntezę abstrakcyjna oraz minimalizacje liczby stanów.
Zaprojektować automat do kontroli czterobitowych słów podawanych szeregowo na jego wejście. Automat ma sprawdzać, czy słowa należą do kodu 2 z 4.
Synteza abstrakcyjna
Konstrukcję grafu stanów automatu pokazano na rys. 4.13. Automat pracuje w czterech taktach, co odpowiada przejściom ze stanu S1 np. przez stany S2, S4, S8 i powrót do stanu S1. Takich możliwych przejść jest 16 – każde odpowiada jednemu z szesnastu czterobitowych słów wejściowych. W czwartym takcie pracy automatu (przy powrocie do stanu S1) na wyjściu pojawia się sygnał 1 – jeśli w słowie wejściowym były dokładnie dwie jedynki (np. przejście S1, S2, S5, S11, S1, lub sygnał 0 – jeśli w słowie wejściowym była inna liczba jedynek niż dwie.
Na podstawie grafu stanów z rys. 4.13 utworzono tablicę przejść-wyjść automatu (tab. 4.28).
Tablica 4.28
|
x S |
0 |
1 |
0 |
1 |
|
1 |
2 |
3 |
0 |
0 |
|
2 |
4 |
5 |
0 |
0 |
|
3 |
6 |
7 |
0 |
0 |
|
4 |
8 |
9 |
0 |
0 |
|
5 |
10 |
11 |
0 |
0 |
|
6 |
12 |
13 |
0 |
0 |
|
7 |
14 |
15 |
0 |
0 |
|
8 |
1 |
1 |
0 |
0 |
|
9 |
1 |
1 |
0 |
1 |
|
10 |
1 |
1 |
0 |
0 |
|
11 |
1 |
1 |
1 |
0 |
|
12 |
1 |
1 |
0 |
1 |
|
13 |
1 |
1 |
1 |
0 |
|
14 |
1 |
1 |
1 |
0 |
|
15 |
1 |
1 |
0 |
0 |
Rys. 4.13. Graf stanów automatu z przykładu 4.4
Minimalizacja liczby stanów
W tablicy trójkątnej 4.29 znakiem v zaznaczono pary zgodne, krzyżykami ´ zaznaczono pary sprzeczne, a polach odpowiadających parom zgodnym warunkowo podano warunki. Następnie eliminujemy pary zgodne warunkowo na podstawie par sprzecznych (1,9; 2,9 itd.). Powstają nowe pary sprzeczne, które dalej eliminują pary zgodne warunkowo, itd. Okazuje się, że w wyniku tego postępowania uzyskano pary zgodne: (5,6), (8,15), (9,10), (9,12), (10,12), (11,13), (11,14), (131,14). Na tej podstawie wyznaczamy maksymalne klasy zgodności: {1}, {2},{3},{4},{5,6},{7}, {8,15}, {9,10,12}, (11,13,14}. Ponieważ dla spełnienia warunku pokrycia trzeba wziąć wszystkie klasy, zatem warunek zamkniętości też będzie spełniony.
Tablica 4.29
Jeśli wymienionym wcześniej klasom zgodności przypiszemy nazwy kolejno A, B, … , H, I, to uzyskamy tablicę przejść automatu minimalnego (tab. 4.30)
Tablica 4.30
|
x S |
0 |
1 |
0 |
1 |
|
A |
B |
C |
0 |
0 |
|
B |
D |
E |
0 |
0 |
|
C |
F |
G |
0 |
0 |
|
D |
G |
H |
0 |
0 |
|
E |
H |
I |
0 |
0 |
|
F |
I |
G |
0 |
0 |
|
G |
A |
A |
0 |
0 |
|
H |
A |
A |
0 |
1 |
|
I |
A |
A |
1 |
1 |
Na zakończenie wrócimy do syntezy automatów, dla których w przykładach 4.1 i 4.2 już wykonano syntezę abstrakcyjną. W wyniku tej syntezy otrzymaliśmy następujące tablice przejść-wyjść tych automatów.
Pokazane są one odpowiednio w tablicach 4.31 oraz 4.32. Odpowiadające im tablice trójkątne, pokazane w tablicach 4.33 i 4.34, wykazują, że automatów tych nie można zminimalizować.
Tablica 4.31
Tablica 4.32
Tablica 4.33
Tablica 4.34
