1
I
T
P
W
ZPT
Minimalizacja liczby stanów
a
b
c
d
a
b
c
d
A
C B
C
A
0
1
1
1
B
C C
A
–
0
1
1
–
C
B C
A
B
0
0
0
1
x
S
a
b
c
d
a
b
c
d
S1
–
S3 S4 S2 –
1
1
1
S2
S4
–
–
–
0
–
–
–
S3
S6 S6
–
–
0
1
–
–
S4
–
S6 S1 S5 –
0
0
1
S5
–
–
S2
–
–
–
1
–
S6
S3
–
S2 S3 0
–
0
1
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 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
Czysty zysk – zamiast trzech przerzutników tylko dwa!
Czysty zysk – zamiast trzech przerzutników tylko dwa!
2
I
T
P
W
ZPT
Minimalizacja liczby stanów
x
S
a b c d a b c d
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
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
, 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 S
i
, S
j
są zgodne warunkowo,
jeżeli ich stany wyjść są
niesprzeczne oraz dla
pewnego v V para stanów
następnych do S
i
, S
j
(ozn. S
k
,
S
l
):
(S
i
, S
j
) (S
k
, S
l
)
Dwa stany wewnętrzne S
i
, S
j
są
zgodne warunkowo
,
jeżeli ich stany wyjść są
niesprzeczne oraz dla
pewnego v V para stanów
następnych do S
i
, S
j
(ozn. S
k
,
S
l
):
(S
i
, S
j
) (S
k
, S
l
)
Stany Si, Sj są sprzeczne,
jeżeli dla pewnego v V
ich stany wyjść są
sprzeczne.
Stany Si, Sj są
sprzeczne,
jeżeli dla pewnego v V
ich stany wyjść są
sprzeczne.
Stany zgodne
warunkowo
Stany zgodne
Stany
sprzeczne
3
I
T
P
W
ZPT
Relacja zgodności
Ze względu na zgodność warunkową w
obliczeniach (wszystkich!) par zgodnych
posługujemy się tzw. tablicą trójkątną.
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:
Tablica trójkątna zawiera tyle kratek, ile jest
wszystkich możliwych par stanów. Na przykład
dla automatu o 5 stanach:
4
I
T
P
W
ZPT
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
parą (parami stanów następnych), jeżeli jest
to para zgodna warunkowo.
Kratki tablicy wypełniamy symbolami:
v
– jeżeli para stanów jest zgodna,
x
– jeżeli para stanów jest sprzeczna, lub
parą
(parami stanów następnych), jeżeli jest
to para zgodna warunkowo.
5
I
T
P
W
ZPT
Tablica trójkątna - przykład
a b c d a b c d
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
2
3
4
5
6
1
2
3
4
5
1,2; 3,5
v
v
v
v
v
v
36
36
46
24
24
34
6
I
T
P
W
ZPT
Tablica trójkątna - przykład
2
3 3,6
4,6
4
5 2,4
6
3,4
1,2; 3,5
1
2
3
4
5
Po wypełnieniu tablicy sprawdzamy, czy pary stanów
sprzecznych (zaznaczone ) nie występują przypadkiem
jako pary stanów następnych.
Po wypełnieniu tablicy sprawdzamy, czy pary stanów
sprzecznych
(zaznaczone ) nie występują przypadkiem
jako pary stanów następnych.
Wszystkie kratki
niewykreślone
odpowiadają parom
zgodnym:
Wszystkie kratki
niewykreślone
odpowiadają
parom
zgodnym
:
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.
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.
(1,2); (1,3); (1,5); (2,3);
(2,4); (2,5); (3,5); (3,6);
(4,6).
(1,2); (1,3); (1,5); (2,3);
(2,4); (2,5); (3,5); (3,6);
(4,6).
7
I
T
P
W
ZPT
Obliczanie MKZ
1,2 v
1,3 v
1,5 v
2,3 v
2,4
2,5 v
3,5 v
3,6
4,6
1,2,3 v
MKZ:
1,2,3,5
MKZ = {{1,2,3,5}, {2,4}, {3,6}, {4,6}}
MKZ = {{1,2,3,5}, {2,4}, {3,6}, {4,6}}
1,2,5 v
1,3,5 v
2,3,5 v
2,4
3,6
4,6
8
I
T
P
W
ZPT
Algorytm minimalizacji
1) Wyznaczenie par stanów zgodnych,
1) Wyznaczenie par stanów zgodnych,
2) Obliczenie maksymalnych
zbiorów stanów zgodnych
(MKZ),
2) Obliczenie maksymalnych
zbiorów stanów zgodnych
(MKZ),
3) Selekcja zbiorów spełniających tzw.
warunek pokrycia (a) i
zamknięcia (b):
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;
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 jednej klasy.
b) dla każdej litery wejściowej wszystkie
następniki (stany następne) danej klasy
muszą wchodzić do jednej klasy.
9
I
T
P
W
ZPT
Warunek pokrycia - przykład
a b c d a b c d
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
MKZ = {{1,2,3,5}, {3,6},
{ 2,4}, 4,6}}
Aby spełnić warunek pokrycia wystarczy wybrać klasy:
Aby spełnić warunek pokrycia wystarczy wybrać klasy:
{1,2,3,5}, {4,6}
10
I
T
P
W
ZPT
Warunek zamknięcia - przykład
a b c d a b c d
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
Dla wybranych klas {1,2,3,5},
{4,6}}
obliczamy ich następniki:
a
b
c
d
1,2,3,
5
4,6
Nie jest spełniony warunek zamknięcia !
Nie jest spełniony warunek zamknięcia !
4,6
4,6
3,6
3,6
2,4
2,4
2
2
3
3
6
6
1,2
1,2
3,5
3,5
3,6!
3,6!
2,4!
2,4!
11
I
T
P
W
ZPT
Warunek pokrycia i zamknięcia –
druga próba
a b c d a b c d
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
a
b
c
d
A
1,2
B
3,5
C
4,6
MKZ = {{1,2,3,5}, {3,6},
{ 2,4}, {4,6}}
Wybór:
a b
c
d
a
b
c
d
A C B
C
A
0
1
1
1
B C C
A
–
0
1
1
–
C B C
A
B
0
0
0
1
{1,2}, {3,5},
{4,6}
3 6 1,
2
3,
5
6 6
2
–
4 3
4
2
0
1
1
1
0
1
1
–
0
0
0
1
O.K.
O.K.
12
I
T
P
W
ZPT
Jeszcze jeden przykład
0
1
0
1
1
2
6
0
0
2
3
1
1
1
3
–
4
–
0
4
–
5
–
0
5
3
–
1
–
6
7
–
1
–
7
–
8
–
0
8
–
–
–
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
37
37
46
46
56
56
68
68
45
45
48
48
58
58
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
37
37
13
I
T
P
W
ZPT
Jeszcze jeden przykład c.d.
2
3
4
5
6
7
8
1
2
3
4
5
6
7
37
37
46
46
56
56
68
68
45
45
48
48
58
58
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
37
37
1,3
1,7
2,5
2,8
3,4
3,5
3,6
4,5
4,6
4,7
5,7
5,8
6,7
6,8
1,3
1,7
2,5
2,8
3,4
3,5
3,6
4,5
4,6
4,7
5,7
5,8
6,7
6,8
Pary zgodne:
Pary zgodne:
3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8
3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8
MKZ:
MKZ:
3,4,
5
3,4,
5
2,5,
8
2,5,
8
14
I
T
P
W
ZPT
Jeszcze jeden przykład c.d.
0
1
0
1
1
2
6
0
0
2
3
1
1
1
3
–
4
–
0
4
–
5
–
0
5
3
–
1
–
6
7
–
1
–
7
–
8
–
0
8
–
–
–
1
2,5,8 3,4,
5
3,4,6 4,5,7 4,6,7
1,3
1,7
6,8
(0,S
i
)
(1,S
i
)
2,5,
8
3,4,
5
3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8
2,5,
8
3,4,
5
3,4,
6
4,5,
7
4,6,
7
1,3
1,7
6,8
MKZ:
MKZ:
33–
33–
1– –
1– –
– –3
– –3
45–
45–
– –7
– –7
45–
45–
5–8
5–8
5–8
5–8
64
64
68
68
7–
7–
– –
– –
2–
2–
–3–
–3–
–7–
–7–
2–
2–
Tablica następników
Tablica następników
15
I
T
P
W
ZPT
Jeszcze jeden przykład c.d.
0
1
0
1
1
2
6
0
0
2
3
1
1
1
3
–
4
–
0
4
–
5
–
0
5
3
–
1
–
6
7
–
1
–
7
–
8
–
0
8
–
–
–
1
2,5,8 3,4,
5
3,4,6 4,5,7 4,6,7
1,3
1,7
6,8
(0,S
i
)
3
3
7
3
7
2
2
7
(1,S
i
)
1
45
45
58
58
46
68
–
X
S
0
1
0
1
A
C
C
1
1
B
B
A
1
0
C
A
B
0
0
A
A
B
B
C
C
16
I
T
P
W
ZPT
Detektor sekwencji
Zaprojektować układ sekwencyjny
Mealy’ego o jednym wejściu
binarnym i jednym wyjściu binarnym.
Układ ma badać kolejne „trójki”
symboli wejściowych. Sygnał
wyjściowy pojawiający się podczas
trzeciego skoku układu ma wynosić
1, gdy „trójka” ma postać 001, a 0,
gdy „trójka” jest innej postaci.
Sygnał pojawiający się podczas
pierwszego i drugiego skoku układu
może być nieokreślony.
Zaprojektować układ sekwencyjny
Mealy’ego o jednym wejściu
binarnym i jednym wyjściu binarnym.
Układ ma badać kolejne
„trójki”
symboli wejściowych. Sygnał
wyjściowy pojawiający się podczas
trzeciego skoku układu ma wynosić
1
, gdy
„trójka”
ma postać
001
, a
0
,
gdy
„trójka”
jest
innej postaci
.
Sygnał pojawiający się podczas
pierwszego i drugiego skoku układu
może być nieokreślony.
1
2
3
4
5
6
7
0/-
1/-
0/-
0/0
0/0
0/0
0/0
1/0
1/0
1/0
1/1
0/-
1/-
1/-
01100100110101001
01100100110101001
- -
0
- -
0
- -
1
- -
1
- -
1
- -
1
- -
0
- -
0
- -
0
- -
0
17
I
T
P
W
ZPT
Detektor sekwencji
0/-
1/-
0/0
1
2
3
4
5
6
7
0/-
1/-
0/-
0/0
0/0
0/0
1/0
1/0
1/0
1/1
0/-
1/-
1/-
0/0
0/-
1/-
1
2
3
4
5
0/-
1/-
0/-
0/0
1/0
1/1
1/-
S 0 1 0 1
1 2 3 -
-
2 4 5 -
-
3 5 5 -
-
4 1 1 0 1
5 1 1 0 0
S
0
1
0 1
1
2
3
-
-
2
4
5
-
-
3
6
7
-
-
4
1
1
0 1
5
1
1
0 0
6
1
1
0 0
7
1
1
0 0
18
I
T
P
W
ZPT
Minimalizacja detektora
sekwencji
X
S
0
1
0
1
1 2
3
–
–
2 4
5
–
–
3 5
5
–
–
4 1
1
0
1
5 1
1
0
0
2 2 4, 3 5
3 2 5, 3 5
45
4 1 2, 1 3 1 4, 1 5
1 5
5 1 2, 1 3 1 4, 1 5
1 5
1
2
3
4
Bardzo dużo par zgodnych!
Bardzo dużo par zgodnych!
Do wyznaczenia MKZ wykorzystamy pary
sprzeczne, których jest znacznie mniej
(dwie).
Do wyznaczenia MKZ wykorzystamy pary
sprzeczne, których jest znacznie mniej
(dwie).
19
I
T
P
W
ZPT
Minimalizacja detektora
sekwencji
Pary sprzeczne zapisujemy w postaci wyrażenia
boolowskiego typu iloczyn (koniunkcja) dwu-
składnikowych sum.
Pary sprzeczne zapisujemy w postaci wyrażenia
boolowskiego typu iloczyn (koniunkcja) dwu-
składnikowych sum.
Na tej podstawie zapisujemy wyrażenie: (2 3) (4
5),
które po wymnożeniu uzyskuje postać:
(2 3) (4 5) = 2 4 2 5 3 4 3 5
Na tej podstawie zapisujemy wyrażenie: (2 3) (4
5),
które po wymnożeniu uzyskuje postać:
(2 3) (4 5) = 2 4 2 5 3 4 3 5
W detektorze sekwencji pary sprzeczne są: (2, 3); (4, 5).
W detektorze sekwencji pary sprzeczne są: (2, 3); (4, 5).
Odejmując od zbioru S = {1, 2, 3, 4, 5} wszystkich
stanów zbiory zapisane w poszczególnych
składnikach uzyskujemy rodzinę wszystkich MKZ.
Odejmując od zbioru S = {1, 2, 3, 4, 5} wszystkich
stanów zbiory zapisane w poszczególnych
składnikach uzyskujemy rodzinę wszystkich MKZ.
{1, 2, 3, 4, 5} – {2, 4} = {1, 3, 5}
{1, 2, 3, 4, 5} – {2, 5} = {1, 3, 4}
{1, 2, 3, 4, 5} – {3, 4} = {1, 2, 5}
{1, 2, 3, 4, 5} – {3, 5} = {1, 2, 4}
20
I
T
P
W
ZPT
Minimalizacja detektora
sekwencji
X
S
0 1 0 1
1
2 3 - -
2
4 5 - -
3
5 5 - -
4
1 1 0 1
5
1 1 0 0
X
S
0
1
135 125 135
134 125 135
125 124 135
124 124 135
MKZ: {1, 3, 5}, {1, 3, 4}, {1, 2, 5},
{1, 2, 4}
Funkcja przejść dla wszystkich MKZ
Funkcja przejść dla wszystkich MKZ
Dokładamy klasę {1,2,5}
Dokładamy klasę
{1,2,5}
X
S
0
1
0
1
A 135 125 135
0
0
B 125 124 135
0
0
C 124 124 135
0
1
X
S
0
1
0
1
A
B
A
0
0
B
C
A
0
0
C
C
A
0
1
Klasy: {1,3,5}, {1, 2, 4}, {1, 2, 5} spełniają
warunek pokrycia i zamkniętości
Klasy:
{
1,3,5}, {1, 2, 4},
{1, 2, 5}
spełniają
warunek pokrycia i zamkniętości
ale nie spełniają
warunku zamkniętości
– stany następne:
{1,2,5} !
ale nie spełniają
warunku zamkniętości
– stany następne:
{1,2,5} !
Klasy {1, 3, 5}, {1, 2, 4} spełniają warunek
pokrycia,
Klasy
{1, 3, 5}, {1, 2, 4}
spełniają warunek
pokrycia,
21
I
T
P
W
ZPT
...a to już było
X
S
0
1
0
1
A
B
A
0
0
B
C
A
0
0
C
C
A
0
1
Uzyskany automat był już realizowany na
przerzutnikach i bramkach – wykład cz5, plansze
13 do 20.
22
I
T
P
W
ZPT
E
S
0
1
S
0
S
0
S
1
S
1
S
1
S
2
S
2
S
2
S
3
S
3
S
3
S
4
S
7
S
7
S
0
Synteza licznika
Licznik
E
clock
Q
Przykład licznika z wejściem
Enable
23
I
T
P
W
ZPT
E
S
0
1
E
Q2Q1Q0
0
1
S
0
S
0
S
1
000
000
001
S
1
S
1
S
2
001
001
010
S
2
S
2
S
3
010
010
011
S
3
S
3
S
4
011
011
100
S
4
S
4
S
5
100
100
101
S
5
S
5
S
6
101
101
110
S
6
S
6
S
7
110
110
111
S
7
S
7
s
0
111
111
000
S’
Q2Q1Q0
Q2’Q1’Q0’
Licznik modulo 8
Tablica przejść
Tablica przejść
Zakodowana tablica przejść
kod binarny
Zakodowana tablica przejść
kod binarny
24
I
T
P
W
ZPT
E
Q2Q1Q0
0
1
E
Q2Q1Q
0
0
1
000
000
001
000
000
001
001
001
010
001
001
010
010
010
011
011
011
100
011
011
100
010
010
011
100
100
101
110
110
111
101
101
110
111
111
000
110
110
111
101
101
110
111
111
000
100
100
101
Q2Q1Q0
Q2’Q1’Q0’
Q2Q1Q
0
Q2’Q1’Q0’
Zakodowana tablica p-w
25
I
T
P
W
ZPT
E
Q2Q1Q0
0
1
E
Q2Q1Q0
0
1
0
1
0
1
000
000
001
000
0
0
0
0
0
1
001
001
010
001
0
0
0
1
1
0
011
011
100
011
0
1
1
0
1
0
010
010
011
010
0
0
1
1
0
1
110
110
111
110
1
1
1
1
0
1
111
111
000
111
1
0
1
0
1
0
101
101
110
101
1
1
0
1
1
0
100
100
101
100
1
1
0
0
0
1
Q2Q1Q0
Q2’Q1’Q0’
Q2Q1Q0
D2
D1
D0
Zakodowana tablica p-w (D)
D2 =
D2 =
1
Q
Q2
0
Q
Q2
D1 =
D1 =
E
Q1
D0 =
D0 =
E
Q0
E
Q2
2Q1Q0E
Q
1Q0E
Q
0
Q
Q1
0E
Q
26
I
T
P
W
ZPT
E
Q2Q1Q0
0
1
E
Q2Q1Q0
0
1
0
1
0
1
000
000
001
000
0
0
0
0
0
1
001
001
010
001
0
0
0
1
0
1
011
011
100
011
0
1
0
1
0
1
010
010
011
010
0
0
0
0
0
1
110
110
111
110
0
0
0
0
0
1
111
111
000
111
0
1
0
1
0
1
101
101
110
101
0
0
0
1
0
1
100
100
101
100
0
0
0
0
0
1
Q2Q1Q0
Q2’Q1’Q0’
Q2Q1Q0
T2
T1
T0
Zakodowana tablica p-w (T)
T2 =
T2 =
EQ1Q0
T1 =
T1 =
T0 =
T0 =
EQ0
E
27
I
T
P
W
ZPT
Schemat licznika
T Q
Q
Clock
T Q
Q
Enable
T Q
Q
1
1
1
0
2
0
1
0
Q
T
Q
EQ
T
EQ
T
E
T
28
I
T
P
W
ZPT
Problem kodowania
x
s
0 1 0 1
A
A B 0 0
B
A C 0 0
C
D C 0 0
D
A B 0 1
Wariant I
A = 00
B = 01
C = 10
D = 11
Wariant I
A = 00
B = 01
C = 10
D = 11
Wariant II
A = 00
B = 11
C = 01
D = 10
Wariant II
A = 00
B = 11
C = 01
D = 10
2
1
2
1
1
Q
Q
x
Q
Q
D
2
1
2
1
2
1
2
Q
Q
x
Q
xQ
Q
Q
x
D
2
1
Q
xQ
y
2
1
2
1
Q
Q
x
Q
x
D
x
D
2
2
1
Q
xQ
y
Wariant II
Wariant II
Wariant I
Wariant I
29
I
T
P
W
ZPT
Kodowanie
3 stany - 3 różne kodowania
3 stany - 3 różne kodowania
4 stany - 3 różne kodowania
4 stany - 3 różne kodowania
5 stanów
-
5 stanów
-
140
kodowań
140
kodowań
7 stanów
-
7 stanów
-
840
kodowań
840
kodowań
9 stanów
-
9 stanów
-
ponad 10 milionów
kodowań
ponad 10 milionów
kodowań
Jak przewidzieć (obliczyć)
najlepsze kodowanie stanów?
Jak przewidzieć (obliczyć)
najlepsze kodowanie stanów?
Czy realne jest sprawdzenie wszystkich
możliwości
Czy realne jest sprawdzenie wszystkich
możliwości
30
I
T
P
W
ZPT
KODOWANIE
Klasyczne procedury kodowania są bardzo
skomplikowane i omówienie ich w ograniczonym
czasie wykładu jest niemożliwe.
Klasyczne procedury kodowania są bardzo
skomplikowane i omówienie ich w ograniczonym
czasie wykładu jest niemożliwe.
Można korzystać z oprogramowania
akademickiego: JEDI, NOVA (uniwersytet
kalifornijski: Berkeley).
Można korzystać z oprogramowania
akademickiego: JEDI, NOVA (uniwersytet
kalifornijski: Berkeley).
Document Outline