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.

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. Np. {134, 256} • {135, 246}
= {13, 4, 5, 26}. Ma zasto −

sowanie przy sprawdzaniu warunku zerowego iloczynu i liczeniu cen.

Sumą π1 + π2 podziałów π1 i π2 nazywamy najmniejszy podział π' taki, że jeżeli stan S jest elementem jakiegoś bloku z π1 lub π2 to cały ten blok jest zawarty w jednym bloku podziału π'. Np. {123, 45} + {1, 2345} = {12345}.

Podział π1 jest nie większy od podziału π2 , czyli

π1 ≤ π2, gdy każdy blok z π1 jest zawarty w pewnym bloku π2. Np. {1, 2, 3, 45, 67} ≤

{12, 345, 67}. Ma zastoso −

wanie przy liczeniu cen i kodowaniu automatów asynchronicznych (wyzna − czanie podziałów niemnie −

jszych od wewnętrznych).

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. Ma zastosowa − nie przy wyznaczaniu rodzin końcowych (struktura kratowa, ceny).

Dobór podziałów do rodziny końcowej z grafu podziałów:

1) 1 → τ_i (L=0), 2) τ_i → τ_i (L=1), 3) τ_r → τ_i (L=1),

4) π → τ_i, π ≥ τ₁ ∗ τ₂ (L=2),

5) π → τ_i, π ≥ τ₁ ∗ τ₂ ∗... ∗ τ_k (L=k).

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 Qj od których zależy funkcja wzbudzeń przerzutnika Qk.

Cena wyjścia dla automatu Mealy'ego

:

c(yi) = n + L - 1, gdzie:

n - liczba zmiennych wejściowych, L - liczba sygnałów Qj od których zależy wyjście y_i.

Stabilne stany wewnętrzne to stany trwające przez cały czas, gdy stan wejść się nie zmienia,

s(t + τ) = s(t), τ − czas wynikający z opóźnień elementów logicznych.

Stany niestabilne to stany występujące w momencie zmiany stanu wejść,

s(t + *) ≠ s(t), τ − czas wynikający z opóźnień elementów logicznych.

Etapy metody kodowania automatów synchronicznych metodą rachunku podziałów:

1. Wyznaczyć zbiór par podziałów π → τ, gdzie τ jest pewnym podziałem dwublokowym lub w szczególności prawidłowym,

2. Narysować graf par podziałów,

3. Zaznaczyć na grafie podziały dogodne ze względu na wyjście,

4. Wybrać rodzinę Tk opt. o minimalnej cenie.

Prawidłowa praca układu asynchronicznego: wymagane jest spełnienie dwóch warunków: 1) przy zmianie stanu wejść zmienia się tylko jeden sygnał wejściowy

2) następna zmiana stanu wejść może nastąpić dopiero po czasie τ niezbędnym dla ustalenia się stanu wewnętrznego układu.

Stany pseudorównoważne to dwa stany zgodne mające stany stabilne w jednej kolumnie.

Tworzenie tablicy wyjść automatu Mealy'ego dla automatu asynchronicz − nego odbywa się dwuetapowo. Dla stanów stabilnych wpisuje się takie wyjścia jakie były dla tych stanów w pierwotnej tablicy przejść − wyjść. Dla stanów niestabilnych w odpowiadającej im klatce wpisuje się takie samo wyjście jakie ma stan stabilny, do którego układ ma przejść pod warunkiem, że w tym wierszu występuje już taka wartość wyjścia, Jeżeli takiej wartości nie ma, to wpisuje się wartość nieokreśloną.

Wyścig krytyczny

to zjawisko możliwości przejścia automatu ze stanu niestabilnego do różnych stanów stabilnych.

Wyścig niekrytyczny

to zjawisko przejścia automatu ze stanu niestabilnego różnymi drogami do odpowiadającego mu stanu stabilnego.

Kodowanie automatów asynchronicznych z zastosowaniem rachunku podziałów eliminuje wyścigi krytyczne, gdy podziały wzięte do kodowania oprócz podstawowego warunku, który muszą spełniać t.j. warunku zerowego iloczynu (jednoznaczność kodowania) spełniają wszystkie warunki separacji generowane przez podziały wewnętrzne. W szczególnym przypadku, gdy nie da się spełn

ić wszystkich warunków separacji można spróbować rozbicia na warunki elementarne (separowany musi być stan stabilny od stabilnego i niestabilnego).

Struktury automatu asynchronicznego:

