Rok / Year: 2013
Svazek / Volume: 15
Číslo / Issue: 2
Je řadič počítače sekvenční či kombinační? Is the controller of computer sequential or combinational? Josef Bokr
[email protected] Fakulta aplikovaných věd ZČU v Plzni
Abstrakt: Článek se zabývá řízením operačních automatů počítačů a ukazuje, že při daném vývojovém diagramu jejich činnosti je příslušný statický řídicí automat někdy nutné opatřit rekonstruktorem stavů operačního automatu.
Abstract: The article deals with the management of operational machines of computers and shows that in the flowchart of their activity is still relevant static automat that need to be obtain with state observer operating the machine.
VOL.15, NO.2, APRIL 2013
Je řadič počítače sekvenční či kombinační? Josef Bokr Fakulta aplikovaných věd ZČU v Plzni e-adresa: bokr @ kiv.zcu.cz
Anotace: Článek se zabývá řízením operačních automatů Buď dán (stavový) Mealyho konečno-automatový model počítačů a ukazuje, že při daném vývojovém diagramu jejich deterministického logického objektu činnosti je příslušný statický řídicí automat někdy nutné opatřit rekonstruktorem stavů operačního automatu. 〈 X , S ,Y , δ , λ , s0 〉, Klíčová slova: chování, počítač, relační struktura, vývojový diagram, operační a řídicí automat, rekonstruktor stavů.
kde S je stavová abeceda, δ je přechodová
δ : S × X → S : s, x a s′ a λ je výstupní
λ : S × X → Y : s, x a y
1 Úvod Protože se neustále tvrdí, že chování řadiče počítače je sekvenční, nehledě na jeho chování kombinační, zmiňme se nejprve o chování logického objetu. Uvažujme proto iniciální fenomenologický model deterministického objektu
kde X, Y je abeceda příslušně vstupní, výstupní, B je chování objektu +
+
→ Y : s0 , xi1 xi 2 ,..., xim a a y j1 y j 2 ,..., y jm ,
přičemž X+, Y+ je množina všech slov (vyjma prázdného) konečné délky nad abecedou příslušně X, Y a s0 je počáteční stav. Snad překvapí výskyt počátečního stavu s0 v modelu, kdy se na objekt nazírá jako na černou schránku. Ale neuvažovat s0 by znamenalo, že chování, byť deterministického objektu je relací +
(
)
(
+
(
)
a stěží bychom podle chování rozlišovali objekt deterministický a nedeterministický. Platí-li pro libovolná rovná vstupní podslova délky jedna xik, xil (k ≠ l) : xik = xil vstupního slova xi1 xi2 … xik-1 xik xik+1 … xil-1 xil xil+1 …xim, že pro výstupní podslova yjk, yjl délky jedna výstupního slova slovo yj1 yj2 … yjk-1 yjk yjk+1, … yj,l-1 yjl yj,l+1 … yjm = B (s0, xi1 xi2 … xim) je jednak yjk, = yjl a jednak yjk, ≠ yjl , hovoříme příslušně o chování jednak kombinačním a jednak sekvenčním.
92
S ≥ 2 , neboť pro
je
(
)
λ s i ,k −1 , x ik =
= y jk ≠ λ si ,l −1 , xil = y jl , zatímco pro kombinační objekt
může
( = λ (s
být
S =1,
) )= y
protože
i ,l −1 , x il
může jl
pro být
(
)
δ s i , k −1 , x ik = s k =
(
)
λ s i ,k −1 , x ik = y jk =
, ale nemusí. Proto raději hovoříme o
objektech statických, které se chovají kombinačně a dynamických, jejichž chování může být jak kombinační tak i sekvenční. Fenomenologickým modelem statického deterministického logického objektu je 〈X, Y, B〉, kde B : X → →Y a konečno-automatovým modelem pak je 〈X, Y, λ〉, kde λ : X → → Y, vždy ovšem pro S ≠ ∅ a S = 1 . Položíme-li totiž S = ={s0}, potom lze přechodovou funkci δ : {s0 }× X → {s0 } formálně ignorovat a Mealyho výstupní funkci λ :{s0}× X → → Y modifikovat na tvar λ : X → Y : x a y . 2
B : X × Y : xi1 xi 2 ,..., xim , y j1 y j 2 ,..., y jm
)
δ si ,k −1 , xik = sk ≠ δ si ,l −1 , xil = sl
= δ s i ,l −1 , x il = s l
〈 X , Y , B , s0 〉,
B : {s0 }× X
funkce. Sekvenční objekt vyžaduje
Relační struktury
Uspořádanou trojici 〈L, V, S〉, kde L, V je množina příslušně návěští a vrcholů a S je množina hran
( )
S : L × U V : li , v1 , v2 ,..., vi (= li (v1v2 ...vi )) i
i∈I
(
)
Přičemž I je množina indexů I ⊆ { j} j =1 , li je i-místné m
návěští a l i v1 v 2 ...v i je i-místná hrana, nazýváme relační strukturou, krátce jen strukturou.
VOL.15, NO.2, APRIL 2013
takové, že S = {β (1), α (12 )}, T1 = {α (ab ), α (ac )},
Příklad 1.: Aritmetika celých čísel je relační struktura A = + (abc ) a + b = c U − (abc ) a − b = c U
{ U {× (abc )
} { ab = c}U {: (abc )
}
}
T2 = {β (a ), α (ab ), α (bc )} , T3 = {β (a ), α (aa ), α (ab )}.
a:b = c .
Nakreslením struktury rozumíme návěštími li hranově ohodnocený diagram, jehož vrcholům (kroužkům) odpovídají vrcholy vi spojené orientovanými čarami vedenými od v1 k v2, v3,…, vi.
{l } , { j} 5
Příklad 1.: Nakreslete diagram struktury
{l1 (1), l 5 (3), l 2 (12), l 3 (22 ), l 4 (234 ), l2 (3245)} l1
j i =1
5 j =1 ,
– obr.1.
Homomorfismus h1 : S ⇒ T1 neexistuje, h2 : S ⇒ T2: 1 a a , 2 a b , h3: S ⇒ T3: 1 a a , 2 a b nebo 1 a a , 2 a a. Hranově ohodnocený graf 〈L,V, E, f 〉, kde L, V, E je množina příslušně binárních návěští, vrcholů, binárních hran (E ⊆ V2) a f : E → L : vi , vi +1 a a l j , je spec. případem
struktury. Zvl. případ grafu nazýváme řetězcem (slovem) nad abecedou L, je-li E = {l1 (v1v2 ), l 2 (v2 v3 ) , ..., l m (vm vm +1 )}
(= {l1l2 ...lm }) ; nakreslením řetězce je diagram:
4
1
2
l5 3
l2
5
Množinu vrcholů z definice struktury S označme symbolem Nod (S). Buď S a T struktury; funkci h: Nod (S) → → Nod (T) takovou, že
a) l
2
l
c)
a
r 2
α
a r
3
b
T h
d)
c)
d)
3
β a
R
α
α
c
2
l b
r 3
T
b) pravidla při c) homomorfismu h : T ⇒ R, d)výsledná struktura z příkl. 3.
α
b
h
l
1
Obrázek 3. Substituce do a) S za R podle
β a
α
r
a l
c
r α b
l β 1
r
l
l
R
Příklad 2.: Buď S a T1, T2, T3 struktury – obr.2. tj.
α
m+1
b) 1
nazýváme homomorfismem z S do T (h : S ⇒ T).
α
lm
homomorfismu h : T ⇒ R (obr.3.c)) dostaneme strukturu na obr.3.d).
l i (v1 v 2 ... v i ) ⇒ l i (h (v1 ) h (v 2 ) ... h (v i ))
b)
m
Příklad 3.: Buď dána [1] struktura S (obr.3.a)) a její podstruktura R; podle pravidla T → V (obr.3.b)) při
Obrázek 1. Nakreslení struktury z příkl.1.
2
3
(produkce) T → V, existuje-li homomorfismus h : T ⇒ R, rozumíme záměnu R strukturou V v dané struktuře S (podrobněji v [1]).
l3
a)
l2
2
Nazvěme R podstrukturou struktury S (R ⊆ S), je-li množina hran R podmnožinou množiny hran struktury S. Substitucí za podstrukturu R do struktury S podle pravidla
l4
l2
l1
1
Příklad 4.: V dané struktuře S [1]nahraďme její podstrukturu (obr.4.a)) podle pravidla T → V (obr.4.b)) při homomorfismu
b
h : T⇒ R (obr.4.c)) strukturou V (obr. 4.d)) při h (γ) = 5 a h (δ) = 6.
Obrázek 2. Struktury a) S, b)T1, c) T2, d) T3 z příkl. 2.
93
VOL.15, NO.2, APRIL 2013
a)
b) l
1
a
2
l
r
r
α
γ
β
δ
b
3
V
T
R
d)
h
r 2
r
a l
l h
3
1
l
2
l
b
{
5
3
{
b) pravidla při c) homomorfismu h : T⇒ R, d) výsledná struktura z příkl. 4.
b)
α
2 l
γ
T
T
c)
l
2 l
2
4
{
}
3
3 r
predikát i relaci označujeme rel. Jsou-li v1, v2,…, vm vrcholy rozšířené aritmetiky celých čísel A a identifikátory l1, l2, …, lm řetězce, jejichž prvním symbolem je malé písmeno latinské abecedy a dalšími symboly jsou malá písmena nebo číslice, tvoří data počítače relační strukturu s množinou hran D = l1( v1 ) , l2 ( v2 ) ,... , lm ( vm ) U A . Hodnotou výrazu
Příklad 6. : Buď D = {anna (4), iva (2), jan (-2), x (-5)} U A [1]. Potom f (iva + ((anna + 3) × jan + 4)× × x) = 2 + (4 + 3) × (-2) + 4) × (-5) = 52 a f ((iva × × anna - 3) > (jan + 2)) = = f (2 × 4 – 3 > (-2)+ 2) = yes.
d) 1
a , b ∈ rel , přičemž
tehdy a jen tehdy, když li vi ∈ D .
r
b
a, b ∉ rel , a, b a yes pro
rozumíme hodnotu funkce f : {l1 , l2 ,..., lm } → NodA : li a vi
a
l
U {< (ab yes) a < b} U {< (ab no ) a < b}
2
Příklad 5.: Nahraďme v dané struktuře S [1] její podstrukturu R1,2 (obr. 5.a)) podle pravidla T→ V (obr. 5.b)) při homomorfismu h1 : T⇒ R1: a a 2, b a 2 , h2 : T ⇒ R1: a a 1, b a 2 . Odtud vzniklé struktury obr.5.c), obr. 5.d).
l
}
vacím predikátem je funkce Z → {yes, no} : a, b a no pro
a
} {
a vytvoříme rozšířenou aritmetiku A. Uvažujme totiž binární relaci rel : Z2: 〈a, b〉; rozhodo-
Obrázek 4. : Substituce do a) S za R podle
1
}
platí-li či nikoliv relace <, ≤, =, ≠. Jinými slovy, k relační struktuře A z příkl. 1. připojíme = (ab yes) a = b U = (ab no ) a ≠ b U
6
a)
Počítače s libovolným přístupem
Počítač s libovolným přístupem se skládá z paměti a procesoru (řadič a aritmeticko-logická jednotka), přičemž paměť umožňuje kdykoliv přečíst nebo přepsat její obsah. Paměť budeme modelovat relační strukturou, a procesor produkcemi. Předpokládáme, že obsah paměti sestává z dat a programu. Program zachytíme vývojovým diagramem s tím, že se během výpočtu program nemění. Data jsou uložena v adresovaných paměťových buňkách a předpokládáme, že jsou celočíselná. Procesor provádí aritmetické operace (viz relační struktura z příkl.1.). Aritmetiku celých čísel rozšiřme o relace <, ≤, =, ≠; proto, je-li Z množina celých čísel, je Nod (aritmetika celých čísel) = n n ∈ Z U {yes, no}podle toho,
l
l
c)
3
Vývojový diagram (VD) je struktura, která: obsahuje dosazovací (operační) a rozhodovací příkazy (viz níže), - disponuje vrcholy vp, vf příslušně počátečním, koncovým, tj. vp, vf ∈ Nod (VD) a start (vp), end (vf) ∈VD, přičemž každý vrchol z VD je na cestě z vp do vf, - z každého vrcholu až na vf vychází právě jedna hrana; z vrcholu koncového žádná hrana nevychází; např. obr.6.
r
-
4
Obrázek 5.: Substituce do a) S podle b) pravidla při homomorfismu c) h1, d) h2 z příkl. 5.
94
VOL.15, NO.2, APRIL 2013
1 no
a=b
start
C
yes
yes
3 yes
a>b
no
1
start
a ≥0
no
2 2 end
4
5
a a (- a)
l a a-b
r a b-a
3
end
Obrázek 8. Příklad snímku paměti.
Obrázek 6. Příklad vývojového diagramu. Kromě dat obsahuje paměť program – vývojové diagramy, jimiž se procesoru předepisuje implementace posloupností instrukcí (příkazů). Pří-kazy jsou dosazovací a rozhodovací a představují hrany relační struktury VD. Dosazovací (operační) příkaz je binární hrana, jejíž návěští je řetězec l a a , kde l je identifikátor a a je aritmetický výraz (obr.7.a)) – l a a (m n). Rozhodovací příkaz je ternární hrana, jejíž návěští je rozhodovací výraz (obr.7.b)) – rel (kmn).
b)
a) m
k yes
la a n
q
m
rel
no n
Je-li řízení na dosazovacím příkazu l a a , provede procesor zmíněný příkaz tak, že stanoví hod-notu aritmetického výrazu a, kterou dosadí za l jako novou hodnotu. Buď proto snímek F, v němž je říze-ní na dosazovacím (operačním) příkazu l a a (m n) s tím, že l a i , l a j . Pravidlem d v F obdržíme snímek F′ , je-li F′množina hran F ′ = (F − {l (i ), C (m )}) U {l ( j ), C (n )}.
Je-li řízení na rozhodovacím příkazu, procesor rel stanoví pravdivostní hodnotu logického výrazu. Jestliže je hodnota výrazu yes, no, přesune se řízení na ten či onen vrchol. Mějme proto snímek F, v němž je řízení na rozhodovacím příkazu rel (kmn) a hodnota rel budiž yes; pravidlem ryes dostaneme nový snímek F ′ = (F − {C (n )}) U {C (m )} . Je-li hodnota relno, potom pravidlem rno obdržíme nový snímek F ′ = (F − {C (m )}) U {C (n )} . Procesor počítače je pak množina pravidel {d, ryes, rno}. Jednotlivé produkce
Obrázek 7. Hrana : a) operační, b) rozhodovací
d = {l (i ), f (a )( j ), C (m ), l a a (mn )} →
Během výpočtu se ve VD pohybuje tzv. řízení – hrana C (v), kde v je vrchol struktury řízení R označující aktuálně prováděný příkaz. Data, VD a řízení je modelem aktuálního výpočtu. Snímek F je struktura sestávající z D U VD U R , která popisuje uspořádání paměti v některém okamžiku provádění výpočtu; např. obr. 8.
→ {l ( j ), f (a )( j ), l a a (mn ), C (n )}
ryes = { f (rel )(i ), yes (i ) , C ( j ), rel ( jmn )} →
→ { f (rel )(i ), yes (i ) , rel ( jmn ), C (m )},
rno = { f (rel )(i ), no (i ) , C ( j ), rel ( jmn )} →
→ { f (rel )(i ), no (i ) , rel ( jmn ), C (n )}
viz obr. 9 a), b), c).
95
VOL.15, NO.2, APRIL 2013 Rel
a) i
C m la a
f (a)
což příslušně znamená, že se bezprostředně po dané mikroinstrukci při daných rozhodovacích predikátech vyvolá příslušně nutně a právě jedna následující mikroinstrukce.
la a
n
j
∨ reli = yes; reli & relj = no (i ≠ j),
i =1
m
l, f (a) j
n
C
Příklad 7.: Pro VD z obr. 11. platí
(rel ∨ rel ) rel rel 1
b) C yes
i
j no
rel
yes
C
rel1
yes
∨
rel1 rel2 = yes.
yes
rel2 no
n rel1 ∨ rel 2
rel1 rel 2
f (rel),no j
i no
rel
Obrázek 11. VD z příkl. 7.
j yes
n
m
m
Disponujme iniciálním fenomenologickým modelem operačního automatu
no
rel C
OA = 〈 X , Rel , B , s0 〉,
n
kde X, Rel je abeceda příslušně strojového řízení mikrooperací, binárních rozhodovacích predikátů, B je chování
Obrázek 9. Produkce a) d, b) ryes, c) rno.
4.
= no a rel1 ∨ rel2
no
rel
m
2
no
j yes
n
m c) f (rel),no i C
1
f (rel),yes
f (rel),yes i
2
B : {s0 }× X
Logické řízení
Popis činnosti číslicových zařízení vychází z klasické představy [2] zařízení jako soustavy automatického logického řízení (obr.10.) sestávající z deterministického řídicího (ŘA) a deterministického operačního (OA) automatu. Za operační automat
ŘA
x
+
+
→ Rel : s0 , ξ a ρ
zadané VD činnosti OA a s0 je počáteční stav. Protože chování B zachovává délky a prefixy slov, lze místo chování B zavést redukované chování Br [4] B : {s0 }× X → Rel : s0 , ξ a proj ρ ρ (= rel ), r proj ρ je projekce na ρ -osu ξ = ρ a +
(
kde
)
rel ∈ {yes, no}. Hledáme konečno-automatový model ŘA
OA
rel
ŘA = 〈 Rel , Q , X , δR , λR , q0 〉,
Obrázek 10. Soustava logického řízení
kde Q je stavová abeceda, δR je přechodová funkce – řízení C (q′) δ R : Q × Rel → Q : q, rel a q ′ ,
považujeme např. registry, čítače, paměti, sčítačky, sběrnice apod. a řídicí automat je pak podstatnou částí řadiče. Elementární kroky činnosti (elementární dosazovací příkazy) OA jmenujeme mikrooperace [3]; každá mikrooperace se vyvolá strojovým řízením x, a proto označujeme mikrooperace symbolem příslušné-ho strojového řízení. Vyvolá-li se několik mikrooperací souběžně, hovoříme o mikroinstrukci [3]. Pro rozhodovací predikáty (rel ∈ Rel) platí [3]:
96
λR je Mealyho výstupní
λ R : Q × Rel → X : q, rel a x = Br (s0 , rel ) funkce a q0 je počáteční stav, Odtud, zobecníme-li přechodovou δR a výstupní λR funkci , +
δ R : Q × Rel → Q : q , ρ a q ′′ ,
VOL.15, NO.2, APRIL 2013
λ R : Q × Rel → X : q , ρ a x = Br (s0 , ξ ) +
tak,
a)
δ R : (q, relρ ) = δ R (δ R (q, rel ), ρ ) = δ R (q ′, ρ )
že
a
λ R : (q , relρ ) = λ R (δ R (q , rel ), ρ ) = λ R (q ′, ρ ) ,což předepisuje
návod na rozmístění stavů ŘA ve VD činnosti OA. Stavy q řídicího automatu ztotožníme s vrcholy relační struktury VD (obr. 7.) tak, že: - stav q0 ztotožníme vrcholem počátečním a koncovým, - různé stavy qi (qi ≠ q0) ztotožníme s různými koncovými vrcholy dosazovacích (operačních) hran identifikovaných s počátečními vrcholy hran rozhodovacích. Protože disponujeme pouze fenomenologickým modelem OA, nelze očekávat, že výstupní funkce Λ O : S → Rel : s a rel
OA = 〈 X , S , Rel , δO , ΛO , s0 〉,
δ O : S × X → S : s, x a s′ je funkce přechodová, bude obecně prostá. Pro potenciální konečno-automatový model soustavy automatického logického řízení (obr.10.) potom je SŘ = 〈 Q × S , δ 〉, kde δ je přechodová funkce
= δ R (q , rel ), δ O (s , λ R (q, rel )) . −1 = ΛO
(rel ) ,
nelze
( )(
)
δ O s j , x j = s k , reli = Λ O (si ) = Λ O s j s i ≠ s j . Potom
δ R (qi , reli ) =
(
)
λ q j , reli =
0 qj,δR
(q , rel ) = q , a λ (q , rel ) = x , j
i
k
R
qk
reli xi
qi
reli x j
qij
i
sk /-
qk
Obrázek 12. Vývojový diagram: a) OA s × vyznačenými stavy ŘA, b) ŘA. Příklad 8.: Navrhněte ŘA binární děličky celých čísel – c a a : b – v pevné řádové čárce (obr. 13.a)) [3,6]; číslo má tvar: ±
n cifry
Dělička sestává ze: sčítačky se střadačem (∑), ve kterém se před zahájením operace dělení nachází dělenec (〈∑〉 = a), registru D dělitele (〈D〉 = b) a registru P podílu (〈P〉 = c). Činnost děličky po příslušných substitucích do VD (obr.13.a) popisuje VD na obr.12.b). Nejprve se určí polarita podílu. Je-li sign 〈D〉 ≠ sign 〈∑〉 je sign 〈P〉 = 1 a naopak pro sign 〈D〉 = sign 〈∑〉 je sign 〈P〉 = 0. Dále se vynuluje obsah registru P, čítače taktů CT a znaménkového místa registru D i střadače ∑. Je-li znaménkové místo ∑ nulové, odečte se od dělence dělitel, tj. ∑ a ∑ + D inv , kde D inv je obsah
i
)
〈∑〉 = 1, pak CT a CT + 1 a obsah střadače i registru
minimalizovat ŘA co do počtu stavů a pohodlně dospět ke statickému ŘA s kombinačním chováním [5]. Skutečně, buď bez újmy na obecnosti (obr.12.) δ O (s i , x i ) = s j ,
)
qj
(
taková, že δ (q , s ) = δ R (q , rel ), δ O (s , x ) =
(
xj
sj/reli
D v inverzním kódu. Je-li v prvním kroku dělení (〈CT〉 = 0) po odečtení sign 〈∑〉 = 0, je dělenec větší než dělitel (〈∑〉 > > 〈D〉), tj. dojde k přetečení a po záznamu 1 do klopného obvodu přetečení KOP a 1 se dělení ukončí. Je-li sign
δ : Q × S → Q × S : q, s a q ′, s ′
Protože, bohužel, obecně neplatí s
b)
xi
1
Moorova potenciálního konečno-automatového modelu OA kde
qi
si /reli
i
podílu se posune o ∑ a L1 ∑ , P a L1 P
Vyskytne-li se v některém kroku ve střadači záporné číslo (sign 〈∑〉 = 1), pak se v následujícím kroku místo odečtení obsahu D od obsahu ∑ provede přičtení, tj. ∑ a ∑ + D čili provede se dělení bez regenerace zbytku. Je-li v některém kroku, s výjimkou prvého, po odečtení ve střadači ∑ kladné číslo (sign 〈∑〉 = 0), potom se do nejnižšího řádu n podílu zaznamená jednička, tj. Pn a 1 . Po n krocích CT a n dělení končí a podíl je
(
⎛ ⎞ x j ⎜ xi ≠ x j ⎟, ⎝ ⎠
což v žádném případě neznamená, že ŘA není sta-tický, ale je opatřený rekonstruktorem potenciálních stavů si, sj OA při daném stavu s0 počátečním. Rekonstruktor stavů OA je posuvný registr odezev reli , z jejichž sledu lze usuzovat, zda se OA nachází ve stavu si či sj; proto je nezbytné znát s0 .
jedno místo vlevo, tj. a zahajuje se druhý krok.
)
zapsán v registru P. Sestrojme podle obr.13.b) s vyznačenými stavy ŘA : q0, q1, q2, q3 (dále stručně jen 0,1,2,3) vývojovou tabulku ŘA děličky (tab. 1.a)) s tím, že pro jednoduchost zápisu označíme příkazy rozhodovací symboly ri a dosazovací příslušnými strojovými řízeními xj. Povšimněme si „sekvenčního“chování ŘA děličky, přijímá-li ŘA podnět r3, neboť λ R (2, r3 ) = λ R (6, r3 ) = r7 ≠ ≠ λ R (4, r3 ) = x10 ; jinak se však ŘA chová kombinačně.
97
VOL.15, NO.2, APRIL 2013
Zdá se tedy, že ŘA není statický s kombinačním chováním, ale dynamický s chováním „sekvenčním“. Zdánlivě sekvenční chování ŘA je však důsledkem faktu, že výstupní funkce potenciálního konečno-automatového modelu OA není injektivní (prostá). Bylo by tedy na místě sestrojit k danému VD činnosti OA stavový model OA? Ovšem přejít od VD činnosti OA ke konečnému automatu OA není vůbec jednoduché, a především není potřebné. Např. dělička z příkl.6., která sestává z dynamického střadače, registru D a P se sekvenčním chová-ním, každý o 2n stavech S stř = S D = S P , obsahuje 23n stavů, neboť
(
b)
q0
r1
yes
〈D〉 = 0
no
r2
sign 〈D〉 = = sign 〈∑〉
)
yes
no
Sděl = Sstř × SD × SP, tj. ⎪Sděl⎪ = S stř S D S P . Rozpoznáme-li podle VD činnosti OA, resp. podle vývojové tabulky příslušného ŘA, že výstupní funkce potenciálního konečného automatu OA není prostá, opatříme ŘA rekonstruktorem implicitních stavů OA – posuvným, event. cyklickým posuvným registrem. Tab.1. a) – vývojová tabulka Mealyho ŘA děličky – vybízí k radikální minimalizaci počtu stavů ŘA tak, že ŘA vystačí se stavem jediným – tab. 1.b). ŘA děličky pak chápeme jako statický a pro opa-kovanou akcepci r3 opatříme ŘA rekonstruktorem implicitních stavů děličky, tj. cyklickým posuvným registrem délky 2. (tab.1.b)), kde x7, x10 je posloupnost strojového řízení příslušná sledu skrytých stavů OA, reprezentovanému opakováním odezvy r3.
start
1
sign 〈P〉 a 1
x1
x2
CT a 0
x3
sign D a 0, sign ∑ a 0
x5
P a 0,
x4
q1 r3
no x6
∑
∑
a
+
sign 〈∑〉=1 D
x7
inv
∑
yes
a
∑
+
D
q2 4
r3
Závěr
sign 〈∑〉=1
Tvrdíme proto, že chování ŘA daného OA je kombinační, je-li výstupní funkce stavového modelu OA prostá. Není-li výstupní funkce konečného automatu OA injektivní, opatříme ŘA OA rekonstruktorem implicitních stavů OA, který je dynamický se sekvenčním chováním. a)
1
yes
no
r4
no
〈CT〉 =0 x9 x8
start
yes
〈KOP〉 a 1
〈P n〉 a 1 r5
x10 〈CT〉 a CT + 1
yes
q3
〈D〉 = 0
no P a ∑
2
yes D
end q0
Obrázek 13. VD operace dělení v pevné řádové čárce: a) ideový
2
end
no
〈CT〉 =1
x11
∑
a L1 ∑
x12
P
a L1 P
Obrázek 13. VD operace dělení v pevné řádové čárce: b) po substitucích s × vyznačenými stavy ŘA z příkl. 5.
98
VOL.15, NO.2, APRIL 2013
Tabulka 1.: a) Vývojová tabulka, b) výstupní tabulka ŘA z příkl. 6. a) q′/x r
r3
r3
1
2 x7
2 x6
2
3 x10
q 0
r1
r1 r2
r1 r2
0−
1 x1 , x2 , x3 , x4 , x5
1 x2 , x3 , x4 , x5
r3 r4
r3 r4
3 x9 , x10
0 x8
3
r5
r5
0−
1 x11, x12
b) r
r1
r1r2
r1r2
x
–
x1 , x2 , x3 , x4 , x5
x2 , x3 , x4 , x5
r
r33
r3
r3r4
r3r4
r5
r5
x6
x9 , x10
x8
–
x11 , x12
D1 RG
1
x7
D2 R C Literatura
[1] [2] [3] [4] [5]
[6]
RAJLICH, Václav. Úvod do teorie počítačů. Praha: SNTL, 1979 GLUŠKOV,V.M. Teorija avtomatov i vaprosy projektirovanija struktur cifrovych mašin. Kibernetika č.1. 1965, pp. 3-11 BARANOV,S.I. Sintez mikroprogrammnych avtomatov. Leningrad: Energija, 1979 BOKR, Josef, JÁNEŠ, Vlastimil. Logické systémy. Praha: vyd. ČVUT, 1999 BOKR, Josef. Zpětná vazba ve strukturním modelu logického objektu. Elektrorevue č. 70, 2010 s. (70-1) – (70-14). ISSN 1213 – 1539. Dostupné z http://www/elektrorevue.cz/cz/clanky/ostatní 1/0/zpetna_vazba_ve_strukturnim_modelu_logickeho_objektu -1/ MAJOROV,S.A., NOVIKOV, G.I.Principy organizacii cifrovych mašin. Leningrad: Mašinostroenie, 1976
99
2
x10
