Automaty

Trocha teorie o konečných stavových automatech, jejich implementaci ve VHDL, a jako bonus opravdové Hello World, tentokrát ne jako blikající LEDka, ale pěkně, řádně, přes sériové rozhraní!

Konečné automaty

Už jsme si říkali, že ve VHDL není, jako v programování, nějaké „tohle, a pak tamto“ a že se věci dějí „najednou“. Samozřejmě s nadsázkou, ve skutečnosti mají obvody svá zpoždění a pokud navrhujete opravdu rychlé zapojení, tak je třeba s těmito časy počítat. Pro běžné „domácí“ použití ale nejsou tyto časy kritické, takže se můžeme na výsledek dívat tak, že se změny projevují „ihned“.

Jenže problém je, že často potřebujeme, aby se něco stalo v důsledku něčeho jiného, a poté se stalo ještě něco dalšího. Nejjednodušším případem je automat na bonbóny: čeká a nic nedělá. Jakmile někdo zmáčkne tlačítko, tak se dostane do stavu „počítej mince“. Když jich je dostatek, tak se spustí proces „vydej bonbón“. Po něm následuje proces „vrať drobné“ a poté zase „čekej“. Když minicí není dostatek po nějakou dobu, nebo když člověk stiskne tlačítko „storno“, tak se jde na bod „vracení peněz“ a zpátky na čekání. Ve skutečnosti se taková logika dnes nejsnáze implementuje programovatelným obvodem (jednočipem, procesorem), ale princip je jasný.

Strojům, které jsou schopné mít nějaké různé stavy a na základě vnějších či vnitřních vlivů přecházet z jednoho do druhého říkáme konečné stavové automaty, anglicky FSM. Je k nim i celá matematická teorie, kde se dělí na různé typy a druhy; souvisí například s regulárními výrazy. Teorii si můžete nastudovat tam, pro naše použití stačí barbarská definice: Konečný automat (FSM) je zařízení, které má schopnost zůstávat v různých stavech, a na základě vstupních signálů přecházet z jednoho stavu do druhého. Popisujeme jej množinou stavů, množinou možných vstupních signálů a přechodovou funkcí, která říká: Ze stavu X se v případě, že na vstupech je to a to, automat dostane do stavu Y. Kromě těchto tří vlastností je potřeba též určit, který stav je počáteční a které stavy jsou (případně) konečné. V elektronice bude takový „konečný stav“ většinou nějaká neopravitelná chyba, která vyžaduje fyzický restart.

Stavový automat, copyright Farisori, CC-BY-SA

Na obrázku je příklad automatu, který má sedm stavů (a až g) a jeden vstup. Uzly grafu udávají stavy, orientované hrany grafu říkají, za jakých podmínek se přechází z jednoho stavu do druhého. V tomto případě se začíná ve stavu „a“. Pokud je vstup „0“, přechází se do stavu „b“, pokud je vstup 1, přechází se do stavu „f“. A tak dál. Graf je redundantní, stavy „c“, „e“ a „g“ jsou ekvivalentní a konečné a stav „d“ je nedosažitelný (nelze se dostat „do něj“).

Celý automat je řízen hodinovými pulsy – s příchodem hodinového pulsu se rozhoduje, jak se změní stav automatu.

Ve VHDL se řeší stavový automat například podle tohoto vzoru:

Konkrétní implementace se může lišit – například se často spojuje synchronizační proces (tj. ten, který sleduje hodiny a při jejich příchodu nastaví správně aktuální stav) s přechodovou funkcí – její roli zde má proces s velkým „case“.

Konečné automaty použijeme ve spoustě nejrůznějších aplikací, od primitivních sekvenčních automatů (např. semafor na křižovatce) po implementaci mikroprocesoru.

UART

Dobře, uznávám, je to přehnané. Nebudeme implementovat celý UART (Univerzální asynchronní přijímač a vysílač), ale jen jednu jeho část, totiž vysílač, a nebudeme ji implementovat univerzálně, ale docela natvrdo. Univerzální rozšíření si můžete dodělat za domácí úkol.

