Minimalizacja liczby stanów
Minimalizacja stanów to transformacja automatu o danej tablicy przejść-wyjść na
równoważny mu (pod względem przetwarzania sygnałów cyfrowych) automat o
mniejszej liczbie stanów wewnętrznych. Jest to prawie zawsze możliwe, gdyż w
procesie pierwotnej specyfikacji często wprowadzane są stany nadmiarowe lub
równoważne.
Minimalizacja liczby stanów
x
a b c d a b c d
a b c d a b c d
S
S1
 S3 S4 S2  1 1 1
A C B C A 0 1 1 1
S2
S4    0   
B C C A  0 1 1 
S3
S6 S6   0 1  
S4
 S6 S1 S5  0 0 1 C B C A B 0 0 0 1
S5
  S2    1 
S6
S3  S2 S3 0  0 1
I
T
P
Czysty zysk  zamiast trzech przerzutników tylko dwa!
W
ZPT
1
Minimalizacja liczby stanów
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.
x
a b c d a b c d
S
Stany zgodne
1  3 4 2  1 1 1
warunkowo
2 4    0   
3 6 6   0 1  
Stany zgodne
4  6 1 5  0 0 1
5   2    1 
Stany sprzeczne
6 3  2 3 0  0 1
Dwa stany wewnętrzne Si, Sj są
Stany Si, Sj sÄ… sprzeczne,
zgodne warunkowo, jeżeli ich
jeżeli dla pewnego v " V
I
stany wyjść są niesprzeczne oraz
T
ich stany wyjść są sprzeczne.
P
dla pewnego v " V para stanów
W
następnych do Si, Sj (ozn. Sk, Sl):
ZPT
(Si, Sj) `" (Sk, Sl)
2
Relacja zgodności
Ze względu na zgodność warunkową w obliczeniach
(wszystkich!) par zgodnych posługujemy się tzw.
tablicą trójkątną.
Tablica trójkątna zawiera tyle kratek, ile jest
wszystkich możliwych par stanów. Na przykład dla
automatu o 5 stanach:
I
T
P
W
ZPT
3
Tablica trójkątna
2
3
4
5
1 2 3 4
Kratki tablicy wypełniamy symbolami:
v  jeżeli para stanów jest zgodna,
x  jeżeli para stanów jest sprzeczna, lub
I
T
P
W
parą (parami stanów następnych), jeżeli jest to para
ZPT
zgodna warunkowo.
4
Tablica trójkątna - przykład
a b c d a b c d
1  3 4 2  1 1 1
2
v
2 4    0   
3
36 46
3 6 6   0 1  
4  6 1 5  0 0 1
4
v
5   2    1 
5
24 v v
6 3  2 3 0  0 1
34 v
6
1,2; 3,5
1 2 3 4 5
I
T
P
W
ZPT
5
Tablica trójkątna - przykład
Po wypełnieniu tablicy sprawdzamy, czy pary stanów
sprzecznych (zaznaczone ×) nie wystÄ™pujÄ… przypadkiem jako
pary stanów następnych. Jeśli są takie pary, to należy je
skreÅ›lić (czyli zaznaczyć ×). Proces ten trzeba powtarzać tak
długo, aż sprawdzone zostaną wszystkie krzyżyki.
Wszystkie kratki
niewykreślone odpowiadają
2 ("
parom zgodnym:
3 3,6 4,6
(1,2); (1,3); (1,5); (2,3); (2,4);
(2,5); (3,5); (3,6); (4,6).
4 × (" ×
5 2,4 (" (" ×
6 × 3,4 (" 1,2; 3,5 ×
I
T
P
1 2 3 4 5
W
ZPT
6
Relacja zgodności
Relacja zgodności jest zwrotna, symetryczna,
ale nie jest przechodnia.
Pary zgodne umożliwiają wyznaczenie maksymalnych
zbiorów stanów zgodnych (MKZ, MCC).
Zbiór S = {s1,...,sp} nazywamy maksymalnym zbiorem
stanów zgodnych (maksymalną klasą zgodności),
jeżeli każda para si, sj wzięta z tego zbioru jest zgodna
oraz nie istnieje żaden inny zbiór stanów zgodnych S2 ,
zawierajÄ…cy S.
I
T
P
W
ZPT
7
Obliczanie MKZ
MKZ:
1,2 v
1,2,3 v
1,3 v
1,2,5 v
1,2,3,5
1,5 v
1,3,5 v
2,3 v
2,3,5 v
2,4
2,4
3,6
2,5 v
4,6
3,5 v
3,6
4,6
I
T
P MKZ = {{1,2,3,5}, {2,4}, {3,6}, {4,6}}
W
ZPT
8
Algorytm minimalizacji
1) Wyznaczenie par stanów zgodnych,
2) Obliczenie maksymalnych zbiorów
stanów zgodnych (MKZ),
3) Selekcja zbiorów spełniających tzw.
warunek pokrycia (a) i zamknięcia (b):
a) każdy stan musi wchodzić co najmniej
do jednej klasy;
b) dla każdej litery wejściowej wszystkie następniki
(stany następne) danej klasy muszą wchodzić do
I
T
jednej klasy.
P
W
ZPT
9
Warunek pokrycia - przykład
a b c d a b c d
1  3 4 2  1 1 1
MKZ = {{1,2,3,5}, {3,6}, { 2,4}, 4,6}}
2 4    0   
3 6 6   0 1  
4  6 1 5  0 0 1
5   2    1 
6 3  2 3 0  0 1
Aby spełnić warunek pokrycia wystarczy wybrać klasy:
I
{1,2,3,5}, {4,6}
T
P
W
ZPT
10
Warunek zamknięcia - przykład
a b c d a b c d Dla wybranych klas {1,2,3,5},{4,6}}
obliczamy ich następniki:
1  3 4 2  1 1 1
2 4    0   
3 6 6   0 1  
4  6 1 5  0 0 1
5   2    1 
6 3  2 3 0  0 1
a b c d
1,2,3,5
4,6 3,6! 2,4 2
3,6 2,4!
4,6
36 1,2 3,5
I
T
P
Nie jest spełniony warunek zamknięcia !
W
ZPT
11
Warunek pokrycia i zamknięcia  druga próba
a b c d a b c d
1  3 4 2  1 1 1
MKZ = {{1,2,3,5}, {3,6}, { 2,4}, {4,6}}
2 4    0   
Wybór: {1,2}, {3,5}, {4,6}
3 6 6   0 1  
4  6 1 5  0 0 1
a b c d a b c d
5   2    1 
A 1,2 4 3 4 2 0 1 1 1
6 3  2 3 0  0 1
B 3,5 6 6 2  0 1 1 
0 0 0 1
C 4,6 3 6 1,2 3,5
a b c d a b c d
I O.K.
A C B C A 0 1 1 1
T
P
B C C A  0 1 1 
W
C B C A B 0 0 0 1
ZPT
12
Jeszcze jeden przykład
0 1 0 1
1 2 6 0 0
2
2 3 1 1 1
3
46
3  4  0
4
56
45
4  5  0
5
v v v
5 3  1 
6
37 vv 37
6 7  1 
7
68 v v
48 58
7  8  0
v
8
v v
8    1
1 2 3 4 5 6 7
I
T
P
W
ZPT
13
Jeszcze jeden przykład c.d.
2
1,3
Pary zgodne: MKZ:
1,7
3
46 2,5,8
2,5
3,4,5
2,8
4
56
45
3,4 3,4,6
5
v v v
3,5 4,5,7
3,6 4,6,7
6
37 vv 37
4,5 1,3
4,6 1,7
7
68 v v
48 58
4,7 6,8
v
8
v v
5,7
5,8
1 2 3 4 5 6 7
6,7
6,8
I
T
P
W
ZPT
14
Jeszcze jeden przykład c.d.
0 1 0 1
MKZ: 2,5,8
1 2 6 0 0
3,4,5
2 3 1 1 1
3,4,6
3  4  0
4,5,7
4  5  0 4,6,7
1,3
5 3  1 
1,7
6 7  1 
6,8
7  8  0
8    1
Tablica następników
2,5,8 3,4,5 3,4,6 4,5,7 4,6,7 1,3 1,7 6,8
´(0,Si)   3   7  3  7 2 2 7
33
I
T
P
´(1,Si)
45
1  45 5 8 5 8 64 68  
W
ZPT
15
Jeszcze jeden przykład c.d.
0 1 0 1
1 2 6 0 0
2 3 1 1 1
X
3  4  0 0 1 0 1
S
4  5  0
A C C 1 1
5 3  1 
B B A 1 0
6 7  1 
C A B 0 0
7  8  0
8    1
A B C
2,5,8 3,4,5 3,4,6 4,5,7 4,6,7 1,3 1,7 6,8
´(0,Si) 3 3 7 3 7 2 2 7
I
T
P
´(1,Si) 1 45 45 58 58 46 68 
W
ZPT
16
Problem kodowania
x
Wariant I Wariant II
0 1 0 1
s
A A B 0 0
A = 00 A = 00
B = 01 B = 11
B A C 0 0
C = 10 C = 01
C D C 0 0
D = 11 D = 10
D A B 0 1
Wariant II
Wariant I
D = Q Q + xQ Q
D = xQ + xQ Q
D = xQ Q + xQ Q + xQ Q
D = x
I
y = xQ Q
T
y = xQ Q
P
W
ZPT
17
Kodowanie
Jak przewidzieć (obliczyć) najlepsze
kodowanie stanów?
Czy realne jest sprawdzenie wszystkich możliwości
3 stany - 3 różne kodowania
4 stany - 3 różne kodowania
5 stanów -
140 kodowań
7 stanów - 840 kodowań
I
T
P
9 stanów - ponad 10 milionów kodowań
W
ZPT
18
KODOWANIE
JedynÄ… rozsÄ…dnÄ… z punktu widzenia dzisiejszych
technologii i realną do omówienia w ograniczonym
czasie wykładu jest metoda wykorzystująca podział
z własnością podstawienia
I
T
P
W
ZPT
19
Elementy rachunku podziałów
Podziałem na zbiorze S jest system zbiorów P = {Bi }, którego bloki
są rozłączne, czyli
Bi )" Bj =Ć, jeśli tylko i `" j.
Dla S = {1,2,3,4,5,6}, P = {{1,2}, {3,5}, {4,6} } jest podziałem na S.
 =
