Teoria automatelor

Definiția unui automat și a soiurilor sale. Tabele și grafice ale tranzițiilor și ieșirilor. Subautomate. Teorema automată redusă

Operații cu mașini

Conversia unei mașini de făină într-o mașină Moore și a unei mașini Moore la o mașină de făină. Echivalența automatelor. Distingerea stărilor automatelor. Minimizarea automatelor. Sinteza automatelor. Recunoașterea automatelor

Automat - un sistem de mecanisme, dispozitive, în care procesele de obținere, conversie, transfer de energie, materiale, informații sunt complet automatizate. Termenul „automat” este folosit în două aspecte:

1) tehnic,

2) matematică.

În abordarea matematică, un automat este înțeles ca un model matematic al unui dispozitiv tehnic care trebuie să aibă intrări, stări interne și ieșiri. Nu ar trebui să existe informații cu privire la detaliile structurii dispozitivului.

În abordarea tehnică, un automat este înțeles ca fiind un dispozitiv foarte real, de exemplu, o cabină telefonică, un automat de vânzare etc. În acest caz, desigur, sunt cunoscute detaliile structurii interne a dispozitivului.

Un caz special și important al unui automat este un automat digital (DA), în care procesele de primire, conversie, stocare și emitere a informațiilor digitale sunt complet automatizate.

Din punct de vedere al semnalelor, este util să definim CA ca un sistem care poate recepționa semnale de intrare, sub influența lor, să treacă de la o stare la alta, să-l salveze până la sosirea următorului semnal de intrare și să emită semnale de ieșire.

CA este considerat finit dacă seturile de semnale de intrare X, stările S și semnalele de ieșire Y sunt finite. Un automat finit poate fi asociat cu un dispozitiv precum un computer. Calculatorul procesează datele de intrare primite în date de ieșire (rezultat), dar acest rezultat corespunde nu numai datelor de intrare, ci și stării curente a computerului, adică. acele date care sunt stocate în memoria computerului, de exemplu, rezultatele calculelor anterioare, programele de calcul.

Lucrarea CA este efectuată în timp automat, determinat de numărul de perioade de recepție a semnalelor de intrare.

Un automat abstract este un model matematic al unui dispozitiv discret care are un canal de intrare, care primește secvențe de simboluri din orice limbă, un canal de ieșire, din care sunt preluate secvențe de simboluri din orice altă limbă și care se află în orice stare la fiecare moment de timp discret. Grafic, automatul abstract este prezentat în fig.

Cuvintele limbajului de intrare pot fi reprezentate prin simboluri ale mulțimii X=(x 1 ,x 2 ,...x n ), care se numește alfabet de intrare, iar cuvintele limbajului de ieșire sunt simboluri ale mulțimii Y=(y 1 ,y 2 ,...y p ), care se numește alfabetul de ieșire. Mulțimea stărilor automatului S=(s 1 ,s 2 ,...s m ) se numește alfabet de stat.

concept starea mașinii este folosit pentru a descrie sisteme ale căror semnale de ieșire depind nu numai de semnalele de intrare la un moment dat, ci și de o anumită preistorie, adică semnale care au ajuns mai devreme la intrările sistemului. În consecință, automatele digitale aparțin unor circuite secvențiale, care, după cum sa menționat deja, au memorie. Conceptul de stare a unui automat corespunde unei amintiri a trecutului, deci introducerea acestui concept permite eliminarea timpului ca variabilă explicită și exprimarea semnalelor de ieșire în funcție de stări și semnale de intrare.

Funcționarea unui automat abstract ar trebui luată în considerare în raport cu anumite intervale de timp, deoarece fiecare interval discret t va potrivi ieșirea sa y(t). În consecință, funcționarea automatului este considerată prin intervale de timp discrete de durată finită. În teoria abstractă a automatelor digitale, se consideră că semnalele de intrare acționează asupra automatului sincron la începutul fiecărui i-al-lea interval (cuantum) de timp alocat de impulsul (ciclul) de ceas corespunzător, iar modificarea stărilor interne ale automatului are loc în intervalele de timp dintre impulsurile de ceas adiacente, când nu există nicio influență a semnalelor de intrare.

