Sekvenční logické obvody, klopné obvody a stavové automaty

Kapitola4

Konečné stavové automaty

Souhrn

V úvodní kapitole jsme definovali sekvenční logické obvody. V dalších kapitolách jsme popsali základní bistabilní klopné obvody, čítače, registry a další příklady sekvenčních obvodů. Jejich zobecněním jsou tzv. konečné stavové automaty.

V anglické literatuře je označujeme jako FSM (Finite State Machine).

Definice

Konečný stavový automat je sekvenční logický obvod, který obsahuje konečný počet vnitřních stavů Q, mezi nimiž definovaným způsobem prochází na základě svého buzení.

Konečným stavovým automatem je tedy čítač, registr, klopný obvod JK apod.

V úvodní kapitole jsme si vysvětlili synchronní i asynchronní režim sekvenčního logického obvodu a dále jsme pomocí algebraického způsobu zavedli důležité pojmy pro popis činnosti sekvenčního logického obvodu – konečného stavového automatu.

Souhrn

Pro každý konečný stavový automat definujeme:

konečnou množinu vstupních stavů obvodu $X = \{x_{1}, x_{2}, x_{3}, \dots, x_{m}\}$ , kde počet vstupů obvodu je obecně 1, …, m,

konečnou množinu výstupních stavů obvodu $Y = \{y_{1}, y_{2}, y_{3}, \dots, y_{n}\}$ , kde počet výstupů obvodu je obecně 1, …, n,

konečnou množinu vnitřních stavů obvodu $Q = \{q_{1}, q_{2}, q_{3}, \dots, q_{p}\}$ , kde počet vnitřních stavů obvodu je obecně 1, …, p.

Na základě toho můžeme sestavit konečnou množinu přechodových funkcí obvodu G:

Q^{t + 1} = g_{1} (x_{1}^{t}, x_{2}^{t}, x_{3}^{t}, \dots, x_{m}^{t}; q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{p}^{t}), g_{2} (x_{1}^{t}, x_{2}^{t}, x_{3}^{t}, \dots, x_{m}^{t}; q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{p}^{t}), \dots = G (X^{t}; Q^{t})

A také konečnou množinu výstupních funkcí obvodu F:

pro obvod typu Mealy $Y^{t + 1} = f_{1} (x_{1}^{t}, x_{2}^{t}, x_{3}^{t}, \dots, x_{m}^{t}; q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{p}^{t}), f_{2} (x_{1}^{t}, x_{2}^{t}, x_{3}^{t}, \dots, x_{m}^{t}; q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{p}^{t}), \dots = F (X^{t}; Q^{t})$

pro obvod typu Moore $Y^{t + 1} = f_{1} (q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{p}^{t}), f_{2} (q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{p}^{t}), \dots = F (Q^{t})$ .

Definice

Z uvedené definice výstupních funkcí konečného automatu pro typ Mealy a typ Moore tedy vyplývá, že výstup obvodu typu Moore je závislý pouze na současném vnitřním stavu, zatímco Mealy je závislý kromě stavu i na současných vstupech obvodu.

Sekvenční logický obvod typu Moore je specifickým případem obvodu typu Mealy, který je nejobecnějším sekvenčním logickým obvodem.

Principiálně lze obecným blokovým schématem zakreslit oba typy konečných stavových automatů, jak uvádí obrázek 33. Rozdíl je vyznačen červeně odlišenou cestou, kdy výstup typu Mealy závisí i na aktuálním vstupu obvodu, zatímco výstup typu Moore nikoliv.

Obr. 33. Principiální blokové schéma obou typů obvodů.

Zajímavost

Konečný stavový automat (sekvenční obvod) typu Mealy je pojmenován po Georgeovi H. Mealym (1927–2010), americkém matematikovi a vědci z oboru informatiky, který jako první popsal tento typ sekvenčního logického obvodu v roce 1955 ve svém článku „A Method for Synthesizing Sequential Circuits“.

Obvod typu Moore je zase pojmenován po americkém matematikovi, informatikovi a vědci z oboru kybernetiky, Edwardu F. Mooreovi (1925–2003), který uvedl tento typ sekvenčního logického obvodu v roce 1956 v článku „Gedanken-experiments on Sequential Machines“.

