Systémom sa nazýva objekt, pre ktorý sú definované veličiny sledované na objekte, ich
rozlišovacie úrovne a vzájomné vzťahy medzi sledovanými veličinami.
Pre obidva druhy logických systémov (synchrónnych a asynchrónnych) je teda
príznačné, že v jednotlivých taktoch je určitý stav na vstupe, určitý vnútorný stav a určitý stav
na výstupe. Zmeny jednotlivých stavov sa uskutočňujú v časových intervaloch medzi
jednotlivými taktami a priebeh týchto zmien sa nesleduje. Pritom v systéme platí, že vnútorný
stav v takte t+1, nasledujúci za taktom t (t = 0, 1, 2, . . .) je vo všeobecnosti závislý jednak od
stavu na vstupe v takte t a jednak od vnútorného stavu v takte t. Prechody medzi vnútornými
stavmi daného logického systému určuje jeho vnútorná funkcia (nazývaná tiež prechodová
funkcia), ktorú môžeme zapísať takto:
Systém, ktorého veličiny nadobúdajú konečný počet diskrétnych hodnôt sa nazýva
logický systém. Zmeny hodnôt veličín logického systému sa uskutočňujú len v určitých
časových okamihoch, medzi ktorými existujú časové intervaly s nemeniacimi sa hodnotami
týchto veličín.
kde S(t + 1) je vnútorný stav systému v takte t + 1, S(t) je vnútorný stav systému v takte t, X(t)
je vstupný stav systému v takte t a δ je zobrazenie S × X → S.
HW23. Základná charakteristika logického systému:
Definícia logického systému, vstupný (výstupný, vnútorný) stav, diskrétny čas, takt,
synchrónne a asynchrónne systémy, prechodová a výstupná funkcia, abstraktný model
logického systému, sekvenčný (kombinačný) logický systém, štruktúra logického
systému.
Logický systém pracuje v určitom prostredí, s ktorým sa vzájomne ovplyvňujú. Toto
prostredie tvorí okolie systému, s ktorým je systém spojený prostredníctvom vstupných a
výstupných kanálov systému (obr. 1). Vstupné kanály, vstupné veličiny, resp. vstupné signály
sa vo všeobecnosti nazývajú vstupy systému a výstupné kanály, ich veličiny, resp. signály sa
nazývajú výstupy systému.
S(t + 1) = δ [S(t), X(t)]
(1)
Množina S obsahuje prvky:
S = S1 , S 2 , . . . , S R , R ≤ 2r
(2)
kde r je počet vnútorných premenných, ktoré sú obyčajné označované písmenami p1, p2, ..., pr.
Podobne množina X obsahuje prvky:
X = X1, X2, . . . , XN, N ≤ 2n
(3)
kde n je počet vstupných premenných x1, x2, ..., xn.
Stav na výstupe logického systému je charakterizovaný výstupnou funkciou, ktorú vo
všeobecnosti môžeme zapísať v tvare:
Y(t) = λ [S(t), X(t)]
Obr. 1 Spojenie systému s okolím.
V danom časovom intervale nadobúdajú vstupné, resp. výstupné veličiny určité
hodnoty. Kombinácia hodnôt vstupných (výstupných) veličín sa nazýva stavom na vstupe
(výstupe), resp. vstupným (výstupným) stavom. Vzťahy medzi vstupnými a výstupnými
veličinami (stavmi) logického systému sú determinované samotným systémom. Tieto vzťahy
sú sprostredkovávané veličinami vo vnútornej štruktúre systému, ktoré sú nazývané vnútorné
veličiny. Vnútorné veličiny nadobúdajú tiež konečný počet hodnôt. Kombinácia hodnôt
vnútorných veličín predstavuje vnútorný stav systému.
Pre logické systémy je príznačné, že pracujú v diskrétnom čase. V plynulo
prebiehajúcom čase sa vyskytujú časové intervaly, v ktorých všetky veličiny systému
nadobúdajú určitú, v tomto intervale sa nemeniacu hodnotu. Tieto diskrétne po sebe
nasledujúce a vzájomne sa neprekrývajúce časové intervaly sa nazývajú takty. Zmeny
fyzikálnych veličín prebiehajú medzi uvedenými taktami. Takty sa obyčajne číslujú pomocou
vzrastajúcej postupnosti dekadických čísel.
V synchrónnych systémoch sú časové okamihy, v ktorých môže dochádzať ku zmene
veličín, určované osobitnými synchronizačnými signálmi, generovanými osobitnými
synchronizačnými systémami. V tomto prípade takty zodpovedajú časovým intervalom,
v ktorých synchronizačná veličina nadobúda jednu z dvoch hodnôt (napr. 0). Pri druhej
hodnote synchronizačnej veličiny sa uskutočňujú zmeny jednotlivých veličín systému
(prechod z jedného stavu do druhého).
V asynchrónnych systémoch sú takty určované zmenami vstupných a vnútorných
veličín (zmeny výstupných veličín sú vždy vyvolané zmenami vstupných resp. vnútorných
veličín). Nový takt začne vždy vtedy, keď hociktorá vstupná alebo vnútorná veličina
nadobudne novú hodnotu a trvá dovtedy, kým opäť nedôjde k zmene hodnoty niektorej
vstupnej alebo vnútornej veličiny.
otázky LS.doc
(4)
kde Y(t) je výstupný stav logického systému v takte t, λ je zobrazenie S × X → Y, S(t) je
vnútorný stav systému v takte t a X(t) je vstupný stav systému v takte t.
Strana 1 z 34
Množina Y obsahuje prvky:
Y = Y1, Y2, . . . , YM, M ≤ 2m
(5)
kde m je počet výstupných signálov y1, y2, . . . , ym.
Na základe vzťahov (1) až (5) sa môže vytvoriť usporiadaná pätica M = (X, S, Y, δ, λ),
ktorá sa nazýva konečný automat. Uvedená pätica predstavuje abstraktný model logického
systému.
Vzťahy (1), resp. (4) je možné rozpišať podľa jednotlivých zložiek:
pi(t + 1) = δi [p1(t), . . . , pr(t), x1(t), . . . , xn(t)], i = 1, 2, . . . , r
(6)
yj(t) = λj [p1(t), . . . , pr(t), x1(t), . . . , xn(t)], j = 1, 2, . . . , r
(7)
Vzťahy (6), resp. (7) sa nazývajú štruktúrne vnútorné, resp. výstupné funkcie
uvažovaného systému.
Štruktúra logického systému je tvorená jednoduchšími systémami (často sú to logické
členy, ktoré realizujú základné logické funkcie) a vzájomnými väzbami medzi nimi. Bloková
štruktúra logického systému, zodpovedajúca štruktúrnym funkciám (6) a (7) sa môže vyjadriť
schémou podľa obr. 2. V tejto štruktúre je vyčlenená kombinačná a pamäťová časť. Do
kombinačnej časti systému prichádzajú vstupné signály z okolia ako aj vnútorné signály z
pamäťovej časti a formujú sa v nej budiace signály pre pamäťovú časť a výstupné signály
systému.
V logických systémoch vo všeobecnosti výstupný stav v danom okamihu nie je
jednoznačne určený okamžitým stavom na vstupe obvodu, ale je závislý od sekvencie stavov
na vstupe v predchádzajúcich taktoch. Preto sa tieto systémy nazývajú sekvenčné logické
systémy. To znamená, že sekvenčný logický systém obsahuje podsystémy, ktoré sú schopné
pamätať si informáciu z predchádzajúcich taktov. Táto informácia je vyjadrená vnútorným
otázky LS.doc
Strana 2 z 34
stavom systému, ktorý je reprezentovaný určitou kombináciou hodnôt vnútorných
premenných. Hodnoty vnútorných premenných sú uchované v pamäťovej časti systému.
HW24. Kombinačné logické obvody:
Štruktúrna analýza a syntéza, prechod od formálnej reprezentácie (pravdivostná
tabuľka, Karnaughova mapa, algebraické vyjadrenie, ...) do štruktúrnej reprezentácie na
báze logických členov.
Kombinačné logické obvody (KLO)
Zapojenie logických členov prostredníctvom
spätnoväzobných slučiek nazývame KLO.
uzlov
prvého
typu
bez
aktívnych
Uzol prvého typu je uzol, v ktorom sa uskutočňujú pravidelné väzby.
Pravidelné väzby: ak platí, že y ≡ x alebo y ≡ x1 ≡ x2 ≡ x3
Obr. 2 Všeobecná štruktúra logického systému.
Kombinačné logické systémy vo svojej štruktúre neobsahujú žiadne pamäťové časti.
V kombinačných logických systémoch každému vstupnému stavu prislúcha určitý výstupný
stav, bez ohľadu na to, aké stavy boli na vstupe systému v minulosti. Pre tieto systémy platí,
že hodnoty výstupných premenných v takte t sú vždy jednoznačne určené kombináciou
hodnôt vstupných premenných v tom istom takte a nezávisia od hodnôt vstupných
premenných v predchádzajúcich taktoch.
Spätnoväzobná slučka vzniká, keď výstup člena je zapojený na svoj vstup buď priamo, alebo
cez niekoľko členov.
Aktívna spätná väzba je taká, ktorá zosilňuje svoj výstup a teda obvod je od nej závislý.
Hradlové kombinačné obvody
Pozostávajú zo špeciálnych logických členov – hradiel a spojení v uzloch prvého a druhého
typu.
Uzol druhého typu je uzol, v ktorom sa uskutočňujú podmienečné pravidelné väzby. Medzi
výstupmi z viacerých členov je určitá funkcia (obvykle logický súčet).
Podmienečné pravidelné väzby: ak platí, že y1 + y2 + y3 + ... + yz ≡ x1 ≡ x2 ≡ x3 ≡ ... ≡ xn
Hradlo je prvok s jedným hradeným vstupom, jedným výstupom a niekoľkými hradlovými
alebo hradiacimi vstupmi x1, x2, ..., xn.
otázky LS.doc
Strana 3 z 34
otázky LS.doc
Strana 4 z 34
Príklad: Zistite, či daný obvod realizuje porovnanie dvoch dvojradových čísel.
Schéma:
a1
u1
1
y = hf ( x1 , x2 ,⋯, xn )
b1
h - priechodnosť hradla
a2
u2
1
b2
Poznáme dva typy hradiel:
a2
spínací kontakt
b2
- realizujeme ním priamu premennú
u3
1
u4
u5
1
u6
y1
1
y2
a1
y
h
1
1
1
b1
x
Zistíme hodnoty v jednotlivých uzloch:
rozpínací kontakt
- realizujeme ním negovanú premennú
y
h
u1 = a1 ↓ b1
u5 = u 2 ↓ u 4
u2 = a2 ↓ b2
u6 = u1 ↓ u3
u3 = a2 ↓ b2
y1 = u1 ↓ u5
u4 = a1 ↓ b1
y2 = u6 ↓ u4
x
Realizácia booleovej algebry pomocou hradiel:
realizácia AND
Určíme algebraické vyjadrenie výstupných funkcií v závislosti od vstupov:
x1
x2
y1 = a1 + b1 + a 2 + b2 + a1 + b1 = (a1 + b1 ).[( a 2 + b2 ) + ( a1 + b1 )] = ( a1 + b1 )( a 2 .b2 + a1 .b1 ) = a1a 2 b2 + a 2 b1 b2 + a1 b1
y 2 = a1 a 2 b2 + a 2 b1b2 + a1b1
realizácia OR
Zapíšeme funkcie y1 , y 2 do máp:
x1
b1
B
x2
a2
a1
- pomocou hradiel je teda možné vytvárať logické obvody
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
a2
a1
y2
Teda, ak:
Analýza KLO
•
•
b2
A
y1
•
•
b1
B
b2
A
zadaný je obvod a máme určiť jeho funkciu
z obvodu zostavíme štruktúrnu schému (praktický model) – štruktúrna schéma
predstavuje grafický model logického obvodu
zo štruktúrnej schémy si vytvoríme algebraický model
dosadením v algebraickom modeli získame algebraické vyjadrenie obvodu
A = B ⇒ y1 = y2 = 0
A < B ⇒ y1 =1, y2 = 0
A > B ⇒ y1 = 0, y2 =1
Z toho sme zistili, že obvod naozaj realizuje porovnanie dvoch binárnych čísel na
dvoch rádoch
otázky LS.doc
Strana 5 z 34
otázky LS.doc
Strana 6 z 34
Syntéza KLO
- opačná úloha ako analýza
- zo zadanej funkcie zostaviť obvod na realizáciu funkcie
HW25. Štruktúrna syntéza KLO z modulov:
Multiplexory, demultiplexory, pamäte typu ROM, programovateľné logické polia.
Postup: Zo zadanej funkcie získame algebraické vyjadrenia (pre jednu funkciu môže
existovať viac algebraických vyjadrení). Z algebraického vyjadrenia vyjadríme štruktúrnu
schému, z nej samotný obvod.
-
algebraické vyjadrenie musí spĺňať určité kritériá (minimalizácia, optimalizácia)
o vyjadrenie algebraického vyjadrenia v minimálnej konjunktívnej forme
o výber spoločných častí pred zátvorky (faktorizácia)
o rozloženie funkcie na jednoduchšie funkcie
-
zo všetkých rôznych vyjadrení zostavujeme štruktúru obvodu
o ak je to 1. normálna forma potom je to:
dvojstupňový obvod s komplementárnymi vstupmi (máme x aj x )
alebo trojstupňový obvod
o ak je to 2. normálna forma potom je to:
trojstupňový obvod s komplementárnymi vstupmi
alebo štvorstupňový obvod
-
ak vyberáme pred zátvorku spoločné faktory, tak nám vznikajú jednoduchšie
viacstupňové obvody, znižuje sa zaťaženie signálov, ale obvody sa nám stávajú
pomalšie
Zadaná funkcia
Algebraické vyjadrenie
Algebra
Typy väzieb v štruktúre obvodu:
• Uzly 1.typu – tento uzol má 1 vstup až 1 až n výstupov
•
Uzly 2.typu – má viac vstupov a 1 alebo viac výstupov
Kombinačné obvody s normálnou štruktúrou
Vyjadrenie:
slovné, množina f0, fx, f1, mapa
normálna forma (úplná, skrátená,
iredundantná, minimálna)
Boolova, Peirceho, Shefferova
•
•
majú uzly 1.typu
neobsahujú aktívne slučky :
o ak v slučke je aspoň 1 logický člen, ktorý regeneruje úroveň logického signálu
o slučka realizuje pamäť – využitie pri sekvenčných LO
Stupeň obvodu : počet logických členov zapojených v sérii
Kombinačné hradlové obvody
Hradlo je logický člen s 1 výstupom a n+1 vstupnými signálmi, ktorý realizuje logickú funkciu
x2
xi
xn
x1
h
y
y = h f(x1,x2, ... ,xn);
h – hlavný vstup hradla
Analýza KLO:
KLO → GM (grafický model) → AM (algebraický model ) → AV (algebraický výraz)
Syntéza KLO
Funkcia → zápis B.F → AV (výsledok je viac značný, preto je nutná minimalizácia)
Multiplexor:
Multiplexor je KLO s 2n udajovymi vstupmi a n riadiacimi vstupmi a 1výstupom
D0
D1
D2
D3
.
. MUX
Dn-1
C0
C1
Cn-1
otázky LS.doc
Strana 7 z 34
otázky LS.doc
Strana 8 z 34
Pamäte typu ROM je možné použiť na realizáciu ľubovoľnej B-funkcie.
SYNTÉZA LOGICKÝCH OBVODOV Z MODULOV
Univerzálnou funkciou n premenných x1, x2, ..., xn sa nazýva Boolova funkcia
U(u1, u2, ..., uv), pre ktorú platí
U(u1, u2, ..., uv) = fj(x1, x2, ..., xn) ∀j ∈ <1, 22n>
(6.28)
kde ui ∈ {0, 1, x1, x2, ..., xn, g1, g2, ..., gs}, pričom
gk je funkciou premenných x1, x2, ..., xn ∀ k ∈ {1,2,...,s}
Univerzálna funkcia v kanonickom tvare
2 n -1
f( x1 , x 2 , ... x n ) = ∨ ai x1i1 xi22 ... xinn
(6.29)
i=0
kde ai ∈ {0, 1}, i1 i2 ... in tvoria binárne vyjadrenie čísla i a
x0j
= xj a
x1j
= xj pre j = 1, 2, ..., n.
Realizácia systému B-funkcií prostredníctvom demultiplexorov
n
Multiplexorom sa nazýva kombinačný logický obvod s 2 údajovými vstupmi
d0, d1, ..., d2n-1, n riadiacimi vstupmi c1, c2, ..., cn a jedným výstupom f, pre ktorý platí,
že f = di, 0 ≤ i ≤ 2n-1, práve vtedy, ak číslo c1, c2, ..., cn je binárnym vyjadrením čísla i (cj ∈ {0,
1} pre 1 ≤ j ≤ n).
Nevýhoda - veľký počet vstupov obvodu (n + 2n).
Realizácia B-funkcií prostredníctvom
Programmable Logic Array).
programovateľných
logických
polí
(PLA
-
Celkový počet vstupov sa môže znížiť takmer o polovicu
2 n -1
f( x1 , x2 , ... x n ) = ∨ x1i1 xi22 ... xinn
. f( i ,i , ... i ,x )
1
2
n -1
n
(6.30)
kde f(i1, i2, ..., in-1, xn) sú reziduálne funkcie, ktoré nadobúdajú hodnoty z množiny {0, 1, xn,xn}.
i=0
Štruktúra programovateľného logického poľa
Realizácia B-funkcie štyroch premenných dvoma multiplexormi s dvoma riadiacimi vstupmi
Zapojenie PROM pre zväčšenie počtu výstupných funkcií
Štruktúra pamäti PROM
otázky LS.doc
Strana 9 z 34
otázky LS.doc
Strana 10 z 34
HW26. Sekvenčné logické obvody:
Spôsoby reprezentácie sekvenčných logických systémov, abstraktná syntéza.
Spôsoby reprezentácie sekvenčných logických systémov
Na rozdiel od kombinačných logických obvodov, výstupné stavy sekvenčného
logického obvodu nie sú jednoznačne určené stavom na vstupe, ale sú závislé od sekvencie
(poradia), v akom vstupné stavy prichádzali na vstup obvodu. Z toho pochádza aj názov
sekvenčných obvodov. Často sa stretávame aj s iným pomenovaním obvodov hore uvedeného
typu. Používajú sa napr. termíny konečný automat, sekvenčný automat, sekvenčný stroj.
Termín konečný automat však budeme používať vo význame matematického modelu, ktorým
sa popisuje chovanie sekvenčného obvodu. Sekvenčný obvod sa bude používať najmä vo
význame technickej realizácie automatu.
Zapojenie PROM pre zväčšenie počtu adresných vstupov
Konečný automat M definujeme ako usporiadanú päticu:
M = (X, S, Y, δ, λ)
kde: X je konečná neprázdna množina vstupných stavov automatu X = X1, X2, . . . , XN
S je konečná neprázdna množina vnútorných stavov automatu S = S1, S2, . . . , SR
Y je konečná neprázdna množina výstupných stavov automatu Y = Y1, Y2, . . . , YM
δ je prechodová funkcia automatu δ : X × S → S
λ je výstupná funkcia automatu λ : X × S → Y pre konečný automat typu Mealy,
λ : S → Y pre konečný automat typu Moore.
Rozdiel medzi konečným automatom typu Mealy a typu Moore je v odlišnej závislosti
výstupnej funkcie na veličinách sekvenčného obvodu. Zatiaľ čo výstupný stav automatu
Moore je jednoznačne určený len aktuálnym vnútorným stavom, výstupný stav automatu
Mealy závisí od aktuálneho vnútorného stavu a aj od aktuálneho stavu pôsobiaceho na vstupe
obvodu.
Činnosť konečného automatu je vždy uvažovaná v diskrétnom čase t = 0, 1, ...
Konečným automatom je možné jednoznačne opísať správanie sa sekvenčného obvodu
nasledujúcimi vzťahmi:
pre automat Mealy: S(t + 1) = δ(X(t), S(t))
Y(t) = λ(X(t), S(t))
pre automat Moore: S(t + 1) = δ (X(t), S(t))
Y(t) = λ (S(t))
Prechodovú a výstupnú funkciu je potrebné nejakým spôsobom zapísať. Kvôli prehľadnosti sa
zaužívali dva základné spôsoby reprezentácie konečného automatu:
• graf prechodov a výstupov,
• tabulka prechodov a výstupov.
Graf prechodov a výstupov je možné použiť pri menšom počte vnútorných a výstupných
stavov. Je to orientovaný graf, ktorého vrcholy predstavujú vnútorné stavy automatu a hrany
predstavujú prechody medzi stavmi pre každý vstup automatu.
Časť grafu prechodov a výstupov pre automat typu Mealy je na Obr. 1a a pre automat typu
Moore na Obr. 1b.
Obr. 1 Časť grafu prechodov a výstupov automatu typu: a) Mealy, b) Moore.
otázky LS.doc
Strana 11 z 34
otázky LS.doc
Strana 12 z 34
Tabuľka prechodov (resp. výstupov) je reprezentácia prechodovej (resp. výstupnej) funkcie
vo forme tabuľky. Tabuľka výstupov je pre automat typu Mealy podobná ako tabuľka
prechodov (Tab.1), pretože výstupný stav závisí od aktuálneho vnútorného a vstupného stavu.
Pre automat typu Moore je možné obidve tabuľky spojiť (Tab.2).
Vyjadrenie vstupných stavov prostredníctvom kombinácie hodnôt vstupných pre menných je
uvedené v tab. 3. Priradenie kombinácie hodnôt premenných jednotlivým stavom sa nazýva
kódovanie.
Tab. 1: Tabuľka prechodov a výstupov pre automat typu Mealy
Obr. 2 Bloková schéma systému automatického dávkovania tekutiny
Tab. 2: Tabuľka prechodov a výstupov pre automat typu Moore
Ak sú symboly označujúce vstupné, vnútorné a výstupné stavy zapísané v tabuľke
skutočnými kombináciami hodnôt príslušných premenných (vektormi binárnych hodnôt
dávajúcimi kód príslušného stavu) nazývame túto tabuľku kódovaná tabuľka prechodov, resp.
kódovaná tabuľka výstupov.
Medzi ďalšie spôsoby reprezentácie sekvenčných logických systémov patria: inverzná
prechodová tabuľka, normálny tvar (pomocou korešpondencie medzi vstupnými a im
zodpovedajúcimi výstupnými slovami rovnakej dĺžky), regulárny výraz, Petriho siet, program
(postupnosť inštrukcií zapísaných v špecifickom tvare).
Tab. 3: Vyjadrenie vstupných stavov prostredníctvom hodnôt vstupných premenných
Podobne sa môžu vyjadriť aj výstupné stavy prostredníctvom kombinácie hodnôt výstupných
premenných (tab. 4).
Abstraktná syntéza
Abstraktná syntéza sa zaoberá určením konečného automatu na základe požadovanej
činnosti obvodu. Zahŕňa v sebe určenie množiny stavov, prechodovej a výstupnej funkcie pre
automat zvoleného typu (Mealy, Moore) na základe požadovanej funkcie obvodu. Výsledkom
abstraktnej syntézy býva obyčajne tabuľka prechodov a výstupov, alebo graf prechodov
konečného automatu. Voliteľnou súčasťou abstraktnej syntézy je redukcia poctu stavov
konečného automatu.
Príklad:
Postup pri abstraktnej syntéze ilustruje príklad asynchrónneho systému s dvoma vstupnými a
dvoma výstupnými premennými, ktorý riadi automatické dávkovanie tekutiny podľa obr. 2.
Množina vstupných stavov (stavov hladiny) je daná kombináciami hodnôt vstupných
premenných x1, x2 definovaných nasledovne:
xi = 0 ak h < Hi
xi = 1 ak h ≥ Hi, pre i = 1, 2, ...
otázky LS.doc
Strana 13 z 34
Tab. 4: Vyjadrenie výstupných stavov prostredníctvom kombinácie hodnôt výstupných
premenných
Z tabuliek 3 a 4 vyplýva, že kombináciou hodnôt vstupných premenných x1 = 1, x2 = 0 ako aj
kombinácie hodnôt výstupných premenných y1 = 0, y2 = 0 a y1 = 1, y2 = 1 sa v danom
systéme vyskytovať nebudú. Vstupné stavy sa nemôžu vyskytovať v ľubovoľnom poradí.
Napr. po stave X0 nemôže bezprostredne nastať stav X2 a naopak.
Postup abstraktnej syntézy automatu je nasledovný. Ku každému stavu Si, ktorý treba v
priebehu syntézy zaviesť, stanovujeme nasledujúce stavy pre všetky vstupy. Pritom treba
uvážiť, či niektorým z týchto nasledujúcich stavov nemôže byt stav z množiny už
vytvorených stavov. Ak nie, zavedie sa nový stav Sj . Pre automat typu Moore priradíme
výstupy jednotlivým stavom. Pre automat typu Mealy priradíme príslušné výstupy
jednotlivým prechodom. Proces syntézy sa končí, ak netreba zaviesť žiaden nový stav.
otázky LS.doc
Strana 14 z 34
Zadaný riadiaci systém sa bude interpretovať ako automat typu Moore. Východiskovým
stavom sa zvolí stav označený symbolom S0, v ktorom sa zásobník vyprázdňuje. V tomto
vnútornom stave sa na vstupe môžu objaviť všetky tri vstupné stavy (00 - ak hladina
v zásobníku poklesla pod Hmin a obvod ešte nezapojil plnenie, 01 - ak je zásobník
poloprázdny a 11 - ak sa vyprázdňovanie práve začalo a hladina nepoklesla ešte pod Hmax).
Nasledujúci stav δ(S0, X0) sa nemôže stotožniť so stavom S0, pretože podľa zadania má
nastať plnenie zásobníka a v stave S0 je jeho vyprázdňovanie. Preto sa definuje nový stav S1 =
δ(S0, X0), v ktorom sa uskutočňuje plnenie zásobníka. Pri ostatných dvoch vstupných stavoch
X1, X2 nasledujúce stavy δ(S0, X1) resp. δ(S0, X2) sa môžu stotožniť so stavom S0, lebo
v týchto prípadoch systém uskutočňuje vyprázdňovanie zásobníka.
V stave S1 sa tiež môžu objaviť všetky tri vstupné stavy X0, X1, X2. Nasledujúci stav
δ(S1, X0) a δ(S1, X1) bude ten istý stav S1, v ktorom sa uskutočňuje plnenie zásobníka.
Nasledujúcim stavom δ(S1, X2) má byt stav S0, v ktorom sa uskutočňuje vyprázdňovanie
zásobníka.
Uvedený automat sa môže zapísať aj pomocou tabuľky prechodov a výstupov (tab. 5).
1. Pre danú regulárnu udalosť E sa nájdu všetky rôzne derivácie udalosti E podľa
všetkých slov e ∈ X*, t.j. zostaví sa množina

 ∂E
