Post on 11-Dec-2020
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