Pro popis činnosti a funkce konečného stavového automatu využíváme různé možnosti, které byly uvedeny v kapitole 1 tohoto textu. Zvláště výhodné je použití orientovaných grafů přechodů, které jsme si ukázali pro oba typy na obrázku 3.

Z výše uvedeného popisu obou typů sekvenčních obvodů (automatů) vyplývají pro jejich aplikaci některé rozdíly.

Výstup automatu (obvodu) typu Mealy je nesynchronní, kdežto výstup automatu (obvodu) typu Moore je vždy synchronní.

Pro realizaci stejného sekvenčního obvodu pomocí automatu typu Moore obvykle potřebujeme více vnitřních stavů, a tedy i více klopných obvodů než při realizaci téhož obvodu pomocí automatu typu Mealy.

První uvedený rozdíl vychází z principu chování obou obvodů.

Definice

Výstup obvodu typu Moore je sice závislý pouze na jeho vnitřním stavu, ale ten se mění vždy synchronně po příchodu aktivační hrany hodinového vstupu Clock, a proto se výstup obvodu typu Moore mění také pouze synchronně, v okamžicích daných tímto hodinovým signálem Clock.

Oproti tomu výstupní funkce obvodu typu Mealy je funkcí nejen jeho vnitřního stavu, ale i jeho vstupu v daném okamžiku. Ačkoliv se tedy vnitřní stav typu Mealy mění rovněž synchronně, vstupy obvodu se mohu změnit v jakémkoliv časovém okamžiku, a tedy i jeho výstup se mění nezávisle na stavu hodinového vstupu Clock, čili asynchronně.

Poznámka

Uvedený rozdíl je patrný i z grafu přechodů obou typů obvodů. Zatímco výstupy obvodu typu Moore zapisujeme do uzlů grafu společně s vnitřními stavy, v případě obvodu Mealy je zapisujeme na hrany grafu společně s jeho vstupy.

Druhý uvedený rozdíl souvisí s realizací obou typů.

Definice

Protože jsou výstupy obvodu typu Moore vázány na jeho vnitřní stavy, potřebujeme vždy pro každou odlišnou výstupní hodnotu obvodu jeden vnitřní stav. Oproti tomu, pokud se v případě realizace obvodu typem Mealy vyskytne situace, že v obvodu existují přechody mezi vnitřními stavy se stejnou výstupní hodnotou při stejné vstupní hodnotě, lze tyto stavy sloučit. Snížením počtu vnitřních stavů lze následně snížit počet potřebných klopných obvodů a zjednodušit realizaci obvodu.

Obvykle lze daný sekvenční obvod realizovat pomocí automatu typu Moore i automatu typu Mealy. Obvod již realizovaný jedním z typů tak lze převést na druhý typ a naopak.

Převod automatu typu Moore na automat typu Mealy.

V prvním kroku přepíšeme hodnoty výstupů z uzlů k jednotlivým hranám grafu, které do těchto uzlů směřují při daném vstupu obvodu.

Ve druhém kroku můžeme sloučit ty hrany, které vycházejí i končí ve stejných stavech a mají stejné výstupní hodnoty.

Ve třetím kroku můžeme sloučit ty stavy, pro něž platí, že hrany, které z nich vycházejí, vstupují do stavů se stejnou výstupní hodnotou při stejné hodnotě vstupu.

Příklad

Příklad převodu automatu typu Moore na automat typu Mealy si předvedeme pomocí grafů přechodů daného obvodu na obrázku 34.

Obr. 34. Příklad převodu obvodu typu Moore na obvod typu Mealy.

V příkladu vidíme, že můžeme sloučit stavy q₂ a q₃ z Mooreova typu do jednoho stavu q₂ Mealyho typu, protože oba dávají stejnou výstupní hodnotu a přechody z obou do stavu q₁ jsou shodné.

Převod automatu typu Mealy na automat typu Moore

V prvním kroku zjistíme, zda do jednoho stavu směřují dvě hrany s odlišnými výstupními hodnotami. Pokud ano, musíme tento stav rozštěpit na dva samostatné – do každého nového stavu pak budou vcházet jen hrany se stejným výstupem.

