Université des Sciences et de Technologie Houari

Boumediene USTHB

MASTER ELECTRONIQUE DES SYSTÈMES EMBARQUÉS

MACHINE À ÉTATS FINIS

(FSM : FINITE STATE MACHINE)
 Objectif de ce cours

A la fin de ce chapitre, vous devez être capable:

D’analyser une machine à états finis et d’en donner les graphes et

les tables d’états.

De synthétiser une machine à états finis à partir de sa description

fonctionnelle.
 Machine à états
Les machines à état permettent de décrire des systèmes séquentiels
dont l’évolution est plus complexe que les compteurs ou les
registres.

Il est remarquable de constater que le concept relatif aux automates

(au sens machines à état) se retrouvent désormais dans des
applications diverses :

– Circuits numériques ;
– Automatismes industriels ;
– Processeurs ou microcontrôleurs ;
– Programmes informatiques.
 Machine à états
Par exemple, pour une machine à café, les états peuvent être :
1 – Attente de pièce ;
2 – Descente du gobelet ;
3 – Versement de la poudre à café ;
4 – Versement de l’eau chaude ;
5 – Affichage "café est prêt"...
Et les évènements :
Pièce insérée ;
Gobelet présent ;
Gobelet absent ;
Timer terminé (compte-à-rebours)...

Le comportement (succession d’états) de la machine se déroule selon une

séquence. Un tel système est donc bien séquentiel.
 Machine à états
Principe de fonctionnement

La machine d’état s’apparente à un automate ou un grafcet

Le système est dans un état stable ( équivalent d’une étape pour le grafcet)
Il peut évoluer vers un autre état du système en fonction des entrées ( réceptivité VRAIE)
A chaque état correspond une/des sorties actives ( les actions associées aux étapes)
La représentation graphique est un diagramme à bulle
Ne pas oublier de faire un tableau à côté pour préciser les sorties en fonction de l’état
 Machine à états

Contraintes de fonctionnement
Une machine d’état a besoin d’une horloge (quartz, astable en
externe ou PLL embarquée)

Une transition est activée lorsque

L’étape source est active

La réceptivité est vrai (équation logique sur les entrées)
Un front d’horloge survient
 Machine à états
Les différentes types de Finite State Machine (FSM)
Machine de Moore

La sortie ne dépend que de l’état courant

Le temps de réaction dépend donc de l’horloge
Cette machine peut-être qualifiée de synchrone

Machine de Mealy
La sortie ne dépend de l’état courant mais aussi des entrées
Le temps de réaction est plus rapide que Moore
Cette machine peut-être qualifiée d’asynchrone
Inconvénients: la durée minimum d’un état n’ait plus garanti => L’état peut-
être interprété par un autre système comme un état parasite
Machine à états
Machines de MOORE et de MEALY
Analyse d’un système séquentiel
Exemple de machine à états finis
 Machine à états
Codage des états
Création d’un type énuméré
Le compilateur affecte automatiquement un entier à chaque état
• TYPE etat IS (debut, etat1, etat2);
• SIGNAL etat_present : etat;
Codage à la main
L’utilisateur affecte un entier « à la main »
• Ex: début vaudra 0,état1 vaudra 1 et état 2 vaudra 2
SIGNAL etat_present : integer range 0 to 2; OU
SIGNAL etat_present : std_logic_vector(1 down to 0);

Gestion des transitions

DANS UN PROCESS (car séquentiel)
Instructions CASE/IS bien adaptée
 Machine à états finie
Etat d’un système séquentiel

Chaque variable d'état peut être stockée dans une bascule D.

ƒ est une fonction combinatoire.
 Machines séquentielles synchrones MSS
Afin de connaitre l'évolution du système une mémorisation est
nécessaire.
L’état du système est stocké dans les variables (bits) d’état du
système.
Ces variables, à un instant donné, contiennent toutes les
informations nécessaires au calcul du comportement futur du
système.
L’état futur du système est fonction de son état courant et des
entrées
état futur = F(état présent,entrées).
Un système séquentiel synchrone voit son état synchronisé par
un signal dit d’ «horloge».
Une MSS est aussi appelée machine d’état.
 Machines séquentielles synchrones MSS
Décomposition d'une MSS

Ramener les MSS (machines séquentiels synchrones) à :

Des systèmes combinatoires

+ des variables internes (mémoires)

Eléments mémoires constitués par des flip-flops, nommés :

Bits d'état
 Machine à états finie
Description du fonctionnement
Chronogramme :

Présente une seule séquence

Vue partielle

Graphe des états :

