Automata elmélet

Az automata definíciója és fajtái. Átmenetek és kilépések táblázatai és grafikonjai. Alautomata. Redukált automata tétel

Műveletek gépekkel

Lisztes gép átalakítása Moore géppé és Moore gép átalakítása lisztes géppé. Az automaták egyenértékűsége. Az automaták állapotainak megkülönböztethetősége. Az automaták minimalizálása. Automaták szintézise. Az automaták felismerése

Automatikus - olyan mechanizmusok, eszközök rendszere, amelyben az energia, anyagok, információk megszerzésének, átalakításának, átvitelének folyamatai teljesen automatizáltak. Az "automatikus" kifejezést két vonatkozásban használják:

1) műszaki,

2) matematikai.

A matematikai megközelítésben az automata egy műszaki eszköz matematikai modellje, amelynek bemenetekkel, belső állapotokkal és kimenetekkel kell rendelkeznie. Az eszköz szerkezetének részleteiről nem szabad tájékoztatást adni.

Technikai megközelítésben automatán egy nagyon is valós eszközt értünk, például telefonfülkét, automatát stb. Ebben az esetben természetesen ismertek az eszköz belső felépítésének részletei.

Az automata speciális és fontos esete a digitális automata (DA), amelyben a digitális információ fogadásának, konvertálásának, tárolásának és kiadásának folyamatai teljesen automatizáltak.

A jelek szempontjából célszerű a CA-t úgy definiálni, mint egy olyan rendszert, amely bemeneti jeleket tud fogadni, azok hatására egyik állapotból a másikba mozogni, a következő bemeneti jel megérkezéséig elmenteni, kimenő jeleket kiadni.

A CA végesnek tekinthető, ha az X bemeneti jelek, az S állapotok és az Y kimeneti jelek halmazai végesek Egy véges automata társítható egy eszközhöz, például egy számítógéphez. A számítógép a bejövő bemeneti adatokat kimeneti adatokká (eredmény) dolgozza fel, de ez az eredmény nem csak a bemeneti adatoknak, hanem a számítógép aktuális állapotának is megfelel, pl. azokat az adatokat, amelyek a számítógép memóriájában tárolódnak, például korábbi számítások eredményei, számítási programok.

A CA munkáját a bemeneti jelek vételi periódusainak száma határozza meg, automatikus időben.

Az absztrakt automata egy olyan diszkrét eszköz matematikai modellje, amelynek egy bemeneti csatornája van, amely bármely nyelv szimbólumsorozatait fogadja, egy kimeneti csatornát, amelyből bármely más nyelv szimbólumsorozatát veszik, és amely minden egyes nyelven bármilyen állapotban van. a diszkrét idő pillanata. Grafikusan az absztrakt automatát a 3. ábra mutatja.

A beviteli nyelv szavai az X=(x 1 ,x 2 ,...x n ) halmaz szimbólumaival ábrázolhatók, amelyet ún. beviteli ábécé, a kimeneti nyelv szavai pedig az Y=(y 1 ,y 2 ,...y p ) halmaz szimbólumai, amelyet ún. kimeneti ábécé. Az S=(s 1 ,s 2 ,...s m ) automata állapothalmazát ún. állapot ábécé.

koncepció a gép állapota olyan rendszerek leírására szolgál, amelyek kimeneti jelei nem csak az adott időpontban bemenő jelektől, hanem valamilyen előtörténettől is függnek, pl. a rendszer bemeneteire korábban érkezett jelek. Következésképpen a digitális automaták szekvenciális áramkörökhöz tartoznak, amelyek, mint már említettük, rendelkeznek memóriával. Az automata állapotának fogalma valamilyen múltbeli emléknek felel meg, így ennek a fogalomnak a bevezetése lehetővé teszi az idő explicit változóként való kiiktatását és a kimeneti jelek állapotok és bemeneti jelek függvényében történő kifejezését.

Egy absztrakt automata működését meghatározott időintervallumokhoz viszonyítva kell mérlegelni, hiszen minden diszkrét intervallum t egyezik az y(t) kimenetével. Következésképpen az automata működését véges időtartamú diszkrét időintervallumokon keresztül vizsgáljuk. A digitális automaták absztrakt elmélete úgy tekinti, hogy a bemeneti jelek hatnak a szinkron automatára az egyes automaták elején. én-edik intervallum (kvantum), amelyet a megfelelő órajel impulzus (ciklus) lefoglal, és az automata belső állapotainak változása a szomszédos órajelek közötti időintervallumokban következik be, amikor a bemeneti jelek nem befolyásolják.