(1,2; 3,5;4,6)
I
Iloczyn podziałów, suma podziałów oraz relacja d".
T
P
W
ZPT
20
Elementy rachunku podziałów&
Powiemy, że podział a jest nie większy od b (co oznaczamy: a d" b),
   
   
   
jeśli każdy blok z a jest zawarty w pewnym bloku z b.
 
 
 
a = b = . =
(1,2,4;3,5,6) (1,4; 2,6;3,5) (1,2; 4;6;3,5)
c d" a Tak c <  NIE!
/
b
I
(0)  podział najmniejszy
T
P
W
(1)  podział największy
ZPT
21
Elementy rachunku podziałów&
Iloczynem podziałów a " b nazywamy największy (względem
relacji d") podział, który jest nie większy od a oraz b.
a = b =
(1,2,4;3,5,6) (1,4; 2,6;3,5)
a " b =
(1,4; 2;6;3,5)
I
T
P
W
ZPT
22
Elementy rachunku podziałów&
Sumą podziałów a + b nazywamy najmniejszy (względem
relacji d") podział, który jest nie mniejszy od a oraz b.
a = (1,2;3,4;5,6;7,8,9)
b = (1,6;2,3;4,5;7,8;9)
a + b = (1,2,3,4,5,6;7,8,9)
I
T
P
W
ZPT
23
Własność podstawienia
Podział  na zbiorze stanów automatu M=
ma własność podstawienia (closed partition), gdy
zachodzi:
"vp "V , "(si, sj "bk ), bk "  Ò! " (´(si,vp ),(´(si,vp ))"bm
bm" 
Podział ma własność podstawienia, gdy elementy
bloku podziału pod wpływem dowolnej litery
wejściowej przechodzą na siebie lub na inny blok
podziału 
I
T
P
W
ZPT
24
Twierdzenie
Dany jest automat M o zbiorze stanów S, |S| = n.
Do zakodowania stanów potrzeba Q1, ..., Qk elementów pamięci.
Jeżeli istnieje podział  z własnością podstawienia i jeżeli r
spośród k zmiennych kodujących Q1, ..., Qk, gdzie
r = îÅ‚log2²(, ) , jest przyporzÄ…dkowanych blokom podziaÅ‚u  tak, że
wszystkie stany zawarte w jednym bloku sÄ… oznaczone tymi samymi
zmiennymi Q1, ..., Qr , to funkcje Q 1, ..., Q r, są niezależne od
pozostałych (k  r) zmiennych. I odwrotnie, gdy pierwsze r zmiennych
stanu następnego Q 1, ..., Q r (1 d" r < k) mogą być wyznaczone z
wartości wejść i pierwszych r zmiennych Q1, ..., Qr niezależnie od
wartości pozostałych zmiennych, to istnieje podział  z własnością
podstawienia taki, że dwa stany si, sj są w tym samym bloku podziału
wtedy i tylko wtedy, gdy są oznaczone tą samą wartością pierwszych r
I
T
zmiennych.
P
W
ZPT
25
Dekompozycja szeregowa
Dany jest automat M o zbiorze stanów S. Warunkiem
koniecznym i wystarczajÄ…cym dekompozycji szeregowej
automatu M na dwa szeregowo połączone automaty M1, M2 jest
istnienie podziaÅ‚u Ä„ z wÅ‚asnoÅ›ciÄ… podstawienia i podziaÅ‚u Ä
takich, że Ä„ " Ä = 0.
x
q1 Q1
q2 Q2 z
f1(x,Q1) D1 f2(x,Q1,Q2) D2 f0(x,Q2)
I
T
P
W
ZPT
26
Dekompozycja równoległa
Automat M jest dekomponowalny na dwa podautomaty M1, M2
działające równolegle wtedy i tylko wtedy, gdy na zbiorze S tego
automatu istnieją dwa nietrywialne podziały Ą1, Ą2 z własnością
podstawienia takie, że
Ä„1 " Ä„2 = Ä„(0)
q1
f1(x,Q1) D1
Q1 z
f0(x,Q1,Q2)
x
q2
Q2
f2(x,Q2) D2
I
T
P
W
ZPT
27
Dekompozycja szeregowa - przykład
x
s11 s12
0 1 0 1
s
Ä„1 = (A, B, E;C, D, F)
A A F 0 0
B E C 0 1
s21 s22 s23
C C E 0 1
D F A 1 0
Ä = (A, D; B,C; E, F)
E B F 1 1
Ä„ " Ä = Ä„(0)
F D E 0 0
x
S11,0 S11,1 S12,0 S12,1 S11,0 S11,1 S12,0 S12,1
s
x
0 1
s21 s21 s23 s23 s21 0 0 1 0
s
I
s22 s23 s22 s22 s23 0 1 0 1
T
s11 s11 s12
P
W
s23 s22 s23 s21 s23 1 1 0 0
s12 s12 s11
ZPT
28
Dekompozycja równoległa - przykład
s11 s12
x
0 1 0 1
s
Ä„1 = (A, B, E;C, D, F)
A A F 0 0
s21 s22 s23
B E C 0 1
Ä„2 = (A,C; B, D; E, F)
C C E 0 1
D F A 1 0
Ä„1 " Ä„2 = Ä„(0) E B F 1 1
F D E 0 0
x
x
S11,0 S12,0 S11,1 S12,1
s
0 1
s
s21 s21 s21 s23 s23
I
T
s21 s21 s23
s22 s23 s23 s21 s21
P
W
s22 s23 s21
s23 s22 s22 s23 s23
ZPT s23 s22 s23
29
Schematy dekompozycji
Dekompozycja szeregowa
x
y
2
M1 M2(Ä) WY
Dekompozycja równoległa
M1
y
WY
x
I
M2(Ä„2)
T
P
W
ZPT
30
Obliczanie podziału zamkniętego
x
Tworzymy graf par następników
0 1
dla różnych wierzchołków początkowych
s
A A F
A,B
B E C
C C E
A,E
C,F
D F A
E B F
C,D
E
F
F D E
A,C
E,F
A,B,E;C,D,F
A,B  = (A,B,E;C,D,F)
A,B,E;C,D,F
A,B,E;C,D,F
B,D



I
A,C;B,D;E,F
A,C;B,D;E,F
A,C;B,D;E,F
A,C  = (A,C;B,D;E,F)



T
P
A,D A,F
W
( )



A,D
ZPT
31
Dekompozycja z autonomicznym zegarem
Niektóre automaty mają dekompozycję, w której występuje
autonomiczny zegar  podautomat niezależny od wejść.
Podział Ąi zbioru stanów S automatu M jest zgodny z
wejściem, jeśli dla każdego stanu Sj " S i dla wszystkich vl " V
´(Sj,v1), ´(Sj,v2), ..., ´(Sj,vl), ..., ´(Sj,vp),
są w jednym bloku podziału Ąi.
Warunkiem koniecznym i dostatecznym istnienia
dekompozycji automatu M, w której występuje autonomiczny zegar
o îÅ‚log2²(Ä„)Å‚Å‚ stanach jest, aby istniaÅ‚ podziaÅ‚ zamkniÄ™ty Ä„ i
nietrywialny zgodny z wejściem podział Ąi zbioru stanów S tego
I
T
P
automatu, taki że Ąe"Ąi
W
ZPT
32