Méthode graphique
Permet de représenter tous les "chemins" possibles
Pratique pour des MSS simples
 Machine à états finie

Graphe des états …

Constitué d'un série de bulles reliées par des flèches (transitions):

Une bulle représente un état distinct du système séquentiel. Elle

correspond à un code des bits d'état.

Une flèche représente une transition entre deux états. La

condition, fonction des entrées, sera écrite sur chaque transition.
Machine à états finie
Graphe des états …
Convention de dessin :
Graphe des états pour MOORE
Graphe des états pour MEALY
 Conception d'un graphe des états
Méthode de conception :

Génération de proche en proche

Génération depuis un chronogramme
Génération par l'identification des états internes
Dans tous les cas :

Compléter le graphe en respectant les règles de

construction
 Règles construction graphe des états
1. De chaque bulle d'état :
– Autant de flèches que de combinaisons valides des entrées

2. Chaque changement des entrées pertinentes (nouvelle

combinaison) provoque un changement d'état
– Génère souvent trop d'états => seront simplifiés après

3. Chaque changement sur les sorties, avec les mêmes valeurs

des entrées, implique un changement d'état

4. Maintien des sorties pendant un certains temps (multiple

) est réalisé par une succession d'état interne
(1 état = maintien de 1 )
 Codage des états d'une MSS

Jusqu'ici :

Etats internes désignés par un nom symbolique

Réaliser un circuit :

Assigner un code binaire distinct à chaque état

MSS comportant M états, il faudra N bits avec :

M
 Choix du code des états

Il y a des règles obligatoires à respecter pour

garantir le bon fonctionnement de la MSS.
D'autre part il faut optimiser le codage ?
Dans le cas d'une machine à 9 états (m=9), avec laquelle nous utilisons 4 bits
pour le codage (n=4), il y a 10,8 millions de possibilités de codage distincts !

Nous verrons des pistes pour optimiser le codage.

 Choix du code des états
Déterminer le nombre de bits d‘états N :
nombres d‘états

Puis
Essayer de placer les états dans une table de Karnaugh en
respectant les sorties sans aléas et en simplifiant au mieux les
décodeurs

Remarques :
Code zéro ("00…0") pour l'état initial, facile à initialiser
Eventuellement augmenter le nombre de bits d'état
 Exemple de codage des états

Soit une MSS avec 6 états (E0 à E5)

L'état E0 est l'état initial de la MSS
Les entrées sont synchrones
Les sorties sont utilisées pour des commandes synchrones
(aléas acceptables)
aucunes optimisations des décodeurs n'est appliquées
 exemple codage binaire
Voici un codage des états :

Nous avons 6 états => il faut 3 bits ( > 6)

Nous utilisons l'état "000" pour E0 (état initial)

Choix arbitraire pour les autres états :

E0 = "000" E3 = "011"
E1 = "001" E4 = "100"
E2 = "010" E5 = "101«

Les codes "110" et "111" sont non utilisés

 Analyse des machines séquentielles

Déterminer les fonctions d'état futur et de sortie,

de façon à pouvoir prédire le comportement de la
machine

La spécification du comportement est faite à l'aide

de deux types de représentation:
la table d’états
le graphe des états
Exemple: machine de Mealy
Exemple: machine de Mealy
Analyse de machines à états et leur
description en VHDL
 Analyse d’u circuit séquentiel synchrone
• On analyse un circuit pour en comprendre le fonctionnement.

• Analyser un circuit séquentiel synchrone en quatre étapes:

1. Identifier les variables d’états : les sorties des éléments à mémoire

2. Ecrire les équations d’états et les équations de sortie
3. Dresser le tableau d’états
4. Dessiner le diagramme d’états
Analyse d’u circuit séquentiel synchrone
1. {A, B} 4. Diagramme d’états:
2. état 0: AB = « 00 »
A+ = A xor B; état 1: AB = « 01 »
B+ = B’ or X; état 2: AB = « 10 »
Z = A nor B; état 3: AB = « 11 »

3. Tableau d’états:

C’est une machine de Moore, la sortie

ne dépend que de l’état présent.
Évolution de l’état et des sorties en fonction du temps
 Description d’une machine à états en VHDL:
