Prof.univ.dr.ing. Oniga Ștefan

SISTEME CU CIRCUITE INTEGRATE DIGITALE (EA II)

ELECTRONICA DIGITALA (CAL I)

Automate finite

Modelul abstract al dispozitivelor de prelucrare a informației se

numește AUTOMAT (mașină de stare)

Un automat este un sistem dinamic a cărui comportare se poate

descrie ca o succesiune de evenimente numite stări, ce apar la

momente discrete ale variabilei timp

Automate finite

• Automat finit - dacă mulțimea stărilor interne s(t) este finită.

• FSM = Finite state machine

• Automatul finit interacționează cu mediul:• La un anumit moment de timp t este supus unui semnal de intrare x(t)

• La momentul t+dt oferă ca răspuns la ieșire semnalul z(t)

Automate finite

• Automat finit - cvintuplu A = { X, Z, S, f, g }X , Z si S sunt mulțimi finite nevide, f și g sunt funcții definite pe aceste

mulțimi

X = { x1, x2, … xn } – mulțimea variabilelor de intrare

Z = { z1, z2, … zn } – mulțimea variabilelor de ieșire

S = { s1, s2, … sn } – mulțimea stărilor automatului

• Funcția de tranziție f : S X → S

Transformă mulțimea tuturor perechilor ordonate (si, xj) în mulțimea S

Are rolul de a preciza starea în care ajunge automatul în urma aplicării

unei intrări (dă starea următoare, funcție de intrare şi de starea prezentă)

Funcția de ieșire g : S X → Z

Transformă mulțimea tuturor perechilor ordonate (si, xj) în mulțimea Z

Are rolul de a preciza ieşirea automatului în urma aplicării unei intrări

Automate sincrone

• Sunt circuite logice secvențiale care prezintă în structura lor:– circuit logic combinațional pentru determinarea stării viitoare (pe baza intrărilor și

a stării prezente);

– registru de stare pentru memorarea stării curente;

– circuit logic combinațional pentru determinarea valorilor ieșirilor (pe baza intrărilor și a stării prezente).

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

• După dependența ieșirilor de intrări, automatele se clasifică în:– automatele de tip Moore, ieșirea este dependentă exclusiv de starea prezentă;

– automatele de tip Mealy, ieșirea este dependentă atât de starea prezentă cât și de intrări.

Automate sincrone

• După întârzierea ieșirilor față de intrări, automatele se clasifică in:– automatele imediate, ieșirea este generată dintr-un circuit combinațional;

– automatele cu întârziere, ieșirea este generată de un circuit combinațional urmat de un registru.

Automate sincrone

• Comportamentul automatelor poate fi descris în mai multe forme de

reprezentare:

– Organigrama

– Tabelul de tranziție al stărilor

– Graful de tranziție al stărilor

• Organigrama este o formă de reprezentare grafică funcționării unui

automat. O organigramă conține următoarele tipuri de simboluri:

– Simbolul de stare (dreptunghi) care conține în interior numele ieșirilor active în acea stare și în exterior numele simbolic al stărilor și codul binar al acestora.

– Simbolul de decizie (romb) care conține în interior o condiție a intrărilor și în exterior valorile cu care se poate evalua condiția 0 și 1.

– Simbolul de ieșire imediată (oval) care conține în interior numele ieșirilor activate în cazul îndeplinirii condiției din simbolul de decizie precedent.

Tabelul de tranziții

• Include informații complete despre comportamentul automatului într-o

formă ușor de utilizat pentru implementare. Tabelul conține următoarele

secțiuni:

– Intrări, câte o coloană pentru fiecare intrare. Valorile logice ale intrărilor pot fi 0 și 1 sau pot fi considerate indiferente pentru tranziția din anumita stare (se marchează cu X).

– Stare prezenta, pe o coloană denumirea generică a stării curente.

– Stare viitoare, pe o coloana denumirea generică a stării viitoare.

– Ieșiri, cate o coloana pentru fiecare ieșire.

Graful de tranziții

• Este o formă de reprezentare grafică a comportamentului unui automat într-o

manieră algoritmică, utilizând noduri și arce. Nodurile sunt asociate stărilor, iar

arcele modelează tranzițiile între stări. Arcul pornește din nodul asociat stării

prezente și ajunge in nodul asociat stării viitoare.

• În noduri se marchează codul stării (și ieșirea la automatele Moore).

• Pe arce se marchează:

• condițiile intrărilor la automatele Moore

