Wykład cz6b
I
T
P
W
ZPT
1
PRZYKA
AD 1
x
0 1 Z
s
Do zakodowania stanów automatu M
A H B 0
potrzebne są 3 podziały 2-blokowe,
B F A 0
takie że:
C G D 0
D E C 1
a " b " c = (0)
E A C 0
F C D 0
G B A 0
H D B 0
Generujemy podziały zamknięte
I
T
P
W
ZPT
2
PRZYKA
AD 1 c.d.
x
0 1 Z
Graf par następników :
s
A H B 0
B F A 0
A,B F,H
C G D 0
D E C 1
E A C 0
F C D 0
C,D B,D G,H
G B A 0
H D B 0
 = (A,B,C,D;E,F,G,H)
A,B,C,D;E,F,G,H
A,B,C,D;E,F,G,H
A,B,C,D;E,F,G,H



G,E E,F A,C
I
T
P
W
ZPT
3
PRZYKA
AD 1 c.d.
x
0 1 Z
s
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
A,D;B,C E,H;F,G
A,D A,D;B,C;E,H;F,G
A,D;B,C E,H;F,G
A,D;B,C E,H;F,G
I
A,D,E,H;B,C F,G
D,H A,D,E,H;B,C;F,G
A,D,E,H;B,C F,G
A,D,E,H;B,C F,G
T
P
= (A,D,E,H;B,C,F,G)
A,D,E,H;B,C,F,G
A,D,E,H;B,C,F,G
A,D,E,H;B,C,F,G
+ = 2



W
B,C,F,G;A,D E,H
B,F B,C,F,G;A,D;E,H
B,C,F,G;A,D E,H
B,C,F,G;A,D E,H
ZPT
4
PRZYKA
AD 1 c.d.
 = (A,B,C,D;E,F,G,H)
A,B,C,D;E,F,G,H
A,B,C,D;E,F,G,H
A,B,C,D;E,F,G,H



 = (A,D,E,H;B,C,F,G)
A,D,E,H;B,C,F,G
A,D,E,H;B,C,F,G
A,D,E,H;B,C,F,G



Niestety:
 "  = (A,D;B,C;E,H;F,G)`" (0)
A,D;B,C;E,H;F,G
A,D;B,C;E,H;F,G
A,D;B,C;E,H;F,G




Potrzebny jest wiÄ™c jeszcze jeden podziaÅ‚ Ä:
 "  " Ä = (0 )



I
T
Ä = (A,B,G,H;C,D,E,F)
A,B,G,H;C,D,E,F
A,B,G,H;C,D,E,F
A,B,G,H;C,D,E,F
P
W
ZPT
5
PRZYKA
AD 1 c.d.
Ä
Kodowanie wg 1 2
 = (A,B,C,D;E,F,G,H)
A,B,C,D;E,F,G,H
A,B,C,D;E,F,G,H
A,B,C,D;E,F,G,H
1
1
1
1
A 0 0 0
 = (A,D,E,H;B,C,F,G)
A,D,E,H;B,C,F,G
A,D,E,H;B,C,F,G
A,D,E,H;B,C,F,G



B 0 1 0
C 1 1
0
Ä = (A,B,G,H;C,D,E,F)
A,B,G,H;C,D,E,F
A,B,G,H;C,D,E,F
A,B,G,H;C,D,E,F
D 0 1
0
E 0 1
1
F 1 1
1
G 1 0
1
H 0 0
1
I
T
P
W
ZPT
6
PRZYKA
AD 1 c.d.
Przy tak dobranym kodowaniu dwie funkcje wzbudzeń Q1
i Q2 tego automatu będą zależne od jednej zmiennej
wewnętrznej, a trzecia Q3 (w najgorszym przypadku) od
trzech zmiennych, czyli
Q1 = f(x,Q1)
Q2 = f(x,Q2)
Q3 = f(x,Q1,Q2,Q3)
Kto nie wierzy, niech zakoduje, obliczy funkcje
I
Q1 , Q2 , Q3 i sprawdzi.
T
P
W
Dla całego roku!
ZPT
7
Komentarz
Każde inne kodowanie doprowadzi do bardziej
Każde inne kodowanie doprowadzi do bardziej
skomplikowanych funkcji wzbudzeń.
skomplikowanych funkcji wzbudzeń.
W szczególności dla kodowania binarnego:
A 0 0 0
B 0 0 1
C
0 1 0
Q1 = f(x,Q1)
D
0 1 1
Q2 = f(x,Q1,Q2,Q3)
E
1 0 0
Q3 = f(x,Q1,Q2,Q3)
F
1 0 1
G
1 1 0
I
H
1 1 1
T
P
W
ZPT
8
Nie martwmy siÄ™&
Komputerowe systemy
projektowania
umożliwiają realizacje
automatów dokładnie
wg kodowania
obliczonego zewnętrznie
przez użytkownika
I
T
P
W
ZPT
9
Dekompozycja z autonomicznym zegarem
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
I
tego automatu, taki że Ąe"Ąi
T
P
W
ZPT
10
PRZYKA
AD 2
x
0 1 0 1
s
Podział zgodny z wejściem:
A D C 0 1
( )
I = A,B;C,D;E,F
A,B;C,D;E,F
A,B;C,D;E,F
A,B;C,D;E,F
B C D 0 0
C E F 0 1
Ijest zamknięty
D F E 0 0
E B A 0 1
 = (A,C,E;B,D,F)
A,C,E;B,D,F
A,C,E;B,D,F
A,C,E;B,D,F
F A B 0 0
 "  = (0)
