Podręcznik

Metoda syntezy układu sekwencyjnego w strukturze z rys. 4.16 zostanie omówiona na przykładzie automatu z tab. 4.35, którą dla dalszych obliczeń zapisujemy po odpowiedniej permutacji wierszy, tak jak to pokazano w tabl. 4.36 a i b.

Tablica  4.36

W automacie tym niezbędna liczba wejść adresowych pamięci jest 5. Aby zrealizować ten automat z wykorzystaniem pamięci o 4 wejściach adresowych należy zaprojektować odpowiedni układ modyfikacji adresu. W tym celu dzieli się tablicę przejść-wyjść (stany następne ponumerowano liczbami naturalnymi – tablica 4.36b) na 8 części w taki sposób, aby każda z nich zawierała co najwyżej dwa różne stany następne. Oczywiście podział tablicy przejść na podtablice jest określony przez kodowanie stanów wewnętrznych i liter wejściowych automatu. Dla automatu z tab. 4.36a są to podziały $\pi=\left(\overline{s_1,s_2,s_4};\overline{s_3,s_5}\ \right)\ $ na zbiorze stanów automatu oraz θ na zbiorze liter wejściowych, ale w tym przypadku θ jest podziałem zerowym.
Dla U = {x1, x2, q1}, V = {q2, q3} podziały te wyznaczają zgodne z nimi podziały na zbiorze ponumerowanych komórek pamięci (wg tab. 4.36b).

$P\left(U\right)|P_c=\left(\overline{\left(1\right)\left(6\right)};\overline{\left(2\right)};\overline{\left(3,7\right)\left(4\right)};\overline{\left(5\right)\left(8\right)};\overline{\left(9\right)\left(13\right)};\overline{\left(10\right)\left(14\right)};\overline{\left(11\right)\left(15\right)};\overline{\left(12\right)\left(16\right)};\right)$

$P\left(V\right)=\left(\overline{1,2,3};\overline{4,5,13,14,15,16};\overline{6,7,8};\overline{9,10,11,12}\right)$

Zgodnie z metodą dekompozycji szeregowej należy teraz wyznaczyć odpowiedni podział P_G, który dla zapewnienia warunku: P(U) × P_G £ P_C musi oddzielać elementy 1 od 6; 3,7 od 4 itp. – jak to wynika z podziału ilorazowego P(U)|P_C. Łatwo sprawdzić, że jest to niemożliwe, gdyż odpowiedni podział P_G miałby w swoim pierwszym bloku B₁ dwa pierwsze bloki P(V), a w drugim – B₂ – dwa ostatnie bloki P(V), czyli

$B_1=\left\{\overline{1,2,3};\overline{4,5,13,14,15,16}\right\}$, $B_2=\left\{\overline{6,7,8};\overline{9,10,11,12}\right\}$

Tym samym po oddzieleniu 1 od 6 nie można spełnić warunku na oddzielenie elementów 3,7 od 4. Dlatego powiększamy zbiór B dodając do niego argument x₁. Zmienna x₁ oddziela elementy 1,2 od 3 (tab. 4.36b), tym samym element 3 będzie można przenieść do drugiego bloku podziału P_G.

Zatem:

V ’ = {<i>x</i>₁, <i>q</i>₂, <i>q</i>₃}

$P\left( V^{\prime }\right) =\left(\overline{1,2} ;\overline{3} ;\overline{4,5,15,16} ;\overline{13,14} ;\overline{6,} ;\overline{7,8} ;\overline{9,10} ;\overline{11,12}\right)$

$\Pi ^{\prime }_{G} =\left(\overline{1,2,4,13,14,15,16} ;\overline{3,6,7,8,9,10,11,12}\right)$

W tej sytuacji

$P( U) \cdot \Pi ^{\prime }_{G} =\left(\overline{1} ;\overline{2} ;\overline{6} ;\overline{3,7} ;\overline{4;}\overline{5} ;\overline{8;}\overline{9} ;\overline{10} ;\overline{11} ;\overline{12} ;\overline{13} ;\overline{14;}\overline{15;}\overline{16}\right)$

czyli $P( U) \cdot \Pi ^{\prime }_{G} \leq P_{C}$

Tablica prawdy funkcji g reprezentującej UMA jest podana w tablicy 4.37, a tablica określająca zawartość pamięci – w tablicy 4.38.

Tablica  4.37

Z tablicy 4.37 wyznaczamy  $g=q_2+{\bar{q}}_3x_1$. Schemat realizacji automatu pokazano na rysunku 4.17.

