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
1
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
2
KODOWANIE
JedynÄ… rozsÄ…dnÄ… z punktu widzenia dzisiejszych
technologii i realną do omówienia w ograniczonym1)
czasie wykładu jest metoda wykorzystująca podział
z własnością podstawienia.
1) A wszystkich wytrwałych w tym procesie specjalnie
nagradzam na egzaminie.
I
T
P
W
ZPT
3
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
4
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
5
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
6
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.
= (1,2;3,4;5,6; 7,8,9)
a
b
= (1,6;2,3;4,5; 7,8; 9)
a + b
= (1,2,6;...)
= (1,2,3,6;...)
a + b
a + b = (1,2,3,4,6;...)
I
T
a + b = (1,2,3,4,5,6;...)
P
W
ZPT
a + b
= (1,2,3,4,5,6;7,8,9)
7
Własność podstawienia
Podział  na zbiorze stanów automatu M= ma
własność podstawienia (closed partition), gdy dla
każdej pary stanów Si, Sj należącej do tego samego
bloku  i każdego wejścia Ik stany Ik Si oraz Ik Sj należą
do wspólnego bloku .
x
Podziały z własnością podstawienia:
0 1 0 1
s
A A F 0 0
(
Ä„ = A, B, E;C, D, F )
B E C 0 1
1
C C E 0 1
D F A 1 0 Ä„ = A,C;B, D;E, F )
(
2
I
T
E B F 1 1
P
W
F D E 0 0
ZPT
8
Twierdzenie
Dany jest automat M o zbiorze stanów S, |S| = n.
Do zakodowania stanów potrzeba Q1, ..., Qk elementów pamięci.
²( )  liczba bloków podziaÅ‚u 
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
kodami Q1, ..., Qr , to funkcje Q 1, ..., Q r, są niezależne od pozostałych
(k  r) zmiennych.
I
T
P
W
ZPT
9
Przykład 1- interpretacja w.p.
x
0 1 0 1
s
(
Ä„ = A, B, E;C, D, F )
1
A A F 0 0
B E C 0 1
Ä = (A, D; B,C; E, F)
C C E 0 1
D F A 1 0
E B F 1 1
Kodowanie wg 1 Ä
F D E 0 0
A 0 0
0
B 0 1
0
C 0 1
1
Nie wystarcza to do
D 0 0
1
zakodowania
I
E 1 0
0
T
P
F 1 0
1
W
1 " Ä = (0)
Warunek jednoznaczności kodowania!
ZPT
10
Przykład 1&
Co to znaczy, że zastosujemy
x
kodowanie wg podziału zamkniętego:
0 1 0 1
s
Q1Q2Q3
A A F 0 0
A 0 0 0
B E C 0 1
B 0 0 1
Q1 = D1 = f(x,Q1)
C C E 0 1
C 1 0 1
D F A 1 0
D 1 0 0
a co z pozostałymi?
E B F 1 1
E 0 1 0
F D E 0 0
F 1 1 0
Niestety tylko jedną zmienną zakodowaliśmy wg
podziału zamkniętego, zatem:
Nie musimy obliczać funkcji wzbudzeń,
aby stwierdzić, że pierwsza z nich, czyli D1
I
będzie&
Q2 = D2 = f(x,Q1,Q2,Q3)
T
P
W
Q3 = D3 = f(x,Q1,Q2,Q3)
ZPT
11
Przykład 1&
A może jest więcej podziałów zamkniętych:
Póz
niej wykażemy, że oprócz 1
x
0 1 0 1
s
(
Ä„ = A, B, E;C, D, F )
1
A A F 0 0
jest 2
B E C 0 1
Ä„ = (A,C;B, D;E, F)
2
C C E 0 1
Kodowanie wg 1 2
D F A 1 0
E B F 1 1 A 0 0
0
F D E 0 0 B 0 1
0
C 0 0
1
D 0 1
1
Jest to kodowanie jednoznaczne
I
E 1 0
0
T
P
 "  = (0)
F 1 0

1

W
ZPT
12
PRZYKA
AD 1 c.d.
Przy tak dobranym kodowaniu pierwsza funkcja wzbudzeń
Q1 tego automatu będzie zależna od jednej zmiennej
wewnętrznej, a druga i trzecia łącznie (Q2 , Q3 ) od dwóch
zmiennych wewnętrznych, czyli
Q1 = f(x,Q1)
Q2 = f(x,Q2,Q3)
Q3 = f(x,Q2,Q3)
Kto nie wierzy, niech zakoduje, obliczy funkcje
I
Q1 , Q2 , Q3 i sprawdzi.
T
P
W
Dla całego roku!
ZPT
13
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
14
PRZYKA
AD 2
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
15
PRZYKA
AD 2 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
16
PRZYKA
AD 2 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
17
PRZYKA
AD 2 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
18
PRZYKA
AD 2 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
19
PRZYKA
AD 2 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)
Warto zakodować, obliczyć funkcje wzbudzeń Q1 , Q2 ,
I
Q3 i sprawdzić, czy rzeczywiście tak jest.
T
P
W
ZPT
20
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 wg naturalnego kodu
binarnego1):
0 0 0
A
0 0 1
B
Q1 = f(x,Q1)
C 0 1 0
Q2 = f(x,Q1,Q2,Q3)
D
0 1 1
Q3 = f(x,Q1,Q2,Q3)
E
1 0 0
F
1 0 1
G
1 1 0
I
T
H
1 1 1
P
W
1)
Naturalny kod binarny jest przyjmowany domyślnie do kodowania automatów w
ZPT
komercyjnych systemach projektowania układów cyfrowych
21
Nie martwmy siÄ™&
W najnowszych
systemach istnieje
opcjonalna możliwość
wprowadzenia
kodowania obliczonego
zewnętrznie przez
użytkownika
I
T
P
W
ZPT
22
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
23
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
24
Schematy dekompozycji
Dekompozycja szeregowa
x
y
2
M1(Ä„) M2(Ä) WY
Dekompozycja równoległa
M1 (Ä„1)
y
WY
x
I
M2(Ä„2)
T
P
W
ZPT
25
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
26
Dekompozycja równoległa - 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
(
Ä„ = A,C; B, D; E, F )
2
D F A 1 0
E B F 1 1
Ä„1 " Ä„2 = Ä„(0)
F D E 0 0
x x x
S11,0 S12,0 S11,1 S12,1
0 1 s 0 1
s
s
s21 s21 s21 s23 s23
I
s21 s21 s23
T s11 s11 s12
s22 s23 s23 s21 s21
P
s22 s23 s21
W
s12 s12 s11
s23 s22 s22 s23 s23
s23 s22 s23
ZPT
27
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
28
PRZYKA
AD 3
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
29
PRZYKA
AD 3
)
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
30