Conceptul de „stare” este folosit pentru a stabili dependența funcțională a simbolurilor și/sau cuvintelor limbajului de ieșire generat de automat de simbolurile și/sau cuvintele limbajului de intrare atunci când automatul implementează algoritmul dat. Pentru fiecare stare a automatului sОS și pentru fiecare simbol xОX la momentul timpului discret [t], simbolul yОY este generat la ieșirea dispozitivului. Această dependență este determinată de funcția de ieșire a automatului j. Pentru fiecare stare curentă a automatului sОS și pentru fiecare simbol xОX în momentul timpului discret [t], automatul trece la următoarea stare sОS. Această dependență este determinată de funcția de tranziție a automatului y. Funcționarea automatului constă în generarea a două secvențe: o succesiune de stări succesive ale automatului (s 1[ s 2 s 3 ...) și o secvență de simboluri de ieșire (y 1 y 2 y 3 ...), care pentru succesiunea de simboluri (x 1 x 2 x 3 ...) se desfășoară la momentele de timp discret t = 1,2,3,.... În paranteze dreptunghiulare indicați momentele de timp discret, care altfel se numesc cicluri, în paranteze - secvențe de simboluri ale alfabetelor X, Y și S.

Deci, modelul matematic al unui automat finit este o algebră cu trei de bază, ale cărei purtători sunt trei mulțimi X, Y și S, iar operațiile sunt două funcții j și y.

În acest articol, termenul „mașină de stări” se referă la un algoritm care poate fi într-una dintr-un număr mic de stări. „Starea” este o anumită condiție care definește o relație dată de semnale de intrare și de ieșire, precum și semnalele de intrare și stările ulterioare. Cititorul inteligent va observa imediat că mașinile de stat descrise în acest articol sunt mașini Mealy. O mașină Mealy este o mașină cu stări finite în care ieșirile sunt funcții ale stării curente și ale intrării, spre deosebire de mașina Moore, unde ieșirile sunt doar funcții ale stării. În ambele cazuri, starea ulterioară este o funcție a stării curente și a semnalului de intrare.

Luați în considerare un exemplu de mașină simplă cu stări finite. Imaginați-vă că într-un șir de text trebuie să recunoașteți secvența de caractere „//”. Figura 1 arată cum se face acest lucru folosind o mașină de stări. Prima apariție a barei oblice nu produce un semnal de ieșire, dar face ca automatul să intre în a doua stare. Dacă automatul nu găsește o bară oblică în a doua stare, revine la prima, deoarece are nevoie de 2 bare oblice la rând. Dacă se găsește a doua bară oblică, automatul emite un semnal „gata”.

Aflați de ce are nevoie clientul.

Desenați o diagramă de tranziție a stărilor

Codați „scheletul” mașinii de stări fără a detalia operațiunile de tranziție.

Asigurați-vă că tranzițiile funcționează corect.

Specificați detaliile tranzițiilor.

Fa un test.

Exemplu de mașină de stat

Să luăm în considerare un exemplu mai interesant de mașină cu stări finite - un program care controlează retragerea și extinderea trenului de aterizare a aeronavei. Deși în majoritatea aeronavelor această procedură este efectuată folosind un mecanism de control electro-hidraulic (pur și simplu pentru că nu există computer la bord), în unele cazuri, cum ar fi vehiculele aeriene fără pilot, merită să utilizați controlul software.

În primul rând, să ne ocupăm de echipament. Trenul de aterizare al aeronavei este format din trenul de aterizare din față, trenul de aterizare principal din stânga și trenul principal de aterizare din dreapta. Acestea sunt antrenate de un mecanism hidraulic. O pompă hidraulică acționată electric furnizează presiune către servomotorul de putere. Folosind software-ul, pompa este pornită sau oprită. Calculatorul ajustează poziția supapei direcționale - „jos” sau „sus” pentru a permite presiunii să ridice sau să coboare șasiul. Fiecare dintre picioarele trenului de aterizare are un întrerupător de limită: unul dintre ele este închis dacă trenul de aterizare este ridicat, celălalt - dacă este fixat în poziția „jos”. Pentru a determina dacă aeronava se află la sol, comutatorul de limită de pe brațul treptei frontale se închide dacă greutatea aeronavei se află pe trenul anterior. Comenzile pilotului constau dintr-un braț al trenului de aterizare superior/inferior și trei lumini (câte una pentru fiecare picior) care pot fi stinse, verzi (poziție în jos) sau roșii (poziția de tranziție).

Și acum să trecem la dezvoltarea unei mașini cu stări finite. Primul și cel mai dificil pas este înțelegerea așteptărilor reale ale clientului. Unul dintre avantajele unei mașini de stări este că forțează programatorul să se gândească la toate cazurile posibile și, ca urmare, să primească toate informațiile necesare de la client. De ce o consider cea mai dificilă etapă? Și de câte ori vi s-a dat o descriere a sarcinii ca aceasta: nu retrageți trenul de aterizare dacă avionul este la sol.

Desigur, acest lucru este important, dar clientul crede că aici se termină totul. Dar celelalte cazuri? Este suficient să retragi trenul de aterizare în momentul în care avionul decolează de la sol? Ce se întâmplă dacă avionul sare peste o denivelare de pe pistă? Ce se întâmplă dacă pilotul mută maneta schimbătorului de viteze în poziția „sus” în timpul parcării și, ca urmare, începe să decoleze? Ar trebui să se ridice șasiul în acest caz?

Unul dintre avantajele gândirii în termeni de mașină de stări este că puteți desena rapid o diagramă de tranziție a stării pe o placă de proiecție, chiar în fața clientului, și puteți parcurge procesul cu el. Se acceptă următoarea denumire a tranziției stării: „evenimentul care a provocat tranziția” / „semnal de ieșire ca urmare a tranziției”. Dacă am fi dezvoltat doar ceea ce a cerut inițial clientul („nu retrageți trenul de aterizare dacă aeronava este la sol”), atunci am fi primit mașina prezentată în Figura 2.

Când elaborați o diagramă de tranziție de stare (sau orice alt algoritm), țineți cont de următoarele:

Calculatoarele sunt foarte rapide în comparație cu hardware-ul mecanic.

Inginerul mecanic care explică ceea ce trebuie făcut poate să nu știe atât de multe despre computere și algoritmi ca tine. Și acesta este și un punct pozitiv, altfel nu ar fi nevoie de tine!

Cum se va comporta programul dumneavoastră dacă se rupe o piesă mecanică sau electrică?

O mașină de stare bazată pe ceea ce își dorește cu adevărat clientul este prezentată în Figura 3. Aici dorim să împiedicăm trenul de aterizare a aeronavei să se retragă până când este cu siguranță în aer. Pentru a face acest lucru, după deschiderea comutatorului de aterizare, mașina așteaptă câteva secunde. De asemenea, vrem să răspundem la marginea de ridicare a pârghiei pilotului, mai degrabă decât la nivel, ceea ce va evita problemele dacă cineva mișcă maneta în timp ce avionul este parcat. Retragerea sau extinderea trenului de aterizare durează câteva secunde, iar noi trebuie să fim pregătiți pentru situația în care pilotul, în timpul acestei operațiuni, se răzgândește și mișcă maneta în sens invers. De asemenea, rețineți că dacă avionul aterizează din nou în timp ce suntem în starea „Așteptăm decolarea”, cronometrul va reporni și retragerea va avea loc numai dacă avionul a fost în aer timp de 2 secunde.

Implementarea mașinii de stat

Lista 1 este implementarea mea a mașinii de stare prezentată în Figura 3. Să discutăm câteva dintre detaliile codului.

/*lista 1*/

typedef enumerare(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) State_Type;

/*Această matrice conține pointeri către funcții care trebuie apelate în anumite stări*/

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

State_Type curr_state;

InitializeLdgGearSM();

/* Inima automatului este această buclă nesfârșită. Funcția corespunzătoare

Starea curentă, apelată o dată pe iterație */

in timp ce (1) {

tabel_state();

DecrementTimer();

gol InitializeLdgGearSM( gol )

curr_state = GEAR_DOWN;

/*Opriți hardware-ul, stingeți luminile etc.*/

gol GearDown( gol )

/* Treci în starea de așteptare dacă avionul

Nu la sol și a fost primită o comandă de ridicare a șasiului * /

dacă((pârghia de viteze == SUS) && (pârghia_de_troale_prev == JOS) && (comutator_de_squat == SUS)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

gol RaisingGear( gol )

dacă((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*Dacă pilotul s-a răzgândit, treci în starea trenului de aterizare jos*/

dacă(pârghia de viteze == JOS) (

curr_state = LOWERING_GEAR;

gol Se pregătesc( gol )

/*dacă pilotul a mutat maneta în poziția „jos”,

Treceți în starea „coborâre trenul de aterizare” * /

dacă(pârghia de viteze == JOS) (

curr_state = LOWERING_GEAR;

gol WtgForTakeoff( gol )

/* Așteptați înainte de a ridica șasiul. */

dacă(temporizator<= 0.0) {

curr_state = RAISING_GEAR;

/*Dacă ne-am atins din nou sau pilotul s-a răzgândit, începe totul de la capăt*/

dacă((squat_switch == DOWN) || (pârghia de viteze == DOWN)) (

curr_state = GEAR_DOWN;

/* Nu vreau să-i cer ca el să comute din nou pârghia

Aceasta a fost doar o săritură.*/

prev_gear_lever = DOWN;

gol Coborârea vitezei( gol )

dacă(pârghia de viteze == SUS) (

curr_state = RAISING_GEAR;

dacă((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

În primul rând, puteți observa că funcționalitatea fiecărei stări este implementată de o funcție C separată. Desigur, ar fi posibil să se implementeze un automat folosind o instrucțiune switch cu un caz separat pentru fiecare stare, dar acest lucru poate duce la o funcție foarte lungă (10-20 de linii de cod pe 1 stare pentru fiecare dintre cele 20-30 de stări). ). De asemenea, poate duce la erori dacă modificați codul în etapele finale ale testării. Poate că nu ați uitat niciodată declarația break de la sfârșitul unui caz, dar am avut astfel de cazuri. Codul unui stat nu va intra niciodată în codul altuia dacă aveți o funcție separată pentru fiecare stat.

Pentru a evita utilizarea unei instrucțiuni switch, folosesc o matrice de pointeri către funcțiile de stare și declar ca variabila folosită ca index al matricei să fie de tip enum.

Pentru simplitate, hardware-ul I/O responsabil de citirea stării comutatoarelor, pornirea și oprirea pompelor etc., este reprezentat ca variabile simple. Se presupune că aceste variabile sunt „adrese magice” asociate echipamentelor prin mijloace invizibile.

Un alt lucru evident este că în acest moment codul nu joacă un rol special. Doar trece de la o stare la alta. Acesta este un pas intermediar important și nu trebuie ignorat. Apropo, ar fi bine să adăugați instrucțiuni print incluse între directivele de compilare condiționată (#ifdef DEBUG .. #endif) care ar imprima starea curentă și valorile semnalelor de intrare.

Cheia succesului constă în codul care provoacă tranziția de stare, adică. determină că intrarea a avut loc.

Dacă codul trece corect prin toate stările, următorul pas este să scrieți „umplutura” codului, adică exact ceea ce produce semnalul de ieșire. Rețineți că fiecare tranziție are un semnal de intrare (evenimentul care a declanșat-o) și un semnal de ieșire (dispozitiv I/O hardware, ca în exemplul nostru). Este adesea util să capturați acest lucru sub forma unui tabel de tranziție a stărilor.

Tabelul de tranziție de stare are un rând pe tranziție de stare.

Când codificați o mașină de stat, încercați să o mențineți puternică - o corespondență puternică între cerințele clientului și cod. Poate fi necesar să ascundeți detaliile hardware într-un alt strat de funcție, de exemplu, pentru ca codul mașinii de stare să arate ca un tabel de tranziție de stare și o diagramă de tranziție de stare cât mai aproape posibil. Această simetrie ajută la prevenirea erorilor și explică de ce mașinile de stat sunt o parte atât de importantă din arsenalul programatorului încorporat. Desigur, puteți obține același efect cu casete de selectare și un număr infinit de declarații if imbricate, dar ar fi foarte dificil să urmăriți codul și să-l comparați cu dorințele clientului.

Fragmentul de cod din Lista 2 extinde funcția RaisingGear(). Rețineți că codul pentru funcția RaisingGear() tinde să oglindească cele 2 rânduri ale tabelului de tranziție pentru starea Raising Gear.

gol RaisingGear( gol )

/*După ce toate comutatoarele sunt activate, treceți la starea „șasiu sus”*/

dacă((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pump_motor=OFF;

gear_lights = STINGERE;

curr_state = GEAR_UP;

/*Dacă pilotul se răzgândește, începe retragerea trenului de aterizare*/

dacă(pârghia de viteze == JOS) (

directia_pompa = JOS;

curr_state = GEAR_LOWERING;

Nu uitați să evitați stările ascunse. Starea ascunsă apare atunci când, din lene, încerci să adaugi o substare condiționată în loc să adaugi o stare concretă. De exemplu, dacă codul dumneavoastră procesează aceeași intrare în moduri diferite (adică inițiază tranziții diferite de stare) în funcție de mod, atunci este o stare ascunsă. În acest caz, m-aș întreba dacă această stare nu ar trebui împărțită în două? Utilizarea stărilor ascunse anulează toate beneficiile utilizării unei mașini de stări.

Ca practică, puteți extinde mașina de stare la care tocmai ne-am uitat adăugând un timeout la ciclul de retragere sau extindere al șasiului, după cum inginerul mecanic nu dorește ca pompa hidraulică să funcționeze mai mult de 60 de secunde. Dacă ciclul se termină, pilotul trebuie să fie alertat prin comutarea luminilor verzi și roșii și trebuie să poată mișca din nou maneta pentru a încerca din nou. De asemenea, puteți întreba un ipotetic inginer mecanic cum este afectată pompa de inversarea direcției în timp ce funcționează, deoarece se întâmplă în 2 cazuri când pilotul se răzgândește. Desigur, mecanicul va spune că este negativ. Atunci cum ați schimba mașina de stare pentru a opri pompa rapid atunci când schimbați direcția?

Testarea mașinii de stat

Frumusețea algoritmilor de codare ca mașini cu stări finite este că planul de testare se scrie aproape automat. Tot ce trebuie să faci este să treci prin fiecare tranziție de stat. De obicei fac acest lucru cu un marker în mână, tăind săgețile de pe diagrama de tranziție a stărilor pe măsură ce trec testul. Aceasta este o modalitate bună de a evita „stările ascunse” - acestea sunt ratate mai des în teste decât stări specifice.

Acest lucru necesită răbdare considerabilă și multă cafea, deoarece chiar și o mașină de stat de dimensiuni medii poate avea până la 100 de tranziții diferite. Apropo, numărul de hamei este o modalitate excelentă de a măsura complexitatea unui sistem. Acesta din urmă este determinat de cerințele clientului, iar mașina de stat face evidentă domeniul testării. Cu o abordare mai puțin organizată, cantitatea de testare necesară poate fi la fel de impresionantă, dar pur și simplu nu știi despre asta.

Este foarte convenabil să utilizați instrucțiuni de tipărire în cod care afișează starea curentă, valorile semnalelor de intrare și de ieșire. Acest lucru vă permite să observați cu ușurință ceea ce exprimă „Regula de aur a testării software-ului”: testați dacă programul face ceea ce este intenționat să facă și, de asemenea, că nu face nimic în plus. Cu alte cuvinte, obțineți doar rezultatele pe care le așteptați și ce se mai întâmplă în afară de asta? Există vreo tranziție de stare „dură”, de ex. stări care trec la întâmplare, doar pentru o iterație a buclei? Ieșirile se schimbă atunci când nu vă așteptați să o facă? În mod ideal, rezultatul printfs-ului dvs. ar trebui să semene îndeaproape cu un tabel de tranziție a stărilor.

În cele din urmă - și acest lucru se aplică oricărui software încorporat, nu doar software-ului bazat pe mașini de stat - fiți foarte atenți când rulați software-ul pentru prima dată pe hardware real. Este foarte ușor să greșiți polaritatea - „Hopa, am crezut că „1” înseamnă să ridice șasiul și „0” să-l coboare”. În multe cazuri, asistentul meu hardware a folosit un „comutator de pui” temporar pentru a proteja componentele valoroase până când a fost sigur că software-ul meu îndrepta lucrurile în direcția corectă.

lansa

Când toate cerințele clienților sunt îndeplinite, pot lansa o mașină de stat de această complexitate în câteva zile. Aproape întotdeauna automatele fac ce vreau eu. Cel mai dificil lucru este, desigur, să înțelegi exact ce își dorește clientul și să te asiguri că clientul însuși știe ce vrea. Acesta din urmă durează mult mai mult!

Martin Gomez este programator la Laboratorul de Fizică Aplicată de la Universitatea Johns Hopkins. Angajat în dezvoltarea de software pentru zborul navelor spațiale de cercetare. El a lucrat în domeniul dezvoltării sistemelor încorporate timp de 17 ani. Martin deține o licență în inginerie aerospațială și un master în inginerie electrică de la Universitatea Cornell.

Unul dintre criteriile pentru complexitatea unui automat finit este numărul stărilor sale. Cu cât acest număr este mai mic, cu atât este mai simplu dispozitivul discret care implementează acest automat. Prin urmare, una dintre problemele importante în teoria automatelor finite este construcția unui automat cu cel mai mic număr de stări.

Deoarece în computerele moderne orice informație este reprezentată sub formă de coduri binare, atunci pentru a construi un automat, puteți utiliza elemente care au doar două stări stabile diferite, dintre care una corespunde numărului 0, iar cealaltă numărului 1.

Iată câteva exemple de automate finite.

Exemplul 1. Element de întârziere (element de memorie).

Elementele de întârziere sunt un dispozitiv cu o intrare și o ieșire. Mai mult, valoarea semnalului de ieșire la momentul respectiv t coincide cu valoarea semnalului din momentul anterior. Schematic, elementul de întârziere poate fi reprezentat după cum urmează (Fig. 2).

Să presupunem că alfabetul de intrare și, prin urmare, de ieșire este X ={0, 1}, Y =(0, 1). Apoi Q =(0, 1). Sub starea elementului de întârziere la momentul respectiv t conţinutul elementului de memorie în momentul de faţă este înţeles. În acest fel q (t )= X (t 1), a Y (t )= q (t )=X (t 1).

Să setăm elementul de întârziere după tabel, unde dar 1 =0, dar 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

Diagrama Moore este prezentată în fig. 3

Pentru a reprezenta acest automat printr-un sistem de funcții booleene, folosim tabelul de automate și algoritmul de mai sus. În acest caz, codificarea nu este necesară, deoarece alfabetele și stările de intrare și de ieșire sunt deja codificate.

Să fim atenți la faptul că m=p=p =2. Apoi k =r =s =1 și, prin urmare, elementul de întârziere este dat de două funcții  Și  . Tabelul de adevăr al acestor funcții conține 2 k + r =2 2 =4 rânduri și k +r +r +s =4 coloane:

X	z

Exemplul 2. Adunator binar secvenţial.

Acest sumator secvenţial este un dispozitiv care adaugă două numere în sistemul binar. Numerele sunt introduse în intrările sumatorului X 1 și X 2, începând cu cifrele cele mai puțin semnificative. La ieșire, se formează o secvență corespunzătoare introducerii numărului X 1 +X 2 în sistemul binar de calcul (Fig. 4).

Alfabetele de intrare și de ieșire sunt definite în mod unic: X ={00; 01; 10; 11}, Y =(0,1). Setul de stări este determinat de valoarea transferului la adăugarea biților de numere corespunzători X 1 și X 2. Dacă în timpul adunării unor cifre se formează o purtare, atunci vom presupune că sumatorul a trecut în stare q unu . Dacă nu există transport, vom presupune că sumatorul este în stare q 0 .

Adunatorul este dat de un tabel.

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

Diagrama Moore a unui sumator secvenţial este prezentată în fig. cinci.

Rețineți că caracterele de intrare și de ieșire sunt deja codificate. Codificăm stările după cum urmează:  (q 0)=0,  (q 1)=1. Prin urmare, sumatorul secvenţial este dat de două funcţii booleene, al căror tabel de adevăr este următorul:

X 1	X 2	z

Exemplul 3. Schema de comparare a egalității.

Un circuit de comparare a egalității este un dispozitiv care compară două numere. X 1 și X 2, dat în sistemul binar. Acest dispozitiv funcționează după cum urmează. La introducerea dispozitivului secvenţial, începând de la cea mai mare, se alimentează cifrele numerelor X 1 și X 2. Aceste ranguri sunt comparate. Dacă biții se potrivesc, semnalul de ieșire 0 se formează la ieșirea circuitului, în caz contrar la ieșire apare semnalul 1. Este clar că apariția lui 1 în secvența de ieșire înseamnă că numerele comparate X 1 și X 2 diferit. Dacă secvența de ieșire este zero și lungimea sa se potrivește cu numărul de cifre ale numerelor comparate, atunci X 1 și X 2 .

Pentru această mașină X ={00, 01, 10, 11}; Y ={0,1}.

Funcționarea circuitului este determinată de două stări. Stat q 0 corespunde egalității biților comparați în prezent. În acest caz, mașina rămâne în aceeași stare. Dacă în momentul următor cifrele comparate sunt diferite, atunci automatul va trece într-o stare nouă q 1 și rămâne în el, deoarece înseamnă că numerele sunt diferite. Astfel, schema de comparație poate fi specificată prin tabel:

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

Diagrama Moore a schemei de comparație pentru egalitate este prezentată în fig. 6.

Vom codifica stările după cum urmează:  (q 0)=0,  (q 1)=1. Automatului i se vor da două funcții.

X 1	X 2	z

Exemplul 4. Schema de comparare a inegalității.

Circuitul de comparare a inegalității este un dispozitiv care vă permite să aflați dacă este comparat X 1 și X 2, iar dacă nu sunt egale, află care dintre ele este mai mare decât cealaltă. Acest dispozitiv are două intrări și două ieșiri. Semnale de ieșire y 1 (t ) Și y 2 (t ) se determină după următoarele reguli:

y 1 (t )=y 2 (t )=0 dacă X 1 (t )=X 2 (t );

y 1 (t )=1, y 2 (t )=0 dacă X 1 (t )>X 2 (t ), adică X 1 (t )=1, X 2 (t )=0;

y 1 (t )=0, y 2 (t )=1 dacă X 1 (t )<X 2 (t ), adică X 1 (t )=0, X 2 (t )=1.

Astfel, atunci când se aplică la intrarea circuitului de comparație pentru inegalitatea numerelor X 1 =X 1(l)… X 1 (t ) Și X 2 =X 2(l)… X 2 (t ) cifrele acestor numere sunt comparate secvenţial, începând cu cele mai mari. Semnalele de ieșire sunt formulate conform regulilor de mai sus. Mai mult, dacă secvența de ieșire constă din zero perechi, atunci X 1 =X 2. Dacă primul este diferit de zero, perechea are forma , () apoi X 1 >X 2 (X 1 <X 2).

Din descrierea circuitului rezultă că

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

Starea schemei este definită după cum urmează. Presupunem că la momentul inițial t =1 mașina este în stare q 1 . Dacă cifrele comparate ale numerelor X 1 Și X 2, atunci mașina rămâne în această stare. Rețineți că la ieșire va apărea semnalul 00. Dacă cifra numărului X 1 va fi mai mică (mai mare decât) cifra corespunzătoare a numărului X 2, apoi mașina va intra în stare q 2 (q 3). În acest caz, la ieșire va apărea un semnal 01 (10). În viitor, atunci când trimiteți cifrele rămase ale numerelor X 1 Și X 2 la intrările automatului automatul va rămâne în stare q 2 (q 3) și generează simbolul de ieșire 10 (01). Din cele de mai sus rezultă că schema de comparație pentru inegalitate poate fi specificată de tabel:

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

Diagrama Moore corespunzătoare este prezentată în Fig. 7.

Alfabetele de intrare și de ieșire sunt deja codificate aici. state q 1 , q 2 și q 3 codifica:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

Prin urmare, acest circuit poate fi definit printr-un sistem format din patru funcții booleene care depind de patru variabile. Aceste funcții sunt parțial definite și date de tabelul de adevăr

	X 1	X 2	z 1	z 2

În tabel, simbolurile * marchează seturi de variabile X 1 , X 2 , z 1 , z 2 , pe care funcţiile  1 ,  2 ,  1 ,  2 nu sunt definite. Sa punem valorile funcției  1 ,  2 ,  1 ,  2 pe aceste seturi egal cu 1.

Astăzi vom vorbi despre mitraliere, dar în niciun caz despre cele care sunt ținute în mâinile soldaților armatei ruse. Vom vorbi despre un stil atât de interesant de programare a microcontrolerelor precum programarea automată. Mai exact, acesta nu este nici măcar un stil de programare, ci un întreg concept, datorită căruia un programator de microcontrolere își poate face viața mult mai ușoară. Datorită faptului că multe sarcini prezentate programatorului sunt rezolvate mult mai ușor și mai simplu, scutindu-l pe programator de o durere de cap. Apropo, programarea automată este adesea numită Tehnologia SWITCH.

Vreau să observ că stimulul pentru scrierea acestei postări a fost serie de articole despre tehnologia SWITCH Vladimir Tătarchevski. Seria de articole se numește „Aplicarea tehnologiei SWITCH în dezvoltarea de aplicații software pentru microcontrolere” Așa că în acest articol voi încerca în cea mai mare parte să dau un exemplu de cod de lucru și descrierea acestuia.

Apropo, am planificat o serie de articole despre programare, în care voi lua în considerare în detaliu tehnicile de programare pentru microcontrolere ABP, nu ratați…. Ei bine, hai să mergem!

Programul execută secvenţial comenzile stabilite de programator. Pentru un program de calculator obișnuit, este complet normal când programul și-a încheiat și a oprit execuția, în timp ce afișează rezultatele muncii sale pe monitor.

Un program de microcontroler nu poate să-și încheie pur și simplu execuția. Imaginați-vă că ați pornit playerul sau casetofonul. Ați apăsat butonul de pornire, ați selectat melodia dorită și vă bucurați de muzică. Totuși, atunci când muzica a încetat să-ți mai ciufulie timpanul, playerul îngheață și nu reacționează în niciun fel la apăsarea butoanelor și cu atât mai mult la dansul tău cu tamburină.

Și ce este asta? Totul este în regulă - controlerul, cel din adâncurile playerului tău, tocmai și-a terminat de executat programul. Aici puteți vedea cât de incomod se dovedește.

Deci de aici concluzionăm că programul pentru microcontroler pur și simplu nu ar trebui să se oprească. În esență, ar trebui să fie o buclă infinită - doar în acest caz playerul nostru ar funcționa corect. În continuare, vă voi arăta care sunt modelele de cod de program pentru microcontrolere, acestea nu sunt nici măcar modele, ci niște stiluri de programare.

Stiluri de programare.

„Stilurile de programare” sună cam de neînțeles, dar ei bine. Ce vreau să spun cu asta? Să ne imaginăm că o persoană nu a mai făcut niciodată programare, adică, în general, un manechin complet.

Această persoană a citit multe cărți despre programare, a învățat toate constructele de bază ale limbajului.El a colectat informații bit cu bit, deoarece acum accesul la informații este nelimitat. Toate acestea sunt bune, dar cum vor arăta primele sale programe? Mi se pare că nu va filozofa, ci va urma calea de la simplu la complex.

Deci aceste stiluri sunt pași care duc de la un nivel simplu la unul mai complex, dar în același timp mai eficient.

La început, nu m-am gândit la nicio caracteristică de proiectare a programului. Tocmai am format logica programului - am desenat o diagramă și am scris codul. Din ceea ce a dat în mod constant peste o greblă. Dar aceasta a fost prima dată când nu am făcut o baie de aburi și am folosit stilul „simple looping”, apoi am început să folosesc întreruperi, apoi au apărut automate și am plecat...

1. Buclă simplă. În acest caz, programul circulă fără complicații, iar acest lucru are avantajele și dezavantajele sale. Plus că doar în simplitatea abordării, nu trebuie să inventezi modele viclene, scrii așa cum crezi (săpându-ți treptat propriul mormânt).

Void main(void) ( initial_AL(); //inițializarea periferiei while(1) ( Leds_BLINK(); //funcția LED-ului intermitent signal_on(); //funcția de pornire a semnalului signal_off(); // functie de oprire a semnalului l=button( ); // variabila responsabila cu apasarea butoanelor switch(l) // In functie de valoarea variabilei se executa una sau alta actiune ( cazul 1: ( Deistvie1 (); / / În loc de o funcție, poate exista un operator condiționat Deistvie2 (); // sau mai multe ramuri comută cazul Deistvie3(); Deistvie4(); Deistvie5(); ); cazul 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ); . . . . . . . . ) ) )

Punctul de lucru al programului se deplasează în ordine. În acest caz, toate acțiunile, condițiile și ciclurile sunt executate secvenţial. Codul începe să încetinească, trebuie să introduceți o mulțime de condiții suplimentare, complicând astfel percepția.

Toate acestea încurcă foarte mult programul, făcând o încurcătură de condiții din cod. Ca urmare, acest cod nu poate fi adăugat sau luat, devine ca o piesă monolitică. Desigur, atunci când volumul nu este mare, codul poate fi modificat, dar cu cât mai departe, cu atât mai dificil.

Cu această abordare, am scris mai multe programe, nu erau mari și destul de funcționale, dar vizibilitatea lăsa de dorit. Pentru a adăuga o condiție nouă, a trebuit să dau cu lopata întregul cod, pentru că totul era legat. Acest lucru a dat naștere la multe erori și dureri de cap. Compilatorul a înjurat cât de repede a putut, depanarea unui astfel de program s-a transformat în iad.

2. Ciclu + întreruperi.

Puteți rezolva parțial ciclul de frânare infinit folosind întreruperi. Întreruperile ajută la ieșirea dintr-un cerc vicios, ajută la nu rata un eveniment important, adaugă funcționalități suplimentare (întreruperi de la temporizatoare, întreruperi externe).

Să presupunem că puteți închide procesarea butoanelor sau urmărirea unui eveniment important la o întrerupere. Ca urmare, programul devine mai vizual, dar nu mai puțin confuz.

Din păcate, întreruperea nu vă va salva de mizeria în care se transformă programul. Nu va fi posibil să împărțiți în părți ceea ce este un singur întreg.

3. Programare automată.

Așa că ajungem la subiectul principal al acestui articol. Programarea în mașini cu stări finite salvează programul de deficiențele inerente primelor două exemple. Programul devine mai simplu, este ușor de modificat.

Un program scris în stil automat este ca un comutator care, în funcție de condiții, trece într-o stare sau alta. Numărul de stări este inițial cunoscut de programator.

Aproximativ, este ca un întrerupător de lumină. Există două stări pornit și oprit și două condiții pornit și oprit. Ei bine, primul lucru.

Implementarea multitasking-ului în tehnologia switch-ului.

Microcontrolerul este capabil să controleze sarcina, să clipească LED-urile, să urmărească tastele și multe altele. Dar cum să faci toate acestea în același timp? Există multe soluții la această problemă. Cea mai simplă dintre acestea pe care am menționat-o deja este utilizarea întreruperilor.

În timpul programului, când apare o întrerupere, controlerul este distras de la executarea codului programului și execută pentru scurt timp o altă parte a programului pentru care întreruperea este responsabilă. Întreruperea va funcționa, apoi punctul de lucru al programului va continua din locul din care controlerul a fost întrerupt de întrerupere (cuvântul însuși indică faptul că controlerul este întrerupt).

O altă modalitate de a implementa multitasking este prin utilizarea sistemelor de operare. Da, au început deja să apară sisteme de operare mici, care pot fi folosite pe un controler de putere redusă. Dar adesea această metodă se dovedește a fi oarecum redundantă. La urma urmei, de ce să risipești resursele controlerului cu muncă inutilă, când este foarte posibil să te descurci cu puțină vărsare de sânge.

În programele scrise folosind tehnologia switch, o astfel de „iluzie” de multitasking se obține datorită sistemului de mesagerie. Am scris „iluzie” pentru că este într-adevăr, deoarece programul fizic nu poate executa diferite părți ale codului în același timp. Despre sistemul de mesagerie voi vorbi puțin mai departe.

Sistem de mesagerie.

Puteți distruge mai multe procese și puteți crea iluzia de multitasking folosind sistemul de mesagerie.

Să presupunem că avem nevoie de un program în care LED-ul este comutat. Aici avem două mașini, să le numim LEDON - mașina responsabilă cu aprinderea LED-ului și mașina LEDOFF - mașina responsabilă cu stingerea LED-ului.

Fiecare dintre automate are două stări, adică automatul poate fi într-o stare activă sau într-o stare inactivă, așa cum un comutator cu cuțit este fie pornit, fie oprit.

Când o mașină este activată, LED-ul se aprinde, când cealaltă mașină este activată, LED-ul se stinge. Luați în considerare un mic exemplu:

Int main(void) ( INIT_PEREF(); //inițializarea perifericelor (LED-uri) InitGTimers(); //inițializarea temporizatoarelor InitMessages(); //inițializarea mecanismului de procesare a mesajelor InitLEDON(); //inițializarea automatului LEDON InitLEDOFF(); // inițializarea automatului LEDOFF SendMessage(MSG_LEDON_ACTIVATE); //activează automatul LEDON sei(); //Activează întreruperi //Programează bucla principală while(1) ( ProcessLEDON(); //iterarea LEDON automatul ProcessLEDOFF(); //iterația automatului LEDOFF ProcessMessages (); //procesarea mesajelor ); )

În rândurile 3-7, apar diverse inițializari, așa că nu ne interesează în mod deosebit acest lucru acum. Dar apoi se întâmplă următoarele: înainte de a începe bucla principală (în timp ce (1)), trimitem un mesaj automatului

Trimite mesaj(MSG_LEDON_ACTIVATE)

responsabil de aprinderea LED-ului. Fără acest mic pas, gita noastră nu va funcționa. Apoi, bucla principală infinită while face cea mai mare parte a muncii.

Mică digresiune:

Mesajul are trei stări. Și anume, starea mesajului poate fi inactivă, setată, dar inactivă și activă.

Se dovedește că inițial mesajul a fost inactiv, când am trimis mesajul, acesta a primit starea „instalat dar inactiv”. Și asta ne dă următoarele. Când programul este executat secvenţial, automatul LEDON nu primeşte un mesaj. Are loc o iterație inactivă a automatului LEDON, în care mesajul pur și simplu nu poate fi primit. Deoarece mesajul are starea „instalat dar inactiv”, programul își continuă execuția.

După ce toate automatele sunt inactive, coada ajunge la funcția ProcessMessages(). Această funcție este întotdeauna plasată la sfârșitul buclei, după ce toate iterațiile automate au fost finalizate. Funcția ProcessMessages() schimbă pur și simplu mesajul din starea „setat, dar inactiv” în starea „activ”.

Când bucla infinită completează a doua rundă, imaginea este deja complet diferită. Iterația automatului ProcessLEDON nu va mai fi inactiv. Aparatul va putea primi mesajul, va putea trece la starea aprinsă și, de asemenea, va putea trimite mesajul pe rând. Se va adresa automatului LEDOFF și se va repeta ciclul de viață al mesajului.

Vreau să observ că mesajele care au starea „activă” sunt distruse atunci când se întâlnesc cu funcția ProcessMessages. Prin urmare, un mesaj poate fi primit doar de un automat. Există un alt tip de mesaje - acestea sunt mesaje difuzate, dar nu le voi lua în considerare, sunt, de asemenea, bine acoperite în articolele lui Tatarchevskiy.

Cronometre

Cu o mesagerie adecvată, putem controla ordinea în care funcționează mașinile de stat, dar nu ne putem lipsi de mesaje singuri.

Este posibil să fi observat că exemplul anterior de fragment de cod nu va funcționa așa cum a fost prevăzut. Aparatele vor schimba mesaje, LED-urile se vor comuta, dar nu vom vedea asta. Vom vedea doar un LED slab aprins.

Acest lucru se datorează faptului că nu ne-am gândit la procesarea competentă a întârzierilor. La urma urmei, nu este suficient să pornim și să oprim LED-urile alternativ, LED-ul trebuie să rămână în fiecare stare, de exemplu, pentru o secundă.

Algoritmul va fi după cum urmează:

Puteți face clic pentru a mări

Am uitat să adaug pe această diagramă bloc că atunci când cronometrul bifează, desigur, se efectuează o acțiune - aprinderea LED-ului sau stingerea acestuia.

1. Intrăm în stare primind un mesaj.

2. Verificăm citirile cronometrului/contorului, dacă bifează, atunci executăm acțiunea, altfel ne trimitem doar un mesaj.

3. Trimitem un mesaj următorului automat.

4. Ieșire

În următoarea intrare, totul se repetă.

Program de tehnologie SWITCH. Trei pasi.

Și să scriem un program în automate finite și pentru aceasta va trebui să facem doar trei pași simpli. Programul va fi simplu, dar merită să începeți cu lucruri simple. Un program cu LED de comutare este potrivit pentru noi. Acesta este un exemplu foarte bun, așa că să nu inventăm nimic nou.

Voi scrie programul în limbajul C, dar asta nu înseamnă deloc că în automate finite trebuie să scrieți doar în C, este foarte posibil să folosiți orice alt limbaj de programare.

Programul va fi modular și, prin urmare, va fi împărțit în mai multe fișiere. Modulele noastre vor fi:

• Modulul de buclă principal al programului conține fișierele leds_blink.c, HAL.c, HAL.h
• Modul temporizator conține fișierele timers.c, timers.h
• Modul de procesare a mesajelor conține fișierele messages.c, messages.h
  
• Modulul mașinii 1 conține fișiere ledon.c, ledon.h
• Modulul mașinii 2 conține fișiere ledoff.c, ledoff .h

Pasul 1.

Creăm un proiect și conectăm imediat fișierele modulelor noastre statice la acesta: timers.c, timers.h, messages.c, messages.h.

Fișierul leds_blink.c al modulului ciclului principal al programului.

#include "hal.h" #include "messages.h" //modul de procesare a mesajelor #include "timers.h" //modul timers //Timer interrupts //############# # #################################################################### ############################ ISR(TIMER0_OVF_vect) // Întreruperea tranziției vectorului (T0 overflow timer counter) ( ProcessTimers(); / /Manager de întrerupere a temporizatorului) //###################################################################### ############################################# int principal (void) ( INIT_PEREF(); //inițializarea periferiei (LED-uri) InitGTimers(); //inițializarea temporizatoarelor InitMessages(); //inițializarea mecanismului de procesare a mesajelor InitLEDON(); //inițializarea automatului LEDON InitLEDOFF(); StartGTimer( TIMER_SEK); //Porniți temporizatorul SendMessage(MSG_LEDON_ACTIVATE); //activează automatul FSM1 sei(); //Activează întreruperi //Programează bucla principală while(1) ( ProcessLEDON(); //iterează automatul LEDON ProcessLEDOFF(); ProcessMessages(); //procesarea mesajelor); )

În primele rânduri, modulele rămase sunt conectate la programul principal. Aici vedem că modulul cronometru și modulul de procesare a mesajelor sunt conectate. Următorul în program este vectorul de întrerupere de overflow.

Din linia int main (void) putem spune că începe programul principal. Și începe cu inițializarea tuturor și a tuturor. Aici inițializam perifericele, adică setăm valorile inițiale la porturile de intrare / ieșire ale comparatorului și toate celelalte conținuturi ale controlerului. Toate acestea sunt realizate de funcția INIT_PEREF, o rulăm aici, deși corpul său principal se află în fișierul hal.c.

În continuare, vedem inițializarea temporizatoarelor, modulul de procesare a mesajelor și inițializarea automatelor. Aici, aceste funcții sunt, de asemenea, lansate simplu, deși funcțiile în sine sunt scrise în fișierele modulelor lor. Vezi cât de convenabil. Textul principal al programului rămâne ușor de citit și nu este aglomerat cu cod redundant care vă rupe piciorul.

Inițializările principale s-au încheiat, acum trebuie să începem bucla principală. Pentru a face acest lucru, trimitem mesajul de pornire și, în plus, pornim ceasul - pornim cronometrul.

StartGTimer(TIMER_SEK); //Porniți cronometrul SendMessage(MSG_LEDON_ACTIVATE); //activează mașina FSM1

Și bucla principală, așa cum am spus, pare foarte simplă. Notăm funcțiile tuturor automatelor, doar le scriem într-o coloană, fără a urma ordinea. Aceste funcții sunt manipulatoare de automate și sunt amplasate în modulele automate. Funcția modulului de procesare a mesajelor completează această piramidă automată. Desigur, am spus asta deja mai devreme când m-am ocupat de sistemul de mesagerie. Acum puteți vedea cum arată încă două fișiere ale modulului buclei principale de program

Hal.h este fișierul antet al modulului de buclă principală al programului.

#ifndef HAL_h #define HAL_h #include #include //Biblioteca standard care include întreruperi #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

După cum puteți vedea, acest fișier nu conține în mod inerent o singură linie de cod executabil - toate acestea sunt substituții de macro și conexiuni de bibliotecă. Având acest fișier pur și simplu face viața foarte bună, îmbunătățește vizibilitatea.

Dar fișierul Hal.c este deja un fișier executabil și, așa cum am menționat deja, conține diverse inițializari periferice.

#include "hal.h" void INIT_PEREF(void) ( //Inițializați porturile I/O //############################ #################################################################### # ##### Komparator = ViklKomparator; //inițializarea comparatorului - dezactivați DDRD = 1<

Ei bine, am arătat modulul ciclului principal al programului, acum trebuie să facem ultimul pas, trebuie să scriem singuri modulele automatelor.

Pasul 3

Ne rămâne să scriem modulele automatelor finite, în cazul nostru, automatul LEDON și automatul LEDOFF. Pentru început, voi da textul programului pentru mașina care aprinde LED-ul, fișierul ledon.c.

//fișier ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" nesemnat char ledon_state; //variabilă de stare void InitLEDON(void) ( ledon_state=0; //aici puteți inițializa alte variabile automate dacă există ) void ProcessLEDON(void) ( switch(ledon_state) (caz 0: //stare inactivă if(GetMessage (MSG_LEDON_ACTIVATE) )) //dacă există un mesaj, acesta va fi acceptat ( //și cronometrul va fi verificat if(GetGTimer(TIMER_SEK)==one_sek) //dacă timer-ul a setat 1s, apoi executați ( StopGTimer(TIMER_SEK); PORTD = 1<

Aici, în primele rânduri, ca întotdeauna, bibliotecile sunt conectate și variabilele sunt declarate. În continuare, am trecut deja la funcțiile cu care ne-am întâlnit deja. Aceasta este funcția de inițializare a automatului InitLEDON și funcția de gestionare a automatului ProcessLEDON însuși.

În corpul handlerului, funcțiile din modulul temporizator și modulul de mesaje sunt deja procesate. Iar logica automatului în sine se bazează pe designul carcasei comutatorului. Și aici puteți vedea că gestionarea automatelor se poate complica și prin adăugarea câtorva comutatoare de carcasă.

Fișierul antet pentru automat ar fi și mai simplu:

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

Aici conectăm fișierul link hal.h și specificăm și prototipurile funcțiilor.

Fișierul responsabil pentru stingerea LED-ului va arăta aproape la fel doar în imaginea în oglindă, așa că nu îl voi afișa aici - reticență 🙂

Puteți descărca toate fișierele de proiect aici, la acest link ====>>> LEGĂTURĂ.

Iată doar trei pași și programul nostru a căpătat un aspect finit, ceea ce înseamnă că misiunea mea de astăzi s-a încheiat și este timpul să închei. Mi se pare că informațiile date în acest articol îți vor fi foarte utile. Dar va aduce beneficii reale doar atunci când vei pune aceste cunoștințe în practică.

Apropo, am planificat o serie de proiecte interesante care vor fi deosebit de interesante, așa că asigurați-vă că abonați-vă pentru articole noi . De asemenea, plănuiesc să trimit materiale suplimentare, așa că mulți oameni se abonează deja prin pagina principală a site-ului. Vă puteți abona și aici.

Ei bine, acum chiar am de toate, așa că vă doresc mult succes, bună dispoziție și ne revedem.

N/A Vladimir Vasiliev

O mașină de stări este un model abstract care conține un număr finit de stări ale ceva. Folosit pentru a reprezenta și controla fluxul de execuție al oricăror comenzi. Mașina de stat este ideală pentru implementarea inteligenței artificiale în jocuri, obținând o soluție îngrijită fără a scrie cod greoi și complex. În acest articol, vom acoperi teoria și, de asemenea, vom învăța cum să folosim o mașină de stări simplă și bazată pe stivă.

Am publicat deja o serie de articole despre scrierea inteligenței artificiale folosind o mașină de stat. Dacă nu ați citit încă această serie, o puteți face acum:

Ce este o mașină cu stări finite?

O mașină cu stări finite (sau pur și simplu FSM - mașină cu stări finite) este un model de calcul bazat pe o mașină cu stări ipotetice. O singură stare poate fi activă la un moment dat. Prin urmare, pentru a efectua orice acțiune, mașina trebuie să își schimbe starea.

Mașinile de stat sunt de obicei folosite pentru a organiza și reprezenta fluxul de execuție a ceva. Acest lucru este util în special atunci când implementați AI în jocuri. De exemplu, pentru a scrie „creierul” inamicului: fiecare stare reprezintă un fel de acțiune (atac, eschiv etc.).

Un automat finit poate fi reprezentat ca un grafic, ale cărui vârfuri sunt stările, iar muchiile sunt tranzițiile dintre ele. Fiecare margine are o etichetă care indică când ar trebui să aibă loc tranziția. De exemplu, în imaginea de mai sus, puteți vedea că automatul va schimba starea de la „rătăcire” în starea „atac”, cu condiția ca jucătorul să fie în apropiere.

Planificarea stărilor și tranzițiile lor

Implementarea unei mașini cu stări finite începe cu identificarea stărilor sale și a tranzițiilor dintre ele. Imaginați-vă o mașină de stat care descrie acțiunile unei furnici care transportă frunze într-un furnicar:

Punctul de plecare este starea „găsește frunza”, care rămâne activă până când furnica găsește frunza. Când se întâmplă acest lucru, statul se va schimba în „du-te acasă”. Aceeași stare va rămâne activă până când furnica noastră ajunge la furnicar. După aceea, starea se schimbă din nou la „găsește frunza”.

Dacă starea „găsește frunza” este activă, dar cursorul mouse-ului este lângă furnică, atunci starea se schimbă în „fugi”. De îndată ce furnica se află la o distanță suficient de sigură de cursorul mouse-ului, starea se va schimba înapoi la „găsi frunza”.

Vă rugăm să rețineți că atunci când mergeți acasă sau ieșiți din casă, furnica nu se va teme de cursorul mouse-ului. De ce? Și pentru că nu există o tranziție corespunzătoare.

Implementarea unei mașini de stare simplă

O mașină de stări poate fi implementată folosind o singură clasă. Să-i spunem FSM. Ideea este de a implementa fiecare stare ca metodă sau funcție. De asemenea, vom folosi proprietatea activeState pentru a determina starea activă.

Clasa publică FSM ( private var activeState:Function; // pointer către starea activă a funcției publice automate FSM() ( ) public function setState(state:Function) :void ( activeState = state; ) public function update() :void (dacă (activeState != null) (activeState(); ) ) )

Fiecare stare este o funcție. Mai mult, astfel încât va fi apelat de fiecare dată când cadrul de joc este actualizat. După cum sa menționat deja, activeState va stoca un pointer către funcția de stare activă.

Metoda update() a clasei FSM trebuie numită fiecare cadru de joc. Și el, la rândul său, va apela funcția statului care este activ în prezent.

Metoda setState() va seta noua stare activă. Mai mult, fiecare funcție care definește o anumită stare a automatului nu trebuie să aparțină clasei FSM - acest lucru face clasa noastră mai universală.

Folosind o mașină de stat

Să implementăm AI furnici. Mai sus, am arătat deja un set de stări și tranziții dintre ele. Să le ilustrăm din nou, dar de data aceasta ne vom concentra pe cod.

Furnica noastră este reprezentată de clasa Furnicilor, care are un câmp cerebral. Aceasta este doar o instanță a clasei FSM.

Clasa publică Ant ( public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) (poziție = new Vector3D(posX, posY); viteza = new Vector3D( -1, -1); creier = FSM nou(); // Începe prin a căuta o frunză. creier. setState(findLeaf); ) /** * Afișează „findLeaf". * Face furnica să caute frunze. */ funcția publică findLeaf( ) :void ( ) /** * Starea „goHome” * Determină furnica să intre în furnicar */ public function goHome() :void ( ) /** * Starea „fugă” * Provoacă furnică să fugă de cursorul mouse-ului * / public function runAway() :void ( ) public function update():void ( // Actualizați mașina de stări. Această funcție va apela // funcția de stare activă: findLeaf(), goHome () sau runAway(). brain.update(); // Aplică viteză mișcării furnicii. moveBasedOnVelocity(); ) (...) )

Clasa Ant conține și proprietăți de viteză și poziție. Aceste variabile vor fi utilizate pentru a calcula mișcarea folosind metoda Euler. Funcția update() este apelată de fiecare dată când cadrul de joc este actualizat.

Mai jos este implementarea fiecăreia dintre metode, începând cu findLeaf(), statul responsabil cu găsirea frunzelor.

Funcția publică findLeaf() :void ( // Mută ​​furnica pe frunză. viteza = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distanță (Joc .instance.leaf, asta)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

Starea goHome() este folosită pentru a face furnica să meargă acasă.

Funcția publică goHome() :void ( // Mută ​​furnica la viteza de acasă = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distanță( Joc. exemplu.acasă, asta)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

Și, în cele din urmă, starea runAway() - folosită atunci când ocoliți cursorul mouse-ului.

Funcția publică runAway() :void ( // Mută ​​furnica departe de viteza cursorului = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Este cursorul încă în jur ? if ( distanta(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Nu, este deja departe. Este timpul să ne întoarcem la găsirea frunzelor. brain.setState(findLeaf); ) )

Îmbunătățirea FSM: automat bazat pe stivă

Imaginați-vă că furnica în drum spre casă trebuie și ea să fugă de cursorul mouse-ului. Iată cum vor arăta statele FSM:

Pare o schimbare banala. Nu, o astfel de schimbare ne creează o problemă. Imaginați-vă că starea actuală este „fugă”. Dacă cursorul mouse-ului se îndepărtează de furnică, ce ar trebui să facă: să meargă acasă sau să caute o frunză?

Soluția la această problemă este o mașină de stări bazată pe stivă. Spre deosebire de FSM simplu pe care l-am implementat mai sus, acest tip de FSM folosește o stivă pentru a gestiona stările. În partea de sus a stivei se află starea activă, iar tranzițiile apar atunci când stările sunt adăugate/eliminate din stivă.

Și iată o demonstrație vizuală a funcționării unei mașini de stări bazată pe stiva:

Implementarea unui FSM bazat pe stivă

O astfel de mașină cu stări finite poate fi implementată în același mod ca una simplă. Diferența va fi utilizarea unei matrice de pointeri către stările necesare. Nu vom mai avea nevoie de proprietatea activeState, deoarece partea de sus a stivei va indica deja starea activă.

Clasa publică 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 popState() :Function ( return stack.pop(); ) public function pushState(state:Function) :void ( if (getCurrentState() != state) ( stack.push(state) ; ) ) funcția publică getCurrentState() :Function ( return stack.length > 0 ? stack : null; ) )

Rețineți că metoda setState() a fost înlocuită cu pushState() (adăugând o stare nouă în partea de sus a stivei) și popState() (eliminând starea din partea de sus a stivei).

Utilizarea FSM bazată pe stivă

Este important de reținut că atunci când se utilizează o mașină de stări bazată pe stivă, fiecare stare este responsabilă pentru eliminarea ei din stivă atunci când nu este nevoie. De exemplu, starea atac() ar trebui să se îndepărteze singură din stivă dacă inamicul a fost deja distrus.

Public class Ant ( (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // Începeți prin a căuta un creier de frunză. pushState( findLeaf); (...) ) /** * Stați „findLeaf". * Face furnica să caute frunze. */ public function findLeaf() :void ( // Mută ​​furnica pe frunză. viteza = new Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y); if (distanță(Game.instance.leaf, this)<= 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) ( // Nu, este deja departe. E timpul să revenim la căutarea frunzelor. brain.popState(); ) ) (...) )

Ieșire

Mașinile de stat sunt cu siguranță utile pentru implementarea logicii inteligenței artificiale în jocuri. Ele pot fi reprezentate cu ușurință sub formă de grafic, ceea ce permite dezvoltatorului să vadă toate opțiunile posibile.

Implementarea unei mașini de stare cu funcții de stare este o tehnică simplă, dar puternică. Pot fi implementate chiar și mai multe stări complexe folosind FSM.