Nejprve trocha teorie: Sériový vysílač bere osmibitová vstupní data, a jakmile dostane signál „vysílej!“, vyšle je na jednobitový výstup Tx. Tx je normálně v logické 1. Jakmile je dán požadavek na vysílání, je vyslán start bit („0“), pak jsou vyslány bity od nejnižšího po nejvyšší, po nich případně paritní bit (není vyžadován a já ho neimplementoval) a nakonec jeden, dva nebo „jeden a půl“ stop bitu („1“). Doba trvání jednotlivých pulsů je dána vysílací frekvencí a udává se v baudech = bitech za sekundu. Pozor, je potřeba si uvědomit, že osmibitové vysílání zabere nejméně 10 bitů (start bit + 8 bitů dat + 1 stop bit) a nepočítat maximální přenosovou rychlost v bajtech jako „rychlost / 8“!

U synchronního vysílání se spolu se signálem přenášejí i hodiny, u asynchronního je potřeba nastavit vysílač i přijímač na stejnou frekvenci. Používají se frekvence odvozené od frekvence 150 Hz, tedy 150, 300, 600, 1200, 2400, 4800, 9600, 19200, 38400, 57600 či 115200 Hz.

Proto se u sériových portů nastavuje mnoho parametrů, kromě hodin i počet stop bitů či parita, a k tomu další způsoby řízení přenosu (dtr, rts, dsr, cts). My si implementujeme přenos 9600/8-N-1, tedy 9600 Bd, 8 bitů, bez parity (N) a s jedním stop bitem, bez hardwarového řízení přenosu.

Přenos "8-N-1". Copyright Adam Novozámský, CC-BY

Přenos „8-N-1“. Copyright Adam Novozámský, CC-BY

Implementace vysílače je poměrně přímočará. Můžeme použít čítač, který je ve stavu 0, a jakmile přijde signál „Vysílej!“, tak začne čítat hodinové impulsy. Při hodnotě 1 se vyšle log. 0, při hodnotách 2 až 9 se budou vysílat jednotlivé bity, při hodnotě 10 se vyšle log. 1 a při hodnotě 11 se opět vynuluje. Ale pojďme použít FSM.

Struktura

Entitu uděláme alespoň trošku generickou – generické parametry jsou rychlost systémových hodin a vysílací rychlost v baudech. Port tvoří hodinový vstup „clk“, nulovací vstup „rst“, sériový výstup tx, datový vstup tx_data, řídicí vstup tx_send a stavový výstup tx_ready.

Vstupem „rst“ nulujeme celý obvod, vstupem tx_send dáváme signál „Vysílej!“, signálem tx_ready říká obvod, zda právě vysílá (0), nebo zda je připraven vysílat (1). Zbytek asi nepotřebuje vysvětlení.

Hodiny

Ačkoli se to nezdá (a na začátku článku jsem psal, že se „věci dějí najednou“), tak je programovatelná logika založená na hodinovém signálu. Hodiny jsou „svaté“, bez nich máme jen poměrně tupou kombinační logiku. Někdy si probereme složitější téma, jakým jsou hodinové domény a přechod signálu mezi nimi, což je poměrně zásadní věc u složitých obbvodů. Pro naše použití si teď vystačíme s jedním „centrálním časem“ (v případě doporučeného začátečnického kitu je to 50 MHz) a ostatní časy si odvodíme z něj. V našem případě potřebujeme získat hodinový signál o frekvenci 9600 Hz. Nejjednodušší postup je počítat pulsy hlavních hodin, a jakmile jich napočítáme N, tak hodíme puls na vysílací hodiny a vynulujeme čítač. N je číslo, rovné podílu frekvence hodin a frekvence vysílání, tedy 50MHz / 9600 Hz = 5208,333… Použijeme hodnotu 5208, výsledný kmitočet tedy bude 9600,6144… což je v toleranci.

Hodinový dělič bude nulován vstupem rst.

