Automaty a regularní výrazy. (Lekce 3)

Сентябрь 15, 2022

Главная
Физика
Automaty a regularní výrazy. (Lekce 3)

Содержание

2. Bod1: Navrhněte automat, jehož výstup Y bude signalizovat "1" (logickou jedničkou), že vstup A přešel do
3. Bod2: Analýza zadání Návrh vždy začínáme vždy podrobnou analýzou zadání. Jaké možné varianty připouští slovní formulace?
4. Odpověď: Možné průběhy Obrázek ukazuje několik možných průběhů, vyhovujících požadavkům, přičemž zadavatel si přál poslední průběh
5. Bod 3: Vyjádření chování automatu v orientovaném grafu.
6. Bod 4: Zápis automatu do tabulky přechodů Označte stabilní stavy automatu kolečky. Stabilní stavy poznáte podle
7. Bod 4: Zápis automatu do tabulky přechodů
8. Bod 5: Minimalizace stavů Cílem minimalizace je vyloučit nadbytečné stavy a tím zjednodušit celkovou realizaci obvodu.
9. Pseudoekvivalence Pseudoekvivalence - dva stavy jsou pseudoekvivalentní, pokud mají stabilní stav pro stejný vstupní vektor, pro
10. Minimalizace stavů
11. Bod 6: Kódování stavů Další postup závisí na typu návrhu. Pokud navrhujeme synchronní automat pomocí synchronních
12. Graf propojení Vytvoříme pomocnou tabulku, která popisuje vztahy sousednosti mezi stavy, tj. existenci přechodu z jednoho
13. Změna tabulky b) Lze přecházet před jiný stav, využít již existujícího skoku anebo dodefinovat neurčitý stav
14. Bod 7: Zakódování tabulky
15. B A q1 q0 0 1 X 0 0 1 1 0 X X X X
16. Univerzální tvar této mapy získáme tím, že si v mapěoznačíme některé významné přechody, které nás při
17. Tlusté 1 a 0 pro JK
18. Tlusté 1 a 0 pro RS
19. Tlusté 1 a 0 pro nonRS
20. Bod9: Vyznačíme tlusté 1 a 0: S1' B A q1 q 0 0 0 X 1
21. R1' B A q1 q 0 0 0 X 1 0 0 0 0 X X
22. S0' B A q1 q 0 0 1 X 0 0 1 1 0 X X
23. R0' B A q1 q 0 0 1 X 0 0 1 1 0 X X
25. Скачать презентацию

Слайд 2

Bod1: Navrhněte automat, jehož výstup Y bude signalizovat "1" (logickou jedničkou),

že vstup A přešel do "1" dříve než vstup B.

Слайд 3

Bod2: Analýza zadání
Návrh vždy začínáme vždy podrobnou analýzou zadání. Jaké možné

varianty připouští slovní formulace? Co zadavatel vlastně požaduje? Které možné průběhy mohou nastat?
Úkol: Zkuste některé možné průběhy nakreslit

Слайд 4

Odpověď: Možné průběhy
Obrázek ukazuje několik možných průběhů, vyhovujících požadavkům, přičemž zadavatel

si přál poslední průběh Y. Kdo se nezeptal...

Слайд 5

Bod 3: Vyjádření chování automatu v orientovaném grafu.

Слайд 6

Bod 4: Zápis automatu do tabulky přechodů
Označte stabilní stavy automatu

kolečky.
Stabilní stavy poznáte podle toho, že jejich čísla se shodují s označením řádku, tj. současný stav (v čase n) se rovná budoucímu stavu (v čase n+1).
Máte-li označené stabilní stavy, definujte dále neurčité stavy pro zjednodušení návrhu.
Budou jimi takové přechody z některého stabilního stavu, u nichž by došlo k současné změně dvou vstupních signálů. Například stav 0 (řádek 0) má stabilní stav pro vstupy A=0 a B=0 (levý krajní sloupec tabulky).
Neurčitý stav se v tomto případě nachází ve sloupci, který odpovídá negaci těchto vstupů, na A=1 a B=1 (třetí sloupec).
Pro automat se dvěma vstupy mohou existovat neurčité stavy pouze v řádcích, na nichž se nachází nejvýše jeden stabilní stav. Proč?