A partir d’un schéma
Approche adéquate: library IEEE;
– Quand on désire modéliser un circuit pour lequel on a le schéma use IEEE.std_logic_1164.all;
– Quand on à les équations d’états et de sortie entity cctsequentielex1 is
port (
reset, CLK, X : in STD_LOGIC;
Z : out STD_LOGIC
);
end cctsequentielex1;
architecture arch1 of cctsequentielex1 is
signal A, B : STD_LOGIC;
begin
process(CLK, reset) is
begin
if (reset = '0') then
A <= '0';
B <= '0';
elsif (rising_edge(CLK)) then
A <= A xor B;
Deux bascules dans un seul processus B <= x or not(B);
Sortie décrite par un énoncé concurrent à l’extérieur du processus end if;
end process;
(pas de registre).
z <= not(A or B);
Réinitialisation asynchrone. end arch1;
 Description d’une machine à états en VHDL:
architecture arch3 of cctsequentielex1 is
à partir d’un diagramme d’états type type_etat is (Etat0, Etat1, Etat2, Etat3);
signal etat : type_etat := Etat0;
Approche beaucoup plus puissante: begin
– Identifier les états, les conditions de transition et les process(CLK, reset) is
begin
sorties pour chaque état if (reset = '0') then
– Pas besoin d’équations d’états etat <= Etat0;
elsif (rising_edge(CLK)) then
– Plus lisible, robuste, facile à maintenir case etat is
when Etat0 =>
etat <= Etat1;
when Etat1 =>
if x = '0' then etat <= Etat2;
else etat <= Etat3;
end if;
when Etat2 =>
etat <= Etat3;
when Etat3 =>
if x = '0' then etat <= Etat0;
else etat <= Etat1;
end if;
end case;
end if;
end process;
z <= '1' when etat = Etat0 else '0';
end arch3;
 Trois styles de description d’une machine à états en VHDL
architecture unprocessus of cctsequentielex2 is
Avec un seul processus type type_etat is (S1, S2, S3, S4);
signal etat : type_etat := S1;
begin
Attention aux sorties: process(CLK, reset) is
– Inférence de registres pour les sorties begin
if (reset = '0') then
– Spécifier la sortie du prochain état étant donnés un état etat <= S1;
et une entrée présentes. sortie <= '1';
elsif (rising_edge(CLK)) then
– Si plusieurs conditions résultent en un état donné, il faut case etat is
spécifier la sortie de Moore de cet état à chaque fois. when S1 =>
if x = '0' then
etat <= S3;
sortie <= '0';
else
etat <= S2;
sortie <= '1';
end if;
when S2 | S3 =>
etat <= S4;
sortie <= '0';
when S4 =>
etat <= S1;
sortie <= '1';
end case;
end if;
end process;
end unprocessus;
 Trois styles de description d’une machine à états en VHDL
Avec deux processus architecture deuxprocessus of cctsequentielex2 is
type type_etat is (S1, S2, S3, S4);
signal etat : type_etat := S1;
• Bon compromis entre la flexibilité et la lisibilité begin
process(CLK, reset) is
du code. begin
if (reset = '0') then
• Deux processus: etat <= S1;
elsif (rising_edge(CLK)) then
– Un pour le calcul et l’entreposage de l’état case etat is
when S1 =>
– Un pour les sorties (peut être remplacé par des if x = '0' then
etat <= S3;
énoncés concurrents) else
etat <= S2;
end if;
when S2 | S3 =>
etat <= S4;
when S4 =>
etat <= S1;
end case;
end if;
end process;
process(etat)
begin
case etat is
when S1 | S2 => sortie <= '1';
when S3 | S4 => sortie <= '0';
end case;
end process;
end deuxprocessus;
 Trois styles de description d’une machine à états en VHDL
Avec trois processus
• Style qui correspondre exactement au modèle.
• Code est très lisible mais moins compact que la version à deux processus.
• La liste de sensibilité du processus qui calcule le Prochain état inclut le signal qui entrepose l’état courant
ainsi que toutes les entrées.
• Le même principe s’applique au processus qui calcule les sorties (pour une machine de Mealy).
 Trois styles de description d’une machine à états en VHDL
architecture troisprocessus of cctsequentielex2 is
type type_etat is (S1, S2, S3, S4);
signal etat : type_etat := S1; -- processus pour le calcul du prochain état
signal etat_prochain : type_etat := S1; process(etat, x) is
begin begin
-- processus pour garder l'état actuel en mémoire case etat is
process(CLK, reset) is when S1 =>
begin if x = '0' then
if (reset = '0') then etat_prochain <= S3;
etat <= S1; else
elsif (rising_edge(CLK)) then etat_prochain <= S2;
etat <= etat_prochain; end if;
end if; when S2 | S3 =>
end process; etat_prochain <= S4;
-- processus pour les sorties when S4 =>
process(etat) etat_prochain<= S1;
begin end case;
case etat is end process;
when S1 | S2 => sortie <= '1'; end troisprocessus;
when S3 | S4 => sortie <= '0';
end case;
end process;
Modélisation de machines à états
• Notation pour les machine à états de Moore et de Mealy.
• Donner le diagramme d’une machine à états à partir d’une
spécification.
 Diagrammes d’états
