1
I
T
P
W
ZPT
Wykład cz6b
1
I
T
P
W
ZPT
Wykład cz6b
2
I
T
P
W
ZPT
PRZYKŁAD 1
x
s
0
1
Z
A
H
B
0
B
F
A
0
C
G
D
0
D
E
C
1
E
A
C
0
F
C
D
0
G
B
A
0
H
D
B
0
Generujemy podziały zamknięte
Generujemy podziały zamknięte
Do zakodowania stanów
automatu M potrzebne są 3
podziały 2-blokowe, takie że:
Do zakodowania stanów
automatu M potrzebne są 3
podziały 2-blokowe, takie że:
(0)
c
b
a
3
I
T
P
W
ZPT
PRZYKŁAD 1 c.d.
x
s
0
1
Z
A
H
B
0
B
F
A
0
C
G
D
0
D
E
C
1
E
A
C
0
F
C
D
0
G
B
A
0
H
D
B
0
Graf par następników :
Graf par następników :
H
G,
F,
E,
;
D
C,
B,
A,
1
A,B
A,B
F,H
F,H
C,D
C,D
E,F
E,F
A,C
A,C
G,E
G,E
G,H
G,H
B,D
4
I
T
P
W
ZPT
PRZYKŁAD 1 c.d.
x
s
0
1
Z
A
H
B
0
B
F
A
0
C
G
D
0
D
E
C
1
E
A
C
0
F
C
D
0
G
B
A
0
H
D
B
0
G
F,
C,
B,
;
H
E,
D,
A,
G
F,
;
H
E,
C
B,
;
D
A,
;
G
F,
C
B,
;
H
E,
D,
A,
;
H
E,
D
A,
;
G
F,
C,
B,
;
A,D
A,D
D,H
D,H
B,F
B,F
+
=
2
+
=
2
5
I
T
P
W
ZPT
PRZYKŁAD 1 c.d.
H
G,
F,
E,
;
D
C,
B,
A,
1
G
F,
C,
B,
;
H
E,
D,
A,
2
Niestety:
Niestety:
Potrzebny jest więc jeszcze jeden podział :
Potrzebny jest więc jeszcze jeden podział :
)
0
(
G
F,
;
H
E,
;
C
B,
;
D
A,
2
1
)
(0
τ
2
1
F
E,
D,
C,
;
H
G,
B,
A,
τ
6
I
T
P
W
ZPT
PRZYKŁAD 1 c.d.
H
G,
F,
E,
;
D
C,
B,
A,
1
G
F,
C,
B,
;
H
E,
D,
A,
2
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
Kodowanie wg
1
Kodowanie wg
1
2
2
A
B
C
D
E
F
G
H
F
E,
D,
C,
;
H
G,
B,
A,
τ
0
0
1
1
1
1
0
0
7
I
T
P
W
ZPT
PRZYKŁAD 1 c.d.
Przy tak dobranym kodowaniu dwie funkcje
wzbudzeń Q
1
’
i Q
2
’ tego automatu będą zależne od
jednej zmiennej wewnętrznej, a trzecia Q
3
’ (w
najgorszym przypadku) od trzech zmiennych, czyli
Q
1
’ = f(x,Q
1
)
Q
2
’ = f(x,Q
2
)
Q
3
’ = f(x,Q
1
,Q
2
,Q
3
)
Przy tak dobranym kodowaniu dwie funkcje
wzbudzeń Q
1
’
i Q
2
’ tego automatu będą zależne od
jednej zmiennej wewnętrznej, a trzecia Q
3
’ (w
najgorszym przypadku) od trzech zmiennych, czyli
Q
1
’ = f(x,Q
1
)
Q
2
’ = f(x,Q
2
)
Q
3
’ = f(x,Q
1
,Q
2
,Q
3
)
Kto nie wierzy, niech zakoduje, obliczy funkcje
Q
1
’, Q
2
’, Q
3
’ i sprawdzi.
Kto nie wierzy, niech zakoduje, obliczy funkcje
Q
1
’, Q
2
’, Q
3
’ i sprawdzi.
Dla całego roku!
Dla całego roku!
8
I
T
P
W
ZPT
Komentarz
Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.
Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.
Q
1
’ = f(x,Q
1
)
Q
2
’ = f(x,Q
1
,Q
2
,Q
3
)
Q
3
’ = f(x,Q
1
,Q
2
,Q
3
)
Q
1
’ = f(x,Q
1
)
Q
2
’ = f(x,Q
1
,Q
2
,Q
3
)
Q
3
’ = f(x,Q
1
,Q
2
,Q
3
)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
A
B
C
D
E
F
G
H
Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.
Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.
W szczególności dla kodowania binarnego:
W szczególności dla kodowania binarnego:
9
I
T
P
W
ZPT
Nie martwmy się…
Komputerowe
systemy
projektowania
umożliwiają
realizacje
automatów
dokładnie wg
kodowania
obliczonego
zewnętrznie przez
użytkownika
10
I
T
P
W
ZPT
Dekompozycja z autonomicznym
zegarem
Podział
i
zbioru stanów S automatu M jest zgodny z
wejściem, jeśli dla każdego stanu S
j
S i dla wszystkich v
l
V
(S
j
,v
1
),
(S
j
,v
2
), ...,
(S
j
,v
l
), ...,
(S
j
,v
p
),
są w jednym bloku podziału
i
.
Warunkiem koniecznym i dostatecznym istnienia
dekompozycji automatu M, w której występuje
autonomiczny zegar o log
2
(
)
stanach jest, aby istniał
podział zamknięty
i nietrywialny zgodny z wejściem podział
i
zbioru
stanów S tego automatu, taki że
i
Podział
i
zbioru stanów S automatu M jest zgodny z
wejściem, jeśli dla każdego stanu S
j
S i dla wszystkich v
l
V
(S
j
,v
1
),
(S
j
,v
2
), ...,
(S
j
,v
l
), ...,
(S
j
,v
p
),
są w jednym bloku podziału
i
.
Warunkiem koniecznym i dostatecznym istnienia
dekompozycji automatu M, w której występuje
autonomiczny zegar o log
2
(
)
stanach jest, aby istniał
podział zamknięty
i nietrywialny zgodny z wejściem podział
i
zbioru
stanów S tego automatu, taki że
i
11
I
T
P
W
ZPT
PRZYKŁAD 2
x
s
0
1
0
1
A
D
C
0
1
B
C
D
0
0
C
E
F
0
1
D
F
E
0
0
E
B
A
0
1
F
A
B
0
0
F
D,
B,
;
E
C,
A,
O
F
E,
;
D
C,
;
B
A,
I
Podział zgodny z wejściem:
Podział zgodny z wejściem:
Π(0)
Π
Π
O
I
I
jest zamknięty
I
jest zamknięty
12
I
T
P
W
ZPT
PRZYKŁAD 2
F
E,
;
D
C,
;
B
A,
Π
I
F
D,
B,
;
E
C,
A,
Π
O
0
0
0
0
0
1
0
1
1
0
1
0
0
1
0
1
0
1
Kodowanie wg
I
Kodowanie wg
I
wg
O
wg
O
A
B
C
D
E
F
Q
1
’ = f(Q
1
,Q
2
)
Q
1
’ = f(Q
1
,Q
2
)
Q
2
’ = f(Q
1
,Q
2
)
Q
2
’ = f(Q
1
,Q
2
)
Q
3
’ = ???
Q
3
’ = ???
y = f(x,Q
3
)
y = f(x,Q
3
)
13
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
Kodowanie intuicyjne
Licznik
E
clock
Q
Przykład licznika z wejściem
Enable
14
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
15
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
16
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
17
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
18
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
19
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
20
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
21
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).
22
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}
23
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,
24
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.