Слайд 7

Bod 4: Zápis automatu do tabulky přechodů

Слайд 8

Bod 5: Minimalizace stavů
Cílem minimalizace je vyloučit nadbytečné stavy a

tím zjednodušit celkovou realizaci obvodu. Zmodifikujme si obecnou definici ekvivalentních a pseudoekvivalentních stavů na prakticky použitelnou metodiku:
Ekvivalence stavů - dva stavy jsou ekvivalentní, pokud mají stabilní stav pro stejný vstupní vektor, pro tento stabilní stav mají stejný výstupní vektor a všechny přechody pro ostatní vstupní vektory jdou do stejných nebo ekvivalentních stavů. Je přípustná i ekvivalence do kruhu.

Слайд 9

Pseudoekvivalence
Pseudoekvivalence - dva stavy jsou pseudoekvivalentní, pokud mají stabilní stav pro

stejný vstupní vektor, pro tento stabilní stav mají stejný výstupní vektor nebo není výstup definován a všechny přechody pro ostatní vstupní vektory jdou do stejných, ekvivalentních stavů nebo přechody nejsou definovány (neúplně určený automat).

Слайд 10

Minimalizace stavů

Слайд 11

Bod 6: Kódování stavů
Další postup závisí na typu návrhu.
Pokud

navrhujeme synchronní automat pomocí synchronních klopných obvodů (JK anebo D) s pomocným externím hodinovým signálem, potom můžeme stavům přiřadit jejich binární kódy zcela libovolně.
Navrhujeme-li ale asynchronní automat, například asynchronní kódový zámek, pak musíme zajistit, aby logický obvod pracoval ve fundamentálním režimu, tj. na jeho vstupech se měnil v daném čase výhradně jediný signál. Vzhledem k tomu, že kódy stavů se zavádějí díky zpětné vazbě na vstupy, je nutné, aby se měnil právě jeden bit při přechodu mezi stavy. Podmínku splníme, budou-li kódy stavů sousedit v Karnaughově mapě.

Слайд 12

Graf propojení
Vytvoříme pomocnou tabulku, která popisuje vztahy sousednosti mezi stavy, tj.

existenci přechodu z jednoho stavu do druhého, jednosměrně či obousměrně. Na jejím základě zkusíme umístit stavy. Pokud úloha nemá řešení, nezbývá než modifikovat přechodovou tabulku. K tomu si můžeme vybrat metodu:
a) Lze přidat do přechodové tabulky další stav

Слайд 13

Změna tabulky
b) Lze přecházet před jiný stav, využít již existujícího skoku

anebo dodefinovat neurčitý stav X.

Слайд 14

Bod 7: Zakódování tabulky

Слайд 15

B

A

q1 q0

0
1
X
0
0
1
1
0
X
X
X
X
0
0
0
0
q
0
*

q1 q0

Výsledné Karnaughovy mapy

Výsledkem návrhu automatu je zapojení uskutečňující zadané chování automatu, ale zpětná vazba tvořící paměť obvodu obsahuje i zapojení paměťových členů, které svojí strukturou odpovídají statickým klopným obvodům. Je příliš složitá a vyplatí se její dekompozice na tlusté 0 a 1.

Слайд 16

Univerzální tvar této mapy získáme tím, že si v mapěoznačíme některé

významné přechody, které nás při realizaci budících funkcí klopných obvodů budou zvláště zajímat. Z hlediska obsahu mapy vnitřní funkce se tedy nic nemění (všechny zápisy v mapě zůstávají stejné), pouze některé přechody si označíme zvýrazněním. V univerzální mapě proto budeme používat místo třech symbolů (1, 0, -) symbolů pět (1, 0, 1, 0, -) podle následující tabulky.

Univerzální mapa: Tlusté 1 a 0

Z tabulky je zřejmé, že zvýrazňujeme (barvou, tloušťkou) v mapě vnitřní funkce přechody (překlápění) klopného obvodu z 0 nebo z 1. Méně nás budou zajímat stavy pamatování, ty v mapě ponecháváme nezvýrazněné.

Слайд 17