• condițiile intrărilor și starea ieșirilor la automatul Mealy.

Automat MooreAutomat Mealy

Codificarea stărilor

• Se poate face în diferite feluri:

• Numărare efectivă, în binar: de exemplu, la o codificare pe 3 biți, se

numără stările de la 000, 001, 010, … 111

• Codul Gray, în care numerele consecutive diferă doar printr-un singur bit:

000, 001, 011, 010 …

• Codul “one-hot”, în care avem nevoie de atâția biți câte stări există. În

starea i, toți biții sunt 0, mai puțin bitul i, care e pe 1 (hot).

• Codul “one-cold”, asemănător cu cel de mai sus, numai că valorile sunt

inversate.

Zecimal Binar One-hot Gray

0 000 00000001 000

1 001 00000010 001

2 010 00000100 011

3 011 00001000 010

4 100 00010000 110

5 101 00100000 111

6 110 01000000 101

7 111 10000000 100

Detectarea unei secvențe cu un automat Moore

• Se cere desenarea grafului de tranziții pentru un automat Moore folosit pentru

detectarea unei secvențe.

• Secvența de detectat 1101.

• Starea ieșirii va fi 1 daca se va detecta secvența așteptată.

• Starea inițială este s0 corespunzătoare stării in care încă nu s-a recepționat nici un 1.

0

Registrul de stare

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

CLC pentru determinarea stării viitoare

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

CLC pentru determinarea ieșirii

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

Simulare automat Moore

pentru detectarea secvenței 1101

Detectarea unei secvențe cu un automat Mealy

• Se cere desenarea grafului de tranziții pentru un automat Mealy folosit pentru

detectarea unei secvenței 1101.

• Starea ieșirii va fi 1 daca se va detecta secvența așteptată.

• Starea inițială este s0 corespunzătoare stării in care încă nu s-a recepționat nici un 1.

Registrul de stare automat Mealy

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

CLC pentru determinarea stării viitoare

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

CLC pentru determinarea ieșirii

NEXT

STATE

STATE

REGISTERINPUTS

OUTPUT

FUNCTION

CLK RESET

Mealy model

OUTPUTS

Simulare automat Mealy pentru detectarea

secvenței 1101

Exemplu FSM

• Semafor (simplu)

– Stări: roșu, roșu-galben, verde, galben

– Intrări: temporizatoare pentru diferitele stări

– Ieșiri: starea

R

RY

G

Y

Codificare stări semafor (Verilog)

module light( input clk, rst, output reg [2:0] led);

// codificare stari

parameter RED = 2'b00;

parameter RY = 2'b01;

parameter GREEN = 2'b10;

parameter YELLOW = 2'b11;

reg [15:0] timer;

reg [1:0] state_reg;

reg [1:0] next_state;

// registru de stare

always @ (posedge clk)

if (rst)

state_reg <= RED;

else

state_reg <= next_state;

• Semafor se află in fiecare stare un timp determinat.

• Codificare binară:

CLC pentru determinarea stării viitoare

always @ (*)

case(state_reg)

RED: begin

if (timer == 0)

next_state <= RY;

else

next_state <= R;

end

RY: begin

if (timer == 0)

next_state <= GREEN;

else

next_state <= RY;

end

YELLOW: begin

if (timer == 0)

next_state <= RED;

else

next_state <= YELLOW;

end

GREEN: begin

if (timer == 0)

next_state <= YELLOW;

else

next_state <= GREEN;

end

default:

next_state <= 2'bxx;

endcase

R

RY

G

Y

Temporizator

always @ (posedge clk)

case(state_reg)

RED: begin

if (timer == 0)

timer <= 500; //next_state <= RY;

else

timer <= timer - 1;

end

RY: begin

if (timer == 0)

timer <= 4000; //next_state <= GREEN;

else

timer <= timer - 1;

end

YELLOW: begin

if (timer == 0)

timer <= 4500; //next_state <= RED;

else

timer <= timer - 1;

end

GREEN: begin

if (timer == 0)

timer <= 500; //next_state <= YELLOW;

else

timer <= timer - 1;

end

endcase

• Încarcă noua valoare când

se schimbă starea

• Numărare în jos

• ==0: schimbare stare

CLC pentru decodificarea ieșirilor

always @ (*)

case (state_reg)

RY : led <= 3'b110;

RED: led <= 3'b100;

YELLOW: led <= 3'b010;

GREEN: led <= 3'b001;

default: led <= 3’b100;

endcase

endmodule