Machine d’états finis

1
Machine d’états finis

- Machine d’états finis ( FSM : Finite State Machine) est un outil pour représenter
un système séquentiel
- Une machine d’états finis ou automate ou séquenceur câblé est une système
dynamique qui a un nombre d’état fini.

entrées État Registre État sorties

G F
future d’états présent

clk M
Circuit combinatoire
Circuit combinatoire
qui calcule l’état
qui calcule l’état de
future Circuit séquentiel sortie
synchrone

2
Machine d’états finis

- Machine d’états finis ( FSM : Finite State Machine) est un outil pour représenter
un système séquentiel
- Une machine d’états finis ou automate ou séquenceur câblé est une système
dynamique qui a un nombre d’état fini.

entrées État Registre État sorties

G F
future d’états présent

clk M
Circuit combinatoire
Circuit combinatoire
qui calcule l’état
qui calcule l’état de
future Circuit séquentiel sortie
synchrone
- Les sorties du système dépendent de l’état courant (machine de Moore) ou de
l’état courant et des entrées (machine de Mealy)
- Dans le cas d’une FSM synchrone, la valeur des entrées est analysée sur front
3
d’horloge
Graphe d’états

- Une machine d’états est associée à un graphe d’état qui définit différents états dans
lesquels peut être situé le système

M0
S1 = 0 - Le passage d’un état à un autre s’effectue
S2 = 0
Y=1 M1 sur un front d’horloge et si une condition sur
S1 = 1
X=0 S2 = 0
l’entrée est remplie
M3
S1 = 0 - A chaque instant la machine peut se trouver
S2 = 1
M2 dans un état parmi les n états possible.
S1 = 1
S2 = 1

4
Graphe d’états

- Une machine d’états est associée à un graphe d’état qui définit différents états dans
lesquels peut être situé le système

M0
S1 = 0 - Le passage d’un état à un autre s’effectue
S2 = 0
Y=1 M1 sur un front d’horloge et si une condition sur
S1 = 1
X=0 S2 = 0
l’entrée est remplie
M3
S1 = 0 - A chaque instant la machine peut se trouver
S2 = 1
M2 dans un état parmi les n états possible.
S1 = 1
S2 = 1

5
Graphe d’états

Sorties
Entrées
Etat

dénomination de l’état
transition M0
S1 = 0
S2 = 0 Sorties
Y=1
+
Etat des sorties

Condition sur la transition transition inconditionnelle

6
Graphe d’états

M0
S1 = 0 - Un système à 4 états (M0 à M3), 2
S2 = 0
Y=1 M1 sorties (S1 et S2), 2 entrées X et Y, sans
S1 = 1
X=0 S2 = 0 oublier l’entrée d’horloge qui fait avancer
M3
S1 = 0 le processus, et celle de remise à zéro qui
S2 = 1
M2 permet de l’initialiser
S1 = 1
S2 = 1

- L’état initial est M0. Les 2 sorties sont à 0.

- Au coup d’horloge on passe :
- inconditionnellement à l’état M1
- si la condition Y=1 est vérifiée à l’état M3
- si la condition X=0 est validé à l’état M2.
- De M1 on passe à M2, et de M2 on passe à M 3 sans condition
- De M3 on revient au coup d’horloge à M0. 7
Description en VHDL

La machine d’états finis peut être décrite en 3 façons:

3 process : G / M / F

2 process : G + M / F

2 process : G + F / M

8
Graphe d’états

Exemple 1

Ecriture de la machine d’états avec :

* une seule ENTITE
* une seule ARCHITECTURE

9
Graphe d’états

Ecriture de la machine d’états avec :

* une seule ENTITE
* une seule ARCHITECTURE

M0
S1 = 0
S2 = 0
Y=1 M1
S1 = 1
X=0 S2 = 0
M3
S1 = 0
S2 = 1
M2
S1 = 1
S2 = 1

10
Ecriture de la machine d’états avec :
* une ENTITE
* une ARCHITECTURE de description d’état avec 3 PROCESS G / F / M
deux process combinatoire (G )et (F) et un process synchrone (M).

