Podręcznik

Niech A = áV, S, δ, lñ będzie automatem (zupełnym lub niezupełnym), gdzie: V – zbiór liter wejściowych, S – zbiór stanów wewnętrznych, d – funkcję przejść, a l – funkcja wyjść. Przyporządkujmy (w sposób wzajemnie jedno­znaczny) elementowi (v, s) z dziedziny funkcji przejść automatu liczbę naturalną ze zbioru K = {1, …, <i>t </i>= </span><span style="line-height:150%"><span style="font-family:Symbol">ú</span></span><i><span style="line-height:150%">D</span></i>_{<span style="line-height:150%"><span style="font-family:Symbol">d</span></span>}<span style="line-height:150%"><span style="font-family:Symbol">ú</span></span><span style="line-height:150%">}. Oznaczmy odwzorowanie D_d ® K przez K i określmy na zbiorze K podział charakterystyczny P_c w następujący sposób: do jednego bloku B podziału P_c zaliczamy te elementy z K, będące obrazami (przy odwzorowaniu K) takich par (v, s) z D_d, którym funkcja przejść d przyporządkowuje taki sam stan s' z S.

Na przykład dla automatu o tablicy przejść podanej w tablicy 4.35a i odwzorowania K podanego w tablicy 4.35b podział P_c ma następującą postać:

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

Tablica 4.35

Niech P = {<i>P</i>₁, …, <i>P_w</i>} będzie zbiorem dwublokowych podziałów na K, gdzie w spełnia nierówność:

élog₂úSúù £ w < élog₂úSúù + élog₂úVúù

    Oznaczmy przez (B₁, …, B_i, …, B_t) bloki iloczynu podziałów P₁ × P₂ ×…× P_w . Ustalonej komórce pamięci (rys. 4.15) odpowiada zawsze jej adres w UMA – wektor (a₁, …, a_w), który tu będzie wyznaczany w sposób następujący: i-ta składowa wektora (a₁, …, a_w) odpowiadająca elementom k ze zbioru B_i jest 0, jeśli B_i należy do pierwszego bloku podziału P_i, natomiast 1 – jeśli B_i należy do drugiego bloku podziału P_i.

    Zgodnie ze schematem z rys. 4.15 ustalonej komórce pamięci są przyporządkowane tylko takie elementy z K, którym odpowiadają pary (v, s) o tej samej wartości funkcji przejść d auto­matu. W związku z tym adresy komórek spełniających powyższy warunek wyznaczymy za pomocą podziałów ze zbioru P wtedy i tylko wtedy, gdy:

P = P₁ × P₂ ×…× P_i ×…× P_w £ P_c

przy czym liczba zajętych komórek (liczba słów) pamięci ROM będzie 2^w ´ p, gdzie p = élog₂÷S÷ù.

   Poszczególnym podziałom P_i na K, spełniającym powyższy warunek, odpowiadają tym samym zmienne adresowe a₁, …, a_w , wytwarzane w układzie adresowania UMA. Przy ustalonym kodowaniu stanów wewnętrznych i liter wejściowych automatu, zmienne te są określonymi funkcjami zmiennych wewnętrznych q i zewnętrznych x tego automatu, a usta­lenie podziałów P_i na K zapewniających najprostszy – przy danym w – układ adresowania nie sprawia trudności. Istotną rolę w syntezie układu UMA będzie spełniać pojęcie zgodności podziałów na zbiorze K z podziałami na zbiorze stanów S lub zbiorze wejść automatu A = áV, S, d, lñ.

   Podział P na zbiorze K nazywamy zgodnym z podziałem p na zbiorze S wtedy i tylko wtedy, gdy dla dowolnych wejść v_a, v_b warunek, że s_i i s_j należą do jednego bloku podziału p implikuje warunek, że elementy z K przyporządkowane odpowiednio parom (v_a, s_i) oraz (v_b, s_j) należą do jednego bloku podziału P.

   Podział P na K nazywamy zgodnym z podziałem q na V wtedy i tylko wtedy, gdy dla dowolnych stanów s_a, s_b warunek, że v_i, v_j należą do jednego bloku podziału q implikuje warunek, że elementy z K przyporządkowane parom (v_i, s_a) oraz (v_j, s_b) należą do jednego bloku podziału P. W szczególności podział P na zbiorze K może być zgodny ze zbiorem  {</span><span style="line-height:150%"><span style="font-family:Symbol">p, q</span></span><span style="line-height:150%">}, jeśli jest zgodny zarówno z podziałem p, jak też q. Natomiast podział P będziemy nazywać zgodnym ze zbiorem {p₁,</span></span><span style="line-height:150%"> …</span><span style="line-height:150%"><span style="font-family:Symbol">,</span></span> <span style="line-height:150%"><span style="font-family:Symbol">p_a} podziałów na S ({</span><span style="line-height:150%"><span style="font-family:Symbol">q</span></span>_{<span style="line-height:150%">1</span>}<span style="line-height:150%">, …, </span><span style="line-height:150%"><span style="font-family:Symbol">q_b</span></span><span style="line-height:150%">} podziałów na V) wtedy i tylko wtedy, gdy P jest zgodny z podziałem p: p = p₁ × p₂ ×…× p_a (gdy P jest zgodny z podziałem q: q = q₁ × q₂ ×…× q_b).

