Dlaczego rachunek podziału wpływa nauproszczenie układu ?

Przy kodowaniu dąży się do znalezienia takich podziałów, aby funkcje przejść automatu zakodowanego zgodnie z tymi podziałami zależały od jak najmniejszej ilości zmiennych.

Co to jest para podziałów ?

Para podziałów П1 i П 2 stanów wewnętrznych to uporządkowana dwójka podziałów П 1--> П2 taka, że dla każdych dwóch stanów zawartych w pewnym bloku z П 1 i dla każdego xi
X, xi - następniki tych stanów zawarte są w pewnym bloku podziału П 2

Co to są podziały prawidłowe ?

Podziałami prawidłowymi nazywamy podziały spełniające warunki:

- są to podziały dwublokowe

- liczba elementów każdego bloku 2k - 1

Etapy kodowania automatów synchronicznych z zastosowaniem rachunku podziałów

- Wyznaczyć zbiór par podziałów gdzie П --> τ gdzie τ jest pewnym podziałem dwublokowym lub w szczególności prawidłowym

- Narysować graf par podziałów

- Zaznaczyć na grafie podziały dogodne ze względu na wyjście

- Wybrać rodzinę Tkopt. o minimalnej cenie

Co to jest rodzina końcowa T_k i rodzina końcowa optymalna T_kopt

Rodziną końcową podziałów Tk nazywamy zbiór podziałów który można przyjąć do kodowania, tzn. zbiór spełniający warunek zerowego iloczynu

Rodziną końcową optymalną Tkopt nazywamy rodzinę końcową Tk wyznaczającą kod dający najprostsze funkcje przejść i wyjść (najprostszy układ)

Cena podziału wewnętrznego

Ceną podziału wewnętrznego c(τ_i) nazywamy szacunkową ilość zmiennych od których zależy funkcja wzbudzeń przerzutnika Qi zakodowanego zgodnie z τ_i zmniejszoną o 1.

Cenę podziału wewnętrznego wyznacza się z zależności

c(τ_i) = n + l - 1 gdzie n - liczba zmiennych wejściowych

l - liczba sygnałów Ql od których zależy funkcja wzbudzeń przerzutnika Qi

Cena sygnału wyjściowego

Dla automatu Moore'a jako cenę sygnału wyjściowego przyjmuje się c(yi) = l - 1 gdy yi = λ(Q1,..., Ql)

Dla automatu Mealy'ego cena sygnału wyjściowego wzrasta o liczbę zmiennych wejściowych n c(yi) = n + l - 1

Łączna cena układu uwzględniająca zarówno cenę podziałów jak i cenę wyjść wyraża się wzorem c = Σc(τ_i) +Σc(yi)

Czy do kodowania automatów synchronicznych można brać podziały nieprawidłowe ? Jeśli tak to czym to skutkuje ?

Tak, można brać podziały nieprawidłowe ale spowoduje to wzrost liczby elementów z pamięcią użytych do prawidłowego działania naszego automatu.

Struktura automatu Mealy'ego