process (etat_pre)
BEGIN
ENTITY machine1 IS
CASE etat_pre IS
PORT (RAZ, H :IN STD_LOGIC;
WHEN M0 => S1 <= '0'; S2<= '0';
X, Y :IN STD_LOGIC;
WHEN M1 => S1 <= '1'; S2<= '0';
S1, S2 :OUT STD_LOGIC);
WHEN M2 => S1 <= '1'; S2<= '1';
END machine1;
WHEN M3 => S1 <= '0'; S2<= '1';
END CASE;
ARCHITECTURE arch OF machine1 IS
END ;
TYPE etat4 IS (M0, M1, M2, M3);
END arch ;
SIGNAL etat_pre, etat_fut :etat4 := M0;
process(etat_pre,x,
BEGIN
y)BEGIN
ROCESS( raz, H)
CASE etat_pre IS
BEGIN
WHEN M0 => IF Y='1' then etat_fut <= M3;
If raz = '1' THEN etat_pre <= M0;
elsif X='0' then etat_fut <= M2;
ELSIF (H’event and H=‘1’)
ELSE etat_fut <= M1;
THEN etat_pre <= etat_fut;
END IF;
END IF;
WHEN M1 => etat_fut <= M2;
END PROCESS;
WHEN M2 => etat_fut <= M3;
WHEN M3 => etat_fut <= M0;
END CASE;
END ; 11
END arch ;
Description en VHDL avec 3 process

Exemple 2

Ecriture de la machine d’états avec :

* une seule ENTITE
* une seule ARCHITECTURE

12
 Description en VHDL avec 3 process

Un process séquentiel permet

la mise à jour de l’état présent
par l’état futur sur les fronts
montant d’horloge type Etat is (Etat0, Etat1, Etat2);
Signal Etat_present, Etat_futur : Etat := Etat0;

État État process (clk, reset)

future présent sorties begin
entrées
G Registre F
d’états if reset = '0' then
Etat_present <= Etat0;
clk M elsif clk'event and clk = '1' then
Etat_present <= Etat_futur;
end if;
end process 13
 Description en VHDL avec 3 process

process (E, Etat_present)

Un process combinatoire de begin
calcul de l’état futur à partir case Etat_present is
des entrées et de l’état présent when Etat0 => if E = '1' then Etat_futur <= Etat1;
Else Etat_futur <= Etat0;
end if;
État État when Etat1 => if E = ‘0' then Etat_futur <= Etat2;
future présent sorties else Etat_futur <= Etat1;
entrées
G Registre F end if;
d’états
when Etat2 => if E = '1' then Etat_futur <= Etat1;
clk M Else Etat_futur <= Etat0;
end if;
end case;
end process; 14
 Description en VHDL avec 3 process

Un process combinatoire de
calcul des sorties à partir des
entrées et de l’état présent

process (Etat_present)
État État begin
future présent sorties case Etat_present is
entrées
G Registre F
d’états when Etat0 => S <= '0';
when Etat1 => S <= '0';
clk M when Etat2 => S <= '1';
end case;
end process
15
Graphe d’états

Exemple 3

Ecriture de la machine d’états avec :

* une seule ENTITE
* une seule ARCHITECTURE

16
Machine à état : Exemple « détecteur de séquence »

La porte ne s’ouvre que si l’on tape la

séquence ‘1’‘2’‘3

Etat 0 : le système attend un ‘1’en entrée, la porte est fermée (P=0)

Etat 1 : le système attend un ‘2’en entrée, la porte est fermée (P=0)
Etat 2 : le système attend un ‘3’en entrée, la porte est fermée (P=0)
Etat 3 : la bonne séquence a étéentrée, la porte est ouverte (P=1)

17
Machine à état : Exemple « détecteur de séquence »

On représente une machine à état par un graphe d’état

18
Machine à état : Exemple « détecteur de séquence » // 3 process

Entité

Entity machine is
Port ( H : in std_logic ;
bouton : in integer rang 0 to 9;
p : out std_logic ) ;
End machine;

Architecture

Architecture arch of machine is

Type statetype is (etat0, etat1, etat2, etat3 ) ;
Signal etat_courant, etat_suivant : statetype ;
begin
19
Machine à état : Exemple « détecteur de séquence » // 3 process

Process (etat_courant, bouton)

Begin
Case etat_courant is
When etat0 => If bouton = 1 then etat_suivant <= etat1 ;
Else etat_suivant <= etat0 ;
End if;

When etat1 => If bouton = 2 then etat_suivant <= etat2 ;

Else etat_suivant <= etat0 ;
End if;

When etat2 => If bouton = 3 then etat_suivant <= etat4

Else etat_suivant <= etat0 ;
End if;

When etat3 => etat_suivant <= etat0 ;

End case;

20
Machine à état : Exemple « détecteur de séquence » // 3 process

Process (etat_courant, bouton)

Begin
Case etat_courant is
When etat0 => p <= ‘0’;
When etat1 => p <= ‘0’;
When etat2 => p <= ‘0’;
When etat3 => p <= ‘1’;
End case;
End process;

Process (clk)
Begin
If (clk’event and clk = ‘1’ ) then
If RST = ‘1’ then Etat_courant <= etat0 ;
Else Etat_courant <= etat_suivant ;
End if ;
End if ;
End process;
End arch
21