CURS 4

CURS 4

Capitolul IV

AUTOMATE ASINCRONE

4.1. Analiza automatelor asincrone

Analiza = procedura de determinare a funciilor pe care un anume automat le poate ndeplini i eventual depistarea unor anomalii ce pot interveni n funcionarea lui.

x1

z1variabile

variabile

de intrare

de ieire

xn

CLC

zm

y1

Elem. de memorie

Y1 funcii

variabile

secundare

secundare

CLS

(de stare)

ys

Ys

Evoluia automatului este descris printr-un sistem de ecuaii, innd cont de variabilele de intrare, stare, respectiv ieire, pentru determinarea strii urmtoare i a ieirii.

Yi(t) = fi(x1(t), , xn(t), y1(t), , ys(t))i = 1,s

Zj(t) = gj(x1(t), , xn(t), y1(t), , ys(t))j=1,m

La automatele asincrone se obine:

yi(t+1) = Yi(t)i = 1,s

n evoluia automatelor asincrone un rol important l va avea identificarea strilor stabile i instabile. Problemele deosebite apar datorit strilor instabile.

O stare va fi stabil dac:

Yi(t) = yi(t+1) = yi(t)

La analiza automatelor asincrone, tranziiile dintr-o stare n alta se efectueaz ca rspuns la modificarea variabilelor de intrare. Se presupune c nu se modific alt variabil de intrare pn cnd automatul nu ajunge ntr-o stare stabil. Astfel automatul este determinist.

Automatele asincrone pot funciona n:

mod fundamental variabilele de intrare considerate ca nivel funcioneaz ca mai sus;

mod impuls la un moment dat apare un singur impuls ca intrare.

Etapele analizei

1. Se identific variabilele de intrare, stare i ieire. Se determin funciile secundare Yi i de ieire Zj.

2. Se construiete tabelul funciilor secundare i de ieire.

3. Se construiete tabelul de evoluie al automatului, determinnd strile stabile i instabile.

4. Se verific evoluia automatului pentru stri iniiale i intrri specificate.

Exemplu:

x

z1

z2

z3

z4

Y1

Y2

Etapa 1:

Identificm variabilele:

1 variabil de intrare: x,

2 variabile de stare: y1, y2 4 variabile de ieire: z1, z2, z3, z4.

Funciile secundare i de ieire sunt:

Y1 = xy1 + xy2

Y2 = xy1 + xy2

z1 = y2y1

z2 = y2y1

z3 = y2y1

z4 = y2y1Etapa 2:

Se construiesc tabelul funciilor secundare i tabelul ieirilor:

y1y2 x01y1y2 x01

0000010010001000

0111010101000100

1111101100010001

1000101000100010

Y1Y2

z1z2z3z4Automatul este de tip Moore pentru c ieirile nu depind de intrri.

Etapa 3:

Pentru determinarea strilor stabile i instabile se construiete tabelul de evoluie.

Pentru determinarea strilor stabile se compar valorile variabilelor de stare y1y2 cu cele ale funciilor secundare Y1Y2 i la coincidena lor va fi o stare stabil.

y1y2 x01

000001

011101

111110

100010

Y1Y2y1y2 x01

112

232

334

414

Pentru evidenierea strilor stabile le ncercuim. Din cele 8 stri ale automatului, doar 4 sunt stabile, celelalte 4 fiind instabile.

Etapa 4:

Verificm evoluia automatului pentru stri iniiale i intrri specificate.

y1y2 x01

112

232

334

414

Dac suntem n starea 1 (adic 00), pentru intrarea x = 0, automatul rmne n starea 1, deci starea 1 este stabil. Dac suntem n starea 1, pentru x = 1 automatul trece n starea instabil 2. Durata strii instabile 2 este egal cu cea a duratei procesului de comutaie din circuit. Din starea instabil 2 automatul va trece n starea stabil 2. O tranziie de la o stare instabil la starea stabil corespunztoare este specificat prin notarea celor dou stri cu aceeai cifr.

Pentru a trece de la o stare stabil la alt stare stabil se trece printr-o stare instabil.

