Problem kodowania
x
0 1 0 1
s
A A B 0 0
B A C 0 0
C D C 0 0
D A B 0 1
I
T
P
W
ZPT
1
Kodowanie
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 ograniczonym
czasie wykładu jest metoda wykorzystująca podział
z własnością podstawienia
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ł Pa jest nie większy od Pb (co oznaczamy: Pa d" Pb ),
jeśli każdy blok z Pa jest zawarty w pewnym bloku z Pb.
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
a " b =
(1,4; 2;6;3,5)
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.
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
7
KODOWANIE
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
8
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
9
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
10
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
11
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
12
Dekompozycja równoległa - przykład
s11 s12
s21 s22 s23
Ä„2 = (A, D; B,C; E, F)
Ä„1 = (A, B, E;C, D, F)
Ä„1 " Ä„2 = Ä„(0)
x
x
S11,0 S12,0 S11,1 S12,1
s
0 1
s
s21 s21 s21 s23 s23
s21 s21 s23
s22 s23 s23 s21 s21
s22 s23 s21
s23 s22 s22 s23 s23
s23 s22 s23
I
T
P
W
ZPT
13
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
14
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
15
Obliczanie podziału zamkniętego
x
0 1
A,B
s
A A F
A,E
C,F
B E C
C C E
E
D F A
C,D
F
E B F
A,C
E,F
F D E
B,D
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



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
16
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
17
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
18
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
19
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
20
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
=T1Q1
=T0Q0
ZPT
21
Schemat licznika
Enable Q T Q Q
T T
Clock Q Q Q
=
T0 E
=
T1 EQ0
I
= =
T2 EQ0 Q1 T1Q1
T
P
W
ZPT
22