Automat asynchroniczny może być zrealizowany w postaci układu kombinacyjnego objętego sprzężeniem zwrotnym lub na przerzutnikach statycznych (dla których tablica wzbudzeń jest taka jak dla synchronicznego przerzutnika RS). Realizacja na sprzężeniach zwrotnych jest zwykle prostsza.

Kolejność redukcji pierwotnych tablic przejść − wyjść automatu asynchronicznego:

1. Znaleźć grupy stanów pseudorównoważnych i połączyć je, 2. Narysować wykres zgodności i znaleźć minimalny zbiór stanów zgodnych dla automatu Moore'a oraz Mealy'ego,

3. Wyznaczyć minimalną tablicę przejść − wyjść automatu Moore'a i Mealy'ego, 4. Wyznaczyć tablicę wyjść automatu Mealy'ego.

Cechy pierwotnej tablicy przejść − wyjść automat asynchronicznego:

1. Jest zawsze typu Moore'a,

2. Posiada tyle kolumn, ile jest różnych liter wejściowych oraz tyle wierszy, ile jest stanów stabilnych, 3. W danym wierszu może wystąpić tylko jeden stan stabilny, 4. Mogą wystąpić stany pseudorównoważne.

Rozdzielaczem:

nazywamy układ formujący ciąg sygnałów od a₁ do a_n przyjmujących wartość 1 w kolejnych chwilach czasowych t = 1,2 ......,n. Rozdzielacze mogą być zbudowane z wykorzystaniem licznika z dekoderem lub rejestru przesuwającego zawierającego na jednej pozycji jedynkę. Rozdzielacze dzielimy na warunkowe (rozdział impulsów wyjściowych jest zależny od spełnienia pewnych warunków) oraz bezwarunkowe (w rytm impulsów zegarowych pojawia się stan „1” logicznej tylko na jednym wyjściu).

Podziałami prawidłowymi nazywamy podziały spełniające warunki: 1 − są to podziały dwublokowe,

2 − liczba elementów w bloku nie przekracza 2^{k − 1},

k − długość ciągu kodowego.

Podziały nieprawidłowe: to takie, w których liczba elementów w bloku przekracza 2^{k − 1}, k − długość ciągu kodowego. Mogą być wzięte do kodowania, ale tym samym odchodzi się od możliwości minimalizacji złożoności układu.

Zasady zamiany grafu przejść w GSA:

− dla automatu Mealy'ego

− dla automatu Moore'a

Specjalizowane układy sterujące:

Synteza układu Mealy'ego − wzbudzanie i sygnały sterujące zależą zarówno od stanu wewnętrznego jak i od sygnałów wejściowych i kontrolnych z układu operacyjnego. Jest stosowany gdy układ operacyjny jest układem synchronicznym. W automacie tym badanie warunków i wykonywanie następujących po nich mikrooperacji jest realizowane w jednym takcie.

Synteza układu Moore'a −

wykonywanie mikrorozkazów i sprawdzenie warunków powinno odbywać się w różnych taktach. Taktowanie jest dwufazowe, tak aby faza pierwsza taktowała automat sterujący, a faza druga bloki układu operacyjnego. Syntezę automatu prowadzi się na podstawie grafu sterowania, w którym stany wewnętrzne odpowiadają każdej z klatek sieci działań, albo przy użyciu taktowania dwufazowego łączone są mikrorozkaz z występującym po nim warunkiem.

Porównanie mikroprogramowanych i specjalizowanych układów sterujących:

a) szybkość działania-specjalizowane układy sterujące są szybsze. Na szybkość działania wpływa wyłącznie czas propagacji sygnału w elementach tworzących ten układ. Natomiast w układach mikroprogramowanych mamy do czynienia z pamięcią o wielokrotnie dłuższym czasie trwania niż czasy propagacji elementów.

b) złożoność, koszt układu − przy prostych tańsze będą specjalizowane (do 100 klatek), natomiast powyżej tańsze i prostsze będą mikroprogramowane

c) możliwość zmiany realizowanego mikroprogramu − lepsze będą układy mikroprogramowane ponieważ posiadają uniwersalną strukturę. Zmiana sprowadza się tylko do zmiany pamięci stałej.

Operatory LSA:

Y_i − operator odpowiadających symbolom stanów wyjść,

x_k
− operator warunkowy odpowiadający literom wejściowym, jeśli x_k =1 to następnym jest operator z prawej, jeśli x_k = 0, to kolejnym jest operator po ↓ miejscu skoku przy xk = 0, każda taka strzałka powinna mieć inny numer.

− miejsce skoku przy

x_k = 0, każda taka strzałka powinna mieć inny numer.

− symbol bezwarun −

kowego skoku do
.

---