Struktura automatu Moore`a

X - alfabet wejściowy (zbiór stanów wejściowych);

S - alfabet wewnętrzny (zbiór stanów wewnętrznych);
Y - alfabet wyjściowy (zbiór stanów wyjściowych);

δ - funkcja przejść δ = f(X,S);

λ - funkcja wyjść dla automat Mealy'ego λ = f(X,S) dla automatu Moore'a λ =f(S)

Sposoby opisu automatów

- opis słowny - wykresy czasowe- tablica przejść wyjść - grafy stanów układów

Na podstawie opisu słownego, wykresu czasowego lub grafu przejść buduje się tzw. pierwotną tablicę przejść-wyjść automatu. Każdej kombinacji sygnałów wejściowych i wyjściowych przypisuje się odrębny stan stabilny automatu. Należy rozróżnić stany wewnętrzne o identycznych sygnałach wejściowych lecz różnych stanach następnych (stany obciążone różną historią)

Warunki jakie musi spełniać zbiór maksymalnych stanów zgodnych Φopt

- każdy stan musi wchodzić co najmniej do jednej grupy (warunek pełności zbioru)

- dla każdej pary każdego zbioru muszą być spełnione wymogi zgodności warunkowej

Etapy minimalizacji automatu synchronicznego

- zbudowanie tablicy trójkątnej (wpisujemy warunki i wykreślamy wszystkie klatki o sprzecznych wyjściach; klatki niewykreślone, bez względu na zawartość, odpowiadają parom stanów zgodnych

- tworzymy graf relacji zgodności (tworzymy maksymalne grupy stanów zgodnych)

- wyznaczamy zbiór Φ i Φopt

Pokryciem C zbioru S nazywamy zbiór podzbiorów tego zbioru, których suma równa jest S C = { B1, B2, . . ., Bn };B1 ჈ B2 ჈ . . . ჈ Bn = S

Podziałem ၰ zbioru S nazywamy zbiór rozłącznych podzbiorów tego zbioru, których suma równa jest S ၰ = { B1, B2, . . .,Bn };Bi Ⴧ Bj = ၆ dla i Ⴙ j ;B1 ჈ B2 ჈ . . . ჈ Bn = S

Podzbiory Bi nazywamy blokami i oznaczamy kreskami nad elementami zbioru S np. podział ၰ = {B1, B2, B3} = { 13, 4, 25 } dzieli zbiór S = {1,2,3,4,5} na trzy bloki B1= {1,3}; B2={4}; B3={2,5}

Iloczynem ၰ1 • ၰ2 podziałów ၰ1 i ၰ2 nazywamy podział, którego blokami są przecięcia bloków podziału ၰ1 z blokami podziału ၰ2

Sumą ၰ1 + ၰ2 podziałów ၰ1 i ၰ2 nazywamy najmniejszy podział ၰ' taki, że jeżeli stan S jestelementem jakiegoś bloku z ၰ1 lub ၰ2 to cały ten blok jest zawarty w jednym bloku podziału ၰ'

Rodziną końcową podziałów Tk nazywamy zbiór podziałów który można przyjąć do kodowania, tzn. zbiór spełniający warunek zerowego iloczynu

Rodziną końcową optymalną Tk opt nazywamy rodzinę końcową Tk wyznaczającą kod dający najprostsze funkcje przejść i wyjść (najprostszy układ)

Para podziałów ၰ1 i ၰ2 stanów wewnętrznych to uporządkowana dwójka podziałów ၰ1 Ⴎ ၰ2 taka, że dla każdych dwóch stanów zawartych w pewnym bloku z ၰ1 i dla każdego xi ჌ X, xi - następniki tych stanów zawarte są w pewnym bloku podziału ၰ2

Ceną podziału wewnętrznego c(ၴi) nazywamy szacunkową ilość zmiennych od których zależy funkcja wzbudzeń przerzutnika Qi zakodowanego zgodnie z ၴi zmniejszoną o 1.

Podziałem zewnętrznym ၰxj (yi) dla automatu Mealy'ego nazywamy podział, którego bloki zawierają tylko takie stany którym przy sygnale wejściowym xj odpowiadają jednakowe sygnały wyjściowe.

Podziałem zewnętrznym ၰ(yi) dla automatu Moore'a nazywamy podział, którego bloki zawierają stany którym odpowiadają jednakowe sygnały wyjściowe

W układach synchronicznych wyróżnia się stabilne stany wewnętrzne trwające przez cały czas, gdy stan wejść się nie zmienia

W układach asynchronicznych wyróżnia się również stany niestabilne występujące w momencie zmiany stanu wejść.

Kodowanie z zastosowaniem rachunku podziałów. Podstawowym warunkiem jaki musi spełnić kod przyjęty do kodowania automatu asynchronicznego jest zlikwidowanie wyścigów krytycznych. Zastosowanie rachunku podziałów pozwala nie tylko usunąć wyścigi lecz również uzyskiwać układy o minimalnej złożoności.

Ta metoda kodowania dopuszcza równoczesną zmianę stanu kilku elementów pamięci .

Etapy kodowania z zastosowaniem rachunku podziałów. Wypisać podziały wewnętrzne i spośród nich albo podziałów prawidłowych większych od wewnętrznych wyznaczyć podziały do kodowania. Z wypisanych podziałów utworzyć rodziny końcowe. u Spośród rodzin końcowych wyznaczyć rodzinę optymalną uwzględniając zarówno uproszczenie funkcji przejść jak i funkcji wyjśću Zakodować tablice przejść, dookreślając stany występujące na drogach przejść Dla określonej struktury układu wyznaczyć funkcje wzbudzeń. Narysować schemat ideowy układu .

Minimalizacja pierwotnych tablic przejść-wyjść jest operacją prostszą niż minimalizacja tablic automatów synchronicznych: tablice pierwotne są tablicami automatu Moore'a; stany stabilne występują w wierszach pojedynczo; stan niestabilny może wystąpić tylko w tej kolumnie, w której występuje odpowiadający mu stan stabilny .

Kodowanie automatów asynchronicznych polega, podobnie jak w automatach synchronicznych, na przyporządkowaniu stanom wewnętrznym s stanów elementów pamięciowych Q1,..., Qk

C = { B1, B2, . . ., Bn }

B1 ჈ B2 ჈ . . . ჈ Bn = S

Zakodowaniu zbioru stanów wewnętrznych S przy pomocy k sygnałów Q1, . . ., Qk odpowiada k podziałów dwublokowych ၴ1, ၴ2, . . ., ၴk.

---