Na przykład dla automatu o tablicy przejść podanej w tablicy 4.35a i funkcji K podanej w tablicy 4.35b podział:

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

jest zgodny z podziałem $\pi=\left(\overline{s_1,s_3};\overline{s_2,s_4};\overline{s_5}\ \right)\ $natomiast:

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

jest zgodny ze zbiorem podziałów {</span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:Symbol"><span style="color:black">p, q</span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">}: $\pi=\left(\overline{s_1,s_2,s_3};\overline{s_4,s_5}\ \right)$ , $\theta=\left(\overline{v_1,v_2};\overline{v_3,v_4}\ \right)$

Obecnie przedstawimy metodę selekcji podziałów na K umożliwiającą uproszczenie układu adresowania pamięci dla układu o schemacie blokowym pokazanym na rys. 4.15, w którym w (liczba zmiennych adresowych) spełnia warunek:

élog₂úSúù £ w < élog₂úSúù + élog₂úVúù

Punktem wyjścia rozważań będzie zakodowana tablica przejść automatu A = áV, S, d, lñ, gdzie élog₂úSúù  = p, élog₂úVúù = n. Załóżmy, że podziały kodujące stany wewnętrzne są p₁, …, p_p, natomiast podziały kodujące wejścia są q₁, …, q_n. Dla każdego podziału p i każdego podziału q znajdujemy zgodny z nimi podział P. W celu zapewnienia jednoznaczności kodowania zmiennych adresowych a₁, …, a_w i jednocześnie odpowiedniego przyporządkowania elementów ze zbioru K – przy ustalonej funkcji K –poszczególnym komórkom pamięci, należy utworzyć w podziałów P na zbiorze K takich, że:

P₁ × P₂ ×…× P_w £ P_c

gdzie P_c jest podziałem charakterystycznym automatu A.

Proces generacji podziałów P ułatwia pojęcie r-przydatności podziału (zbioru podziałów) P względem podziału P_c (porównaj rozdz. 3). Zauważmy bowiem, że warunek 4-1 mogą spełniać wyłącznie takie podziały P, które są r-przydatne względem P_c, gdzie r £ w.

Wszystkich podziałów P, zgodnych z podziałami p oraz q ustalonymi przez kodowanie automatu A, jest n + p. Oznaczmy je przez P_z = {<i>P</i>₁, …, <i>P_n</i></span>_{<span style="line-height:150%"><span style="font-family:Symbol">+</span></span>}<i>_{<span style="line-height:150%">p</span>}</i><span style="line-height:150%">}. Sytuacja optymalna będzie więc wtedy, gdy w zbiorze P_z istnieje w-przydatny (względem P_c) podzbiór. W tym przypadku każda zmienna adresowa a będzie funkcją jednej zmiennej – wewnętrznej q albo zewnętrznej x – automatu A. Jeśli ze zbioru P_z nie można wyselekcjonować w-elementowego podzbioru w-przydatnego względem P_c, to do dalszych obliczeń należy wybrać u-przydatny (względem P_c) podzbiór ${P_{i_1},...,P_{i_u}}$  , gdzie u = max. Pozostałe w – u podziały należy dobrać tak, aby:

$P_{i_1}\cdot\ P_{i_2}\cdot\ldots\ P_{i_u}\cdot\ P_{i_{u+1}}\cdot\ldots{\cdot P}_{i_w}\le\ P_c$

Oczywiście podziały $\left\{P_{i_{u+1}}\cdot\ldots{\cdot P}_{i_w}\right\}$  nie należą do zbioru P_z. Odpowiednia realizacja automatu jest przedstawiona na rys. 4.16. W układzie z tego rysunku wejścia adresowe a₁, …, a_u są funkcjami jednej zmiennej wewnętrznej q albo zewnętrznej x automatu, natomiast wejścia a_u+1, …, a_w są funkcjami, których argumenty należą do zbioru {<i>q</i>₁, …, <i>q_p</i>, <i>x</i>₁, …, <i>x_n</i>}.

Przyjmijmy, że strukturę układu UMA będziemy określać układem liczb (b₁, …, b_i, …, b_w), gdzie b_i jest liczbą argumentów zmiennej adresowej a_i.

Rys. 4.16. Realizacja automatu wg warunku 4-1

Dla schematu automatu z rys. 4.16 mamy więc (b₁, …, b_u, b_u+1, …, b_w), przy czym b_j = 1 dla 1 £ j £ u oraz 1 < b_j £ m+p dla u < j £ w. Przy ustalonym kodowaniu stanów wewnętrznych i liter wejściowych automatu, najprostszą strukturę UMA (dla danego w oraz u = max) uzyskamy wtedy, gdy zmienne adresowe będą dobrane tak, że:

$\sum\limits ^{w}_{i=u+1} b_{i} =min.$

Z powyższych rozważań wynika, że największy wpływ na stopień skomplikowania układu adresowania ma ta jego część, w której zmienne adresowe są zależne od więcej niż jednego argumentu. Dlatego też najistotniejszy jest taki dobór kodowań stanów wewnętrznych i liter wejściowych automatu, przy którym można uzyskać maksymalny zbiór podziałów P (zgodnych z p albo q) w-przydatny względem P_c Do kodowania należy więc wybierać takie podziały, których r-przydatność względem P_c jest równa co najwyżej w. Kodowania te będziemy generowali korzystając z faktu, że r-przydatność podziału P zgodnego z podziałem p = (B₁, …, B_i, …, B_a) jest równa:

$r=\left\lceil\log_2\alpha\right\rceil+\left\lceil\log_2max\left|\bar{\delta}\left(B_i\right)\right|\right\rceil$

gdzie: B_i – blok podziału p, $\bar{\delta}$  – globalna funkcja przejść, a symbol  $max\left|\bar{\delta}\left(B_i\right)\right|$ oznacza liczbę elementów w najliczniejszym zbiorze $\bar{\delta}\left(B_i\right)$. Analogiczne zależności można wyprowadzić dla podziałów P zgodnych z q,  jak też zgodnych z {</span><span style="line-height:150%"><span style="font-family:Symbol">p, q</span></span><span style="line-height:150%">}.

            Z powyższego wynika, że na zbiorze K ponumerowanych komórek pamięci sposób postępowania jest analogiczny do dekompozycji funkcji boolowskiej i polega na wykonaniu następujących czynności:

1. Wybór zbioru U (wstępne kodowanie)

2. Określenie podziałów:

            P(U),   P_g = P(V)

3. Wyznaczenie podziału P_g ³ P_g

            P(U) · P_g £ P_F

            (czasami istnieje potrzeba wprowadzenia zbioru W)

4. Obliczenie funkcji G reprezentującej układ modyfikacji adresu oraz funkcji H reprezentującej adresowanie pamięci ROM.