Rys. 4.17. Schemat logiczny realizacji automatu z przykładu 4.5

Tablica  4.38

Ten sam automat można również zrealizować w struktu­rze pokazanej na rys. 4.18. W strukturze tej wejściami bezpoś­rednimi są tylko zmienne wewnętrzne zbioru U = {<i>q</i>₁, <i>q</i>₂}, czyli V = {<i>x</i>₁, <i>x</i>₂, <i>q</i>₃}. Taką realizację uzyskamy przy podziale tablicy przejść (tab. 4.35) automatu na 4 części, z których każda zawie­rać będzie nie więcej niż 4 stany następne. Jedną z możliwości takiego podziału pokazano w tablicy 4.39a.

Tablica 4.39

Rys. 4.18. Schemat logiczny innej realizacji automatu z przykładu 4.5

Z kolei w tablicy 4.39b dokonano numeracji zajętych kratek tablicy przejść (są to jednocześnie abstrakcyjne adresy komórek pamięci ROM) oraz wprowadzono kodowanie: wstępne dla zmiennych q₁, q₂ i wtórne dla zmiennej q₃. Na tej podstawie wyznaczamy podziały P(U), P(U)|P_C oraz P(V):

$P\left(U\right)=\left(\overline{1,2,3,4,5};\overline{6,7,8,9};\overline{10,11,12};\overline{13,14,15,16}\right)$

$P\left(U\right)|P_c=\left(\overline{\left(1\right)\left(3,5\right)\left(2\right)\left(4\right)};\overline{\left(6,9\right)\left(7\right)\left(8\right)};\overline{\left(10\right)\left(11\right)}\overline{\left(12\right)};\overline{\left(13\right)\left(14\right)\left(15\right)\left(16\right)}\right)$

$P\left(V\right)=\left(\overline{1,6};\overline{10,13};\overline{2,7};\overline{14};\overline{3,8};\overline{4,11,15};\overline{9};\overline{5,12,16}\right)$

Bloki P(V) są elementami kratek należących do wierszy S₁, S₃ albo S₂, S₄, S₅ i kolumn x₁x₂ kodowanych 00, 01, 11, 10. Na przykład blok z elementami 1,6 należy do wierszy S₁, S₃ i kolumny x₁x₂ = 00, natomiast blok 10,13 należy do wierszy S₂, S₄, S₅ i tej samej kolumny x₁x₂ = 00. Z bloków podziału P(V) konstruujemy podział P_G:

$\Pi _{G} =\left(\overline{1,6,9,14} ;\overline{3,5,8,12,16} ;\overline{2,7,10,13} ;\overline{4,11,15}\right)$

Korzystamy przy tym z warunków „rozdziału” zapisanych w podziale ilorazowym P(U)|P_C. Sposób tej konstrukcji jest pokazany w tablicy 4.40.

Tablica  4.40

Oczywiście, w celu obliczenia tablicy prawdy (co pomijamy) dla funkcji g₁, g₂ modyfikujących adres należy zakodować bloki podziału P_G. Wystarczy przyjąć dla pierwszego bloku kod 00, a dla następnych kolejno 01, 10, 11. Wtedy poszczególne wiersze tej tablicy będą wyznaczane przez bloki podziałów P(U) i P_G. Na przykład blok $\overline {1,6}$ determinuje wektor x₁, x₂, q = 000, któremu odpowiadają wyjścia g₁g₂ = 00. Dalej analogicznie. Natomiast do obliczenia tablicy adresowania pamięci ROM trzeba obliczyć iloczyn P(U) × P_G:

$P( U) \cdot \Pi ^{\prime }_{G} =\left(\overline{1} ;\overline{2;}\overline{3,5} ;\overline{4;}\overline{6,9} ;\overline{7;}\overline{8;}\overline{10} ;\overline{11} ;\overline{12} ;\overline{13} ;\overline{14;}\overline{15;}\overline{16}\right)$

Bloki tego iloczynu determinują rzeczywiste adresy i zawartość komórek pamięci ROM. Na przykład, abstrakcyjnemu adresowi, reprezentowanemu przez blok $\overline 1$ odpowiada adres rzeczywisty q₁q₂g₁g₂ = 0000. W komórce ROM o tym adresie musi być zapisany kod stanu S₁, czyli q₁q₂q₃ = 000. Podobnie, dla trzeciego bloku $\overline {3,5}$  mamy adres q₁q₂g₁g₂ = 0001 oraz zawartość jako kod stanu S₄, czyli 111.