Putem reprezenta tranziiile unui automat asincron prin diagrame de timp:

x

Y1

Y2 (t

y1 (t

y2

1 2 2 3 3

4.2. Sinteza automatelor asincrone

Sinteza unui automat asincron (circuit secvenial asincron) cu o anumit comportare (descris n cazul cel mai general prin cuvinte) const n construirea unei scheme logice (reele de comutare) secveniale care s realizeze comportarea cerut.

Etape:

1. Se determin tabelul primar al strilor.

2. Se elimin strile redundante din tabelul primar.

3. Se construiete un tabel al strilor cu un numr minim de stri interne.

4. Se codific strile interne obinndu-se tabelul tranziiilor.

5. Se scriu expresiile minime pentru starea urmtoare i pentru ieiri.

6. Se proiecteaz (deseneaz) schema circuitului pe baza expresiilor obinute.

7. Se verific dac schema obinut funcioneaz corect (dac are hazard, acesta se elimin).

Exemplu:

S se proiecteze un automat asincron cu 2 intrri x1 i x2 i o ieire z, care respect urmtoarele condiii de funcionare:

- ieirea automatului va fi 1 cnd pe ambele intrri x1 i x2 se aplic 1, dar numai cnd x2 se aplic naintea lui x1;

- n acest caz ieirea z se menine 1 att timp ct se menine x2;

- se consider c x1 i x2 nu se pot modifica simultan.

x101000111001011011000100

x200010010011110001101110

z00000000001110000000110

S12131242135652124313561

Etapa 1. Tabelul primar al strilor = matrice ce va conine pe o linie o singur stare stabil i toate tranziiile posibile implicate de aceast stare. Numrul de coloane va fi dat de numrul maxim de combinaii ale variabilelor de intrare. Tabelului primar al strilor i corespunde un tabel al ieirilor pentru fiecare stare stabil determinat a automatului. Schimbnd starea intrrilor, automatul aflat ntr-o stare stabil trece ntr-o stare instabil pe coloana corespunztoare intrrilor, care trebuie s fie stabil pe alt rnd. Deoarece starea prezent pentru un anumit rnd este aceeai cu starea stabil (ncercuit), nu se mai scrie n tabelul primar al strilor starea prezent.

S x1x200011110

113-2

21-42

3135-

4-342

5-652

6165-

S x1x200011110

100x0

20x00

300xx

4x000

5x11x

6x11x

z

Tabelul primar al strilor trebuie completat n totalitate. Pentru locaiile care nu pot fi atinse avem 2 situaii:

stri interzise corespund unor condiii de funcionare interzise, dar care pot s apar. Pentru astfel de situaii interzicerea tranziiilor se reduce la menionarea ieirilor sau la modificarea lor impus;

stri indiferente corespund situaiilor de funcionare care nu pot fi atinse. Coninutul lor este indiferent.

n cazul nostru locaiile necompletate corespund condiiei ca variabilele de intrare s nu comute simultan.

Tabelul ieirilor se completeaz n prima etap cu ieirile corespunztoare strilor stabile. Pentru continuarea completrii tabelului se analizeaz tranziiile dintre strile stabile.

1. i ( j ( j nu modific ieirea ( ieirea automatului trebuie meninut i n starea instabil;

2. i ( j ( j dac se modific ieirea pe durata strii instabile, ieirea poate fi considerat indiferent.

n cazul nostru locaiile indiferente se pot considera cele care corespund trecerii ntre dou stri stabile care presupun modificarea simultan a variabilelor de intrare.

Observaie: Sunt automate care trebuie s evolueze mai rapid sau mai lent; dac se cere o evoluie mai rapid, atunci n starea instabil se pune deja ieirea corespunztoare strii stabile urmtoare (nu se las indiferent); dac evoluia este mai lent atunci se pstreaz n starea instabil ieirea strii stabile anterioare.

Etapa 2. Pentru reducerea costului automatului se face o reducere a liniilor tabelului primar al strilor. Reducerea se obine prin fuzionarea liniilor n condiiile impuse de compatibilitile i acoperirile din teoria automatelor finite.

Fuzionarea a dou linii se face dup urmtoarele reguli:

dou linii pot fuziona dac locaiile corespunztoare fiecrei coloane corespund aceluiai numr de stare stabil sau instabil;

prin fuzionarea unei stri stabile cu una instabil rezult o stare stabil;

prin fuzionarea unei stri stabile sau instabile cu o stare interzis rezult o stare stabil, respectiv instabil.

Observaie: nu se pune problema ieirii, ea fiind cuprins n numrul strii.

Exist urmtoarele combinaii posibile:

ijijki-i-k--

ijijk-j-j-k-

Forma minim obinut dup fuzionare nu este unic.

Etapa 3. Pentru a se obine cea mai bun soluie de minimizare se construiete un poligon al alipirilor. Acest poligon are n noduri strile automatului i se marcheaz prin arce toate alipirile posibile ntre liniile tabelului primar al strilor.

S x1x200011110

113-2

21-42

3135-

4-342

5-652

6165-

1

6

2

5 3

4

Pentru obinerea formei minime se urmrete determinarea de poligoane nchise att interior ct i exterior, cu un numr ct mai mare de laturi. O stare poate s apar o singur dat. Soluii pot fi:

A{1, 3}

{1, 2, 4}

B{2, 4}

sau

{3}

C{5, 6}

{5, 6}

Dac se alege prima soluie se obin urmtoarele tabele ale strilor i ieirilor:

x1x200011110

A{1, 3}1352

B{2, 4}1342

C{5, 6}

1652

x1x200011110

00x0

0000

x11x

z

Etapa 4. Codificarea strilor interne

n tabelul primitiv al strilor codificarea unei stri se realizeaz numai prin variabilele secundare.

n tabelul redus al strilor, pe aceeai linie pot s apar mai multe stri stabile, deci putem avea o evoluie a automatului dintr-o stare stabil n alt stare stabil fr modificarea variabilelor de stare, doar prin modificarea variabilelor de intrare.

Pentru un numr p de stri reduse sunt necesare q variabile de stare:

2q ( p

Restricie: codificarea strilor trebuie fcut pentru a se evita hazardul de tranziie, care poate s apar n cazul modificrii simultane a cel puin 2 variabile secundare.

Definiii:

1. Un eveniment n care se modific mai mult de o variabil secundar se numete curs.

2. Dac starea final a automatului nu depinde de ordinea de modificare a variabilelor secundare cursa este necritic.

3. Dac starea final a automatului depinde de ordinea de modificare a variabilelor secundare cursa este critic i trebuie evitat.

4. Trecerea automatului printr-o succesiune unic de stri instabile se numete ciclu.

5. Codificarea (asignarea) strilor care nu conine curse critice este o codificare (asignare) valid.

Exemplu:

y1y2 x1x200011110

00159

012610

113711

104812

Dac automatul se afl n starea instabil 1, pentru x1x2 = 00 el va evolua pn ajunge n starea stabil 3. n funcie de ordinea de modificare a variabilelor de stare y1y2 avem urmtoarele posibiliti: 1 ( 2 ( 3 dac y2 se modific mai repede ca y1; 1 ( 4 ( 3 dac y1 se modific naintea lui y2; 1 ( 3 dac y1y2 s-ar modifica simultan, ceea ce n realitate este practic imposibil datorit ntrzierilor diferite; cursa este totui necritic, deoarece starea final nu depinde de ordinea n care s-au modificat variabilele secundare y1y2.

Dac x1x2 = 11 i automatul se afl n starea instabil 5, dac y1 se modific naintea lui y2, atunci 5 ( 8 i dac y2 se modific naintea lui y1, atunci 5 ( 6 deci cursa este critic, deoarece se ajunge n stri finale diferite, n funcie de ordinea de modificare a variabilelor secundare (de stare).

Dac x1x2 = 10 i automatul se afl n starea instabil 9, dac y2 se modific naintea lui y1, atunci 9 ( 10 ( 11 i dac y1 se modific naintea lui y2, atunci 9 ( 12 deci cursa este critic.

Pentru evitarea curselor critice trebuie evitate tranziiile de stare la care se modific simultan mai multe variabile de stare.

Observaii:

- dac ntr-o coloan a tabelului redus al strilor exist o singur stare stabil cursa este necritic;

- cnd ntr-o coloan a tabelului redus al strilor exist mai mult de o stare stabil, tranziiile dintre dou stri codificate neadiacent, care conduc la stri stabile, genereaz curse critice.

Pentru o codificare corect ncepem prin a construi un graf al tranziiilor. Acesta va avea n noduri strile alipite (reduse), iar ca laturi arce orientate conform tranziiilor posibile.

x1x200011110

A001352

B011342

C101652

A 00

01B

C 10

Avnd tranziii duble ntre A i B i A i C, dar i tranziie simpl ntre C i B nu putem face nici o codificare cu 2 variabile secundare care s rezolve problema adiacenei.

Cu codificarea fcut poate s apar curs critic la tranziia din C n B, unde se modific ambele variabile de stare. Pe ultima coloan, corespunztoare tranziiei din C n B avem doar o stare stabil, deci cursa nu este critic i putem pstra codificarea fcut.

Tabelul redus al strilor i cel al ieirilor, cu codificarea fcut vor arta astfel:

y1y2 x1x200011110

001352

011342

11----

101652

y1y2 x1x200011110

0000x0

010000

11xxxx

10x11x

Etapa 5. Se determin expresiile minime pentru starea urmtoare i pentru ieire.

y1y2 x1x200011110

0000001001

0100000101

11xxxxxxxx

1000101001

y1y2 x1x200011110

000010

010000

11xxxx

100110

Y1

y1y2 x1x200011110

000001

010011

11xxxx

100001

Y2

Y1 = y1x2 + y2x1x2

Y2 = y2x1 + x1x2

z = y1Etapa 6. Schema logic care rezult conform ecuaiilor de mai sus este:

x1

z

Y1

x2

Y2

Observaie: Dac n etapa a treia se utilizeaz a doua codificare a strilor avem:

x1x200011110

A{1, 2, 4}1342

B{3}135-

C{5, 6}

1652

x1x200011110

0000

00xx

x11x

z

Graful (poligonul) tranziiilor:

A 00

01B

C 10

Pornind din starea 01 (B), dac y2 se modific prima, tranziia este B ( A, iar dac y1 se modific prima, tranziia este B ( C, deci avem o curs critic (starea final a automatului este funcie de modificarea variabilelor de stare; automatul are ieiri diferite).

4.3. Metode pentru evitarea curselor critice

Evitarea curselor critice se poate face prin mai multe metode:

1. Recodificarea strilor

2. Utilizarea combinaiilor de codificare nefolosite

a. asignarea unei stri cu dou combinaii de variabile secundare

b. introducerea unei stri instabile pe coloana corespunztoare cursei critice

3. Introducerea unei variabile secundare suplimentare

4.3.1. Recodificarea strilor

Avem automatul cu tabelul redus al strilor:

y1y2 x1x200011110

A003162

B013162

C113164

D103562

Din starea stabil C = 11 pentru a ajunge n starea stabil A = 00, la modificarea variabilelor de intrare x1x2 din 00 n 01, dac variabila secundar y1 se modific prima se ajunge n starea stabil A = 00, dar dac y2 se modific prima, se ajunge n starea stabil D = 10, deci avem o curs critic.

Se face o reasignare a strilor nct tranziiile critice s implice schimbarea unei singure variabile secundare.

y1y2 x1x200011110

A003162

B013162

C103164

D113562

Din starea stabil C = 10, la modificarea variabilelor de intrare x1x2 din 00 n 01, se ajunge n starea stabil A = 00 prin modificarea unei singure variabile secundare, y1.

4.3.2. Utilizarea combinaiilor de codificare nefolosite

a. Se acord dou coduri pentru aceeai stare.

Pentru automatul:

y1y2 x1x200011110

A001342

B01135-

C101652

A 00

01B

C 10

avem o curs critic dac se pleac din starea stabil B. Vom codifica starea C cu dou coduri, 10 i 11. Avem atunci tabelul:

y1y2 x1x200011110

A001342

B01135-

C111652

C101652

y1y2 x1x200011110

A0000010000

B01000111-

C1100111100

C1000101000

b. Introducerea unei stri instabile.

Vom avea:

y1y2 x1x200011110

A001342

B01135-

11-6*--

C101652

y1y2 x1x200011110

A0000010000

B01000110-

11-11--

C1000101000

Pentru a ajunge din 01 (B) n 10 (C) se foreaz trecerea prin starea instabil 11. Aceast modalitate de evitare a curselor critice conduce la ecuaii mai simple la minimizare.

4.3.3. Introducerea unei variabile de stare suplimentar

Metoda se folosete n situaiile n care sunt utilizate toate combinaiile de codificare i n nici o asignare nu se poate realiza adiacena codificrii strilor.

Considerm automatul cu tabelul redus al strilor i graful de tranziii:

y1y2 x1x200011110

A001246

B011347

C111258

D101356

00 01

A

B

C

D

11 10

Se introduce variabila de stare suplimentar y3 i se face codificare cu 3 variabile de stare y1y2y3. Urmrim realizarea adiacenei ntre strile automatului pentru a evita apariia curselor critice. Vom folosi tabelul:

y1 y2y300011110

0ACCD

1BD

Pentru a gsi o asignare valid punem A n 000 i B, C, D le plasm n 3 celule adiacente. Tranziiile B ( D i D ( C necesit modificarea a dou variabile secundare. Pentru a rezolva situaia se introduc strile intermediare instabile D i C. Cu codificarea: A = 000; B = 100; C = 001; D = 010 vom obine pentru automatul dat:

y1y2y3 x1x200011110

A0001246

C0011258

C0115

D0101356

D1103

111

101

B1001347

Observaie: Se poate face o asignare valid pentru un tabel redus cu 4 linii, cu ajutorul a 3 variabile secundare, prin asignarea a 2 coduri adiacente ale variabilelor secundare pentru fiecare linie din tabel.

Exemplu:

y1 y2y300011110

0ABBC

1ADDC

Se poate arta c pentru orice tabel primar cu 2n linii, o asignare valid poate fi fcut cu 2n-1 variabile secundare, astfel nct s fie posibil tranziia ntre oricare 2 linii ale tabelului.

Pentru un tabel cu 8 linii se folosesc 4 variabile secundare. O asignare posibil este:

ABEE

ABFF

CCGH

DDGH

4.4. Automate asincrone n mod impuls

Exist situaii practice n care un automat primete un singur impuls.

Pentru ca funcionarea acestui automat s fie determinist se impun restriciile:

1. impulsurile trebuie s fie suficient de lungi ca s schimbe starea automatului;

2. impulsurile trebuie s fie suficient de scurte nct s nu mai fie prezente dup schimbarea strii automatului.

La apariia impulsului automatul evolueaz dintr-o stare stabil n alt stare stabil, stri memorate n bistabile (elementele de memorie). Acest mod de funcionare difer de cel fundamental, deoarece automatul n mod impuls este stabil i cnd nu are intrri. Absena impulsurilor nu conine informaie. Din acest motiv numrul de coloane din tabelul de tranziii este egal cu numrul variabilelor de intrare.

Exemplu:

Automat pentru taxe de automobile. Taxa este de 3500 lei. Se accept monede de 500, 1000, 2000. Un sistem electromecanic accept monezile secvenial, chiar dac ele se introduc deodat, genernd impulsuri X5, X10, X20. Automatul produce un nivel de ieire care aprinde un bec verde dac s-au primit 3500 lei. Dup ce a trecut o main automatul se reseteaz cu impulsul de resetare XR i revine n starea iniial. Orice sum mai mare de 3500 lei este credit pentru maina urmtoare.

Soluie:

LeiStare prezentX5X10X20XRz

0ABCEA0

500BCDFA0

1000CDEGA0

1500DEFHA0

2000EFGHA0

2500FGHHA0

3000GHHHA0

(3500HHHHA1

n momentul n care moneda este primit, este luat n considerare.

11