Notation pour une Machine de Moore
• Chaque bulle représente un état avec un
identificateur.
• L’état de départ est indiqué.
• La transition peut se faire d’un état à un autre lors
d’une transition de l’horloge du système.
• Sur les transitions on indique la valeur nécessaire
des entrées pour que la transition ait lieu. Un tiret
indique une valeur sans importance.
• Si aucune condition de transition n’est satisfaite, la
machine reste dans l’état courant.
• Dans une machine de Moore, les sorties ne
dépendent que de l’état present donc elles sont
indiquées à L’intérieur des états.
• Dans l’exemple il y a une seule entrée et une seule
sortie.
 Diagrammes d’états
Notation pour une Machine de Mealy
• La notation est similaire à celle de la machine de Moore.
• Dans une machine de Mealy, les sorties dépendent a la fois de l’état présent et
des entrées, donc elles sont indiquées sur les transitions après une barre
oblique.
• Dans l’exemple, il y a deux entrées et une sortie.
 Conception de machine à états
principes de base
• La conception d’une machine à états est un processus créatif similaire à la description d’un
algorithme avec un langage de programmation.

• Il faut souvent faire des compromis entre des contraintes qui ne peuvent toutes être satisfaites
simultanément:

– Coût, performance, précision, et consommation de puissance;

– Lisibilité et testabilité.
• Pendant le processus de conception, on réalise souvent que la spécification est incomplète,
ambigüe ou mal comprise.

• Le système une fois conçu se comporte exactement tel qu’il a été décrit, mais pas
nécessairement comme on voudrait qu’il se comporte.

• Utiliser un processus itératif aide les choses.

• Bien documenter toutes les étapes.

 Conception de machine à états
bâtir le diagramme d’états
• La représentation graphique offerte par un diagramme d’états est très
avantageuse. Certains outils de conception produisent automatiquement du
code VHDL à partir d’un diagramme d’états.
• Les étapes suivants peuvent grandement aider à obtenir le diagramme d’état.
1. À partir des données du problème, simuler certaines combinaisons d’entrée et de sortie pour
bien comprendre la nature du problème.
2. Construire un diagramme partiel menant à une sortie désirée du système.
3. Ajouter au diagramme les autres chemins menant aux sorties désirées du système.
4. Vérifier le diagramme pour éviter les états équivalents (deux états qui mènent aux mêmes
prochains états et qui ont les mêmes sorties pour les mêmes entrées).
5. Compléter le diagramme en ajoutant des transitions pour toutes les entrées possibles à partir
de chaque état.
6. Identifier toute condition où le circuit doit être réinitialisé à un état de départ, et annoter le
diagramme avec cette information.
7. Vérifier le diagramme en appliquant des combinaisons d’entrées représentatives.
 Exemple: reconnaître une séquence
• Donner un diagramme d’états pour une machine de Mealy qui doit reconnaître
la séquence « 1101 ».

• Le circuit a une seule entrée sur laquelle la séquence est appliquée.

• Il a une seule sortie: ‘0’ tant que la séquence n’est pas détectée, et ‘1’ dés que
la séquence est détectée.

1. Simuler certaines combinaisons d’entrée et de sortie.

2. Construire un diagramme partiel – une sortie.
3. Ajouter d’autres chemins – autres sorties.
4. Éliminer les états équivalents
5. Ajouter toutes les autres transitions.
6. Ajouter la réinitialisation.
7. Vérifier.
 Exemple: reconnaître une séquence

1. Simuler certaines combinaisons d’entrée et de sortie.

2. Construire un diagramme partiel – une sortie. Solution 1: Machine de Mealy
3. Ajouter d’autres chemins – autres sorties. 4 états, donc 2 bascules
4. Éliminer les états équivalents
5. Ajouter toutes les autres transitions.
6. Ajouter la réinitialisation.
7. Vérifier.
 Exemple: reconnaître une séquence
Donner un diagramme d’états pour une machine de Moore qui doit reconnaître la séquence « 1101 »

Solution 2: Machine de Moore

5 états donc 3 bascules
Les états F, G et H sont implicites avec 3 bascules –attention à la façon de les coder.
 Machine à états
Exemple 1 : moteur pas à pas à sens de rotation unique.

