1 Problem kodowania x s 1 A B C D Wariant I A = 00 B = 01 C = 10 D = 111 A B C D Wariant I A = 00 B = 01 C = 10 D = 11 Wariant II A = 00 B = 11 C = 01 D = 10 Wariant II Wariant I
2 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ń 9 stanów - ponad 10 milionów kodowań
3 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. A wszystkich wytrwałych w tym procesie specjalnie nagradzam na egzaminie.
4 Elementy rachunku podziałówPodział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. = Iloczyn podziałów, suma podziałów oraz relacja .
5 Elementy rachunku podziałów…Powiemy, że podział a jest nie większy od b (co oznaczamy: a b), jeśli każdy blok z a jest zawarty w pewnym bloku z b. a = b = c = c ≤ a Tak c b NIE! (0) – podział najmniejszy (1) – podział największy
6 Elementy rachunku podziałów…Iloczynem podziałów a • b nazywamy największy (względem relacji ) podział, który jest nie większy od a oraz b. a = b = a • b =
7 Elementy rachunku podziałów…Sumą podziałów a + b nazywamy najmniejszy (względem relacji ) podział, który jest nie mniejszy od a oraz b. a b a + b a + b a + b a + b a + b
8 Własność podstawieniaPodział na zbiorze stanów automatu M=
9 Twierdzenie () – liczba bloków podziału 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.
10 Przykład 1- interpretacja w.p.x s 1 A F B E C D Kodowanie wg 1 A B C D E F 1 0 0 0 1 1 0 Nie wystarcza to do zakodowania 1 • = (0) Warunek jednoznaczności kodowania!
11 Przykład 1… Q1’ = D1 = f(x,Q1) Q2’ = D2 = f(x,Q1,Q2,Q3)Co to znaczy, że zastosujemy kodowanie wg podziału zamkniętego: x s 1 A F B E C D Q1Q2Q3 A 0 0 0 B 0 0 1 C 1 0 1 D 1 0 0 E 0 1 0 F 1 1 0 Q1’ = D1 = f(x,Q1) a co z pozostałymi? 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 będzie… Q2’ = D2 = f(x,Q1,Q2,Q3) Q3’ = D3 = f(x,Q1,Q2,Q3)
12 Przykład 1… A może jest więcej podziałów zamkniętych: x s 1 A F B E C1 A F B E C D Później wykażemy, że oprócz 1 jest 2 Kodowanie wg 1 2 A B C D E F 1 0 0 0 1 1 0 Jest to kodowanie jednoznaczne
13 Jeśli wyjdzie inaczej – TŁ stawiaPRZYKŁ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) Jeśli wyjdzie inaczej – TŁ stawia Kto nie wierzy, niech zakoduje, obliczy funkcje Q1’, Q2’, Q3’ i sprawdzi. Dla całego roku!
14 Obliczanie podziału zamkniętegox s 1 A F B E C D Tworzymy graf par następników dla różnych wierzchołków początkowych A,B A,E C,F C,D E F A,C E,F A,B B,D A,C A,D A,F A,D
15 Generujemy podziały zamkniętePRZYKŁAD 2 x s 1 Z A H B F C G D E Do zakodowania stanów automatu M potrzebne są 3 podziały 2-blokowe, takie że: Generujemy podziały zamknięte
16 PRZYKŁAD 2 c.d. Graf par następników : x s 1 Z A H B F C G D E A,B F,H1 Z A H B F C G D E Graf par następników : A,B F,H C,D E,F A,C G,E G,H B,D
17 PRZYKŁAD 2 c.d. x s 1 Z A H B F C G D E A,D D,H + =2 B,F
18 PRZYKŁAD 2 c.d. Niestety: Potrzebny jest więc jeszcze jeden podział :
19 PRZYKŁAD 2 c.d. t Kodowanie wg 1 2 A B C D E F G H 1 1 1
20 PRZYKŁ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’, Q3’ i sprawdzić, czy rzeczywiście tak jest.
21 Komentarz 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 wg naturalnego kodu binarnego1): A B C D E F G H 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Q1’ = f(x,Q1) Q2’ = f(x,Q1,Q2,Q3) Q3’ = f(x,Q1,Q2,Q3) 1) Naturalny kod binarny jest przyjmowany domyślnie do kodowania automatów w komercyjnych systemach projektowania układów cyfrowych
22 Nie martwmy się… W najnowszych systemach istnieje opcjonalna możliwość wprowadzenia kodowania obliczonego zewnętrznie przez użytkownika
23 Dekompozycja szeregowaDany 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. f1(x,Q1) D1 f2(x,Q1,Q2) D2 f0(x,Q2) x q1 Q1 Q2 q2 z
24 Dekompozycja równoległaAutomat 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) f0(x,Q1,Q2) x f2(x,Q2) D2 q2 z f1(x,Q1) D1 q1 Q1 Q2
25 Schematy dekompozycjiDekompozycja szeregowa M1() M2() WY x 2 y Dekompozycja równoległa WY x M2(2) y M1 (1)
26 Dekompozycja szeregowa - przykładx s 1 A F B E C D s11 s12 s21 s22 s23 = (0) x s S11,0 S11,1 S12,0 S12,1 s21 s23 1 s22 x s 1 s11 s12
27 Dekompozycja równoległa - przykładx s 1 A F B E C D s11 s12 s21 s22 s23 1 2 = (0) x s 1 s11 s12 x s S11,0 S12,0 S11,1 S12,1 s21 s23 s22 x s 1 s21 s23 s22
28 Dekompozycja z autonomicznym zegaremNiektó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 automatu, taki że i
29 Podział zgodny z wejściem:PRZYKŁAD 3 x s 1 A D C B E F Podział zgodny z wejściem: I jest zamknięty
30 PRZYKŁAD 3 Q1’ = f(Q1,Q2) Q2’ = f(Q1,Q2) Q3’ = ??? y = f(x,Q3)Kodowanie wg I wg O A B C D E F 1 1 Q2’ = f(Q1,Q2) Q3’ = ??? y = f(x,Q3)