I O
I
T
P
W
ZPT
11
PRZYKA
AD 2
)
1û =(A,C,E;B,D,F
1û A,C,E;B,D,F
1û A,C,E;B,D,F
1û A,C,E;B,D,F
)
I =(A,B;C,D;E,F
Q1 = f(Q1,Q2)
Kodowanie wg I wg O
A 0 0 0
Q2 = f(Q1,Q2)
B 0 0 1
C 0 1 0
Q3 = ???
D 0 1 1
E 1 0 0
I
F 1 0 1
y = f(x,Q3)
T
P
W
ZPT
12
Kodowanie intuicyjne
Przykład licznika z wejściem Enable
E
0 1
S
E
S0 S0 S1
Licznik
S1 S1 S2
clock
S2 S2 S3
Q
S3 S3 S4
"
"
S7 S7 S0
I
T
P
W
ZPT
13
Licznik modulo 8
Zakodowana tablica przejść
Tablica przejść kod binarny
E
E
0 1 0 1
Q2Q1Q0
S
S0 S0 S1 000 000 001
S1 S1 S2 001 001 010
S2 S2 S3 010 010 011
S3 S3 S4 011 011 100
S4 S4 S5 100 100 101
S5 S5 S6 101 101 110
I
S6 S6 S7 110 110 111
T
P
S7 S7 s0 111 111 000
W
S Q2Q1Q0 Q2 Q1 Q0
ZPT
14
Zakodowana tablica p-w
E E
0 1 0 1
Q2Q1Q0 Q2Q1Q0
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
I
T
Q2Q1Q0 Q2 Q1 Q0 Q2Q1Q0 Q2 Q1 Q0
P
W
ZPT
15
Zakodowana tablica p-w (D)
E E
0 1 0 1 0 1 0 1
Q2Q1Q0 Q2Q1Q0
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
I
T
D2 = D1 = D0 = Q0E + Q0E
+Q2E Q1E
Q2Q1 +Q1Q0
P
W
+Q1Q0E
+Q2Q0 +Q2Q1Q0E
ZPT
16
Zakodowana tablica p-w (T)
E E
0 1 0 1 0 1 0 1
Q2Q1Q0 Q2Q1Q0
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
I
T
T2 = T1 = T0 =
EQ1Q0 EQ0
E
P
W
ZPT
17
Schemat licznika
=
T0 E
=
T1 EQ0
= =
T2 EQ0 Q1 T1Q1
Enable Q T Q Q
T T
Clock Q Q Q
I
T
P
W
ZPT
18
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
0/0
 trójka ma postać 001, a 0, gdy  trójka jest
4
innej postaci. Sygnał pojawiający się
0/- 1/1
podczas pierwszego i drugiego skoku
układu może być nieokreślony.
1/-
2
0/0
0/-
5
01100100110101001 1/0
1
- - 0 - - 1- - 1 - - 0 - - 0 0/0
6
0/-
1/0
1/-
3
I
T
0/0
P
1/-
7
W
1/0
ZPT
19
Detektor sekwencji
0/0
0/0
4 4
0/- 0/-
1/1 1/1
0/- 2 1/- 0/0 0/- 2 1/- 0/0
5 5
1/0 1/0
1 1
1/- 1/-
0/0
0/- 0/-
6
1/0
3 0/- 3
1/- 1/-
0/0
7
1/-
1/0
S 0 1 0 1
S 0 1 0 1
1 2 3 - -
1 2 3 - -
2 4 5 - -
2 4 5 - -
3 6 7 - -
3 5 5 - -
4 1 1 0 1
I
T
4 1 1 0 1
5 1 1 0 0
P
W
5 1 1 0 0
6 1 1 0 0
ZPT
7 1 1 0 0
20
Minimalizacja detektora sekwencji
X
0 1 0 1
S
1 2 3  
2 4 5   2 2 4, 3 5
3 5 5  
3 2 5, 3 5 45
4 1 1 0 1
4 1 2, 1 3 1 4, 1 5 1 5
5 1 1 0 0
5 1 2, 1 3 1 4, 1 5 1 5 ×
1 2 3 4
Bardzo dużo par zgodnych!
I
Do wyznaczenia MKZ wykorzystamy pary
T
P
sprzeczne, których jest znacznie mniej (dwie).
W
ZPT
21
Minimalizacja detektora sekwencji
Pary sprzeczne zapisujemy w postaci wyrażenia boolowskiego
typu iloczyn (koniunkcja) dwu-składnikowych sum.
W detektorze sekwencji pary sprzeczne sÄ…: (2, 3); (4, 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
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}
I
T
{1, 2, 3, 4, 5}  {3, 4} = {1, 2, 5}
P
W
{1, 2, 3, 4, 5}  {3, 5} = {1, 2, 4}
ZPT
22
Minimalizacja detektora sekwencji
X
MKZ: {1, 3, 5}, {1, 3, 4}, {1, 2, 5}, {1, 2, 4}
0 1 0 1
S
Klasy {1, 3, 5}, {1, 2, 4} spełniają warunek pokrycia,
1 2 3 - -
X
Funkcja przejść dla wszystkich MKZ
2 4 5 - - 0 1
S
3 5 5 - -
135 125 135
ale nie spełniają warunku
4 1 1 0 1
zamkniętości  stany
134 125 135
następne: {1,2,5} !
5 1 1 0 0
125 124 135
Dokładamy klasę {1,2,5}
124 124 135
Klasy: {1,3,5}, {1, 2, 4}, {1, 2, 5} spełniają
warunek pokrycia i zamkniętości
X
0 1 0 1
X
S
0 1 0 1
S
A B A 0 0
A 135 125 135 0 0
I
B C A 0 0
T
P
B 125 124 135 0 0
W
C C A 0 1
C 124 124 135 0 1
ZPT
23
...a to już było
X
0 1 0 1
S
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.
I
T
P
W
ZPT
24