Az "állapot" fogalmát arra használjuk, hogy megállapítsuk az automata által generált kimeneti nyelv szimbólumainak és/vagy szavainak funkcionális függőségét a bemeneti nyelv szimbólumaitól és/vagy szavaitól, amikor az automata végrehajtja az adott algoritmust. Az automata sОS minden állapotához és minden xОX szimbólumhoz a diszkrét idő [t] pillanatában az yОY szimbólum generálódik a készülék kimenetén. Ezt a függést a j automata kimeneti függvénye határozza meg. Az automata sОS minden aktuális állapotára és minden xОX szimbólumra a diszkrét idő [t] pillanatában az automata a következő sОS állapotba kapcsol. Ezt a függést az y automata átmeneti függvénye határozza meg. Az automata működése két sorozat létrehozásából áll: az automata egymást követő állapotainak sorozatából (s 1[ s 2 s 3 ...) és egy kimeneti szimbólumsorozatból (y 1 y 2 y 3 ...), amely mert a szimbólumsorozat (x 1 x 2 x 3 ...) t = 1,2,3,... diszkrét időpillanatokban bontakozik ki. A téglalap alakú zárójelben a diszkrét idő pillanatait jelöljük, amelyeket egyébként ciklusoknak nevezünk. zárójelek - az X, Y és S ábécé szimbólumsorozata.

Tehát egy véges automata matematikai modellje egy háromalapú algebra, melynek hordozói három X, Y és S halmaz, a műveletek pedig két j és y függvény.

Ebben a cikkben az „állapotgép” kifejezés olyan algoritmusra utal, amely néhány állapot egyikében lehet. Az „állapot” egy bizonyos feltétel, amely meghatározza a bemeneti és kimeneti jelek, valamint a bemeneti jelek és az azt követő állapotok egy adott viszonyát. Az okos olvasó azonnal észreveszi, hogy a cikkben leírt állapotgépek Mealy gépek. A Mealy gép egy véges állapotú gép, ahol a kimenetek az aktuális állapot és a bemenet függvényei, ellentétben a Moore géppel, ahol a kimenetek csak az állapot függvényei. A következő állapot mindkét esetben az aktuális állapot és a bemeneti jel függvénye.

Tekintsünk egy példát egy egyszerű véges állapotú gépre. Képzelje el, hogy egy szöveges karakterláncban fel kell ismernie a "//" karaktersorozatot. Az 1. ábra azt mutatja be, hogyan történik ez állapotgép segítségével. A perjel első előfordulása nem ad kimenő jelet, de az automatát a második állapotba lépteti. Ha az automata a második állapotban nem talál perjelet, akkor visszatér az elsőhöz, mivel egymás után 2 perjelre van szüksége. Ha megtalálja a második perjelet, az automata „kész” jelzést ad ki.

Tudja meg, mire van szüksége az ügyfélnek.

Rajzoljon állapotátmeneti diagramot

Kódolja az állapotgép "csontvázát" az átmeneti műveletek részletezése nélkül.

Győződjön meg arról, hogy az átmenetek megfelelően működnek.

Adja meg az átmenetek részleteit.

Végezzen tesztet.

Állami géppélda

Vegyünk egy érdekesebb példát egy véges állapotú gépre - egy olyan programra, amely vezérli a repülőgép futóművének visszahúzását és kinyújtását. Bár a legtöbb repülőgépen ezt az eljárást elektro-hidraulikus vezérlőmechanizmussal hajtják végre (egyszerűen azért, mert nincs számítógép a fedélzeten), bizonyos esetekben, például pilóta nélküli légi járműveknél érdemes szoftveres vezérlést alkalmazni.

Először is foglalkozzunk a felszereléssel. A repülőgép futóműve az első futóműből, a fő bal oldali futóműből és a fő jobboldali futóműből áll. Meghajtásuk hidraulikus mechanizmussal történik. Az elektromos meghajtású hidraulikus szivattyú nyomást biztosít az erőműködtetőre. A szoftver segítségével a szivattyú be- vagy kikapcsolható. A számítógép úgy állítja be az irányszelep helyzetét – „le” vagy „fel”, hogy lehetővé tegye a nyomást az alváz emeléséhez vagy süllyesztéséhez. A futómű lábai mindegyike rendelkezik végálláskapcsolóval: az egyik zárva van, ha a futómű fel van emelve, a másik - ha "lefelé" helyzetben van rögzítve. Annak megállapításához, hogy a repülőgép a földön van-e, az orrfogaskerék-tartón lévő végálláskapcsoló zár, ha a repülőgép súlya az orrkeréken van. A pilóta kezelőszervei egy felső/alsó futómű karból és három lekapcsolható lámpából állnak (mindegyik lábhoz egy), zöld (lefelé állás) vagy piros (átmeneti helyzet).

És most térjünk át egy véges állapotú gép fejlesztésére. Az első és legnehezebb lépés az ügyfél valós elvárásainak megértése. Az állapotgép egyik előnye, hogy arra kényszeríti a programozót, hogy minden lehetséges esetet végiggondoljon, és ennek eredményeként minden szükséges információt megkapjon a megrendelőtől. Miért tartom ezt a legnehezebb szakasznak? És hányszor kaptál ilyen feladatleírást: ne húzd be a futóművet, ha a gép a földön van.

Természetesen ez fontos, de a megrendelő elhiszi, hogy itt mindennek vége szakad. Mi a helyzet a többi esettel? Elég behúzni a futóművet abban a pillanatban, amikor a gép felszáll a földről? Mi van, ha a gép a kifutón egy ütésről pattan? Mi van akkor, ha a pilóta parkolás közben a sebességváltó kart "fel" helyzetbe állítja, és ennek eredményeként elkezd felszállni? Ebben az esetben fel kell emelkednie az alváznak?

Az állapotgépben való gondolkodás egyik előnye, hogy gyorsan megrajzolhatunk állapotátmenet-diagramot egy vetítőtáblára, közvetlenül az ügyfél előtt, és végig lehet vele menni a folyamaton. Az állapotátmenet következő megnevezése elfogadott: „az átmenetet okozó esemény” / „kimeneti jel az átmenet eredményeként”. Ha csak azt fejlesztettük volna, amit a megrendelő eredetileg kért („ne húzzuk be a futóművet, ha a repülőgép a földön van”), akkor a 2. ábrán látható gépet kaptuk volna.

Állapotátmeneti diagram (vagy bármely más algoritmus) elkészítésekor tartsa szem előtt a következőket:

A számítógépek nagyon gyorsak a mechanikus hardverekhez képest.

A gépészmérnök, aki elmagyarázza, mit kell tenni, nem biztos, hogy annyit tud a számítógépekről és az algoritmusokról, mint te. És ez is egy pozitív pont, különben nem lenne rád szükség!

Hogyan fog működni a programod, ha egy mechanikus vagy elektromos alkatrész elromlik?

A 3. ábrán egy olyan állapotgépet mutatunk be, amely a vevő tényleges igénye alapján történik. Itt azt szeretnénk megakadályozni, hogy a repülőgép futóműve visszahúzódjon egészen addig, amíg biztosan a levegőben van. Ehhez a leszállási kapcsoló kinyitása után a gép vár néhány másodpercet. A szint helyett a pilóta emelőkarjának emelkedő élére is szeretnénk reagálni, így elkerülhető a probléma, ha valaki megmozdítja a kart, miközben a gép parkolt. A futómű be- vagy kihúzása néhány másodpercet vesz igénybe, és fel kell készülnünk arra a helyzetre, hogy a pilóta a művelet során meggondolja magát, és az ellenkező irányba mozgatja a kart. Vegye figyelembe azt is, hogy ha a gép ismét leszáll, miközben "Várakozás a felszállásra" állapotban vagyunk, az időzítő újraindul, és csak akkor történik visszahúzódás, ha a gép 2 másodpercig a levegőben volt.

Állami gépi megvalósítás

Az 1. lista a 3. ábrán látható állapotgépem megvalósítása. Beszéljünk a kód néhány részletéről.

/*1. lista*/

typedef enum(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) Állapot_típus;

/*Ez a tömb mutatókat tartalmaz bizonyos állapotokban meghívandó függvényekre*/

üres(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

Állapot_típus aktuális_állapot;

InitializeLdgGearSM();

/* Az automata szíve ez a végtelen hurok. A megfelelő funkció

Aktuális állapot, ismétlésenként egyszer hívva */

míg (1) {

állapot_tábla();

DecrementTimer();

üres InitializeLdgGearSM( üres )

aktuális_állapot = GEAR_DOWN;

/*Hardver leállítása, világítás lekapcsolása stb.*/

üres GearDown( üres )

/* Menjen a várakozási állapotba, ha a gép

Nem a földön, és parancs érkezett az alváz emelésére * /

ha((gear_lever == UP) && (prev_gear_lever == DOWN) && (squat_switch == FEL)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = sebességváltó kar;

üres RaisingGear( üres )

ha((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*Ha a pilóta meggondolta magát, menjen a futómű lefelé állapotába*/

ha(sebességváltó kar == LE) (

aktuális_állapot = LOWERING_GEAR;

üres GearUp( üres )

/*ha a pilóta a kart "le" helyzetbe mozdította,

Lépjen a "futómű leengedése" állapotba * /

ha(sebességváltó kar == LE) (

aktuális_állapot = LOWERING_GEAR;

üres WtgForTakeoff( üres )

/* Várjon, mielőtt felemeli a vázat. */

ha(időzítő<= 0.0) {

aktuális_állapot = EMELÉS_FEKEZÉS;

/*Ha újra megérintettük, vagy a pilóta meggondolta magát, kezdje elölről*/

ha((guggolás_kapcsoló == LE) || (sebességváltó kar == LE)) (

aktuális_állapot = GEAR_DOWN;

/* Ne akard megkövetelni, hogy ismét megfordítsa a kart

Ez csak egy ugrálás volt.*/

prev_gear_lever = LE;

üres süllyesztő( üres )

ha(sebességváltó kar == FEL) (

aktuális_állapot = EMELÉS_FEKEZÉS;

ha((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

aktuális_állapot = GEAR_DOWN;

Először is észreveheti, hogy az egyes állapotok funkcióit külön C függvény valósítja meg. Természetesen lehetséges lenne egy automata implementálása switch utasítás használatával, minden állapothoz külön esettel, de ez nagyon hosszú függvényhez vezethet (10-20 sor kód 1 állapotonként a 20-30 állapot mindegyikére ). Az is hibákhoz vezethet, ha módosítja a kódot a tesztelés utolsó szakaszában. Lehet, hogy soha nem felejtette el az eset végén a break utasítást, de nekem voltak ilyen eseteim. Az egyik állapot kódja soha nem kerül be egy másik állapot kódjába, ha minden állapothoz külön funkciója van.

A switch utasítás használatának elkerülése érdekében az állapotfüggvényekre mutatók tömbjét használom, és a tömb indexeként használt változót enum típusúnak deklarálom.

Az egyszerűség kedvéért a kapcsolók állapotának leolvasásáért, a szivattyúk be- és kikapcsolásáért stb. felelős I/O hardvert egyszerű változókként ábrázoljuk. Feltételezzük, hogy ezek a változók "varázscímek", amelyek láthatatlan eszközökkel kapcsolódnak a berendezéshez.

Egy másik nyilvánvaló dolog, hogy ezen a ponton a kód nem játszik különösebb szerepet. Csak megy egyik állapotból a másikba. Ez egy fontos köztes lépés, és nem szabad figyelmen kívül hagyni. Egyébként jó lenne hozzáadni a feltételes fordítási direktívák közé zárt print utasításokat (#ifdef DEBUG .. #endif), amelyek kiírnák a bemeneti jelek aktuális állapotát és értékeit.

A siker kulcsa az állapotátmenetet okozó kódban rejlik, azaz. meghatározza, hogy megtörtént-e a bevitel.

Ha a kód helyesen halad át minden állapoton, akkor a következő lépésben meg kell írni a kód "töltelékét", vagyis pontosan azt, ami a kimeneti jelet állítja elő. Ne feledje, hogy minden átmenetnek van egy bemeneti jele (az esemény, amely kiváltotta) és egy kimeneti jele (hardveres I/O eszköz, mint a példánkban). Ezt gyakran hasznos állapotátmeneti táblázat formájában rögzíteni.

Az állapotátmenet-táblázat állapotátmenetenként egy sorral rendelkezik.

Állapotgép kódolásakor próbálja meg erősen tartani – ez erős megfelelés az ügyfél igényei és a kód között. Szükséges lehet a hardverrészletek elrejtése egy másik funkciórétegben, például annak érdekében, hogy az állapotgépi kód a lehető legpontosabban hasonlítson egy állapotátmeneti táblázathoz és egy állapotátmeneti diagramhoz. Ez a szimmetria segít megelőzni a hibákat, és megmagyarázza, hogy az állapotgépek miért olyan fontos részét képezik a beágyazott programozó arzenáljának. Természetesen ugyanezt a hatást el lehet érni jelölőnégyzetekkel és végtelen számú egymásba ágyazott if utasítással, de nagyon nehéz lenne nyomon követni a kódot és összehasonlítani az ügyfél kívánságaival.

A 2. listában található kódrészlet kiterjeszti a RaisingGear() függvényt. Vegye figyelembe, hogy a RaisingGear() függvény kódja általában tükrözi a Raising Gear állapot átmeneti táblázatának 2 sorát.

üres RaisingGear( üres )

/*Miután az összes kapcsoló fel van kapcsolva, lépjen a "váz fel" állapotba*/

ha((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pump_motor=OFF;

gear_lights = ALKALMAZÁS;

curr_state = GEAR_UP;

/*Ha a pilóta meggondolja magát, indítsa el a futómű visszahúzását*/

ha(sebességváltó kar == LE) (

pump_direction = LE;

aktuális_állapot = GEAR_LOWERING;

Ne felejtse el kerülni a rejtett állapotokat. A rejtett állapot akkor jelenik meg, ha lustaságból megpróbál egy feltételes részállapotot hozzáadni a konkrét állapot hozzáadása helyett. Például, ha a kódod ugyanazt a bemenetet különböző módokon dolgozza fel (azaz különböző állapotátmeneteket kezdeményez) az üzemmódtól függően, akkor ez egy rejtett állapot. Ebben az esetben arra lennék kíváncsi, hogy ezt az állapotot nem szabad-e kettéosztani? A rejtett állapotok használata tagadja az állapotgép használatának minden előnyét.

Gyakorlatként meghosszabbíthatja az imént vizsgált állapotgépet úgy, hogy időtúllépést ad az alváz visszahúzási vagy meghosszabbítási ciklusához, mint pl. a gépészmérnök nem akarja, hogy a hidraulika szivattyú 60 másodpercnél tovább működjön. Ha a ciklus véget ér, a pilótát figyelmeztetni kell a zöld és a piros lámpa kapcsolásával, és képesnek kell lennie a kart ismét mozgatni, hogy újra próbálkozzon. Megkérdezheti egy feltételezett gépészmérnököt is, hogy a szivattyút működés közben hogyan befolyásolja az irányváltás, mert ez 2 esetben fordul elő, amikor a pilóta meggondolja magát. Természetesen a szerelő azt fogja mondani, hogy ez negatív. Akkor hogyan változtatná meg az állapotgépet, hogy irányváltáskor gyorsan leállítsa a szivattyút?

Állami géptesztelés

A kódoló algoritmusok, mint véges állapotú gépek szépsége az, hogy a tesztterv szinte automatikusan megírja magát. Mindössze annyit kell tennie, hogy minden állapotátmeneten keresztül kell mennie. Ezt általában markerrel a kezemben teszem, és áthúzom a nyilakat az állapotátmenet diagramon, amikor átmennek a teszten. Ez egy jó módszer a „rejtett állapotok” elkerülésére – ezek gyakrabban hiányoznak a teszteknél, mint a konkrét állapotok.

Ehhez nagy türelem és sok kávé szükséges, hiszen egy közepes méretű állapotú gép is akár 100 különböző átmenettel rendelkezhet. Egyébként az ugrások száma remek módszer a rendszer összetettségének mérésére. Ez utóbbit a megrendelő igényei határozzák meg, az állapotgép pedig nyilvánvalóvá teszi a tesztelés körét. Kevésbé szervezett megközelítéssel a szükséges tesztelések mennyisége ugyanolyan lenyűgöző lehet, de Ön nem tud róla.

Nagyon kényelmes a nyomtatott utasítások használata a kódban, amelyek megjelenítik az aktuális állapotot, a bemeneti és kimeneti jelek értékeit. Így könnyen megfigyelhető, hogy mit fejez ki a "Szoftvertesztelés Aranyszabálya": tesztelje le, hogy a program azt csinálja-e, amire szánták, és azt is, hogy nem csinál-e semmi extrát. Más szóval, csak az elvárt eredményeket kapja, és mi történik még ezen kívül? Vannak-e "kemény" állapotátmenetek, pl. olyan állapotok, amelyek véletlenszerűen mennek át, csak a ciklus egy iterációjára? Változnak-e a kimenetek, amikor nem várod el tőlük? Ideális esetben a printfs kimenetének nagyon hasonlítania kell egy állapotátmeneti táblázatra.

Végül – és ez minden beágyazott szoftverre vonatkozik, nem csak az állapotgép alapú szoftverekre – legyen nagyon óvatos, amikor először futtatja a szoftvert valódi hardveren. Nagyon könnyen el lehet téveszteni a polaritást - "Hoppá, azt hittem, hogy az 1-es a váz felemelését jelenti, a "0" pedig azt, hogy leengedi." A hardveres asszisztensem sok esetben ideiglenes "csirkekapcsolót" használt, hogy megvédje az értékes alkatrészeket, amíg meg nem bizonyosodott arról, hogy a szoftverem a helyes irányba viszi a dolgokat.

dob

Ha minden vásárlói igény teljesül, pár napon belül be tudok dobni egy ilyen bonyolultságú állapotgépet. Szinte mindig az automaták azt csinálnak, amit akarok. A legnehezebb természetesen az, hogy pontosan megértsük, mit akar a vevő, és megbizonyosodunk arról, hogy maga az ügyfél tudja, mit akar. Ez utóbbi sokkal tovább tart!

Martin Gomez a Johns Hopkins Egyetem Alkalmazott Fizikai Laboratóriumának programozója. Kutató űrhajók repüléséhez szükséges szoftver fejlesztésével foglalkozik. 17 éve dolgozik a beágyazott rendszerek fejlesztése területén. Martin a Cornell Egyetemen szerzett Bachelor of Science fokozatot repülőgép- és űrmérnöki szakon, valamint MS diplomát villamosmérnöki szakon.

Egy véges automata bonyolultságának egyik kritériuma az állapotok száma. Minél kisebb ez a szám, annál egyszerűbb az automatát megvalósító diszkrét eszköz. Ezért a véges automaták elméletének egyik fontos problémája a legkisebb állapotszámú automata felépítése.

Mivel a modern számítógépekben minden információt bináris kódok formájában ábrázolnak, akkor egy automata felépítéséhez olyan elemeket használhat, amelyeknek csak két különböző stabil állapota van, amelyek közül az egyik a 0-nak, a másik az 1-es számnak felel meg.

Íme néhány példa a véges automatákra.

Példa 1. Késleltetési elem (memóriaelem).

A késleltető elemek egy bemenettel és egy kimenettel rendelkező eszközök. Sőt, a kimenő jel értéke az adott időpontban t egybeesik a jel előző pillanatbeli értékével. A késleltető elem sematikusan a következőképpen ábrázolható (2. ábra).

Tegyük fel, hogy a bemeneti és így a kimeneti ábécé is x ={0, 1}, Y =(0, 1). Azután K =(0, 1). A késleltető elem akkori állapota alatt t az emlékelem pillanatnyi tartalma megértve. Ily módon q (t )= x (t 1), a Y (t )= q (t )=x (t 1).

Állítsuk be a késleltetési elemet a táblázat szerint, ahol de 1 =0, de 2 =1, q 1 =0, q 2 =1,

(a 1 , q 1)= (0, 0)=0,  (a 1 , q 1)= (0, 0)=0;

(a 1 , q 2)= (0, 1)=0,  (a 1 , q 2)= (0, 1)=1;

(a 2 , q 1)= (1, 0)=1,  (a 2 , q 1)= (1, 0)=0;

(a 2 , q 2)= (1, 1)=1,  (a 2 , q 2)= (1, 1)=1;

q a
	=0,  =0	=0,  =1
	=1,  =0	=1,  =1

A Moore-diagram az ábrán látható. 3

Ennek az automatának Boole-függvényrendszerrel való ábrázolásához az automata táblázatot és a fenti algoritmust használjuk. Ebben az esetben a kódolás nem szükséges, mivel a bemeneti és kimeneti ábécé és állapotok már kódolva vannak.

Figyeljünk arra a tényre m=p=p =2. Azután k =r =s =1, ezért a késleltetési elemet két függvény adja meg  És  . Ezen függvények igazságtáblázata 2-t tartalmaz k + r =2 2 =4 sor és k +r +r +s =4 oszlop:

x	z

2. példa Bináris szekvenciális összeadó.

Ez a szekvenciális összeadó egy olyan eszköz, amely két számot ad össze a bináris rendszerben. A számok az összeadó bemeneteire kerülnek x 1 és x 2, a legkisebb jelentőségű számjegyekkel kezdve. A kimeneten a számbevitelnek megfelelő sorozat jön létre x 1 +x 2 a bináris számítási rendszerben (4. ábra).

A bemeneti és kimeneti ábécé egyedileg meghatározott: x ={00; 01; 10; 11}, Y =(0,1). Az állapothalmazt az átvitel értéke határozza meg a megfelelő számbitek összeadásakor x 1 és x 2. Ha néhány számjegy összeadása során átvitel keletkezik, akkor feltételezzük, hogy az összeadó átment az állapotba q egy . Ha nincs átvitel, akkor feltételezzük, hogy az összeadó állapotában van q 0 .

Az összeadót táblázat adja.

q a	q 0	q 1
	q 0 , 0	q 0 , 1
	q 0 , 1	q 1 , 0
	q 0 , 1	q 1 , 0
	q 1 , 0	q 1 , 1

Egy szekvenciális összeadó Moore-diagramja az 1. ábrán látható. öt.

Vegye figyelembe, hogy a bemeneti és kimeneti karakterek már kódolva vannak. Az állapotokat a következőképpen kódoljuk:  (q 0)=0,  (q 1)=1. Ezért a szekvenciális összeadót két Boole-függvény adja, amelyek igazságtáblázata a következő:

x 1	x 2	z

3. példa Egyenlőségi összehasonlító séma.

Az egyenlőség-összehasonlító áramkör olyan eszköz, amely két számot hasonlít össze. x 1 és x 2 , bináris rendszerben megadva. Ez a készülék a következőképpen működik. A készülék bemenetén sorban, a legmagasabbtól kezdve, a számjegyek betáplálása történik meg x 1 és x 2. Ezeket a rangokat összehasonlítják. Ha a bitek egyeznek, akkor az áramkör kimenetén a 0 kimeneti jel keletkezik, ellenkező esetben a kimeneten az 1. Egyértelmű, hogy az 1 megjelenése a kimeneti sorozatban azt jelenti, hogy az összehasonlított számok x 1 és x 2 különböző. Ha a kimeneti sorozat nulla és hossza megegyezik az összehasonlított számok számjegyeinek számával, akkor x 1 és x 2 .

Ehhez a géphez x ={00, 01, 10, 11}; Y ={0,1}.

Az áramkör működését két állapot határozza meg. Állapot q 0 megfelel az aktuálisan összehasonlított bitek egyenlőségének. Ebben az esetben a gép ugyanabban az állapotban marad. Ha a következő pillanatban az összehasonlított számjegyek eltérnek, akkor az automata új állapotba kerül q 1, és benne marad, mivel ez azt jelenti, hogy a számok eltérőek. Így az összehasonlítási sémát a táblázat adja meg:

q x	q 0	q 1
	q 0 , 0	q 1 , 1
	q 1 , 1	q 1 , 1
	q 1 , 1	q 1 , 1
	q 0 , 0	q 1 , 1

Az egyenlőség összehasonlító sémájának Moore-diagramja az 1. ábrán látható. 6.

Az állapotokat a következőképpen kódoljuk:  (q 0)=0,  (q 1)=1. Az automata két funkciót kap.

x 1	x 2	z

4. példa Egyenlőtlenségi összehasonlító séma.

Az egyenlőtlenség-összehasonlító áramkör egy olyan eszköz, amely lehetővé teszi annak megállapítását, hogy az összehasonlítás x 1 és x 2 , és ha nem egyenlők, derítsd ki, melyik nagyobb a másiknál. Ennek a készüléknek két bemenete és két kimenete van. Kimeneti jelek y 1 (t ) És y 2 (t ) az alábbi szabályok szerint határozzák meg:

y 1 (t )=y 2 (t )=0 ha x 1 (t )=x 2 (t );

y 1 (t )=1, y 2 (t )=0 ha x 1 (t )>x 2 (t ), azaz x 1 (t )=1, x 2 (t )=0;

y 1 (t )=0, y 2 (t )=1 ha x 1 (t )<x 2 (t ), azaz x 1 (t )=0, x 2 (t )=1.

Így amikor az összehasonlító áramkör bemenetére alkalmazzuk a számok egyenlőtlenségét x 1 =x 1 (l)… x 1 (t ) És x 2 =x 2(l)… x 2 (t ) ezeknek a számoknak a számjegyeit a rendszer egymás után összehasonlítja, a legmagasabbakkal kezdve. A kimeneti jelek a fenti szabályok szerint vannak megfogalmazva. Sőt, ha a kimeneti sorozat nulla párból áll, akkor x 1 =x 2. Ha az első eltér nullától, akkor a párnak megvan a formája , () azután x 1 >x 2 (x 1 <x 2).

Az áramkör leírásából az következik

x ={00, 01, 10, 11}, Y ={00, 01, 10}.

A séma állapotát a következőképpen határozzuk meg. Feltételezzük, hogy kezdetben t =1 a gép állapotban van q 1 . Ha a számok összehasonlított számjegyei x 1 És x 2 egyezik, akkor a gép ebben az állapotban marad. Vegye figyelembe, hogy a kimeneten a 00 jel jelenik meg.. Ha a szám számjegye x 1 kisebb (nagyobb) lesz a szám megfelelő számjegye x 2 , akkor a gép állapotba kerül q 2 (q 3). Ebben az esetben a 01 (10) jel jelenik meg a kimeneten. A jövőben a számok fennmaradó számjegyeinek benyújtásakor x 1 És x 2 az automata bemeneteire, az automata állapotban marad q 2 (q 3) és generálja a 10 (01) kimeneti szimbólumot. A fentiekből következik, hogy az egyenlőtlenség összehasonlítási sémáját a táblázat adja meg:

q x	q 1	q 2	q 3
	q 1 , 00	q 2 , 01	q 3 , 10
	q 2 , 01	q 2 , 01	q 3 , 10
	q 3 , 10	q 2 , 01	q 3 , 10
	q 1 , 00	q 2 , 01	q 3 , 10

A megfelelő Moore-diagram az ábrán látható. 7.

A bemeneti és kimeneti ábécé már itt van kódolva. Államok q 1 , q 2 és q 3 kódolás:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

Ezért ez az áramkör definiálható egy négy Boole-függvényből álló rendszerrel, amelyek négy változótól függenek. Ezeket a függvényeket részben az igazságtábla határozza meg és adja meg

	x 1	x 2	z 1	z 2

A táblázatban a * szimbólumok változókészleteket jelölnek x 1 , x 2 , z 1 , z 2 , amelyen a függvények  1 ,  2 ,  1 ,  2 nincs meghatározva. Tegyük fel függvényértékek  1 ,  2 ,  1 ,  2 ezeken a halmazokon egyenlő 1-gyel.

Ma a géppuskákról fogunk beszélni, de semmiképpen sem azokról, amelyeket az orosz hadsereg katonái tartanak. A mikrokontrollerek olyan érdekes programozási stílusáról fogunk beszélni, mint az automatikus programozás. Pontosabban ez nem is egy programozási stílus, hanem egy egész koncepció, aminek köszönhetően egy mikrokontroller programozó nagyban megkönnyítheti az életét. Ennek köszönhetően a programozónak bemutatott számos feladat sokkal könnyebben és egyszerűbben megoldható, megszabadítva a programozót a fejfájástól. Az automatikus programozást egyébként gyakran hívják SWITCH technológia.

Szeretném megjegyezni, hogy ennek a bejegyzésnek a megírására az volt az ösztönzés cikksorozat a SWITCH technológiáról Vlagyimir Tatarcsevszkij. A cikksorozat a "SWITCH technológia alkalmazása mikrokontrollerek alkalmazásszoftvereinek fejlesztésében" címet viseli. Ebben a cikkben tehát nagyrészt megpróbálok példát adni egy működő kódra és annak leírására.

Egyébként terveztem egy cikksorozatot a programozásról, amelyben részletesen megvizsgálom az ABP mikrokontrollerek programozási technikáit, ne hagyja ki…. Hát menjünk!

A program szekvenciálisan hajtja végre a programozó által megadott parancsokat. Egy közönséges számítógépes program esetében teljesen normális, ha a program befejezte és leállította a végrehajtását, miközben munkája eredményét megjeleníti a monitoron.

Egy mikrokontroller program nem fejezheti be egyszerűen a végrehajtását. Képzelje el, hogy bekapcsolta a lejátszót vagy a magnót. Megnyomta a bekapcsológombot, kiválasztotta a kívánt dalt, és élvezheti a zenét. Amikor azonban a zene abbahagyja a dobhártya rángatását, a lejátszó lefagy, és semmilyen módon nem reagál a gombok megnyomására, és még inkább a tamburával való táncra.

És mi ez? Minden rendben van - a vezérlő, amelyik a lejátszó mélyén van, éppen befejezte a program végrehajtását. Itt láthatja, milyen kényelmetlennek bizonyul.

Tehát innen arra a következtetésre jutunk, hogy a mikrokontroller programjának egyszerűen nem szabad leállnia. Lényegében egy végtelen ciklusnak kell lennie - csak ebben az esetben működne megfelelően a lejátszónk. A következőkben megmutatom, hogy milyenek a mikrokontrollerek programkódjai, ezek nem is tervek, hanem néhány programozási stílus.

Programozási stílusok.

A „programozási stílusok” valahogy érthetetlenül hangzik, de hát jó. Mit akarok ezzel mondani?. Képzeljük el, hogy az ember még soha nem programozott, vagyis általában egy komplett duma.

Ez a személy sok könyvet olvasott a programozásról, megtanulta a nyelv összes alapvető konstrukcióját.Apránként gyűjtötte az információkat, hiszen ma már korlátlan az információhoz való hozzáférés. Mindez jó, de vajon milyenek lesznek az első programjai? Számomra úgy tűnik, hogy nem filozofál, hanem az egyszerűtől a bonyolultig vezeti az utat.

Tehát ezek a stílusok egy egyszerű szintről egy összetettebbre vezető lépések, ugyanakkor hatékonyabbak.

Először nem gondoltam a program tervezési jellemzőire. Csak kialakítottam a program logikáját - rajzoltam egy folyamatábrát és megírtam a kódot. Abból, ami állandóan rábukkant egy gereblyére. De ez volt az első alkalom, amikor nem vettem gőzfürdőt, és az „egyszerű hurkolt” stílust használtam, aztán elkezdtem megszakításokat használni, aztán jöttek az automaták, és mentünk...

1. Egyszerű hurkok. A program ebben az esetben minden bonyodalmak nélkül hurkol, és ennek megvannak az előnyei és hátrányai. Ráadásul csak a megközelítés egyszerűsége miatt nem kell ravasz terveket kitalálnia, úgy ír, ahogy gondolja (fokozatosan a saját sírját ásva).

Void main(void) ( kezdeti_AL(); //a periféria inicializálása while(1) ( Leds_BLINK(); //a LED villogó funkciója signal_on(); //a jel bekapcsolásának funkciója signal_off(); // a jel kikapcsolásának funkciója l=button( ); //a gombok megnyomásáért felelős változó switch(l) //A változó értékétől függően egy vagy másik művelet végrehajtásra kerül ( 1. eset: ( Deistvie1(); / /Függvény helyett lehet egy feltételes operátor Deistvie2(); //vagy több ág váltja a kis- és nagybetűket Deistvie3(); Deistvie4(); Deistvie5(); ); 2. eset: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ; . . . . . . . . . ) ) )

A program munkapontja sorrendben mozog. Ebben az esetben minden művelet, feltétel és ciklus egymás után kerül végrehajtásra. A kód lassulni kezd, sok extra feltételt kell beilleszteni, ami megnehezíti az érzékelést.

Mindez nagymértékben megzavarja a programot, és a feltételek kuszaságát hozza létre a kódból. Ennek eredményeként ezt a kódot nem lehet hozzáadni vagy elvenni, olyan lesz, mint egy monolit darab. Természetesen, ha nem nagy a kötet, a kód módosítható, de minél tovább, annál nehezebb.

Ezzel a megközelítéssel több programot is írtam, nem voltak nagyok és teljesen működőképesek, de a láthatóság sok kívánnivalót hagyott maga után. Új feltétel hozzáadásához az egész kódot be kellett lapátolni, mert minden le volt kötve. Ez sok hibát és fejfájást okozott. A fordító megesküdött, amint lehetett, egy ilyen program hibakeresése pokollá vált.

2. Ciklus + megszakítások.

Megszakításokkal részben feloldhatja a végtelen fékezési ciklust. A megszakítások segítenek kitörni egy ördögi körből, segítenek ne lemaradni egy fontos eseményről, további funkciókat adnak hozzá (időzítőkből származó megszakítások, külső megszakítások).

Tegyük fel, hogy leállíthatja a gombok feldolgozását, vagy egy fontos esemény nyomon követését egy megszakításnál. Ennek eredményeként a program vizuálisabbá válik, de nem kevésbé zavaró.

Sajnos a megszakítás nem menti meg attól a káosztól, amibe a program belecsap. Nem lehet részekre osztani azt, ami egyetlen egész.

3. Automatikus programozás.

Tehát eljutunk a cikk fő témájához. A véges állapotú gépeken történő programozás megmenti a programot az első két példában rejlő hiányosságoktól. A program egyszerűbbé válik, könnyen módosítható.

Az automata stílusban írt program olyan, mint egy kapcsoló, amely a körülményektől függően átkapcsol egyik vagy másik állapotba. Az állapotok számát kezdetben a programozó ismeri.

Nagyjából olyan, mint egy villanykapcsoló. Két be- és kikapcsolási állapot, valamint két be- és kikapcsolási állapot létezik. Nos, először a dolgok.

Multitasking megvalósítása kapcsolótechnológiában.

A mikrokontroller képes a terhelés szabályozására, a LED-ek villogására, a billentyűleütések nyomon követésére és még sok másra. De hogyan lehet mindezt egyszerre? Számos megoldás létezik erre a problémára. Ezek közül a legegyszerűbb, amit már említettem, a megszakítások használata.

A program során, amikor megszakítás történik, a vezérlő elvonja a figyelmét a programkód végrehajtásáról, és rövid időre végrehajtja a program egy másik részét, amelyért a megszakítás felelős. A megszakítás működni fog, majd a program munkapontja onnan folytatódik, ahonnan a vezérlőt a megszakítás megszakította (maga a szó jelzi, hogy a vezérlő megszakadt).

A multitasking megvalósításának másik módja az operációs rendszerek használata. Igen, már elkezdtek megjelenni a kis OS-ek, amelyek alacsony fogyasztású vezérlőn is használhatók. De gyakran ez a módszer kissé feleslegesnek bizonyul. Végül is minek pazarolni az irányító erőforrásait felesleges munkával, ha kevés vérontással is meg lehet boldogulni.

A switch technológiával írt programokban a multitasking ilyen „illúziója” az üzenetküldő rendszernek köszönhetően keletkezik. Azért írtam "illúziót", mert tényleg az, mert a program fizikailag nem tudja egyszerre végrehajtani a kód különböző részeit. Kicsit tovább fogok beszélni az üzenetküldő rendszerről.

Üzenetküldő rendszer.

Az üzenetküldő rendszer használatával több folyamatot is megsemmisíthet, és a többfeladatos munka illúzióját keltheti.

Tegyük fel, hogy kell egy program, amiben a LED át van kapcsolva. Itt van két gépünk, nevezzük őket LEDON-nak - a LED bekapcsolásáért felelős gép és a LEDOFF gép - a LED kikapcsolásáért felelős gép.

Mindegyik automatának két állapota van, vagyis az automata lehet aktív vagy inaktív állapotban, például a késkapcsoló be- vagy kikapcsolt állapotban van.

Az egyik gép aktiválásakor a LED világít, a másik gép aktiválásakor a LED kialszik. Vegyünk egy kis példát:

Int main(void) ( INIT_PEREF(); //perifériák (LED-ek) inicializálása InitGTimers(); //időzítők inicializálása InitMessages(); //üzenetfeldolgozó mechanizmus inicializálása InitLEDON(); //LEDON automata inicializálása InitLEDOFF(); // a LEDOFF automata inicializálása SendMessage(MSG_LEDON_ACTIVATE); //aktiválja a LEDON automatát sei(); //megszakítások engedélyezése //Fő hurok programozása while(1) ( ProcessLEDON(); //a LEDON iterációja automata ProcessLEDOFF(); //a LEDOFF automata ProcessMessages iterációja (); //üzenetfeldolgozás ); )

A 3-7. sorban különféle inicializálások fordulnak elő, ezért ez most nem különösebben érdekel minket. Ekkor azonban a következő történik: a főhurok elindítása előtt ((1) közben) üzenetet küldünk az automatának

Üzenet küldése (MSG_LEDON_ACTIVATE)

felelős a LED világításáért. Enélkül a kis lépés nélkül a sürgősségünk nem fog működni. Ezután a fő végtelen while ciklus végzi el a munka nagy részét.

Kis kitérő:

Az üzenetnek három állapota van. Ugyanis az üzenet állapota lehet inaktív, beállított, de inaktív és aktív.

Kiderült, hogy az üzenet kezdetben inaktív volt, amikor elküldtük az üzenetet, "telepítve, de inaktív" állapotot kapott. Ez pedig a következőket adja nekünk. A program szekvenciális végrehajtása esetén a LEDON automata nem kap üzenetet. A LEDON automata üresjárati iterációja következik be, amelyben az üzenet egyszerűen nem fogadható. Mivel az üzenet állapota "telepítve, de inaktív", a program folytatja a végrehajtást.

Miután az összes automata tétlen, a sor eléri a ProcessMessages() függvényt. Ez a funkció mindig a ciklus végére kerül, miután minden automata iterációt befejezett. A ProcessMessages() függvény egyszerűen megváltoztatja az üzenetet a "beállított, de inaktív" állapotról "aktív" állapotra.

Amikor a végtelen hurok befejezi a második kört, már teljesen más a kép. A ProcessLEDON automata iterációja többé nem lesz tétlen. A gép képes lesz fogadni az üzenetet, átkapcsolni világító állapotba és felváltva el is küldeni az üzenetet. Ez a LEDOFF automatának lesz címezve, és az üzenet életciklusa megismétlődik.

Szeretném megjegyezni, hogy az "aktív" állapotú üzenetek megsemmisülnek, amikor találkoznak a ProcessMessages funkcióval. Ezért üzenetet csak egy automata fogadhat. Van egy másik típusú üzenet is - ezek sugárzott üzenetek, de nem fogom ezeket figyelembe venni, Tatarcsevszkij cikkei is jól foglalkoznak velük.

Időzítők

Megfelelő üzenetkezeléssel szabályozhatjuk az állapotgépek működési sorrendjét, de nem nélkülözhetjük egyedül az üzeneteket.

Talán észrevette, hogy az előző példakódrészlet nem fog megfelelően működni. A gépek üzenetet váltanak, a LED-ek kapcsolnak, de ezt nem fogjuk látni. Csak egy gyengén világító LED-et fogunk látni.

Ennek az az oka, hogy nem gondoltuk át a késések illetékes feldolgozását. Hiszen nem elég, ha felváltva kapcsoljuk ki-be a LED-eket, a LED-nek minden állapotban el kell maradnia például egy másodpercig.

Az algoritmus a következő lesz:

Kattintson a nagyításhoz

Elfelejtettem hozzátenni ehhez a blokkdiagramhoz, hogy amikor az időzítő ketyeg, akkor természetesen egy műveletet hajtanak végre - meggyújtják a LED-et vagy kikapcsolják.

1. Üzenet fogadásával belépünk az állapotba.

2. Ellenőrizzük az időzítő/számláló állásait, ha ketyeg, akkor végrehajtjuk a műveletet, ellenkező esetben csak üzenetet küldünk magunknak.

3. Üzenetet küldünk a következő automatának.

4. Kilépés

A következő bejegyzésben minden megismétlődik.

SWITCH technológiai program. Három lépés.

És írjunk egy programot véges automatákkal, és ehhez mindössze három egyszerű lépést kell megtennünk. A program egyszerű lesz, de érdemes egyszerű dolgokkal kezdeni. Nekünk egy kapcsoló LED-es program megfelelő. Ez egy nagyon jó példa, úgyhogy ne találjunk ki semmi újat.

C nyelven fogom írni a programot, de ez egyáltalán nem jelenti azt, hogy véges automatákban csak C nyelven kell írni, teljesen lehetséges bármilyen más programozási nyelv használata.

A program moduláris lesz, ezért több fájlra lesz felosztva. Moduljaink a következők lesznek:

• A program főhurok modulja a leds_blink.c, HAL.c, HAL.h fájlokat tartalmazza
• Időzítő modul timers.c, timers.h fájlokat tartalmaz
• Üzenetfeldolgozó modul üzenetek.c, üzenetek.h fájlokat tartalmaz
  
• Gép modul 1 ledon.c, ledon.h fájlokat tartalmaz
• 2. gépmodul ledoff.c fájlokat tartalmaz, ledoff .h

1. lépés.

Létrehozunk egy projektet, és azonnal kapcsoljuk hozzá statikus moduljaink fájljait: timers.c, timers.h, messages.c, messages.h.

A program fő ciklusának moduljának leds_blink.c fájlja.

#include "hal.h" #include "messages.h" //üzenetfeldolgozó modul #include "timers.h" //timers module //Időzítő megszakítások //############# # ################################################# ############################ ISR(TIMER0_OVF_vect) // Vektorátmenet megszakítása (T0 számláló időzítő túlcsordulása) ( ProcessTimers(); / /Időzítő megszakításkezelő) //########################################### ############################################### (void) ( INIT_PEREF(); //periféria (LED-ek) inicializálása InitGTimers(); //időzítők inicializálása InitMessages(); //üzenetfeldolgozó mechanizmus inicializálása InitLEDON(); //LEDON automata inicializálása InitLEDOFF(); StartGTimer( TIMER_SEK); //Az időzítő indítása SendMessage(MSG_LEDON_ACTIVATE); //aktiválja az FSM1 automatát sei(); //Megszakítások engedélyezése //Fő hurok programozása while(1) ( ProcessLEDON(); //iteráció a LEDON automata ProcessLEDOFF(); ProcessMessages( ); //üzenetfeldolgozás ); )

Az első sorokban a többi modul a főprogramhoz kapcsolódik. Itt látjuk, hogy az időzítő modul és az üzenetfeldolgozó modul össze van kötve. A következő a programban a túlcsordulási megszakítási vektor.

Az int main (void) sorból azt mondhatjuk, hogy a főprogram kezdődik. És minden és mindenki inicializálásával kezdődik. Itt inicializáljuk a perifériákat, vagyis beállítjuk a kezdeti értékeket a komparátor bemeneti/kimeneti portjaira és a vezérlő összes többi tartalmára. Mindezt az INIT_PEREF függvény végzi, itt futtatjuk, bár a törzse a hal.c fájlban található.

Ezután az időzítők inicializálását, az üzenetfeldolgozó modult és az automaták inicializálását látjuk. Itt ezek a funkciók is egyszerűen elindulnak, bár maguk a függvények be vannak írva a moduljaik fájljaiba. Nézze meg, milyen kényelmes. A program fő szövege továbbra is könnyen olvasható, és nincs zsúfolva a redundáns kóddal, amely eltöri a lábát.

A fő inicializálások véget értek, most el kell indítani a fő ciklust. Ehhez elküldjük a start üzenetet, és emellett elindítjuk az órát - elindítjuk az időzítőt.

StartGTimer(TIMER_SEK); //Időzítő indítása SendMessage(MSG_LEDON_ACTIVATE); //aktiválja az FSM1 gépet

És a fő hurok, mint mondtam, nagyon egyszerűnek tűnik. Minden automata funkcióját felírjuk, csak egy oszlopba írjuk, a sorrend betartása nélkül. Ezek a funkciók automata kezelők, és az automata modulokban találhatók. Az üzenetfeldolgozó modul funkciója teszi teljessé ezt az automata piramist. Természetesen ezt már korábban is elmondtam, amikor az üzenetküldő rendszerrel foglalkoztam. Most láthatja, hogyan néz ki a fő programhurok moduljának további két fájlja

A Hal.h a program fő hurokmoduljának fejlécfájlja.

#ifndef HAL_h #define HAL_h #include #beleértve //Szabványos könyvtár megszakításokkal #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Amint láthatja, ez a fájl nem tartalmaz egyetlen sort sem a végrehajtható kódból – ezek mind makróhelyettesítések és könyvtárkapcsolatok. Ezzel a fájllal nagyon jó az élet, javítja a láthatóságot.

De a Hal.c fájl már egy futtatható fájl, és mint már említettem, különféle perifériás inicializálásokat tartalmaz.

#include "hal.h" void INIT_PEREF(void) ( //I/O portok inicializálása //############################ ################################################# # ##### Komparátor = ViklKomparator; //összehasonlító inicializálása - DDRD kikapcsolása = 1<

Nos, megmutattam a program fő ciklusának modulját, most meg kell tennünk az utolsó lépést, meg kell írnunk magukat az automaták moduljait.

3. lépés

Nekünk marad a véges automaták moduljainak megírása, esetünkben a LEDON automata és a LEDOFF automata. Kezdésnek megadom a LED-et világító gép programjának szövegét, a ledon.c fájlt.

//ledon.c fájl #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //állapotváltozó void InitLEDON(void) ( ledon_state=0; //itt más automata változókat is inicializálhatunk, ha léteznek ) void ProcessLEDON(void) ( switch(ledon_state) ( 0. eset: //inaktív állapot if(GetMessage (MSG_LEDON_ACTIVATE) )) //ha van üzenet, akkor az elfogadásra kerül ( //és az időzítőt ellenőrizzük if(GetGTimer(TIMER_SEK)==one_sek) //ha az időzítő 1s-et állított be, akkor végrehajtja ( StopGTimer(TIMER_SEK); PORTD = 1<

Itt az első sorokban, mint mindig, a könyvtárak kapcsolódnak és a változók deklarálva vannak. Ezután már elmentünk azokhoz a funkciókhoz, amelyekkel már találkoztunk. Ez az InitLEDON automata inicializálási funkciója és magának a ProcessLEDON automata kezelőnek a funkciója.

A kezelő törzsében az időzítő modulból és az üzenetmodulból származó funkciók már feldolgozás alatt állnak. Maga az automata logikája pedig a kapcsolóház kialakításán alapul. És itt látható, hogy az automatakezelőt is bonyolíthatja néhány esetkapcsoló hozzáadásával.

Az automata fejlécfájlja még egyszerűbb lenne:

//fsm1 fájl #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Ide kapcsoljuk a hal.h hivatkozásfájlt, és megadjuk a függvények prototípusait is.

A LED kikapcsolásáért felelős fájl csak tükörképen fog szinte ugyanúgy kinézni, ezért itt nem jelenítem meg - vonakodás 🙂

Az összes projektfájlt letöltheti ezen a linken ====>>> LINK.

Íme, csak három lépés, és programunk kész megjelenést kapott, ami azt jelenti, hogy a mai küldetésem véget ért, és ideje befejezni. Számomra úgy tűnik, hogy az ebben a cikkben található információk nagyon hasznosak lesznek az Ön számára. De ez csak akkor hoz valódi hasznot, ha ezt a tudást a gyakorlatba is átülteti.

Egyébként számos érdekes projektet terveztem, amelyek különösen érdekesek lesznek, úgyhogy mindenképpen tedd meg iratkozz fel az új cikkekre . További anyagok kiküldését is tervezem, így már sokan feliratkoznak az oldal főoldalára. Itt is lehet feliratkozni.

Nos, most már tényleg mindenem megvan, úgyhogy sok szerencsét, jó hangulatot és viszontlátást kívánok.

N/A Vlagyimir Vasziljev

Az állapotgép egy absztrakt modell, amely valaminek véges számú állapotát tartalmazza. Bármely parancs végrehajtási folyamatának ábrázolására és vezérlésére szolgál. Az állapotgép ideális a mesterséges intelligencia játékokban való megvalósításához, ügyes megoldáshoz nehéz és összetett kód írása nélkül. Ebben a cikkben bemutatjuk az elméletet, és megtanuljuk, hogyan kell használni egy egyszerű és veremalapú állapotgépet.

A mesterséges intelligencia állapotgép segítségével történő megírásáról már cikksorozatunk is megjelent. Ha még nem olvastad ezt a sorozatot, most megteheted:

Mi az a véges állapotú gép?

A véges állapotú gép (vagy egyszerűen FSM - véges állapotú gép) egy hipotetikus állapotgépen alapuló számítási modell. Egyszerre csak egy állapot lehet aktív. Ezért bármilyen művelet végrehajtásához a gépnek meg kell változtatnia az állapotát.

Az állapotgépeket általában valami végrehajtási folyamatának megszervezésére és reprezentálására használják. Ez különösen akkor hasznos, ha a mesterséges intelligenciát játékokban valósítja meg. Például az ellenség "agyát" leírni: minden állapot valamilyen cselekvést (támadás, kitérés stb.) képvisel.

Egy véges automata ábrázolható gráfként, melynek csúcsai az állapotok, élei pedig a köztük lévő átmenetek. Minden élen van egy címke, amely jelzi, hogy mikor kell megtörténnie az átmenetnek. Például a fenti képen láthatja, hogy az automata az állapotát „vándorlásról” „támadás” állapotra változtatja, feltéve, hogy a játékos a közelben van.

Ütemezési állapotok és átmeneteik

A véges állapotú gép megvalósítása az állapotok és a köztük lévő átmenetek azonosításával kezdődik. Képzeljünk el egy állapotgépet, amely leírja egy hangya tevékenységét, aki leveleket visz a hangyabolyba:

A kiindulópont a "levél keresése" állapot, amely addig marad aktív, amíg a hangya meg nem találja a levelet. Amikor ez megtörténik, az állapot „hazamegy”-re változik. Ugyanez az állapot aktív marad mindaddig, amíg a hangyánk a hangyabolyhoz nem ér. Ezt követően az állapot visszaváltozik "levél keresésre".

Ha a "levél keresése" állapot aktív, de az egérkurzor a hangya mellett van, akkor az állapot "menekülés"-re változik. Amint a hangya kellően biztonságos távolságra van az egérkurzortól, az állapot visszavált "levél keresésre".

Kérjük, vegye figyelembe, hogy amikor hazafelé vagy házon kívülre indul, a hangya nem fog félni az egérkurzortól. Miért? És mivel nincs megfelelő átmenet.

Egy egyszerű állapotgép megvalósítása

Egy állapotgép egyetlen osztály használatával is megvalósítható. Nevezzük FSM-nek. Az ötlet az, hogy minden állapotot módszerként vagy funkcióként valósítsunk meg. Az aktív állapot meghatározásához az activeState tulajdonságot is használjuk.

Public class FSM ( private var activeState:Function; // mutató az automata aktív állapotára public function FSM() ( ) public function setState(state:Function) :void ( activeState = állapot; ) public function update() :void ( if ( activeState != null) ( activeState(); ) ) )

Minden állapot egy funkció. Sőt, úgy, hogy a játékkeret frissítésekor minden alkalommal meghívásra kerül. Mint már említettük, az activeState egy mutatót tárol az aktív állapot függvényre.

Az FSM osztály update() metódusát minden játékkeretben meg kell hívni. Ő pedig az állam jelenleg aktív funkcióját fogja hívni.

A setState() metódus beállítja az új aktív állapotot. Sőt, minden egyes függvénynek, amely az automata valamilyen állapotát meghatározza, nem kell az FSM osztályhoz tartoznia – ez teszi osztályunkat univerzálisabbá.

Állapotgép segítségével

Valósítsuk meg a hangya AI-t. Fentebb már bemutattuk állapotainak halmazát és a köztük lévő átmeneteket. Illusztráljuk őket még egyszer, de ezúttal a kódra koncentrálunk.

Hangyánkat a Hangya osztály képviseli, amelynek agymezője van. Ez csak egy példánya az FSM osztálynak.

Public class Ant ( public var position:Vector3D; public var speed:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) ( pozíció = new Vector3D(posX, posY); sebesség = new Vector3D( -1, -1); brain = new FSM(); // Kezdje azzal, hogy keressen egy levelet. agy. setState(findLeaf); ) /** * Állítsa be a „findLeaf” kifejezést. * A hangyát leveleket keres. */ public function findLeaf( ) :void ( ) /** * A "goHome" állapot * A hangyát a hangyabolyba indítja */ public function goHome() :void ( ) /** * A "runAway" állapot * A ant hogy elfusson az egérkurzor elől * / public function runAway() :void ( ) public function update():void ( // Frissítse az állapotgépet. Ez a függvény meghívja // az aktív állapotfüggvényt: findLeaf(), goHome () vagy runAway(). brain.update( ); // Sebesség alkalmazása a hangya mozgására. moveBasedOnVelocity(); ) (...) )

Az Ant osztály sebesség- és helyzettulajdonságokat is tartalmaz. Ezeket a változókat használjuk a mozgás kiszámításához az Euler-módszerrel. Az update() függvény minden alkalommal meghívásra kerül, amikor a játékkeret frissül.

Az alábbiakban bemutatjuk az egyes módszerek végrehajtását, a findLeaf()-től kezdve, amely a levelek megtalálásáért felelős állapot.

Nyilvános függvény findLeaf() :void ( // A hangyát a levélre mozgatja. velocity = new Vector3D(Játék.példány.levél.x - pozíció.x, Játék.példány.levél.y - pozíció.y); if (távolság (Játék .instance.leaf, ez)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

A goHome() állapot arra szolgál, hogy a hangyát hazamenjen.

Nyilvános függvény goHome() :void ( // A hangyát az otthoni sebességre mozgatja = new Vector3D(Játék.példány.home.x - pozíció.x, játék.példány.home.y - pozíció.y); if (distance( játék. példa.otthon, ez)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

És végül a runAway() állapot – az egérkurzor elkerülésekor használatos.

Publikus függvény runAway() :void ( // Elmozdítja a hangyát a kurzortól sebesség = new Vector3D(pozíció.x ​​- Játék.egér.x, pozíció.y - Játék.egér.y); // A kurzor még mindig a közelben van ? if ( distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Nem, már messze van. Ideje visszatérni a levelek kereséséhez. brain.setState(findLeaf); ) )

FSM fejlesztés: Stack alapú automata

Képzeld el, hogy a hazafelé tartó hangyának is el kell menekülnie az egérkurzor elől. Így fognak kinézni az FSM államok:

Triviális változásnak tűnik. Nem, egy ilyen változás problémát okoz számunkra. Képzeld el, hogy a jelenlegi állapot "elmenekül". Ha az egérkurzor eltávolodik a hangyától, mit tegyen: menjen haza, vagy keressen egy levelet?

A probléma megoldása egy verem alapú állapotgép. A fentebb megvalósított egyszerű FSM-től eltérően ez a fajta FSM egy veremet használ az állapotok kezelésére. A verem tetején az aktív állapot látható, és az átmenetek akkor következnek be, amikor állapotokat adunk hozzá/eltávolítunk a veremből.

És itt van egy vizuális bemutató egy állapotgép működéséről a verem alapján:

Verem alapú FSM megvalósítása

Egy ilyen véges állapotú gép ugyanúgy megvalósítható, mint egy egyszerű. A különbség a szükséges állapotokra mutató mutatók tömbjének használata lesz. Többé nem lesz szükségünk az activeState tulajdonságra, mert a verem teteje már az aktív állapotra fog mutatni.

Nyilvános osztály StackFSM ( private var stack:Array; public function StackFSM() ( this.stack = new Array(); ) public function update() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction() ; ) ) public function getCurrentState() :Function ( return stack.length > 0 ? verem : null; ) )

Vegye figyelembe, hogy a setState() metódust a pushState() (új állapot hozzáadása a verem tetejéhez) és popState() (az állapot eltávolítása a verem tetejéről) metódusra cserélték.

A verem alapú FSM használata

Fontos megjegyezni, hogy verem alapú állapotgép használatakor minden állapot felelős azért, hogy eltávolítsa magát a veremből, amikor nincs rá szükség. Például az attack() állapotnak magának kell eltávolítania magát a veremből, ha az ellenséget már megsemmisítették.

Public class Ant ((...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ((...) brain = new StackFSM(); // Kezdje azzal, hogy keressen egy levél agyat. pushState( findLeaf); (...) ) /** * Állítsa be a "findLeaf" állapotot. * A hangya leveleket keres. */ nyilvános függvény findLeaf() :void ( // A hangyát a levélre mozgatja. velocity = new Vector3D(Játék.példány.levél.x - pozíció.x, játék.példány.levél.y - pozíció.y); if (távolság(játék.példány.levél, ez)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // Nem, már messze van. Ideje visszatérni a levelek kereséséhez. brain.popState(); ) ) (...) )

Kimenet

Az állapotgépek minden bizonnyal hasznosak a mesterséges intelligencia logikájának játékokban való megvalósításához. Könnyen ábrázolhatók grafikonként, amely lehetővé teszi a fejlesztő számára, hogy minden lehetséges opciót láthasson.

Az állapotgép állapotfüggvényekkel való megvalósítása egyszerű, de hatékony technika. Az FSM használatával még bonyolultabb állapotösszefonódások is megvalósíthatók.