e∈ X ∗
D=

 ∂e
(3)
Pretože E je regulárna udalosť, množina D má konečný počet prvkov.
2. Ku každej derivácii z D sa priradí jeden stav automatu M. Derivácii
∂E
= E sa priradí
∂λ
počiatočný stav S0.
3. Zostaví sa množina K koncových stavov automatu M:
 ∂E
∂E 
λ∈ 
K =
∂e 
∂
e

(4)
Množinu K tvoria všetky stavy automatu, ktoré boli priradené deriváciám z D, ktoré
obsahujú v sebe prázdne slovo λ ∈ X*. Množina K obsahuje práve tie stavy automatu
M, do ktorých sa môže automat dostať z počiatočného stavu, ak príjme vstupné slovo
z udalosti E.
∂E ∂E
=
4. Určí sa prechodová funkcia δ automatu M: Ak ∂e ∂ω , pričom e, ω ∈ X*, x ∈ X
∂E ∂E
a derivácie ∂e a ∂ω sú priradené stavom S a S‘ takým, že δ(S, X) = S‘.
Tab. 5: Tabuľka prechodov a výstupov riadiaceho systému
Abstraktná syntéza na báze derivovania regulárnych výrazov (len pre záujemcov, ktorých
načisto nuda bije).
Nech X je konečná množina symbolov a X* je množina všetkých slov zostavených zo
symbolov z X. Potom udalosťou nad X sa nazýva množina slov E ⊆ X*. Prázdnou udalosťou
sa nazýva množina φ ⊆ X*, jednotkovou udalosťou sa nazýva prázdne slovo λ = λ ⊆ X* a celá
množina X* je univerzálna udalosť.
5. Zostaví sa výstupná funkcia λ:
•
pri automate typu Moore: λ(S) = I ⇔ S je koncový stav, t.j. S ∈ K
•
pri automate typu Mealy: λ(S, X) = I ⇔ λ(S, X) ∈ K
Nech M = (X, S, Y, δ, λ) je ľubovoľný automat, S0 ∈ S je počiatočný stav, a nech E je
udalosť nad X. Potom automat M z počiatočného stavu S0 rozpoznáva udalosť E svojim
výstupom W ∈ Y práve vtedy, ak pre každé vstupné slovo e ∈ X* platí:
λ(S0, e) = W ⇔ e ∈ E
(1)
t.j. automat M rozpoznáva udalosť E svojím výstupom W práve vtedy, ak vstupné slovo e,
prijaté z počiatočného stavu S0, je z udalosti E.
Udalosť, ktorú rozpoznáva niektorý konečný automat, je regulárna udalosť. Regulárne
udalosti sú práve tie udalosti, pre ktoré existuje regulárny výraz.
Jedna z metód abstraktnej syntézy automatu rozpoznávajúceho zadanú udalosť
vzhľadom na daný výstup je založená na báze derivácie regulárnej udalosti (regulárneho
výrazu).
Derivácia udalosti E nad X podľa slova e ∈ X* je definovaná vzťahom:
∂E
= W eW ∈ E
∂e
(2)
Je to opäť udalosť nad X, ktorá vyberá z udalosti E len tie slová, ktorých počiatočný
úsek je e a z týchto slov počiatočný úsek e vypúšťa.
Postup abstraktnej syntézy automatu M s množinou výstupov Y = 0, I, ktorý rozpoznáva
udalosť E vzhľadom na výstup I vyzerá nasledovne:
otázky LS.doc
Strana 15 z 34
otázky LS.doc
Strana 16 z 34
HW27. Realizácia pamäťového podsystému SLO:
Elementárne automaty, kódovanie stavov, určovanie budiacich a výstupných funkcií.
ŠTRUKTÚRNA SYNTÉZA SEKVENČNÝCH OBVODOV
Syntéza pamäťového sekvenčného obvodu predstavuje proces zostavenia štruktúry obvodu
resp. technickej realizácie obvodu, ktorý pozostáva z predpísaného súboru prvkov
(kombinačných i pamäťových) a vykonáva zadanú funkciu. Východiskom pri syntéze
sekvenčného obvodu budeme považovať automat vyjadrený tabuľkou prechodov a výstupov
resp. grafom prechodov.
Parametre časového priebehu synchronizačnej premennej:
Doba trvania ∆ synchronizačného impulzu h
∆ min ≤ ∆ ≤ τ min + t min
kde ∆ min predstavuje minimálnu dobu trvania synchronizačného impulzu potrebnú na
preklopenie elementárneho automatu, τ je oneskorenie elementárneho automatu a t
oneskorenie kombinačnej časti.
Perióda T impulzného priebehu synchronizačnej premennej musí spĺňať podmienku
T ≥ τ max + t max
Frekvencia periodického impulzného priebehu synchronizačnej premennej
ELEMENTÁRNE AUTOMATY
Elementárnym automatom sa nazýva sekvenčný obvod typu Moore s dvoma vnútornými
stavmi a úplným systémom prechodov.
Úplný systém prechodov je tvorený štyrmi prechodmi 0-0, 0-1, 1-0, 1-1.
Tab. 8.1 Tabuľky prechodov elementárnych automatov s jedným vstupom
a)
b)
Úloha syntézy sekvenčného obvodu s pamäťovými členmi zahrňuje:
• kódovanie stavov
• voľbu elementárnych automatov
• určenie tzv. budiacich funkcií elementárnych automatov
• určenie výstupných funkcií obvodu a
• zostavenie celkovej štruktúry obvodu.
X(t)
Pri zadanej pamäťovej časti (zvolených elementárnych automatoch) sa úloha syntézy
sekvenčného obvodu prevádza na syntézu jeho kombinačnej časti.
Súbehy – šírenie signálu k rôznym automatom po rozličných cestách.
súbehy – prípustné resp. nekritické
– kritické
0
1
X(t)
S(t)
0
1
S(t)
0
0
1
0
0
1
1
0
1
1
1
0
S(t+1)
S(t+1)
c)
X(t)
d)
0
1
S(t)
X(t)
0
1
S(t)
0
1
0
0
1
0
1
1
0
1
0
1
S(t+1)
S(t+1)
V synchrónnych sekvenčných obvodoch sa vplyv súbehov odstraňuje synchronizačnými
impulzmi určitej dĺžky.
V asynchrónnych obvodoch uvedené súbehy sa môžu odstrániť vhodným kódovaním
vnútorných stavov obvodu.
Z elementárnych automatov s dvoma vstupnými premennými sa najviac používajú automaty
zadané tabuľkami prechodov (tab. 8.2).
otázky LS.doc
otázky LS.doc
Strana 17 z 34
Strana 18 z 34
Tab. 8.2 Tabuľka prechodov EA typu RS (a) a JK (b)
a)
b)
00
q0 q 1
01
11
10
p
Tab. 8.5 Tabuľka kódovania vstupných (a), výstupných (b) a vnútorných (c) stavov
a)
b)
c)
q0 q1
00
01
11
10
X0
X
p
X1
X2
X3
Y
x1x2
Y0
Y1
Y2
S
y1y2
S0
S1
S2
p1 p2
0
0
1
-
0
0
0
1
1
0
x1
0
0
1
1
y1
1
1
0
p1
1
1
0
1
1
1
-
0
1
1
1
0
0
x2
0
1
0
1
y2
1
0
1
p2
1
0
1
p(t+1)
p(t+1)
Tab. 8.6 Kódovaná tabuľka prechodov (a) a výstupov (b)
a)
b)
Vhodným zápisom pre popis činnosti elementárnych automatov sú matice prechodov
D:
T:
RS:
JK:
qs(t)
q0(t) q1(t)
q0(t) q1(t)
p(t)-p(t+1) qd(t)
0-0
0
0
r1 0
r1 0
0-1
1
1
0
1
r2 1
1-0
0
1
1
0
1 r3
0 r4
1-1
1
0
0
r2
x1x2
00
01
10
11
p1 p2
Elementárne automaty sú realizované vo forme integrovaných obvodov.
x1x2
00
01
10
11
p1 p 2
11
11
10
01
11
11
11
10
01
11
10
10
10
10
11
10
10
10
10
11
01
01
10
01
11
01
01
10
01
11
p1p2(t+1)
y1y2(t)
URČENIE BUDIACICH FUNKCIÍ ELEMENTÁRNYCH AUTOMATOV
Budiace funkcie sa určia podľa požadovaných prechodov obvodu, ktoré spolu so zvoleným
kódovaním vnútorných stavov určujú požadované prechody elementárnych automatov.
Tab. 8.4 Tabuľka prechodov (a) a výstupov (b)
a)
b)
X(t)
X0
X1
X2
X3
X(t)
X0
X1
X2
X3
S(t)
S(t)
S0
S0
S1
S2
S0
S0
Y0
Y1
Y2
Y0
S1
S1
S1
S1
S0
S1
Y1
Y1
Y1
Y0
S2
S2
S1
S2
S0
S2
Y2
Y1
Y2
Y0
S(t+1)
otázky LS.doc
Y(t)
Strana 19 z 34
otázky LS.doc
Strana 20 z 34
r = [log2 R]c dvojhodnotových premenných, kde [a]c znamená prirodzené číslo z intervalu <a,
a+1).
Dva vnútorné kódy K a K' sa v ďalšom budú nazývať štruktúrne ekvivalentné vtedy a len
vtedy, ak K' možno zostaviť z kódu K permutáciou alebo invertovaním premenných.
Počet tried štruktúrnej ekvivalencie
R – počet stavov, r – počet stavových premenných
Počet tried štruktúrnej ekvivalencie
R
2
3
4
5
6
7
8
9
r
1
2
2
3
3
3
3
4
Pek
1
3
3
140
420
840
840
10 810 800
Optimálne kódovanie stavov sekvenčného obvodu - vedie na optimálne vyjadrenie
budiacich a výstupných funkcií.
Princíp spočíva vo voľbe takého kódu, ktorý v čo najväčšom počte máp budiacich a
výstupných funkcií dáva čo najviac susedných bodov s rovnakou hodnotou funkcie.
P1: Stavom Si, Sj ∈S, ktoré pri niektorom vstupe Xp ∈ X vedú na rovnaký nasledujúci
stav resp. na rovnaký výstup, t.j. pre ktoré platí, že
δ(Si, Xp) = δ(Sj, Xp) resp.
λ(Si, Xp) = λ(Sj, Xp)
sa pri kódovaní priraďujú susedné kombinácie hodnôt premenných, resp. kódy patriace v
mape kódovania do jednej pravidelnej konfigurácie, v ktorej sa nenachádzajú žiadne ďalšie
stavy.
KÓDOVANIE STAVOV SEKVENČNÉHO OBVODU
P2: Ak pri susedných vstupoch Xp a Xq existuje prechod z nejakého stavu Si ∈ S do
stavov Su a Sv, t.j. ak platí
Kódovanie stavov - priradenie hodnôt premenných jednotlivým stavom.
Pri kódovaní stavov budeme sledovať dve hlavné podmienky:
1. aby kódovanie bolo jednoznačné, t.j. každej dvojici rôznych stavov boli priradené rôzne
kombinácie hodnôt premenných;
2. aby kódovanie bolo optimálne, t.j. aby viedlo k minimálnemu vyjadreniu budiacich funkcií
elementárnych automatov a výstupných funkcií obvodu.
Pre jednoznačné kódovanie R stavov potrebujeme minimálne
otázky LS.doc
Strana 21 z 34
δ(Si, Xp) = Su
δ(Si, Xq) = Sv
potom stavom Su a Sv sa priraďujú susedné kódy resp. kódy s minimálnou kódovou
vzdialenosťou.
otázky LS.doc
Strana 22 z 34
Pre kódovanie vstupov sa aplikuje modifikované pravidlo P1'.
Voľba typu elementárneho automatu
P1': Vstupom Xi, Xj ∈ X, ktoré z niektorého stavu Sp ∈ S vedú na rovnaký nasledujúci
stav resp. na rovnaký výstup, t.j. pre ktoré platí, že
Pre elementárne automaty D, T, RS a JK matica všeobecného elementárneho automatu bude v
tvare
q0 q1
r1 0
r2 1
r3 r4
0 r5
δ(Sp, Xi) = δ(Sp, Xj) resp.
λ(Sp, xi) = λ(Sp, Xj)
sa pri kódovaní priraďujú susedné kombinácie hodnôt premenných.
Pri kódovaní výstupov sa aplikuje modifikované pravidlo P2'.
P2': Ak v stave Si pri susedných vstupoch Xp a Xq resp. ak v susedných stavoch Si a Sj
pri vstupe Xp nadobúda výstup hodnotu Yu a Yv, t.j. ak platí, že
λ(Si, Xp) = Yu a λ(Si, Xq) = Yv resp.
λ(Si, Xp) = Yu a λ(Sj, Xp) = Yv
Matice jednotlivých elementárnych automatov dostaneme z matice všeobecného
elementárneho automatu, ak za premenné ri dosadíme nasledovné hodnoty:
D: r5 = 1; r1 = r2 = r3 = r4 = 0
T: r4 = 1; r1 = r2 = r3 = r5 = 0
RS: r3 = 1; r2 = r4 = 0
JK: r3 = 1
Pre všeobecný elementárny automat zostavíme mapy jeho budiacich funkcií, v ktorých
hodnoty ri dourčíme tak, aby vyjadrenie budiacich funkcií bolo minimálne (obr. 8.20).
potom výstupom Yu a Yv sa priraďujú kódy s minimálnou kódovou vzdialenosťou.
Rozdelenie stavov podľa prechodov (rozdelenie prechodu) označované symbolom πi sa
určí z tabuľky prechodov, v ktorej namiesto stavov jednej triedy rozdelenia ri sa dosadí
hodnota 0 a namiesto stavov druhej triedy hodnota 1. Stavy, ktorým prislúchajú rovnaké
stĺpce, patria do jednej triedy rozdelenia πi.
Vo všeobecnosti teda platí, že vstupné funkcie elementárneho automatu, zakódovaného
rozdelením rj, budú okrem vektora vstupných signálov závislé od premenných pi1, pi2, ..., pik
qj = h(pi1, pi2, ..., pik, x1, ..., xn)
ak pre rozdelenie prechodu πj platí πj ≥ ri1 . ri2 . ... . rik
Postup: Hľadáme ri, pre ktoré πj ≥ ri1 . ri2 . ... . rik k=min
Kódovanie výstupných stavov.
m = [log2 M] C (8.15)
Napr. nech výstupná funkcia obvodu je zadaná tabuľkou výstupov. Nech počet rôznych
výstupných stavov je M = 3. Na zakódovanie troch stavov potrebujeme
m = [log2 3]C = 2 výstupné premenné.
Vytvoríme všetky prípustné rozdelenia výstupov podľa premennej.
Minimálne vyjadrenie budiacich funkcií dostaneme, ak použijeme elementárny automat typu
D pre realizáciu premenných p1 a p3 a automat typu T pre realizáciu premennej p2.
Vyjadrenia budiacich funkcií získame priamo z máp na obr. 8.20.
qD1 = x1` p 1 + x1 p3 + x2` p3
Budiace a výstupné funkcie predstavujú skupinu B-funkcií, preto je potrebné minimalizovať
ich ako celok.
qT2 = x1` p 2 + x2` p 2 + x1 x2
qD3 = ` x 1 + x2` p 2 + ` x 2 p1
Algebraické vyjadrenie výstupných funkcií sa zmenou typu elementárnych automatov
nemení.
otázky LS.doc
Strana 23 z 34
otázky LS.doc
Strana 24 z 34
Protisúbehové kódovanie stavov
asynchrónnych sekvenčných obvodov
HW28. Dynamické nedokonalosti - SLO
Hazardy, D-trio a spôsoby eliminácie ich vplyvu na činnosť obvodu.
Metódy protisúbehového kódovania vnútorných stavov
- všetky možné prechody sú elementárne - susedné kódovanie.
Ak nie je možné určiť susedné kódovanie, potom sa tabuľka prechodov príslušným spôsobom
upraví.
•
odstraňujú len kritické súbehy
U(i, j) množina všetkých možných stavov (včítane stavov Si a Sj), pri realizácii prechodu zo
stavu Si do stavu Sj, pre každú dvojicu prechodov Si - Sj a Sk - Sm, ktorá zodpovedá tomu
istému vstupnému stavu, množiny U(i, j) a U(k, m) nemajú spoločné stavy, t.j.
U(i, j) ∩ U(k, m) = ∅ ak j ≠ m
P(i) a P(j) sú hodnoty vektora prislúchajúce stavom Si a Sj, vektora totožnosti T(i, j), ktorého
zložky r1, r2, ..., rm nadobúdajú hodnoty 0 resp 1, ak príslušné premenné pri v stavoch Si a Sj
sú= rovnaké a "-" v ostatných prípadoch.
Nutnou a postačujúcou podmienkou neprekrývania sa množín U(i, j) a U(k, m) je
prítomnosť takej zložky pq v kódoch T(i, j) a T(k, m), ktorá nadobúda hodnotu r v jednom z
týchto kódov a hodnotu r‘ v druhom.
hovoríme, že dvojica prechodov Si - Sj a Sk - Sm je rozviazaná.
Aby sme pritom zabezpečili splnenie podmienky jednoznačného kódovania, formálne
doplníme tabuľku prechodov jedným vstupným stavom, pri ktorom sú všetky vnútorné stavy
stabilné.
Kombinačná časť sekvenčného obvodu, realizujúca budiace a výstupné funkcie, je zostavená
z reálnych logických členov. Reálne logické členy vykonávajú svoje funkcie s oneskoreniami,
ktoré sú neoddeliteľné od ich funkcií.
Nevyhnutnou a postačujúcou podmienkou na to, aby počas prechodového stavu, ktorý
zodpovedá zmene hodnoty xi, výstupná premenná y mala hodnotu 1, je platnosť vzťahu
xi +x i = 1
(8.21)
Nevyhnutnou a postačujúcou podmienkou na to, aby počas zmeny premennej xi mala výstupná
premenná hodnotu 0, je platnosť vzťahu
xi . xi = 0
(8.22)
VPZ - vypnutie pred zapnutím - pri kontaktoch VPZ nemožno splniť podmienku (8.21).
ZPV - zapnutie pred vypnutím. - pri kontaktoch ZPV nemožno splniť podmienku (8.22).
Oneskorenia predstavujú určité riziko nesprávnej hodnoty na výstupe obvodu, ktoré nazývame
hazard (niekedy tiež poruchový preskok)..
Kódovanú tabuľku prechodov je potrebné doplniť tak, aby platilo δ(Sq, Xp) = Sj pre každý
stav Sq Î U(i, j).
Tabuľku výstupov automatu typu Mealy tiež rozšírime o hodnoty výstupov pri súbehových
prechodoch podľa vzťahov λ(Sq, Xp) = λ(Si, Xp) pre všetky Sq Î U(i, j).
V automate typu Moore hodnotu výstupu v nestabilných stavoch dourčujeme tak, aby sa pri
prechode Si - Sj menila maximálne raz.
Obr. 8.24 Znázornenie dynamickej nedokonalosti kontaktov VPZ (a), ZPV (b), a invertora (c)
Možnosť vzniku chyby v obvode znázornenom na obr. 8.25a sa nazýva 1-hazard. V ďalšom
sa bude hovoriť, že v obvode je 1-hazard, ak je obvod hazardný preto, lebo na jeho výstupnom kanáli môže vzniknúť statická chyba (hazard) v 1.
Ak rovnaká funkcia je realizovaná podľa minimálnej KNF, na výstupnom kanáli
môže vzniknúť statická chyba v 0 (0-hazard).
Dynamická chyba (dynamický hazard) sa vyznačuje nepárnym počtom (väčším než 1)
zmien hodnôt výstupnej premennej, pričom výstup sa má meniť iba raz.
otázky LS.doc
Strana 25 z 34
otázky LS.doc
Strana 26 z 34
Obr. 8.25 Kombinačný obvod s 1-hazardom (a) a mapa jeho výstupnej funkcie (b)
Zostaviť kombinačný obvod, ktorý by bol bezhazardný pri zmene viacerých vstupných
premenných, je možné vo všeobecnosti s použitím osobitných obvodových prvkov. Tieto prvky
by mali mať charakter filtračných oneskorovacích členov. Filtračným oneskorovacím členom
sa rozumie asynchrónny systém s jednou vstupnou a jednou výstupnou premennou, ktorý má
tieto vlastnosti:
1. Oneskoruje zmeny výstupnej premennej proti zmene vstupnej premennej o čas D.
2. Ak je časový interval medzi dvoma po sebe nasledujúcimi zmenami vstupnej
premennej kratší ako D, potom sa výstupná premenná nezmení.
Chyby v kombinačnej časti sa môžu vyskytnúť:
- vo výstupnej funkcii počas prechodu cez nestabilné stavy (prechodná chyba),
- v prechodovej funkcii, čo spôsobí trvalú chybu vo výstupnej funkcii (trvalá chyba).
Eliminácia hazardu v kombinačnej časti ešte nestačí na to, aby obvod v každom prípade
pracoval bez trvalých chýb. Trvalá chyba môže vzniknúť aj z iných príčin, ako to ilustruje
nasledujúci príklad.
Obr. 8.26 časový diagram zmien hodnôt jednotlivých premenných obvodu z obr. 8.25
Ak na vstupe obvodu v danom časovom okamihu sa bude meniť hodnota najviac jednej
premennej, hazard možno odstrániť návrhom vhodnej štruktúry obvodu. Dosiahneme to tak, že
obvod realizujeme podľa tzv. bezhazardnej DNF (KNF), ktorá sa vyznačuje tým, že
ľubovoľná dvojica susedných bodov funkcie f s hodnotou 1 (0) je pokrytá aspoň jedným
implikantom (implicentom). Kombinačný obvod zodpovedajúci bezhazardnej forme je tiež
bezhazardný.
Obr. 8.27 Bezhazardná realizácia obvodu (a - rozklad na bezhazardný súbor implikantov;
b - štruktúrna schéma)
Postup pre syntézu kombinačných obvodov bez statického hazardu pri súčasnej zmene jednej
vstupnej premennej:
1. Vyjadrenie danej funkcie výrazom v DNF alebo BKNF. Pri kontaktovej realizácii
s kontaktmi VPZ "stačí" nájsť minimálnu KNF a s kontaktmi ZPV zase minimálnu DNF.
2. Úprava danej DNF alebo KNF na zátvorkovú formu, ktorá je potom tiež bezhazardná.
3. Obvodová realizácia funkcie z bezhazardného výrazu v tvare DNF, KNF alebo v
niektorej zátvorkovej forme.
Príčinou zlyhania obvodu je tu to, že súčinový člen D indikuje zmenu stavovej premennej p1
skôr ako zmenu vstupnej premennej x, t.j. indikuje zmenu stavu skôr ako zmenu vstupu,
ktorý zmenu stavu pôvodne inicializoval. Takéto nesprávne poradie zmien sa pri syntéze
otázky LS.doc
otázky LS.doc
Strana 27 z 34
Obr. 8.29 Etapy šírenia signálov v obvode spôsobujúcich vznik trvalej chyby
Strana 28 z 34
obvodu nepredpokladalo. Riziko spojené s možnosťou vzniku trvalej chyby z uvedenej príčiny
sa nazýva podstatný hazard v sekvenčnom obvode. Prechod, pri ktorom takáto možnosť
existuje sa nazýva hazardný.
Podstatný hazard sekvenčnom obvode možno identifikovať už na úrovni konečného
automatu, z ktorého sa vychádza pri štruktúrnej syntéze obvodu. V sekvenčnom obvode
zodpovedajúcom fundamentálnemu automatu A = (X, S, Y, δ, λ) prvého rádu, bez ohľadu
na zvolený vnútorný kód, bude pri prechode S1 → S2 pri zmene vstupu X1 → X2 podstatný
hazard práve vtedy, ak v A platí:
δ*(S1, X2X1X2) ≠ δ(S1, X2) = S2
(8.23)
t.j. ak postupnosť vstupov X2X1X2, ktorá sa aplikuje v stave S1, vedie do stavu rozdielneho od
S2.
Tab. 8.20 Fragmenty tabuliek prechodov, ktoré vedú na podstatný hazard
S(t)
S1
S2
S3
S(t)
S1
S2
S3
S4
X(t)
X(t)
S1
S3
S3
X1
S1
S3
S3
X1
S4
X2
S2
S2
S3
X2
S2
S2
S4
S(t)
X(t)
X1
X2
Tab. 8.21 D-trio
S2
S1
S1
S2
S3
S2
HW29. Konečné automaty s výstupom:
Konečné automaty Moore. Konečné automaty Mealy. Ekvivalencia konečných
automatov. Podobnosť konečných automatov Moore-a a Mealy.
Konečné automaty s výstupom:
S
R
, kde S je vstupná abeceda
R je výstupná abeceda
Reprezentácia KSA ( konečno stavových automatov):
1.) tabuľky funkcií ( analytická)
Pr.
f: Q x S -> Q
Q S f
g: Q x S -> R
q0 Φ1 f(q0,s1)=q1
Q S g
q s g(q,s)=r
2.) prechodové tabuľky
Pr.
S3
S3
S2
V tab. 8.21 je uvedený fragment tabuľky prechodov označovaný ako D - trio, v ktorej nie je
splnená podmienka (8.23) pre existenciu podstatného hazardu. Ale aj v tomto prípade sa okrem
rezultačnej premennej môže meniť aj chybová premenná. V dôsledku toho vznikne súbeh nie
len medzi rezultačnými premennými (s čím sa pri voľbe kódu počítalo), ale zúčastnia sa ho aj
chybové premenné. Takýto súbeh stavových premenných sa nazýva rozšírený súbeh. Rozšírený súbeh môže byť kritický, t.j. môže vzniknúť trvalá chyba.
Odstránenie podstatného hazardu resp. D-tria sa môže dosiahnuť zaradením dodatočného oneskorenia do spätnej väzby rezultačnej premennej, ktoré však znižuje rýchlosť obvodu
(obr. 8.30).
Podstatný hazard sa môže odstrániť aj voľbou vhodnej štruktúry, ktorá mení pomer
medzi oneskoreniami inicializačnej a realizačnej premennej. Účinok D-tria na vznik trvalých
chýb v obvode sa môže odstrániť vhodným kódovaním.
3.) stavový diagram
s/r
q
Obr. 8.30 Odstránenie podstatného hazardu zaradením dodatočného oneskorenia
otázky LS.doc
Strana 29 z 34
q´
<=> f(q,s)=g´ a zároveň g(q,s)=r ,platí pre Mealy
Mealy KSA:
je usporiadaná pätica M=(Q,S,R,f,g), kde Q je konečná množina stavov, S jevstupná a R je
výstupná abeceda, f je prechodová funkcia a g je výstupná funkcia a platí:
f: Q x S - > Q
f(q(t-1) . S(t) ) = q(t)
g: Q x S -> R
g(q(t-1) . S(t) ) = r(t)
otázky LS.doc
Strana 30 z 34
Moore KSA :
je usporiadaná pätica M=(Q,S,R,f,h), kde Q, S, R, f rovnako ako u Mealy a h: Q -> R je
výstupná funkcia a platí: h(q(t))=r(t)
Porovnanie:
Mealy
M= (Q,S,R,f,g)
f: Q x S -> Q
g: Q x S -> R
Moore
M= (Q,S,R,f,h)
f: Q x S -> Q
h: Q -> R
Relácie ekvivalencie:
X – je množina
R je podmnožina X x X
aRb -> a je relácia s b
R – je relácia ekvivalencie <=> df.
R je reflexívna : pre každé a z X : aRa
R je symetrická : aRb => bRa , pre a,b z X
R je tranzitívna : aRb , bRc => aRc ; pre a,b,c z X
s/r
q1
s
q2
q1/r1
q2/r2
Ekvivalencia stavov v :U
Pozn: Mealy je o jeden takt rýchlejší ako Moore
M = (Q , S , R , f , g ) ; Mq = (Q , S , R , f , g , q)
Mp = (Q , S , R , f , g , p) , ak q,p patria do Q
Ak majú KSA inicializačné stavy, tak to vyzerá takto:
Mealy: Mt = ( Q , S , R , f , g , q0 )
,ak q0 , q´0 patria do Q
Moore: Ms = ( Q , S , R , f , h , q´0 )
q je ekvivalentný s p <=> Mq je ekvivalentný s Mp
Podobnosť KSA:
Nech Ms a Mt sú KA Moore a Mealy také, že Ms = ( Q , S , R , f , h , q0S ) a
Mt = ( Q , S , R , f , g , q0t ) a zobrazenie :
TMs,q0s : S* -> R*
TMt,q0t : S* -> R*
,
budeme hovoriť, že Mt je podobný Ms a naopak <=> ak pre každý
vstupný reťazec x z S* ; TMs,q0(x) = h(q0) . TMt,q0(x)
Veta : Ku každému KA Mealy je možné zostrojiť podobný KA Moore a naopak.
a
a/r
Ms : (q0,r0) = > (q,r)
Mt: g = h fs => q0 => q
Ekvivalencia konečných automatov:
r1 … rk
M1
S1 … Sk
M2
Mi = (Qi , S , R , fi , gi , q0i ),
i=1,2
TMi,q0i : S* -> R*
r´1 … r´k
M1 je ekvivalentné M2 <=> ak pre každé x z S* : TM1,q01(x) = TM2,q01(x) , alebo
M1 je ekvivalentné M2 <=> ak pre každé x z S* : g1(q01 , x) = g2 (q02 , x)
Sú ekvivalentné ak pre každý vstup sú výstupy z automatov rovnaké.
otázky LS.doc
Strana 31 z 34
otázky LS.doc
Strana 32 z 34
HW30. Preklápacie obvody a pamäťové prvky v číslicových obvodoch:
Základné typy, charakteristika, použitie.
Klopný obvod (KO):
• najednoduchší sekvenčný pamäťový obvod, ktorý modeluje elementárny automat
• uchová prítomnosť prechodnej informácie aj po strate informácie
RS KO
Vlastnosti :
1. synchrónny pamäťový sekvenčný obvod
2. je odvodený od RS KO
3. má jeden informačný vstup D a vstup hodinových impulzov C
4. ide o oneskorovací (opakovací) obvod
T KO
S – set – nastaví logickú hodnotu
R – reset – nuluje
Ak nie je ani S ani R nastavený tak sa nič nedeje ostáva predošlí stav
Ak je set tak na výstupe je 1
Ak je reset tak výstup nuluje
Stav 1, 1 je neprípustný
Vlastnosti:
1. reaguje len na príchod 1 na vstupe, preklopí sa z 1->0 , ak je 0 nič sa nedeje
2. synchrónny, ak príde hodinový impulz preklopí sa
3. používa sa v čítačoch impulzov
JK KO
Vlastnosti:
1. je to sekvenčný obvod s dvoma stabilnými stavmi 0,1
2. je to asynchronný sekvenčný obvod – lebo sa preklápa len v závislosti od aktívnej
úrovne R a S nie od hodinového impulzu
3. je to pamäťový obvod
4. je asynchrónny
D KO
Vlastnosti:
1. je to vlastne RS obvod, ktorý má ošetrený zakázaný stav
2. je synchrónny
3. 2 spôsoby: JK KO riadený jednou hranou hodinových impulzov alebo JK KO riadený
dvoma hranami hodinových impulzov
Signál na vstupe D sa prevedie na výstup Q až keď príde hodinový impulz C
otázky LS.doc
Strana 33 z 34
otázky LS.doc
Strana 34 z 34
Download

Logické systémy