Automate Secvențiale și Programabile

Cap I. Introducere

1.1. Definiţii

Un automat, reprezintă orice sistem (dispozitiv) ce operează în momente discrete de timp şi este definit de variabile ce iau valori discrete care pot fi codificate binar şi îşi pot atribui un număr finit de configuraţii distincte.

Schema bloc a unui automat este reprezentată în fig.1.1.

Fig.1.1. Schema bloc a unui automat

Prin x(t), z(t) şi y(t) s-au notat variabilele de intrare, ieşire şi respectiv stare, în momentul de timp t.

Se notează cu:

-X= {x1, x2,…,xn} mulţimea nevidă şi finită a variabilelor de intrare ale automatului A.

Mulţimea variabilelor de intrare poate fi privită ca un vector de intrare având componentele (x1, x2,…, xn). Orice înşiruire în timp a unor vectori de intrare definesc o secvenţă de intrare. Mulţimea tuturor secvenţelor de intrare alcătuiesc alfabetul de intrare Xi={X} şi exprimă toate posibilităţile secvenţelor de intrare.

-Z={z1, z2,…,zm} mulţimea nevidă şi finită a variabilelor de ieşire a automatului.

Mulţimea variabilelor de ieşire poate fi privită ca un vector de ieşire care poate să definească o secvenţă de ieşire. Mulţimea tuturor secvenţelor de ieşire alcătuiesc alfabetul de ieşire al automatului Zi={Z}.

-Y={y1, y2,…, ys} mulţimea stărilor automatului A. Starea este o variabilă internă ce evoluează parţial independent de intrare fiind responsabilă de comportamentul autonom al automatului.

Chiar dacă intrarea unui automat este invariabilă, starea lui internă se poate modifica. Din acest motiv, un automat poate avea un comportament variabil la ieşire chiar în intervalul de timp în care intrarea lui este invariabilă.

Mulţimea Y poate fi asociată cu un vector de stare care are drept componente elementele distincte ale mulţimii. Totalitatea vectorilor de stare constituie alfabetul stărilor Yi={Y}.

Cu mulţimile prezentate mai sus definim funcţiile:

1. f: X x YY denumită funcţia de tranziţie şi transformă mulţimea perechilor (xi, yj) în mulţimea Y.

2. g: X x YZ numită funcţia de ieşire care transformă mulţimea perechilor (xi, yj) în mulţimea Z.

Def: Un automat este un cvintuplu de forma {X, Z, Y, f, g}.

Def: Dacă mulţimea Y este finită atunci automatul este finit.

Def: Mulţimea de tipul {y0, y1,…,yk} defineşte evoluţia automatului pornind dintr-o stare iniţială y0 sau stare de pornire până într-o stare yk sau stare finală.

Def: O anumită stare yk este controlabilă în raport cu o stare iniţială y0 dacă ea poate fi atinsă cu ajutorul unei secvenţe de intrare de lungime k (pentru a trece din starea y0 în starea yk este necesară o succesiune de k vectori de intrare).

Def: Dacă ys=f(xi, yp) atunci ys – reprezintă starea succesoare lui yp

yp – reprezintă starea predecesoare lui ys

1.2. Moduri de reprezentare a automatelor

1.2.1. Reprezentarea analitică

Porneşte de la cele două funcţii definite anterior f şi g (funcţie de tranziţie şi de ieşire).

y(t+1)= f(x(t), y(t)) şi z(t)= g(x(t), y(t)) pentru varianta de automat MEALY şi

y(t+1)= f(x(t), y(t)) şi z(t)= g(y(t)) pentru varianta de automat MOORE.

Dacă dezvoltăm avem pentru stare:

y1(t+1)= f1(x1(t), …, xn(t), y1(t), …, ys(t)) (1)

ys(t+1)= fs(x1(t) ), …, xn(t), y1(t), …, ys(t))

Indicele “s” reprezintă de fapt o secvenţă de intrare la un moment dat.

Pentru variabilele de ieşire avem:

z1(t)= g1(x1(t), …, xn(t), y1(t), …, ys(t)) (2)

zm(t)= gm(x1(t), …, xn(t), y1(t), …, ys(t))

Analog se dezvoltă şi pentru varianta MOORE.

Cele două sisteme de ecuaţii (1) şi (2) definesc complet evoluţia unui automat.

1.2.2. Reprezentarea grafică a automatelor

1.2.2.1.Reprezentarea prin grafuri de tranziţie

Graful de tranziţie este un graf orientat format din noduri şi laturi. Nodurile reprezintă de fapt stările automatului, iar laturile grafului sunt căile de tranziţie (condiţiile) între noduri (între stările automatului). Laturile sunt notate prin intrările xi (care generează tranziţia între cele două stări de la extremităţile laturii) şi pun în evidenţă ieşirile corespunzătoare zi= g(yi, xi). Prin indicele “i” s-au considerat valorile variabilelor de intrare, stare şi ieşire la un anumit moment de timp. Pentru variabila de timp s-au considerat valori discrete.

Un exemplu de graf de tranziţie este dat în figura 1.2.

Există o singură restricţie: dintr-un nod al grafului nu putem avea două evoluţii distincte generate de aceeaşi intrare.

1.2.2.2. Reprezentarea prin tabele de stare şi de tranziţie

Funcţiile f şi g definesc complet evoluţia unui automat, ele numindu-se şi funcţii caracteristice.

Această reprezentare presupune punerea sub formă tabelară a relaţiilor:

yi+1= f(xi, yi) (3)

zi= g(xi, yi) (4)

unde indicele “I” ne arată că variabila timp ia valori discrete, iar xi, yi, zi sunt valorile variabilelor de intrare, stare şi ieşire la un anumit moment de timp şi yi+1 reprezintă valoarea la momentul următor.