Synthétisons dans ce premier exemple le séquenceur destiné à la commande d’un moteur pas à pas,
unipolaire 4 phases, à un seul sens de rotation, en fonctionnement pas entier deux phases
Nous avons ci-après les signaux recherchés S0, S1, S2 et S3 pour la commande des phases en fonction de
l’horloge H :

On note 4 états possibles en sortie, s’enchaînant inconditionnellement dans l’ordre E1, E2, E3, E4,
E1…au rythme de l’horloge H.
 Machine à états
A partir de ce cahier des charges, on peut en déduire le diagramme (ou diagramme à bulles) suivant :

Ce diagramme représente les différents états du système, en précisant éventuellement les niveaux
logiques correspondants en sortie, et les conditions de passage d’un état à l’autre. Dans notre cas
très simple, à chaque coup d’horloge, on passe inconditionnellement à l’état suivant.

La machine doit toujours se trouver au moins dans un état, et dans un seul état.
Avant l’apparition des langages HDL (Hardware circuits Description Language) de programmation,
la synthèse d’une machine d’état impliquait la recherche des équations des entrées des bascules
de mémorisation des états. Aujourd’hui, il est possible de retranscrire directement le diagramme
d’état en programme ; voici par exemple, un fichier VHLD associé à ce diagramme :
 Machine à états
library ieee;
use ieee.std_logic_1164.all; L’architecture du programme comprend
entity CDE_MOT_2 is deux parties distincts : l’instruction «
port( H : in std_logic; process » gère le passage d’un état au
SORTIES : out std_logic_vector (3 downto 0));
end CDE_MOT_2;
suivant à chaque coup d’horloge, tandis
architecture ARC_CDE OF CDE_MOT_2 is l’instruction « with select » affecte aux
type TYPE_ETAT is (E1, E2, E3, E4); sorties les valeurs correspondant à chaque
signal X:TYPE_ETAT; état.
begin
process (H)
begin On notera que tous les états possibles des
if H'event and H = '1' then
case X is sorties n’ont pas été traités dans le diagramme
when E1 => X <= E2; d’état, afin de ne pas l’alourdir. Dans la
when E2 => X <= E3; description VHDL cependant, les états imprévus
when E3 => X <= E4;
conduisent à l’état E1 (instruction « when others
when others => X <= E1;
end case; ») au coup d’horloge suivant. Cette solution
end if; n’est pas toujours la plus intéressante, un état
end process; imprévu conduisant alors à un fonctionnement
with X select
SORTIES <= "1001" when E1, aléatoire difficile à détecter et à supprimer ; il
"1010" when E2, est parfois préférable d’avoir une panne
"0110" when E3, franche, en prévoyant par exemple un état «
"0101" when E4;
end ARC_CDE;
Erreur ».
 Machine à états
Exemple 2 : moteur pas à pas à double sens de rotation.
Reprenons le premier exemple en introduisant cette fois une commande S permettant de choisir le sens de
rotation. Nous supposerons cette commande synchrone dans un premier temps.
Les chronogrammes recherchés sont alors :
 Machine à états
Ce qui nous conduit au diagramme d’état suivant :

Remarques :
- lorsque plusieurs entrées interviennent dans un diagramme d’état, on suppose qu’une seule est
susceptible de changer à un instant donné ;
- lorsque les conditions ne sont pas réalisées, l’état ne change pas (dans notre exemple, les
conditions étant complémentaires, elles sont toujours réalisées) ;
- lorsque plusieurs branchements sont possibles à partir d’un état, les conditions ne doivent pas
être vraies en même temps ;
- la présence de l’horloge est implicite, le passage d’un état à l’autre ne peut se faire qu’au front
actif de l’horloge.
 Machine à états
Une description VHDL possible est alors donnée ci-après : when E2 =>
if S='1' then X <= E3;
library ieee; else X <=E1;
use ieee.std_logic_1164.all; end if;
entity CDE_MOT_2S is when E3 =>
port( H,S : in std_logic; if S='1' then X <= E4;
SORTIES : out std_logic_vector (3 downto 0)); else X <=E2;
end CDE_MOT_2S; end if;
architecture ARC_CDE OF CDE_MOT_2S is when others =>
type TYPE_ETAT is (E1, E2, E3, E4); if S='1' then X <= E1;
signal X:TYPE_ETAT; else X <=E3;
begin end if;
process (H) end case;
begin end if;
if H'event and H = '1' then end process;
case X is with X select
when E1 => SORTIES <= "1001" when E1,
if S='1' then X <= E2; "1010" when E2,
else X <=E4; "0110" when E3,
end if; "0101" when E4;
end ARC_CDE;
End of Presentation Thank You!

Any Questions ?
“The future depends on what you do today.”