Ve druhém kroku pak již jen přesuneme výstupy do uzlů grafu.

Příklad

Převod automatu typu Mealy na automat typu Moore si opět předvedeme pomocí příkladu zadaného grafu přechodů obvodu na obrázku 35.

Obr. 35. Příklad převodu obvodu typu Mealy na obvod typu Moore.

V grafu přechodů obvodu typu Mealy je zřejmé, že musíme rozštěpit stav q₁ v Mealyho automatu na stavy q₁₀, jehož výstup je logická 0, a q₁₁, jehož výstupem je logická 1, abychom mohli obvod převést na typ Moore.

V případě syntézy (návrhu a sestavení) konečného stavového automatu postupujeme v následujících krocích.

Rozbor a upřesnění zadání.
Zadání často slovně popisuje princip a činnost konečného stavového automatu a je potřeba jej obvykle doplnit a provést úplnou specifikaci, např. jakým způsobem probíhá resetování automatu a do jakého stavu se má dostat apod.

Sestavení grafu přechodů (přechodového diagramu) navrhovaného automatu.
Graf přechodů nám umožní lépe rozvrhnout a zkontrolovat funkci navrhovaného automatu, případně můžeme v tomto kroku např. sloučit či upravit vnitřní stavy nebo přechody automatu apod.

Zapíšeme tabulky přechodů a výstupů automatu.
Dle zvoleného typu automatu vytvoříme příslušné tabulky, viz kapitola 1.1 a obrázek 2.

Provedeme minimalizaci počtu vnitřních stavů automatu.
Průvodní úpravu jsme uskutečnili již na základě orientovaného grafu přechodů, další úpravy můžeme provést za pomoci sestavených tabulek. Dva stavy v tabulce jsou si ekvivalentní, pokud splňují následující podmínky:

- odpovídá jim stejný výstupní stav,

- odpovídá jim jeden vstupní stav, tj. leží ve stejném sloupci přechodové tabulky,

- na libovolně dlouhou posloupnost vstupních stavů musí obvod reagovat výstupní posloupností stavů, jež je totožná i v případě náhrady stavu zvoleným stavem. V dalším kroku minimalizace pak z každé třídy ekvivalentních stavů ponecháme v nové tabulce přechodů pouze jeden (libovolný) stav a ostatní vyloučíme.

Kódování vnitřních stavů automatu.
Je důležitým procesem při návrhu (viz poznámka níže), kdy jednotlivým stavům přiřadíme jejich binární vyjádření.

Volba typu paměťového (sekvenčního) členu.
Jde o výběr vhodného klopného obvodu. Obecně lze tvrdit, že složitost budicích funkcí je nejnižší u obvodů realizovaných typem JK. Nevýhodou je pak dvojnásobný počet těchto funkcí oproti klopným obvodům typu T nebo D.

Syntéza přechodových a výstupních funkcí.
V případě přechodových funkcí jde o navržení takového kombinačního logického obvodu, který bude odpovídajícím způsobem budit vstupy paměťových obvodů (JK, D, T) tak, aby jejich činnost odpovídala záznamům v přechodové tabulce. Přechodové i výstupní funkce se zapisují do Karnaughových map vhodných pro minimalizaci.

Návrh zapojení konečného stavového automatu.

Ověření návrhu pomocí simulace či realizace automatu.
Pro simulace můžeme využít nejrůznější programové prostředky.

Poznámka

Důležitým krokem při ručním návrhu konečného stavového automatu je tzv. kódování vnitřních stavů. Principiálně jde o proces, kdy jednotlivým vnitřním stavům sekvenčního obvodu přiřazujeme jejich binární vyjádření tak, abychom je v následujícím kroku mohli realizovat pomocí klopných obvodů. Pro toto kódování lze využít kromě přímého dvojkového kódu i řadu dalších binárních kódů. Použití každého z nich má své specifické výhody a nevýhody. Často se pro tyto účely kromě přímého binárního kódu používá Grayův kód, kód 1 z n, Johnsonův kód apod. Výběrem určitého typu kódování lze ve výsledku ovlivnit počet potřebných klopných obvodů, složitost realizace obvodu, jeho zpoždění a další parametry.