Vidíme proměnnou counter, která počítá od 0 do baudrate-1. Baudrate je výše zmíněná konstanta, vzniklá podělením frekvencí fCLK a fBAUD. Counter je inicializován na hodnotu 0. S příchodem hodinového pulsu kontrolujeme, zda už máme načítáno dost (pak pouštíme puls na interní signál baudclk a nulujeme počítadlo), nebo zda počítáme dál. Pokud se objeví signál rst, nulujeme počítadlo i vnitřní hodiny.

Automat

Náš automat bude mít tři stavy: idle, data a stop. Je velmi jednoduchý, lineární. Vstupní stav je idle. V tomto stavu je tx=1 (klidový stav), tx_ready=1 (obvod je připraven vysílat) a čeká se na příchod signálu tx_send. Jeho příchod způsobí hned několik věcí: hodnota z tx_data se zkopíruje do interního bufferu, vynuluje se výstup tx_ready, nastaví se počítadlo vysílaných bitů na 7, spustí se vysílání start bitu (tx=0) a nastaví se, že následující stav je data. Prodleva mezi přechodem stavového automatu vytvoří potřebně dlouhý start bit.

Ve stavu data se vysílají jednotlivé bity. Na výstup tx je zkopírován nejnižší bit z bufferu, buffer rotuje o 1 bit doprava a snižuje se počítadlo bitů. Pokud je nenulové, zůstáváme ve stavu data, jakmile je nulové, přecházíme do stavu stop.

Ve stavu stop nastavíme výstup tx na 1 (stop bit) a řekneme, že s příštím příchodem hodin se přechází do stavu idle.

Celý stavový automat je řízen vysílacími hodinami. Proces ale není postavený na sledování signálu baudclk, ale clk (máme jedny hodiny, které vládnou všem…). Takže s příchodem pulsu na clk se kontroluje, jestli náhodou není už i vhodná doba podle „baudclk“. Pokud ne, neděje se nic, pokud ano, spouští se další iterace stavového automatu.

V implementaci automatu jsem nepoužil dvě proměnné (aktuální stav a následující), ale pouze jednu. Přechodová funkce je tak jednoduchá, že to takto stačí.

Zavedl jsem ale interní signál tx_en, který je „synchronní náhradou“ signálu tx_send. Totiž – při testech jsem narážel na problém, že obvod nechtěl vysílat. Po několika pokusech jsem zjistil, že problém je v tom, že signál tx_send musí být aktivní minimálně po dobu jednoho pulsu vysílacích hodin (baudclk), a to jsem neměl (používal jsem krátké pulsy). Proto jsem si zavedl signál tx_en, který je 0 a v případě, že přijde puls tx_send, tak se nastaví na 1 a podrží tak informaci o zahájení vysílání až do okamžiku, kdy se zpracovávají vysílací hodiny. Vlastní stavový automat pracuje až s tímto signálem tx_en. Výsledkem je, že pro spuštění vysílání stačí velmi krátký impuls tx_send. Dalším důsledkem této změny je, že jsem přesunul kopírování dat do interního bufferu právě do tohoto bodu – bylo by podivné reagovat na krátký signál tx_send, ale data si načíst až za „dlouhou dobu“.

Po „velkém CASE“ je ještě jedna část, která ošetřuje signál rst: nastaví automat do stavu idle, výstup do klidového stavu, nuluje vysílací signál tx_en.

Hello…

Takovouhle komponentu použiju ve velmi primitivním zapojení: jeden čítač postupně čítá od 0 do 7 a adresuje tak osmibajtovou paměť ROM, ve které je uložena zpráva. Když vysílač hlásí „ready“, přejde čítač na další adresu a pošle signál tx_send. Výstup paměti ROM je zapojen na vstup tx_data. Takže se posílá stále dokola osmiznakový vzkaz („Hello!\n\r“).

Po vhodném nastavení hodinového vstupu a datového výstupu se můžeme ke kitu připojit přes převodník USB-UART a v obyčejném sériovém terminálu (9600/8-N-1) uvidíme vzkaz našeho FPGA světu.

Tentokrát už doopravdy.